Совместное использование секрета (также называемое разделением секрета ) относится к методам распространения секрета среди группы таким образом, что ни один человек не владеет какой-либо понятной информацией о секрете, но когда достаточное количество людей объединяют свои «доли», секрет может быть реконструированы. В то время как небезопасный обмен секретами позволяет злоумышленнику получить больше информации с каждым общим ресурсом, безопасный обмен секретами осуществляется по принципу «все или ничего» (где «все» означает необходимое количество общих ресурсов).
В одном типе схемы обмена секретами есть один дилер и n игроков . Дилер передает игрокам долю секрета, но только при выполнении определенных условий игроки смогут восстановить секрет по своим долям. Дилер достигает этого, давая каждому игроку долю таким образом, чтобы любая группа из t (для порога ) или более игроков могла вместе восстановить секрет, но ни одна группа из менее чем t игроков не могла этого сделать. Такая система называется ( t , n ) -пороговой схемой (иногда ее записывают как ( n , t ) -пороговая схема).
Совместное использование секретов было независимо изобретено Ади Шамиром [1] и Джорджем Блейкли [2] в 1979 году.
Схемы обмена секретами идеально подходят для хранения конфиденциальной и очень важной информации. Примеры включают: ключи шифрования , коды запуска ракет и пронумерованные банковские счета . Каждая из этих частей информации должна храниться в строгой конфиденциальности, поскольку их раскрытие может иметь катастрофические последствия; однако также важно, чтобы они не были потеряны. Традиционные методы шифрования плохо подходят для одновременного достижения высокого уровня конфиденциальности и надежности. Это связано с тем, что при хранении ключа шифрования необходимо выбирать между хранением одной копии ключа в одном месте для максимальной секретности или хранением нескольких копий ключа в разных местах для большей надежности. Повышение надежности ключа за счет хранения нескольких копий снижает конфиденциальность за счет создания дополнительных векторов атаки; существует больше возможностей для того, чтобы копия попала в чужие руки. Схемы обмена секретами решают эту проблему и позволяют достичь сколь угодно высокого уровня конфиденциальности и надежности.
Совместное использование секрета также позволяет распространителю секрета доверять группе «в совокупности». Традиционно передача секрета группе на хранение требует, чтобы дистрибьютор полностью доверял всем членам группы. Схемы совместного использования секретов позволяют дистрибьютору надежно хранить секрет в группе, даже если не всем участникам можно постоянно доверять. Пока число предателей не превышает критического числа, необходимого для восстановления секрета, секрет в безопасности.
Схемы обмена секретами важны в средах облачных вычислений . Таким образом, ключ может быть распределен по множеству серверов с помощью порогового механизма совместного использования секрета. Затем ключ реконструируется при необходимости.
Разделение секретов также было предложено [ кем? ] для сенсорных сетей , ссылки в которых могут быть прослушаны, путем отправки данных в виде общих ресурсов, что усложняет задачу перехватчика. [ нужна цитация ] Безопасность в таких средах можно повысить за счет постоянных изменений [ как? ] способа формирования акций. [ нужна цитата ]
Схема безопасного совместного использования секрета распределяет общие ресурсы так, что любой, у кого меньше t общих ресурсов, не имеет больше информации о секрете, чем тот, у кого 0 общих ресурсов.
Рассмотрим, например, схему совместного использования секрета, в которой секретная фраза «пароль» разделена на доли «pa––––––», «––ss––––», «––––wo––», и «––––––rd». Человек с 0 долей знает только то, что пароль состоит из восьми букв, и поэтому ему придется угадывать пароль из 26 8 = 208 миллиардов возможных комбинаций. Однако человеку с одной долей придется угадать только шесть букв из 26 6 = 308 миллионов комбинаций, и так далее по мере того, как все больше людей вступают в сговор. Следовательно, эта система не является «безопасной» схемой совместного использования секретов, поскольку игрок, имеющий менее t секретных долей, может уменьшить проблему получения внутреннего секрета без необходимости предварительного получения всех необходимых долей.
Напротив, рассмотрим схему совместного использования секрета, где X — секрет, который должен быть передан, P i — открытые ключи асимметричного шифрования , а Q i — соответствующие им частные ключи. Каждому игроку J обеспечены { P 1 ( P 2 (...( P N ( X )))), Q j }. В этой схеме любой игрок с закрытым ключом 1 может удалить внешний уровень шифрования, игрок с ключами 1 и 2 может удалить первый и второй уровень и так далее. Игрок, имеющий менее N ключей, никогда не сможет полностью раскрыть секрет X без необходимости сначала расшифровать зашифрованный с помощью открытого ключа большой двоичный объект, для которого у него нет соответствующего закрытого ключа - проблема, которая в настоящее время считается вычислительно неосуществимой. Кроме того, мы видим, что любой пользователь со всеми N закрытыми ключами может расшифровать все внешние уровни, чтобы получить X , секрет, и, следовательно, эта система является безопасной системой распространения секретов.
Некоторые схемы обмена секретами считаются теоретически безопасными , и это может быть доказано, в то время как другие отказываются от этой безусловной безопасности ради повышения эффективности, сохраняя при этом достаточную безопасность, чтобы считаться такими же безопасными, как и другие распространенные криптографические примитивы. Например, они могут позволить защищать секреты с помощью общих ресурсов с энтропией 128 бит каждый, поскольку каждая доля будет считаться достаточной, чтобы загнать в тупик любого мыслимого современного противника, требующего грубой силы среднего размера 2 127 .
Общие для всех безусловно безопасных схем обмена секретами существуют ограничения: [ нужна ссылка ]
t = 1 обмен секретом тривиален. Секрет можно просто раздать всем n участникам.
Существует несколько ( t , n ) схем разделения секрета для t = n , когда для восстановления секрета необходимы все общие ресурсы:
Трудность [ необходимы пояснения ] заключается в создании схем, которые по-прежнему безопасны, но не требуют всех n общих ресурсов.
Когда эффективность использования пространства не является проблемой, можно использовать тривиальные схемы t = n , чтобы раскрыть секрет любому желаемому подмножеству игроков, просто применяя схему для каждого подмножества. Например, чтобы раскрыть секрет s любым двум из трех игроков Алисе, Бобу и Кэрол, создайте три ( ) различных t = n = 2 секретных акций для s , передав три набора по две акции Алисе и Бобу, Алисе и Кэрол, Боб и Кэрол.
Например, представьте, что совет директоров компании хотел бы защитить свою секретную формулу. Президент компании должен иметь возможность получить доступ к формуле, когда это необходимо, но в случае чрезвычайной ситуации любые трое из 12 членов совета директоров смогут вместе разблокировать секретную формулу. Один из способов добиться этого — использовать схему разделения секретов с t = 3 и n = 15 , где 3 акции передаются президенту и по одной акции каждому члену совета директоров.
Тривиальный подход быстро становится непрактичным по мере увеличения количества подмножеств, например, при раскрытии секрета любым 50 из 100 игроков, что потребует создания схем и сохранения каждым игроком отдельных наборов долей для каждой схемы. В худшем случае рост будет экспоненциальным. Это привело к поиску схем, позволяющих эффективно делиться секретами с определенным количеством игроков.
В этой схеме для восстановления секрета можно использовать любые t из n общих ресурсов. Система основана на идее, что вы можете подогнать уникальный полином степени t - 1 к любому набору из t точек, лежащих на полиноме. Для определения прямой линии требуются две точки, для полного определения квадратичной линии — три точки, для определения кубической кривой — четыре точки и так далее. То есть для определения многочлена степени t − 1 требуется t точек . Метод состоит в том, чтобы создать полином степени t - 1 с секретом в качестве первого коэффициента, а остальные коэффициенты выбираются случайным образом. Затем найдите на кривой n точек и раздайте по одной каждому из игроков. Когда хотя бы t из n игроков раскрывают свои очки, имеется достаточно информации, чтобы подобрать к ним полином ( t − 1) -й степени, причем первый коэффициент является секретным.
Две непараллельные прямые в одной плоскости пересекаются ровно в одной точке. Три непараллельные плоскости в пространстве пересекаются ровно в одной точке. В более общем смысле любые n непараллельных ( n − 1) -мерных гиперплоскостей пересекаются в определенной точке. Секрет может быть закодирован как любая отдельная координата точки пересечения. Если секрет закодирован с использованием всех координат, даже если они случайны, то инсайдер (кто-то, владеющий одной или несколькими ( n - 1) -мерными гиперплоскостями ) получает информацию о секрете, поскольку он знает, что он должен лежать на его самолет. Если инсайдер может получить больше знаний о секрете, чем посторонний, то система больше не имеет теоретической информационной безопасности . Если используется только одна из n координат, то инсайдер знает не больше, чем аутсайдер (т. е. что секрет должен лежать на оси x для двумерной системы). Каждому игроку предоставляется достаточно информации, чтобы определить гиперплоскость; секрет раскрывается путем вычисления точки пересечения плоскостей и последующего взятия указанной координаты этого пересечения.
Схема Блейкли менее экономична, чем схема Шамира; в то время как каждая доля Шамира равна исходному секрету, доля Блейкли в t раз больше, где t — пороговое количество игроков. Схему Блейкли можно ужесточить, добавив ограничения на то, какие самолеты можно использовать в качестве акций. Полученная схема эквивалентна полиномиальной системе Шамира.
Китайская теорема об остатках также может быть использована для разделения секретов, поскольку она дает нам метод однозначного определения числа S по модулю k многих попарно взаимно простых целых чисел , учитывая, что . Существуют две схемы разделения секретов, использующие китайскую теорему об остатках: схемы Миньотта и Асмута-Блума. Это пороговые схемы разделения секрета, в которых доли генерируются путем сокращения по модулю целых чисел , а секрет восстанавливается путем решения системы сравнений с использованием китайской теоремы об остатках.
Если игроки хранят свои акции на незащищенных компьютерных серверах, злоумышленник может взломать их и украсть. Если изменить секрет нецелесообразно, бескомпромиссные акции (в стиле Шамира) можно продлить. Дилер генерирует новый случайный полином с нулевым постоянным членом и вычисляет для каждого оставшегося игрока новую упорядоченную пару, где координаты x старой и новой пар одинаковы. Затем каждый игрок складывает старую и новую координаты Y друг с другом и сохраняет результат как новую координату Y секрета.
Все необновленные шары, накопленные злоумышленником, становятся бесполезными. Злоумышленник сможет восстановить секрет только в том случае, если он сможет найти достаточно других необновленных общих ресурсов, чтобы достичь порога. Такой ситуации не должно произойти, потому что игроки удалили свои старые акции. Кроме того, злоумышленник не может восстановить какую-либо информацию об исходном секрете из файлов обновления, поскольку они содержат только случайную информацию.
Дилер может изменить пороговое значение во время распространения обновлений, но всегда должен сохранять бдительность в отношении игроков, хранящих акции с истекшим сроком действия.
Игрок может солгать о своей доле, чтобы получить доступ к другим акциям. Схема проверяемого совместного использования секретов (VSS) позволяет игрокам быть уверенными, что никто из других игроков не лжет о содержимом их общих ресурсов, вплоть до разумной вероятности ошибки. Такие схемы невозможно рассчитать традиционным способом; игроки должны коллективно складывать и умножать числа, при этом никто не знает, что именно складывается и умножается. Таль Рабин и Майкл Бен-Ор разработали систему многосторонних вычислений (MPC) , которая позволяет игрокам выявлять нечестность со стороны дилера или со стороны до одной трети порогового числа игроков, даже если эти игроки координируются «адаптивный» злоумышленник, который может менять стратегию в реальном времени в зависимости от раскрытой информации.
Недостаток безусловно безопасных схем совместного использования секрета заключается в том, что для хранения и передачи общих ресурсов требуется объем ресурсов хранения и пропускной способности, эквивалентный размеру секрета, умноженному на количество общих ресурсов. Если размер секрета был значительным, скажем, 1 ГБ, а количество долей было 10, то акционерам необходимо хранить 10 ГБ данных. Были предложены альтернативные методы для значительного повышения эффективности схем обмена секретами за счет отказа от требования безусловной безопасности.
Один из этих методов, известный как короткое раскрытие секрета , [3] сочетает в себе алгоритм распространения информации Рабина [4] (IDA) с разделением секрета Шамира. Данные сначала шифруются случайно сгенерированным ключом с использованием алгоритма симметричного шифрования. Затем эти данные разбиваются на N частей с использованием IDA Рабина. Этот IDA настраивается с использованием порога, аналогично схемам совместного использования секрета, но в отличие от схем совместного использования секрета размер результирующих данных увеличивается в раз (количество фрагментов/порог). Например, если пороговое значение равно 10, а количество фрагментов, созданных IDA, равно 15, общий размер всех фрагментов будет (15/10) или в 1,5 раза больше размера исходного ввода. В этом случае эта схема в 10 раз эффективнее, чем если бы схема Шамира применялась непосредственно к данным. Последним шагом в упрощенном совместном использовании секрета является использование совместного использования секрета Шамира для создания долей случайно сгенерированного симметричного ключа (который обычно имеет размер порядка 16–32 байтов), а затем передача одной доли и одного фрагмента каждому акционеру.
Связанный подход, известный как AONT-RS, [5] применяет к данным преобразование «все или ничего» в качестве этапа предварительной обработки IDA. Преобразование «все или ничего» гарантирует, что любое количество долей, меньшее порогового значения, будет недостаточным для расшифровки данных.
Теоретико-информационная безопасная схема совместного использования секрета k -of- n генерирует n долей, размер каждой из которых не меньше размера самого секрета, что приводит к тому, что общий требуемый объем хранилища оказывается как минимум в n -раз больше, чем сам секрет. В многосекретном обмене, разработанном Мэтью К. Франклином и Моти Юнгом , [6] несколько точек полиномиальных секретов хоста; этот метод оказался полезным во многих приложениях, от кодирования до многосторонних вычислений. При эффективном совместном использовании секретов, разработанном Абхишеком Парахом и Субхашем Каком , каждая доля примерно равна размеру секрета, разделенному на k - 1 . [7]
Эта схема использует повторяющуюся полиномиальную интерполяцию и имеет потенциальное применение в безопасном распространении информации в Интернете и в сенсорных сетях . Этот метод основан на разделении данных с участием корней многочлена в конечном поле. [8] Позже были отмечены некоторые уязвимости соответствующих схем совместного использования секретов , позволяющих эффективно использовать пространство . [9] Они показывают, что схема, основанная на методе интерполяции, не может использоваться для реализации схемы ( k , n ) , когда k секретов, подлежащих распространению, по своей сути генерируются из полинома степени меньше k - 1 , и схема не работает, если все секреты, которыми нужно поделиться, одинаковы и т. д. [10]
Схема совместного использования секрета может защитить секрет на нескольких серверах и обеспечить возможность его восстановления, несмотря на многочисленные сбои серверов. Дилер может выступать в качестве нескольких отдельных участников, распределяя акции между участниками. Каждая акция может храниться на другом сервере, но дилер может восстановить секрет, даже если несколько серверов выйдут из строя, при условии, что он сможет восстановить хотя бы t акций; однако взломщики , взломавшие один сервер, все равно не узнают секрет, пока на каждом сервере хранится менее t общих ресурсов.
Это одна из основных концепций компьютерного проекта Vanish в Вашингтонском университете , где для шифрования данных используется случайный ключ, а ключ распределяется как секретный по нескольким узлам в P2P- сети. Чтобы расшифровать сообщение, должны быть доступны как минимум t узлов в сети; Принцип этого конкретного проекта заключается в том, что количество узлов, разделяющих секрет в сети, со временем естественным образом уменьшится, что в конечном итоге приведет к исчезновению секрета . Однако сеть уязвима для атаки Сивиллы , что делает Vanish небезопасным. [11]
Любой акционер, у которого когда-либо будет достаточно информации для расшифровки контента в любой момент, сможет взять и сохранить копию X. Следовательно, хотя инструменты и методы, такие как Vanish, могут через некоторое время сделать данные невосстановимыми в их собственной системе, это невозможно. чтобы принудительно удалить данные, как только их увидит злонамеренный пользователь. Это одна из главных загадок управления цифровыми правами .
Дилер может отправить t акций, все из которых необходимы для восстановления первоначального секрета, одному получателю. Злоумышленнику придется перехватить все t общих ресурсов, чтобы восстановить секрет, что является более сложной задачей, чем перехват одного файла, особенно если общие ресурсы передаются с использованием разных носителей (например, некоторые через Интернет , некоторые отправляются по почте на компакт-дисках ).
Для больших секретов может оказаться более эффективным зашифровать секрет, а затем распространить ключ, используя общий доступ к секрету.
Совместное использование секретов является важным примитивом в нескольких протоколах для безопасных многосторонних вычислений . Совместное использование секретов также может использоваться для аутентификации пользователей в системе. [12]
{{cite journal}}: Требуется цитировать журнал |journal=( помощь )