Проверяемый секретный обмен - Verifiable secret sharing - Wikipedia

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

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

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

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

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

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

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

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

Во-первых, циклическая группа грамм высшего порядка п, вместе с генератором грамм из грамм, публично выбирается как системный параметр. Группа грамм должен быть выбран так, чтобы вычисление дискретные логарифмы в этой группе тяжело. (Обычно берется подгруппа (Z_q)^*, куда q такое простое число, что п разделяет q-1.)

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

Пока что это именно схема Шамира. Чтобы эти акции поддались проверке, дилер распределяет обязательства по коэффициентам п по модулю п. Если п(Икс) = s + а₁Икс + ... + а_тИкс^т, то необходимо принять следующие обязательства:

• c₀ = грамм^s,
• c₁ = грамм^а₁,
• ...
• c_т = грамм^а_т.

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

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

Схема Бенало

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

В Секретный обмен Шамиром схема акций s₁, с₂, ..., с_п t-согласованы тогда и только тогда, когда интерполяция точек (1, с₁), (2, с₂), ..., (п, с_п) дает степень полинома не выше d = t-1.

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

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

Случай 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}$
дело, которое мы отменили:
${\displaystyle f_{1}=2x^{2}+3x^{3}}$ , ${\displaystyle f_{2}=x+x^{7}}$ , ${\displaystyle t=6}$

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

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

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

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

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

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

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

Основная статья: сквозные системы голосования с возможностью аудита

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

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

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

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

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

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

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

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

Раунд-оптимальный и эффективный проверяемый секретный обмен

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

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

Смотрите также

• Обмен секретами
• Безопасные многосторонние вычисления
• Публично проверяемый обмен секретами
• Проверяемые вычисления

Рекомендации

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