Совместное использование секрета

редактировать
Метод обмена секретом таким образом, что для его восстановления требуется совместная работа нескольких сторон

Совместное использование секрета (также называется разделением секрета ) относится к методам распределения секрета среди группы участников, каждому из которых выделяется доля секрета. Секрет может быть восстановлен только тогда, когда будет объединено достаточное количество долей, возможно, разных типов; отдельные акции не используются сами по себе.

В одном типе схемы разделения секрета есть один дилер и n игроков. Дилер дает долю секрета игрокам, но только при выполнении определенных условий игроки смогут восстановить секрет из своих долей. Дилер выполняет это, давая каждому игроку долю таким образом, что любая группа из t (для порога) или более игроков может вместе восстановить секрет, но никакая группа из менее чем t игроков не может. Такая система называется (t, n) -пороговой схемой (иногда ее записывают как (n, t) -пороговую схему).

Совместное использование секретов было изобретено независимо Ади Шамиром и Джорджем Блейкли в 1979 году.

Содержание

  • 1 Важность
  • 2 «Безопасность» по сравнению с » небезопасное "совместное использование секрета
  • 3 Ограничения
  • 4 Простое совместное использование секрета
    • 4,1 t = 1
    • 4,2 t = n
    • 4,3 1 < t < n, and, more general, any desired subset of n
  • 5 Эффективное совместное использование секрета
    • 5.1 Схема Шамира
    • 5.2 Схема Блейкли
    • 5.3 Использование китайской теоремы об остатках
  • 6 Упреждающее совместное использование секрета
  • 7 Подтверждаемое совместное использование секрета
  • 8 Совместное использование секрета с вычислительной безопасностью
  • 9 Совместное использование секретов с множеством секретов и эффективное использование пространства
  • 10 Другие применения и приложения
  • 11 См. Также
  • 12 Ссылки
  • 13 Внешние ссылки

Важность

Схемы совместного использования секретов идеальны для хранения конфиденциальной и очень важной информации. Примеры включают: ключи шифрования и пронумерованные банковские счета. Каждый из этих фрагментов информации должен храниться в строгом секрете, поскольку их разоблачение может иметь катастрофические последствия, однако также важно, чтобы они не были потеряны. Традиционные методы шифрования плохо подходят для одновременного достижения высокого уровня конфиденциальности и надежности. Это связано с тем, что при хранении ключа шифрования необходимо выбирать между хранением одной копии ключа в одном месте для максимальной секретности или хранением нескольких копий ключа в разных местах для большей надежности. Повышение надежности ключа за счет хранения нескольких копий снижает конфиденциальность за счет создания дополнительных векторов атаки; у копии больше возможностей попасть в чужие руки. Схемы совместного использования секретов решают эту проблему и позволяют достичь произвольно высоких уровней конфиденциальности и надежности.

Схемы совместного использования секретов важны в средах облачных вычислений. Таким образом, ключ может быть распределен по множеству серверов с помощью порогового механизма разделения секрета. Затем ключ восстанавливается, когда это необходимо. Совместное использование секрета также было предложено для сенсорных сетей, где ссылки могут быть перехвачены путем отправки данных в общих папках, что усложняет задачу перехватчика. Безопасность в таких средах можно повысить за счет постоянного изменения способа создания акций.

«Безопасное» или «небезопасное» совместное использование секрета

Схема безопасного совместного использования секрета распределяет общие ресурсы таким образом, что любой, у кого меньше t общих ресурсов, имеет не больше информации о секрете, чем тот, у кого есть 0 общих ресурсов.

Рассмотрим, например, схему разделения секрета, в которой секретная фраза «пароль» разделена на доли «па ––––––», «––ss –––––», «––– –Wo–– »и« –––––– rd ». Человек с 0 долями знает только то, что пароль состоит из восьми букв. Ему нужно будет угадать пароль из 26 = 208 миллиардов возможных комбинаций. Однако человек с одной долей должен угадать только шесть букв из 26 = 308 миллионов комбинаций и так далее, поскольку все больше людей вступают в сговор. Следовательно, эта система не является «безопасной» схемой совместного использования секрета, потому что игрок с меньшим, чем t секретных долей, может уменьшить проблему получения внутреннего секрета без предварительного получения всех необходимых долей.

Напротив, рассмотрим схему совместного использования секрета, где X - это секрет, который должен быть передан, P i - открытые ключи асимметричного шифрования и Q i соответствующие им закрытые ключи. Каждому игроку J предоставляется {P 1(P2(... (P N (X)))), Q j }. В этой схеме любой игрок с закрытым ключом 1 может удалить внешний уровень шифрования, игрок с ключами 1 и 2 может удалить первый и второй уровень и так далее. Игрок с менее чем N ключами никогда не сможет полностью достичь секретного X без необходимости сначала расшифровать зашифрованный с открытым ключом большой двоичный объект, для которого у него нет соответствующего закрытого ключа - проблема, которая в настоящее время считается вычислительно невыполнимой. Кроме того, мы видим, что любой пользователь со всеми N закрытыми ключами может расшифровать все внешние уровни, чтобы получить X, секрет, и, следовательно, эта система является безопасной системой распространения секретов.

Ограничения

Некоторые схемы совместного использования секретов считаются теоретически безопасными и могут быть доказаны таковыми, в то время как другие отказываются от этой безусловной безопасности для повышения эффективности при сохранении достаточной безопасности, чтобы считаться таким же безопасным, как и другие распространенные криптографические примитивы. Например, они могут позволить защищать секреты с помощью общих ресурсов со 128-битной энтропией каждый, поскольку каждый общий ресурс будет считаться достаточным, чтобы заблокировать любого мыслимого современного противника, требуя атаки грубой силы среднего размера 2.

Общие для всех схем безоговорочно безопасного совместного использования секрета имеют ограничения:

  • Размер каждой доли секрета должен быть не меньше размера самого секрета. Этот результат основан на теории информации, но может быть понят интуитивно. Учитывая t - 1 акций, никакая информация о секрете не может быть определена. Таким образом, итоговая папка должна содержать столько же информации, сколько и сам секрет. Иногда есть обходной путь для этого ограничения, сначала сжимая секрет перед тем, как поделиться им, но это часто невозможно, потому что многие секреты (например, ключи) выглядят как высококачественные случайные данные и поэтому их трудно сжать.
  • Все схемы совместного использования секрета используют random бит. Чтобы распределить однобитовый секрет между людьми с порогом t, необходимо t - 1 случайных битов. Для распределения секрета произвольной длины b битов необходима энтропия (t - 1) × b битов.

Простое совместное использование секрета

t = 1

t = 1 совместное использование секрета банально. Секрет можно просто раздать всем n участникам.

t = n

Существует несколько (t, n) схем разделения секрета для t = n, когда для восстановления секрета необходимы все общие ресурсы:

  1. Кодировать секрет как произвольная длина двоичное число s. Дайте каждому игроку i (кроме одного) случайное число p i той же длины, что и s. Передать последнему игроку результат (s XOR p 1 XOR p 2 XOR... XOR p n − 1), где XOR равно побитовое исключающее или. Секрет заключается в побитовом XOR всех номеров игроков (p).
  2. Кроме того, (1) может быть выполнено с использованием любого линейного оператора в любом поле . Например, вот альтернатива, функционально эквивалентная (1). Выберем 32-битные целые числа с четко определенной семантикой переполнения (т.е. правильный ответ сохраняется по модулю 2). Во-первых, s можно разделить на вектор из M 32-битных целых чисел, называемый v secret. Затем (n - 1) игрокам дается вектор из M случайных целых чисел, игрок i получает v i. Оставшемуся игроку дается v n = (v secret - v 1 - v 2 -... - v п-1). Затем секретный вектор может быть восстановлен путем суммирования всех векторов игрока.

1 < t < n, and, more general, any desired subset of n

Трудность заключается в создании схем, которые все еще являются безопасными, но не требуют всех n общих ресурсов. Например, представьте, что совет директоров компании хочет защитить свою секретную формулу. Президент компании должен иметь доступ к формуле, когда это необходимо, но в экстренной ситуации любые 3 из 12 членов совета директоров смогут вместе открыть секретную формулу. Это может быть достигнуто с помощью схемы разделения секрета с t = 3 и n = 15, где 3 акции передаются президенту, а по 1 - каждому члену совета.

Когда эффективность использования пространства не важна, можно использовать тривиальные схемы t = n, чтобы раскрыть секрет любым желаемым подмножествам игроков, просто применяя схему для каждого подмножества. Например, чтобы раскрыть секрет s любым двум из трех игроков Алисе, Бобу и Кэрол, создайте три разных (2, 2) секретных доли для s, передав три набора из двух долей Алисе и Бобу, Алисе и Кэрол, и Боб и Кэрол.

Эффективное совместное использование секрета

Тривиальный подход быстро становится непрактичным по мере увеличения количества подмножеств, например, при раскрытии секрета любым 50 из 100 игроков, что потребует (100 50) ≈ 1,009 × 10 29 {\ displaystyle {\ binom {100} {50}} \ приблизительно 1,009 \ times 10 ^ {29}}{\ displaystyle {\ binom {100} {50}} \ приблизительно 1.009 \ times 10 ^ {29}} схемы, которые необходимо создать и каждый игрок должен поддерживать (99 49) ≈ 5,04 × 10 28 {\ displaystyle {\ binom {99} {49}} \ приблизительно 5,04 \ times 10 ^ {28}}{\ displaystyle {\ binom {99} {49}} \ приблизительно 5,04 \ раз 10 ^ {28}} различных наборов долей для каждой схемы. В худшем случае рост будет экспоненциальным. Это привело к поиску схем, позволяющих эффективно обмениваться секретами с определенным количеством игроков.

Схема Шамира

В этой схеме любые t из n общих ресурсов могут быть использованы для восстановления секрета. Система основана на идее, что вы можете подогнать уникальный полином степени t - 1 к любому набору из t точек, лежащих на полиноме. Требуются две точки для определения прямой линии, три точки для полного определения квадратичной кривой, четыре точки для определения кубической кривой и так далее. То есть требуется t точек, чтобы определить полином степени t - 1. Метод состоит в создании полинома степени t - 1 с секретом в качестве первого коэффициента, а оставшиеся коэффициенты выбираются случайным образом. Затем найдите n точек на кривой и раздайте по одной каждому из игроков. Когда хотя бы t из n игроков раскрывают свои очки, имеется достаточно информации, чтобы подогнать под них многочлен (t - 1) -й степени, причем первый коэффициент является секретом.

Схема Блейкли

Две непараллельные прямые в одной плоскости пересекаются ровно в одной точке. Три непараллельные плоскости в пространстве пересекаются ровно в одной точке. В более общем смысле, любые n непараллельных (n - 1) -мерных гиперплоскостей пересекаются в определенной точке. Секрет может быть закодирован как любая отдельная координата точки пересечения. Если секрет закодирован с использованием всех координат, даже если они случайны, то инсайдер (кто-то, владеющий одной или несколькими (n - 1) -мерными гиперплоскостями ) получает информацию о секрете, поскольку знает, что он должен лежать в его самолете. Если инсайдер может получить больше информации о секрете, чем посторонний, тогда в системе больше не будет теоретической информационной безопасности. Если используется только одна из n координат, то инсайдер знает не больше, чем посторонний (то есть, что секрет должен лежать на оси x для двухмерной системы). Каждому игроку дается достаточно информации, чтобы определить гиперплоскость; секрет восстанавливается путем вычисления точки пересечения плоскостей и последующего взятия указанной координаты этого пересечения.

Одна акция Две доли, пересекающиеся на линии Три доли, пересекающиеся в точке
Схема Блейкли в трех измерениях: каждая доля - это плоскость, а секрет - это точка пересечения трех долей. Двух долей недостаточно для определения секрета, хотя они предоставляют достаточно информации, чтобы сузить ее до линии , где пересекаются обе плоскости.

Схема Блейкли менее компактна, чем схема Шамира; в то время как каждая из долей Шамира равна первоначальному секрету, доли Блэкли в t раз больше, где t - пороговое количество игроков. Схему Блекли можно ужесточить, добавив ограничения на то, какие самолеты можно использовать в качестве акций. Полученная схема эквивалентна системе полиномов Шамира.

Использование китайской теоремы об остатке

Китайская теорема об остатке также может использоваться при совместном использовании секрета, поскольку она предоставляет нам метод однозначного определения числа S по модулю k много попарно взаимно простых целых чисел m 1, m 2,..., m k {\ displaystyle m_ {1}, m_ {2},..., m_ {k}}m_1, m_2,..., m_k , учитывая, что S < ∏ i = 1 k m i {\displaystyle S<\prod _{i=1}^{k}m_{i}}S <\ prod_ {i = 1} ^ k m_i . Существуют две схемы разделения секрета, в которых используется китайская теорема об остатках, схемы Миньотта и Асмута-Блума. Это схемы порогового разделения секрета, в которых доли генерируются сокращением по модулю целых чисел mi {\ displaystyle m_ {i}}m_ { i} , а секрет восстанавливается путем решения системы сравнений с использованием Китайская теорема об остатках.

Упреждающее совместное использование секретов

Если игроки хранят свои общие ресурсы на небезопасных компьютерных серверах, злоумышленник может взломать и украсть общие ресурсы. Если изменение секрета нецелесообразно, бескомпромиссные (по-шамирски) акции могут быть продлены. Дилер генерирует новый случайный многочлен с постоянным нулевым членом и вычисляет для каждого оставшегося игрока новую упорядоченную пару, где x-координаты старой и новой пар совпадают. Затем каждый игрок добавляет друг другу старые и новые координаты y и сохраняет результат как новую координату y секрета.

Все необновленные общие ресурсы, накопленные злоумышленником, становятся бесполезными. Злоумышленник может восстановить секрет только в том случае, если он сможет найти достаточно других необновленных общих ресурсов для достижения порогового значения. Этой ситуации не должно быть, потому что игроки удалили свои старые акции. Кроме того, злоумышленник не может восстановить какую-либо информацию об исходном секрете из файлов обновлений, поскольку они содержат только случайную информацию.

Дилер может изменять пороговое число при распространении обновлений, но всегда должен сохранять бдительность, чтобы игроки сохраняли просроченные акции.

Совместное использование секрета, поддающееся проверке

Игрок может солгать о своей доле, чтобы получить доступ к другим долям. Поддающаяся проверке схема совместного использования секрета (VSS) позволяет игрокам быть уверенными в том, что другие игроки не лгут о содержимом своих общих ресурсов, с точностью до разумной вероятности ошибки. Такие схемы нельзя рассчитать традиционным способом; игроки должны вместе складывать и умножать числа, не зная, что именно складывается и умножается. Тал Рабин и Майкл Бен-Ор разработали систему многосторонних вычислений (MPC), которая позволяет игрокам выявлять нечестность со стороны дилера или частично до одной трети порогового значения. количество игроков, даже если эти игроки координируются «адаптивным» злоумышленником, который может изменять стратегии в реальном времени в зависимости от того, какая информация была раскрыта.

Безопасное с точки зрения вычислений совместное использование секрета

Недостаток безусловно безопасных схем совместного использования секрета состоит в том, что для хранения и передачи общих ресурсов требуется объем хранилища и ресурсов полосы пропускания, эквивалентных размеру секрета, умноженному количество акций. Если размер секрета был значительным, скажем 1 ГБ, а количество акций было 10, то акционеры должны хранить 10 ГБ данных. Были предложены альтернативные методы для значительного повышения эффективности схем совместного использования секретов за счет отказа от требования безусловной безопасности.

Один из этих методов, известный как краткое разделение секрета, сочетает в себе алгоритм распространения информации (IDA) Рабина с секретным разделением Шамира. Сначала данные шифруются случайно сгенерированным ключом с использованием симметричного алгоритма шифрования. Затем эти данные разделяются на N частей с помощью IDA Рабина. Этот IDA конфигурируется с порогом, аналогично схемам совместного использования секрета, но в отличие от схем совместного использования секрета размер результирующих данных увеличивается в раз (количество фрагментов / порог). Например, если бы порог был 10, а количество фрагментов, созданных IDA, было 15, общий размер всех фрагментов был бы (15/10) или в 1,5 раза больше размера исходного ввода. В этом случае эта схема в 10 раз эффективнее, чем если бы схема Шамира применялась непосредственно к данным. Заключительный шаг в сокращении совместного использования секрета - это использование совместного использования секрета Шамира для создания долей случайно сгенерированного симметричного ключа (который обычно составляет порядка 16–32 байтов), а затем передача одной доли и одного фрагмента каждому акционеру.

Родственный подход, известный как AONT-RS, применяет преобразование «все или ничего» к данным в качестве этапа предварительной обработки в IDA. Преобразование «все или ничего» гарантирует, что любое количество долей, меньшее порогового, недостаточно для дешифрования данных.

Совместное использование секретов с множеством секретов и эффективное использование пространства (пакетное)

Теоретически безопасная схема разделения секретов k-of-n генерирует n общих ресурсов, размер каждой из которых не меньше размера секрета Сама по себе, что приводит к тому, что общая необходимая память становится как минимум в n раз больше, чем секрет. В совместном использовании нескольких секретов, разработанном Мэтью К. Франклином и Моти Юнгом, множество точек полиномиальных секретов хоста; этот метод оказался полезным во многих приложениях, от кодирования до многосторонних вычислений. В экономичном использовании секрета, разработанном Абхишеком Паракхом и Субхашем Каком, каждая доля составляет примерно долю (k-1) размера секрета.

В этой схеме используются повторяющиеся полиномиальная интерполяция и имеет потенциальные приложения для безопасного распространения информации в Интернете и в сенсорных сетях. Этот метод основан на разделении данных с участием корней многочлена в конечном поле. Позднее были указаны некоторые уязвимости связанных схем разделения секрета с эффективным использованием пространства. Они показывают, что схему, основанную на методе интерполяции, нельзя использовать для реализации схемы (k, n), когда k секретов, которые должны быть распределены, по своей сути генерируются из полинома степени меньше k - 1, и схема не работает, если все секретов, которые будут совместно использоваться, одинаковы и т. д.

Другие применения и приложения

Схема совместного использования секретов может обеспечить защиту секрета на нескольких серверах и сохранить возможность восстановления, несмотря на множественные отказы серверов. Дилер может действовать как несколько отдельных участников, распределяя акции между участниками. Каждая акция может храниться на другом сервере, но дилер может восстановить секрет, даже если несколько серверов выйдут из строя, если они могут восстановить не менее t общих ресурсов; однако взломщики, которые взламывают один сервер, все равно не знают секрет, пока на каждом сервере хранится менее t общих ресурсов.

Это одна из основных концепций компьютерного проекта Vanish в Вашингтонском университете, где для шифрования данных используется случайный ключ, а ключ распространяется как секрет между несколькими узлами в сети P2P. Чтобы расшифровать сообщение, должно быть доступно по крайней мере t узлов в сети; Принцип этого конкретного проекта заключается в том, что количество узлов, разделяющих секреты, в сети будет естественным образом уменьшаться со временем, в результате чего секрет в конечном итоге исчезнет. Однако сеть уязвима для атаки Sybil, что делает Vanish небезопасным.

Любой акционер, у которого когда-либо имеется достаточно информации для дешифрования контента в любой момент, может взять и сохранить копию X. Следовательно, хотя инструменты и методы, такие как Vanish, могут сделать данные безвозвратными в их собственной системе через некоторое время, невозможно принудительно удалить данные после того, как злоумышленник их увидел. Это одна из главных загадок Управления цифровыми правами.

. Дилер может отправить t акций, все из которых необходимы для восстановления исходного секрета, одному получателю. Злоумышленник должен будет перехватить все t общих ресурсов, чтобы восстановить секрет, что сложнее, чем перехват одного файла, особенно если общие ресурсы отправляются с использованием разных носителей (например, некоторые через Интернет, некоторые отправляются по почте на компакт-дисках ).

Для больших секретов может быть более эффективным зашифровать секрет, а затем распространить ключ с использованием совместного использования секрета.

Совместное использование секрета является важным примитивом в нескольких протоколах для безопасных многосторонних вычислений.

См. Также

Ссылки

Внешние ссылки

Последняя правка сделана 2021-06-07 08:20:11
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте