Русская Википедия:Проверяемое разделение секрета

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Шаблон:TOCright Проверяемое разделение секрета (Шаблон:Lang-en) — схема разделения секрета, позволяющая участникам группы проверить, что их доли совместные (Шаблон:Lang-en)Шаблон:Sfn, то есть воссоздающие одинаковый секрет. Иными словами, данная схема гарантирует существование секрета, который участники в дальнейшем могут восстановить, даже если распределение было умышленно изменено. (В обычной схеме предполагается, что распределение выполнено правильно.) Концепция проверяемого разделения секрета впервые была представлена Бенни Чором, Шафи Гольдвассер, Сильвио Микали и Барухом Авербухом в 1985 годуШаблон:Sfn.

Участник группы, который разделяет секрет, в протоколе VSS называется дилером (Шаблон:Lang-en)Шаблон:Sfn. Протокол делится на два этапа: разделение и восстановление.

Разделение: Изначально каждый участник имеет независимые случайные входные данные. Дилер в качестве входных данных использует секрет. Разделение состоит из нескольких этапов. На каждом этапе любой участник может приватно отправлять сообщения другим или публично отправить сообщение всем. Каждое такое сообщение определяется входными данными и полученными ранее сообщениями.

Восстановление: На этом этапе каждый участник предоставляет информацию, полученную на этапе разделения. Затем применяется функция восстановления, и её результат используется как выходные данные протокола.

При безопасных многосторонних вычислениях входные данные делятся на тайные доли, которые используются для вычисления некоторой функции. Существуют злонамеренные участники, которые искажают данные и отклоняют их от протокола. Для предотвращения их влияния применяется VSSШаблон:Sfn.

Схема Фельдмана

Шаблон:См. также Протокол Пола Фельдмана основан на схеме разделения секрета Шамира в сочетании с любой схемой гомоморфного шифрования. Рассмотрим пороговую схему (t, n). Вычисления проводятся с элементами циклической группы G порядка p с генератором g. Группа G выбирается так, чтобы получение значения дискретного логарифма в этой группе обладало большой вычислительной сложностью. Затем дилер задает (и оставляет секретным) полином P степени t − 1 с коэффициентами из Zp, т.ч. P(0)=s, где s является секретом. Каждый из n участников получит значение P(1), …, P(n) по модулю pШаблон:Sfn.

Все вышеперечисленное является реализацией разделения секрета Шамира. Чтобы сделать эту схему проверяемой, дилер рассылает проверочные значения к коэффициентам P. Если P(x) = s + a1x + … + at − 1xt − 1, тогда значения:

  • c0 = gs,
  • c1 = ga1,
  • …
  • ct − 1 = gat − 1.

Кроме того, i-ому участнику дилер отправляет поправку zi = gyi, где yi = P(i). Как только это сделано, любой участник может проверить совместность своей доли, убедившись в следующем равенстве:

<math>

g^v = c_0 c_1^i c_2^{i^2} \cdots c_{t-1}^{i^{(t-1)}} = \prod_{j=0}^{t-1} c_j^{i^j} = \prod_{j=0}^{t-1} g^{a_j i^j} = g^{\sum_{j=0}^{t-1} a_j i^j} = g^{y_i} </math>. Убедившись, участник об этом сообщает. В результате каждый знает, что все доли соответствуют одному полиному и, следовательно, являются совместнымиШаблон:Sfn.

Схема Бенало

Схема Бенало также является развитием схемы Шамира. Как только n долей распределены между участниками, каждый из них должен быть способен проверить, что все доли t-совместные (Шаблон:Lang-en), то есть любая подгруппа участников t из n восстанавливает одинаковый секретШаблон:Sfn. В схеме Шамира доли s1, s2, …, sn являются t-совместными тогда и только тогда, когда степень интерполяционного многочлена, построенного по точкам (1, s1), (2, s2), …, (n, sn), не превышает d=t − 1Шаблон:Sfn. Кроме того, если степень суммы двух полиномов F и G меньше или равна t, то либо обе степени полиномов F и G меньше или равны t, либо обе больше t. Это следует из гомоморфного свойства полиномиальной функции.

Примеры:

  • случай 1:
    <math>f_1=3x</math> , <math>f_2=11x^6</math> , <math>t=6</math>
  • случай 2:
    <math>f_1=18x^7</math> , <math>f_2=-18x^7</math> , <math>t=6</math>

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

Проверку совместности можно провести с помощью следующего алгоритма:

  • Дилер задает полином P степени t − 1 и распределяет доли (как в схеме Шамира)
  • Дилер создает очень большое число (k) случайных полиномов <math>P_1, ..., P_k</math> степени t − 1 и также распределяет их доли.
  • Владелец доли выбирает случайный набор из m полиномов (m<k).
  • Дилер раскрывает доли m выбранных полиномов <math>P_{i_1}, ..., P_{i_m}</math>, суммирует оставшиеся k − m полиномы <math>P+\textstyle \sum_{j={m+1}}^k P_j</math> и разделяет результат.
  • Каждый участник проверяет, что все раскрытые полиномы степени t − 1 и соответствуют известной ему доле.

Если дилер честно следует данному алгоритму, то степени полиномов <math>P_{i_1}, ..., P_{i_m}</math>, <math>P+\textstyle \sum_{j={m+1}}^k P_j</math> и степени интерполяционных полиномов, восстановленных по их долям, соответствуют степени t − 1 секретного полинома P по гомоморфному свойству. Таким образом, зная доли <math>P_{i_1}, ..., P_{i_m}</math> и <math>P+\textstyle \sum_{j={m+1}}^k P_j</math>, любой участник может убедиться в t-совместности по свойству схемы Шамира. Кроме того, распределение случайных полиномов не приводит к раскрытию секретаШаблон:Sfn.

Тайные выборы

VSS применим при проведении тайных выборовШаблон:Sfn. Каждый избиратель может голосовать за (1) или против (0), и сумма всех голосов определяет результат голосования. Необходимо убедиться в выполнении следующих условий:

  • Конфиденциальность избирателей не должна быть нарушена.
  • Наблюдатель должен проверить, что ни один избиратель не совершил обман.

При использовании VSS одного наблюдателя заменят n счетчиков голосов. Каждый избиратель распределит доли своего секрета среди всех n счетчиков. В этом случае конфиденциальность избирателя сохраняется, и первое условие выполняется. Для восстановления результата выборов необходимо существование достаточного количества k<n счетчиков для восстановления полинома P. Для подтверждения голосов каждый избиратель может применить описанную в предыдущем разделе проверку совместности распределенияШаблон:Sfn.

Эффективность VSS

Сложность протокола VSS определяется как число этапов обмена сообщениями на этапе разделения, а именно как количество отправленных дилером долей секрета, проверочных значений (в схеме Фельдмана), случайных полиномов и так далее. Восстановление же всегда может быть выполнено за одно действие. Этого можно добиться с помощью одновременной трансляции (Шаблон:Lang-en)Шаблон:Sfn. Следовательно, не существует 1-этапного VSS с t>1, независимо от количества участников. Кроме того, протокол VSS называется эффективным, если он имеет полиномиальную сложность, зависящую от n. Условия эффективного протокола VSSШаблон:SfnШаблон:Sfn:

Количество этапов Параметры
1 t = 1, n > 4
2 n > 4t
3 n > 3t

Примечания

Шаблон:Примечания

Литература

Шаблон:Добротная статья

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Проверяемое_разделение_секрета&oldid=10649353