Проверяемое разделение секрета

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

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

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

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

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

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

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

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

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

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

Убедившись, участник об этом сообщает. В результате каждый знает, что все доли соответствуют одному полиному и, следовательно, являются совместными.

Схема Бенало

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

Примеры:

• случай 1:
  f 1 = 3 x {displaystyle f_{1}=3x} , f 2 = 11 x 6 {displaystyle f_{2}=11x^{6}} , t = 6 {displaystyle t=6}
  
• случай 2:
  f 1 = 18 x 7 {displaystyle f_{1}=18x^{7}} , f 2 = − 18 x 7 {displaystyle f_{2}=-18x^{7}} , t = 6 {displaystyle t=6}
  

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

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

• Дилер задает полином P степени t − 1 и распределяет доли (как в схеме Шамира)
• Дилер создает очень большое число (k) случайных полиномов P 1 , . . . , P k {displaystyle P_{1},...,P_{k}} степени t − 1 и также распределяет их доли.
• Владелец доли выбирает случайный набор из m полиномов (m<k).
• Дилер раскрывает доли m выбранных полиномов P i 1 , . . . , P i m {displaystyle P_{i_{1}},...,P_{i_{m}}} , суммирует оставшиеся k − m полиномы P + ∑ j = m + 1 k P j {displaystyle P+ extstyle sum _{j={m+1}}^{k}P_{j}} и разделяет результат.
• Каждый участник проверяет, что все раскрытые полиномы степени t − 1 и соответствуют известной ему доле.

Если дилер честно следует данному алгоритму, то степени полиномов P i 1 , . . . , P i m {displaystyle P_{i_{1}},...,P_{i_{m}}} , P + ∑ j = m + 1 k P j {displaystyle P+ extstyle sum _{j={m+1}}^{k}P_{j}} и степени интерполяционных полиномов, восстановленных по их долям, соответствуют степени t − 1 секретного полинома P по гомоморфному свойству. Таким образом, зная доли P i 1 , . . . , P i m {displaystyle P_{i_{1}},...,P_{i_{m}}} и P + ∑ j = m + 1 k P j {displaystyle P+ extstyle sum _{j={m+1}}^{k}P_{j}} , любой участник может убедиться в t-совместности по свойству схемы Шамира. Кроме того, распределение случайных полиномов не приводит к раскрытию секрета.

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

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

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

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

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

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