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

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

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

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

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

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

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

См. также: Схема разделения секрета Шамира

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

Все вышеперечисленное является реализацией разделения секрета Шамира. Чтобы сделать эту схему проверяемой, дилер рассылает проверочные значения к коэффициентам 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). Как только это сделано, любой участник может проверить совместность своей доли, убедившись в следующем равенстве:

$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}}$.

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

Схема Бенало

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

Примеры:

• случай 1:
  

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

• случай 2:
  

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

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

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

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

Если дилер честно следует данному алгоритму, то степени полиномов $P_{i_{1}},...,P_{i_{m}}$, $P+\textstyle \sum _{j={m+1}}^{k}P_{j}$ и степени интерполяционных полиномов, восстановленных по их долям, соответствуют степени t − 1 секретного полинома P по гомоморфному свойству. Таким образом, зная доли $P_{i_{1}},...,P_{i_{m}}$ и $P+\textstyle \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:

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

Литература

• 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.