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

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

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

Содержание

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

Схема Бенало

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

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

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

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