Публично проверяемое разделение секрета

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

В схеме каждой стороне $P_{i}$ назначается публичная функция шифрования $E_{i}$ , при этом соответствующую функцию дешифрования $D_{i}$ не знает никто, кроме самого $P_{i}$ .

Дилер использует открытые функции шифрования для распределения долей, вычисляя:

S_{i} = E_{i} (s_{i}), i = 1, \dots, n

и публикуя зашифрованные доли $S_{i}$ . Для проверки достоверности всех зашифрованных долей существует алгоритм PubVerify, свойство которого состоит в том, что:

\exists u \forall A \in 2^{{1, \dots, n}} : (PubVerify ({S_{i} ∣ i \in A}) = 1) \Rightarrow Recover ({D_{i} (S_{i}) ∣ i \in A}) = u

и $u = s$ , если дилер был честенШаблон:Sfn.

Иными словами, если набор зашифрованных долей «достоверен» согласно PubVerify, то честные участники могут расшифровать их и восстановить секрет. Стоит обратить внимание, что PubVerify может быть выполнено, даже если стороны ещё не получили свои доли. Для запуска PubVerify может потребоваться связь с дилером (но не с участником). Схема PVSS называется неинтерактивной, если PubVerify вообще не требует взаимодействия с дилером, или интерактивной, если это не так.

Среди возможных применений PVSS — электронное голосование, пороговые криптосистемы, пороговые отзывные электронные деньги, пороговое программное обеспечение депонирования ключей, пороговые подписи.

Реализация

Фиксируется $G_{p}$ — группа простого порядка $p$ , $g, G$ — независимо выбранные генераторы этой группы. Задача дилера — разделить случайное значение из данной группы. Для этого дилер сначала выбирает $s \in_{R} Z_{p}$ , а затем распространяет доли секрета $S = G^{S}$ .

Возможно использовать протокол Чаума — Педерсена для подтверждения $\log_{g_{1}} h_{1} = \log_{g_{2}} h_{1}$ , где $g_{1}, g_{2}, h_{1}, h_{2} \in G_{p}$ : если подтверждающий знает такое $α$ , что $h_{1} = g_{1}^{α}$ и $h_{2} = g_{2}^{α}$ (дискретные логарифмы), где $g_{1}$ и $g_{2}$ — генераторы группы простого порядка $p$ :

подтверждающий выбирает случайную $r \in Z_{q^{*}}$ и отправляет $a_{1} = g_{1}^{r}$ и $a_{2} = g_{2}^{r}$ ;
проверяющий отправляет случайную посылку $c \in_{R} Z_{q}$ ;
подтверждающий отвечает $s = r - α c (m o d q)$ ;
проверяющий проверяет что $a_{1} = g_{1}^{s} h_{1}^{c}$ и $a_{2} = g_{2}^{s} h_{2}^{c}$ .

Протокол Чаума — Педерсена является интерактивным и требует некоторой модификации для использования в неинтерактивном режиме: замены случайно выбранной $c$ на «безопасную хэш-функцию» с $m$ в качестве входного значения.

Сама схема PVSS состоит из трёх фаз: инициализации, распределения и восстановленияШаблон:Sfn.

На этапе инициализации выбирается группа $G_{p}$ и её генераторы $g, G$ . Непосредственно алгоритм выбора надежных параметров является отдельной задачей криптографии и не относится к протоколу PVSS. Каждая сторона $P_{i} i = 1 \dots n$ генерирует закрытый ключ $x_{i} \in_{R} Z_{p}^{*}$ и регистрирует $y_{i} = G^{x_{i}}$ в качестве своего открытого ключаШаблон:Sfn.

На фазе распределения данная часть протокола состоит из двух шагов — распределение долей и подтверждение долей. На шаге распределение долей дилер выбирает случайный полином $d$ степени $t - 1$ с коэффициентами, принадлежащими $Z_{p}$ :
$d (x) = \sum_{j = 0}^{t - 1} β_{j} x^{j}$
При этом нулевой коэффициент равен распределяемому секрету $β_{0} = s$ .
Этот полином, в отличие от обычных схем разделения секрета, нигде не публикуется и приватно хранится у дилера. Вместо этого дилер публикует $C_{j} = g_{j}^{β}, 0 \leq j \leq t$ и зашифрованные на публичных ключах каждой стороны полиномы $Y_{i} = y_{i}^{d (i)}, 1 \leq i \leq n$ . Дилер доказывает, что зашифрованные полиномы действительно лежат на одной прямой, если для $d (i), 1 \leq i \leq n$ удовлетворяются следующие уравнения:

$X_{i} = \prod_{j = 0}^{t - 1} C_{j}^{i j} = g^{d (i)}$ и $Y_{i} = y_{i}^{d (i)}$ Для данной проверки протокол Чаума — Педерсена применяется параллельно всеми сторонами. На шаге подтверждение долей подтверждающая сторона вычисляет $X_{i}$ с помощью значений $C_{j}$ . Затем, аналогично протоколу Чаума — Педерсена, вычисляются $a_{1 i} = g^{s_{i}} X_{i}^{c}$ и $a_{2 i} = y^{s_{i}} Y_{i}^{c}$ . Если они совпадают, то доли считаются подтверждённымиШаблон:Sfn.

На фазе восстановления каждый участник, используя свой закрытый ключ $x_{i}$ , находит долю $S_{i} = G^{d (i)}$ из $Y_{i}$ , вычисляя $S_{i} = Y_{i}^{1 / x_{i}}$ . Стороны публикуют $S_{i}$ плюс доказательство того, что значение $S_{i}$ является правильной расшифровкой $Y_{i}$ . Для этого достаточно доказать знание $α$ такого, что $y_{i} = G^{α}$ и $Y_{i} = S_{i}^{α}$ , для чего опять же можно применить протокол Чаума — Педерсена.

Возможна операция объединения долей: если участники $P_{i}$ прошли все необходимые проверки и убедились, что значения $S_{i}$ верны для $i = 1, \dots, t$ . Секрет $G^{s}$ , то можно применить интерполяцию Лагранжа: