Подтверждаемый обмен секретами

В криптографии схема совместного использования секрета является проверяемой, если включена вспомогательная информация, позволяющая игрокам проверять целостность своих долей. Более формально, поддающееся проверке разделение секретов гарантирует, что даже если дилер является злонамеренным, существует четко определенный секрет, который игроки могут позже восстановить. (При стандартном обмене секретами предполагается, что дилер честен.) ^[1] Концепция проверяемого совместного использования секретов (VSS) была впервые представлена в 1985 году Бенни Чором , Шафи Гольдвассером , Сильвио Микали и Барухом Авербухом . ^[2]

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

Обмен: изначально дилер хранит секрет в качестве входных данных, а каждый игрок имеет независимый случайный вход. Фаза обмена может состоять из нескольких раундов. В каждом раунде каждый игрок может отправлять сообщения другим игрокам в частном порядке, а также транслировать сообщение. Каждое сообщение, отправленное или переданное игроком, определяется его вводом, его случайным вводом и сообщениями, полученными от других игроков в предыдущих раундах.

Реконструкция: на этом этапе каждый игрок предоставляет всю свою картину из фазы обмена, и применяется функция реконструкции, которая принимается в качестве выходных данных протокола.

Альтернативное определение, данное Одедом Гольдрайхом, определяет VSS как безопасный многосторонний протокол для вычисления рандомизированных функций, соответствующих некоторой (непроверяемой) схеме совместного использования секрета. Это определение более строгое, чем другие определения, и его очень удобно использовать в контексте общих безопасных многосторонних вычислений.

Поддающееся проверке разделение секретов важно для безопасных многосторонних вычислений . Многосторонние вычисления обычно выполняются путем секретного совместного использования входных данных и манипулирования ими для вычисления некоторой функции. Чтобы справиться с «активными» злоумышленниками (то есть злоумышленниками, которые повреждают узлы, а затем заставляют их отклоняться от протокола), схема совместного использования секрета должна быть проверяемой, чтобы предотвратить нарушение протокола отклоняющимися узлами.

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

Часто используемым примером простой схемы VSS является протокол Пола Фельдмана, ^[3] который основан на схеме разделения секретов Шамира в сочетании с любой схемой гомоморфного шифрования . Следующее описание дает общее представление, но не является безопасным в том виде, в каком оно написано. (Заметим, в частности, что опубликованное значение g ^с дилера сливает информацию о секретах .)

Во-первых, циклическая группа G простого порядка q вместе с генератором g группы G публично выбирается в качестве параметра системы. Группа G должна быть выбрана такой, чтобы вычисление дискретных логарифмов в ней было затруднительно. (Обычно берется подгруппа порядка q группы ( Z / p Z ) ^×, где q — простое число, делящее p − 1 .)

Затем дилер вычисляет (и хранит в секрете) случайный полином P степени t с коэффициентами из Z _q , такой, что P (0) = s , где s — секрет. Каждый из n акционеров получит значение P (1), ..., P ( n ) по модулю q . Любые t + 1 акционеров могут восстановить секрет s с помощью полиномиальной интерполяции по модулю q , но любой набор из не более t акционеров не может. (Фактически, в этот момент любая группа, состоящая не более чем из t акционеров, не имеет информации о s .)

Пока это именно схема Шамира. Чтобы сделать эти акции проверяемыми, дилер распределяет обязательства по коэффициентам P по модулю q . Если P ( x ) = s + a ₁ x + ... + a _t x ^т, то обязательства, которые должны быть даны, таковы:

с ₀ = г ^с,
с ₁ = г ¹,
...
с _т = г ^в.

Как только они будут предоставлены, любая сторона может подтвердить свою долю. Например, чтобы убедиться, что v = P ( i ) по модулю q , сторона i может проверить, что

$g^{v}=c_{0}c_{1}^{i}c_{2}^{i^{2}}\cdots c_{t}^{i^{t}}=\prod _{j=0}^{t}c_{j}^{i^{j}}=\prod _{j=0}^{t}g^{a_{j}i^{j}}=g^{\sum _{j=0}^{t}a_{j}i^{j}}=g^{P(i)}$ .

Эта схема в лучшем случае безопасна против вычислительно ограниченных противников, а именно от трудноразрешимых вычислений дискретных логарифмов. Педерсен позже предложил схему ^[4] где никакая информация о тайне не раскрывается даже у дилера с неограниченной вычислительной мощностью.

Схема Бенало

После того, как n акций распределены между их владельцами, каждый владелец должен иметь возможность проверить, что все акции в совокупности являются t -согласованными (т. е. любое подмножество t из n акций даст один и тот же правильный полином без раскрытия секрета).

В секретной схеме Шамира акции $s_{1},s_{2},...,s_{n}$ являются t -согласованными тогда и только тогда, когда интерполяция точек $(1,s_{1}),(2,s_{2}),...,(n,s_{n})$ дает полиномиальную степень не более d = t - 1 .

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

Второе наблюдение заключается в том, что, если степень суммы двух полиномов F и G меньше или равна t , либо степени F и G меньше или равны t , либо обе степени F и G равны. больше, чем т . Это утверждение очевидно из-за гомоморфного свойства полиномиальной функции, примеры:

случай 1:

f_{1}=3x

,

f_{2}=11x^{6}

,

t=6

случай 2:

f_{1}=18x^{7}

,

f_{2}=-18x^{7}

,

t=6

дело, которое мы отменили:

f_{1}=2x^{2}+3x^{3}

,

f_{2}=x+x^{7}

,

t=6

Интерактивное доказательство:
Следующие 5 шагов проверяют честность дилера перед акционерами:

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

Секрет остается в безопасности и нераскрытым.

Эти 5 шагов будут выполнены за небольшое количество итераций для достижения с высокой вероятностью результата о добросовестности дилера.

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

Диагноз 2: Одним из параметров проблемы было предотвращение раскрытия секрета, который мы пытаемся проверить. Это свойство сохраняется за счет использования гомоморфизма алгебры для проверки. (Набор случайных многочленов степени не выше t вместе с набором сумм P и других полиномов степени не выше t не дает никакой полезной информации о P .)

Выборы тайным голосованием

Поддающееся проверке разделение секретов можно использовать для создания сквозных проверяемых систем голосования .

Используя технику поддающегося проверке секретного обмена, можно решить проблему выборов, которая будет описана здесь.

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

Неприкосновенность частной жизни избирателей не должна подвергаться риску.
Организатор выборов должен убедиться в том, что ни один избиратель не совершил мошенничества.

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

Восстановить результат выборов легко, если существует достаточное количество счетчиков k < n, чтобы обнаружить полином P .

Интерактивное доказательство можно немного обобщить, чтобы можно было проверить доли голосов. Каждый избиратель докажет (на этапе распределения секретной доли) счетчикам голосов, что его голос законен, используя пять шагов интерактивного доказательства.

Оптимальный и эффективный поддающийся проверке обмен секретами

Сложность раунда протокола VSS определяется как количество раундов связи на этапе совместного использования; реконструкцию всегда можно выполнить за один раунд. Не существует однораундового VSS с t > 1 независимо от количества игроков. Границы идеальных и эффективных протоколов VSS приведены ниже.

Количество раундов	Безопасность
1	т = 1, п > 4
2	п > 4 т
3	п > 3 т

См. также

Библиография

Т. Рабин и М. Бен-Ор, Поддающееся проверке разделение секретов и многопартийные протоколы с честным большинством. В материалах двадцать первого ежегодного симпозиума ACM по теории вычислений (Сиэтл, Вашингтон, США, 14–17 мая 1989 г.). дои : 10.1145/73007.73014
Розарио Дженнаро, Юваль Ишаи, Эял Кушилевиц, Таль Рабин , Круглая сложность проверяемого обмена секретами и безопасной многоадресной рассылки. В материалах тридцать третьего ежегодного симпозиума ACM по теории вычислений (Херсониссос, Греция, страницы: 580–589, 2001 г.)
Маттиас Фитци, Хуан Гарай, Шьямнатх Голлакота, К. Панду Ранган и Каннан Сринатан, Оптимальный и эффективный проверяемый обмен секретами. Теория криптографии, Третья конференция по теории криптографии, TCC 2006 (Нью-Йорк, штат Нью-Йорк, США, 4–7 марта 2006 г.)
Одед Гольдрайх, Безопасные многосторонние вычисления
Джош Коэн Бенало, Гомоморфизмы, разделяющие секрет: сохраняя долю секрета. Труды о достижениях в криптологии, CRYPTO '86. стр. 251–260, 1987 г.

Ссылки

^ Кренн, Стефан; Лоруэнсер, Томас (2023). Введение в обмен секретами: систематический обзор и руководство по выбору протокола . дои : 10.1007/978-3-031-28161-7 . ISBN 978-3-031-28160-0 . (также доступно по адресу [1] )
^ Чор, Бенни ; Гольдвассер, Шафи; Микали, Сильвио; Авербух, Барух (1985). «Поддающееся проверке разделение секретов и достижение одновременности при наличии неисправностей» . 26-й ежегодный симпозиум по основам информатики (SFCS, 1985) . стр. 383–395. дои : 10.1109/SFCS.1985.64 . ISBN 0-8186-0644-4 . S2CID 12004245 .
^ Фельдман, Пол (1987). «Практическая схема неинтерактивного проверяемого обмена секретами» . 28-й ежегодный симпозиум по основам информатики (SFCS, 1987) . стр. 427–438. дои : 10.1109/SFCS.1987.4 . ISBN 0-8186-0807-2 . S2CID 16283693 .
^ Педерсен, Торбен Придс (1992). «Неинтерактивный и теоретико-информационный безопасный и проверяемый обмен секретами». В Фейгенбауме, Джоан (ред.). Достижения криптологии — КРИПТО '91 . Конспекты лекций по информатике. Том. 576. Берлин, Гейдельберг: Шпрингер. стр. 129–140. дои : 10.1007/3-540-46766-1_9 . ISBN 978-3-540-46766-3 .

Примечания

[1] Кренн, Стефан; Лоруэнсер, Томас (2023). Введение в обмен секретами: систематический обзор и руководство по выбору протокола . дои : 10.1007/978-3-031-28161-7 . ISBN 978-3-031-28160-0 . (также доступно по адресу [1] )

[2] Чор, Бенни ; Гольдвассер, Шафи; Микали, Сильвио; Авербух, Барух (1985). «Поддающееся проверке разделение секретов и достижение одновременности при наличии неисправностей» . 26-й ежегодный симпозиум по основам информатики (SFCS, 1985) . стр. 383–395. дои : 10.1109/SFCS.1985.64 . ISBN 0-8186-0644-4 . S2CID 12004245 .

[3] Фельдман, Пол (1987). «Практическая схема неинтерактивного проверяемого обмена секретами» . 28-й ежегодный симпозиум по основам информатики (SFCS, 1987) . стр. 427–438. дои : 10.1109/SFCS.1987.4 . ISBN 0-8186-0807-2 . S2CID 16283693 .

[4] Педерсен, Торбен Придс (1992). «Неинтерактивный и теоретико-информационный безопасный и проверяемый обмен секретами». В Фейгенбауме, Джоан (ред.). Достижения криптологии — КРИПТО '91 . Конспекты лекций по информатике. Том. 576. Берлин, Гейдельберг: Шпрингер. стр. 129–140. дои : 10.1007/3-540-46766-1_9 . ISBN 978-3-540-46766-3 .

[1]

[2]

[3]

[4]