Поддающийся проверке секретный обмен

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

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Март 2014 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

Эта статья включает в себя список литературы , связанной литературы или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Февраль 2019 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

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

Схема Фельдмана [ править ]

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

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

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

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

c ₀ = g ^s ,
c ₁ = g ^{a ₁} ,
...
с _т = г ^{а _т} .

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

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

Схема Бенало [ править ]

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

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

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

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

Случай 1: , , корпус 2: , , так что мы отменили: , ,
${\ displaystyle f_ {1} = 3x}$ ${\ displaystyle f_ {2} = 11x ^ {6}}$ ${\ displaystyle t = 6}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также [ править ]

Ссылки [ править ]

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