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

{{TOCright}}
'''Проверяемое разделение секрета''' ({{lang-en|Verifiable secret sharing, VSS}}) — схема [[Разделение секрета|разделения секрета]], позволяющая участникам группы проверить, что их доли совместные ({{lang-en|consistent}}){{sfn|Josh Cohen Benaloh|1987|с=256}}, то есть воссоздающие одинаковый секрет. Иными словами, данная схема гарантирует существование секрета, который участники в дальнейшем могут восстановить, даже если распределение было умышленно изменено. (В обычной схеме предполагается, что распределение выполнено правильно.) Концепция проверяемого разделения секрета впервые была представлена Бенни Чором, [[Шафи Гольдвассер]], [[Сильвио Микали]] и Барухом Авербухом в 1985 году{{sfn|B. Chor, S. Goldwasser, S. Micali, B. Awerbuch|1985}}.

Участник группы, который разделяет секрет, в протоколе VSS называется дилером ({{lang-en|dealer}}){{sfn|B. Chor, S. Goldwasser, S. Micali, B. Awerbuch|1985|c=387}}. Протокол делится на два этапа: разделение и восстановление.

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

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

При [[Протокол конфиденциального вычисления|безопасных многосторонних вычислениях]] входные данные делятся на тайные доли, которые используются для вычисления некоторой функции. Существуют злонамеренные участники, которые искажают данные и отклоняют их от протокола. Для предотвращения их влияния применяется VSS{{sfn|Oded Goldreich|2004}}.

== Схема Фельдмана ==
{{см. также|Схема разделения секрета Шамира}}
Протокол Пола Фельдмана основан на [[Схема разделения секрета Шамира|схеме разделения секрета Шамира]] в сочетании с любой схемой [[Гомоморфное шифрование|гомоморфного шифрования]]. Рассмотрим [[Разделение секрета#Пороговая схема|пороговую схему]] (''t'', ''n''). Вычисления проводятся с элементами циклической группы ''G'' порядка ''p'' с генератором ''g''. Группа ''G'' выбирается так, чтобы получение значения [[Дискретное логарифмирование|дискретного логарифма]] в этой группе обладало большой вычислительной сложностью. Затем дилер задает (и оставляет секретным) [[Многочлен|полином]] ''P'' степени ''t'' − ''1'' с коэффициентами из [[Циклическая группа|'''Z'''<sub>''p''</sub>]], т.ч. ''P''(0)=''s'', где ''s'' является секретом. Каждый из ''n'' участников получит значение ''P''(1), …, ''P''(''n'') по модулю ''p''{{sfn|P. Feldman|1987|c=429}}.

Все вышеперечисленное является реализацией разделения секрета Шамира. Чтобы сделать эту схему проверяемой, дилер рассылает проверочные значения к коэффициентам ''P''. Если ''P''(''x'') = ''s'' + ''a''<sub>1</sub>''x'' + … + ''a''<sub>''t'' − 1</sub>''x''<sup>''t'' − 1</sup>, тогда значения:
* ''c''<sub>0</sub> = ''g''<sup>''s''</sup>,
* ''c''<sub>1</sub> = ''g''<sup>''a''<sub>1</sub></sup>,
* …
* ''c''<sub>''t'' − 1</sub> = ''g''<sup>''a''<sub>''t'' − 1</sub></sup>.
Кроме того, ''i''-ому участнику дилер отправляет поправку ''z''<sub>i</sub> = ''g''<sup>''y''<sub>i</sub></sup>, где ''y''<sub>i</sub> = ''P''(''i'').
Как только это сделано, любой участник может проверить совместность своей доли, убедившись в следующем равенстве:<br>
: <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|P. Feldman|1987|c=433}}.

== Схема Бенало ==
Схема Бенало также является развитием [[Схема разделения секрета Шамира|схемы Шамира]]. Как только ''n'' долей распределены между участниками, каждый из них должен быть способен проверить, что все доли [[Разделение секрета#Пороговая схема|''t''-совместные]] ({{lang-en|t-consistent}}), то есть любая подгруппа участников ''t'' из ''n'' восстанавливает одинаковый секрет{{sfn|Josh Cohen Benaloh|1987|с=256}}. В схеме Шамира доли s<sub>1</sub>, s<sub>2</sub>, …, s<sub>n</sub> являются ''t''-совместными тогда и только тогда, когда степень интерполяционного многочлена, построенного по точкам (1, s<sub>1</sub>), (2, s<sub>2</sub>), …, (n, s<sub>n</sub>), не превышает ''d''=''t'' − ''1''{{sfn|Josh Cohen Benaloh|1987|с=256—257}}. Кроме того, если степень суммы двух полиномов ''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|Josh Cohen Benaloh|1987|с=252—253}}{{sfn|Josh Cohen Benaloh|1987|с=256—257}}.

Проверку совместности можно провести с помощью следующего алгоритма:
* Дилер задает полином ''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|Josh Cohen Benaloh|1987|с=256-258}}.

== Тайные выборы ==
VSS применим при проведении тайных выборов{{sfn|Chunming Tang, Dingyi Pei, Zhuojun Liu, Yong He|2004}}.
Каждый избиратель может голосовать за (1) или против (0), и сумма всех голосов определяет результат голосования. Необходимо убедиться в выполнении следующих условий:
* Конфиденциальность избирателей не должна быть нарушена.
* Наблюдатель должен проверить, что ни один избиратель не совершил обман.
При использовании VSS одного наблюдателя заменят ''n'' счетчиков голосов. Каждый избиратель распределит доли своего секрета среди всех ''n'' счетчиков. В этом случае конфиденциальность избирателя сохраняется, и первое условие выполняется. Для восстановления результата выборов необходимо существование достаточного количества ''k<n'' счетчиков для восстановления полинома ''P''. Для подтверждения голосов каждый избиратель может применить описанную в предыдущем разделе проверку совместности распределения{{sfn|Josh Cohen Benaloh|1987|с=258}}.

== Эффективность VSS ==
Сложность протокола VSS определяется как число этапов обмена сообщениями на этапе разделения, а именно как количество отправленных дилером долей секрета, проверочных значений (в схеме Фельдмана), случайных полиномов и так далее. Восстановление же всегда может быть выполнено за одно действие. Этого можно добиться с помощью одновременной трансляции ({{lang-en|simultaneous broadcast}}){{sfn|B. Chor, S. Goldwasser, S. Micali, B. Awerbuch|1985|c=383-387}}. Следовательно, не существует 1-этапного VSS с ''t>1'', независимо от количества участников. Кроме того, протокол VSS называется эффективным, если он имеет [[Временная сложность алгоритма#Полиномиальное время|полиномиальную сложность]], зависящую от ''n''. Условия эффективного протокола VSS{{sfn|Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan, and Kannan Srinathan|2006|с=331—332}}{{sfn|Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan, and Kannan Srinathan|2006|с=340}}:
{| class="wikitable"
|-
! Количество этапов
! Параметры
|-
| 1
| t = 1, n > 4
|-
| 2
| n > 4t
|-
| 3
| n > 3t
|}

== Примечания ==
{{примечания|2}}

== Литература ==
* {{статья
 | автор        = B. Chor, S. Goldwasser, S. Micali, B. Awerbuch
 | заглавие     = Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults
 | год          = 1985
 | страницы     = 383—395
 | ref          = B. Chor, S. Goldwasser, S. Micali, B. Awerbuch
 | издание      = IEEE
 | ссылка       = https://ieeexplore.ieee.org/document/4568164
}}
* {{статья
 | автор        = P. Feldman
 | заглавие     = A practical scheme for non-interactive verifiable secret sharing
 | год          = 1987
 | страницы     = 427—437
 | ref          = P. Feldman
 | издание      = IEEE
 | ссылка       = https://ieeexplore.ieee.org/document/4568297
}}
* {{статья
 | автор        = T. Rabin and M. Ben-Or
 | заглавие     = Verifiable secret sharing and multiparty protocols with honest majority
 | год          = 1989
 | страницы     = 79
 | ref          = T. Rabin and M. Ben-Or
 | издание      = STOC '89 Proceedings of the twenty-first annual ACM symposium on Theory of computing
 | ссылка       = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.481.4444&rep=rep1&type=pdf
}}
* {{статья
 | автор        = Chunming Tang, Dingyi Pei, Zhuojun Liu, Yong He
 | заглавие     = Non-Interactive and Information-Theoritic Secure Publicly Verifiable Secret Sharing
 | год          = 2004
 | ref          = Chunming Tang, Dingyi Pei, Zhuojun Liu, Yong He
 | издание      = IACR Cryptology ePrint Archive
 | ссылка       = http://eprint.iacr.org/2004/201.pdf
}}
* {{статья
 | автор        = Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin
 | заглавие     = The Round Complexity of Verifiable Secret Sharing and Secure Multicast
 | год          = 2001
 | страницы     = 580—589
 | ref          = Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin
 | издание      = STOC '01 Proceedings of the thirty-third annual ACM symposium on Theory of computing
}}
* {{книга
 | автор        = Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan, and Kannan Srinathan
 | заглавие     = Round-Optimal and Efficient Verifiable Secret Sharing
 | год          = 2006
 | страницы     = 330—342
 | ref          = Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan, and Kannan Srinathan
 | ссылка       = https://link.springer.com/content/pdf/10.1007%2F11681878_17.pdf
 | издательство = Springer-Verlag Berlin Heidelberg
}}
* {{книга
 | автор        = Oded Goldreich
 | заглавие     = The Foundations of Cryptography - Volume 2
 | издательство = Cambridge University Press 
 | год          = 2004
 | ref          = Oded Goldreich
}}
* {{статья
 | автор        = Josh Cohen Benaloh
 | заглавие     = Secret Sharing Homomorphisms: Keeping Shares of a Secret Secret
 | год          = 1987
 | ref          = Josh Cohen Benaloh
 | издание      = Proceedings on Advances in cryptology---CRYPTO '86
 | ссылка       = https://link.springer.com/content/pdf/10.1007%2F3-540-47721-7_19.pdf
}}

{{Добротная статья|Математика}}

[[Категория:Криптография]]
[[Категория:Криптографические протоколы]]
[[Категория:Разделение секрета]]