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

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

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

• c₀ = g^s,
• c₁ = g^a₁,
• …
• c_{t − 1} = g^{a_{t − 1}}.
  

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

${\displaystyle 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}}}$.

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

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

Примеры:

• случай 1:
  

  ${\displaystyle f_{1}=3x}$ , ${\displaystyle f_{2}=11x^{6}}$ , ${\displaystyle t=6}$
  

• случай 2:
  

  ${\displaystyle f_{1}=18x^{7}}$ , ${\displaystyle f_{2}=-18x^{7}}$ , ${\displaystyle t=6}$
  

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

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

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

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

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

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

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

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

• B. Chor, S. Goldwasser, S. Micali, B. Awerbuch. Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults // IEEE. — 1985. — С. 383—395.
• P. Feldman. A practical scheme for non-interactive verifiable secret sharing // IEEE. — 1987. — С. 427—437.
• T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority // STOC '89 Proceedings of the twenty-first annual ACM symposium on Theory of computing. — 1989. — С. 79.
• Chunming Tang, Dingyi Pei, Zhuojun Liu, Yong He. Non-Interactive and Information-Theoritic Secure Publicly Verifiable Secret Sharing // IACR Cryptology ePrint Archive. — 2004.
• Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin. The Round Complexity of Verifiable Secret Sharing and Secure Multicast // STOC '01 Proceedings of the thirty-third annual ACM symposium on Theory of computing. — 2001. — С. 580—589.
• Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan, and Kannan Srinathan. Round-Optimal and Efficient Verifiable Secret Sharing. — Springer-Verlag Berlin Heidelberg, 2006. — С. 330—342.
• Oded Goldreich. The Foundations of Cryptography - Volume 2. — Cambridge University Press, 2004.
• Josh Cohen Benaloh. Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret // Proceedings on Advances in cryptology---CRYPTO '86. — 1987.