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

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

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

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

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

Реализация 
Фиксируется  — группа простого порядка ,  — независимо выбранные генераторы этой группы. Задача дилера — разделить случайное значение из данной группы. Для этого дилер сначала выбирает , а затем распространяет доли секрета .

Возможно использовать протокол Чаума — Педерсена для подтверждения , где : если подтверждающий знает такое , что  и  (дискретные логарифмы), где  и  — генераторы группы простого порядка :
 подтверждающий выбирает случайную  и отправляет  и ;
 проверяющий отправляет случайную посылку ;
 подтверждающий отвечает ;
 проверяющий проверяет что  и .

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

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

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

На фазе распределения данная часть протокола состоит из двух шагов — распределение долей и подтверждение долей. На шаге распределение долей дилер выбирает случайный полином  степени  с коэффициентами, принадлежащими :При этом нулевой коэффициент равен распределяемому секрету .Этот полином, в отличие от обычных схем разделения секрета, нигде не публикуется и приватно хранится у дилера. Вместо этого дилер публикует  и зашифрованные на публичных ключах каждой стороны полиномы . Дилер доказывает, что зашифрованные полиномы действительно лежат на одной прямой, если для  удовлетворяются следующие уравнения: и Для данной проверки протокол Чаума — Педерсена применяется параллельно всеми сторонами. На шаге подтверждение долей подтверждающая сторона вычисляет  с помощью значений . Затем, аналогично протоколу Чаума — Педерсена, вычисляются  и . Если они совпадают, то доли считаются подтверждёнными.

На фазе восстановления каждый участник, используя свой закрытый ключ , находит долю  из , вычисляя . Стороны публикуют  плюс доказательство того, что значение  является правильной расшифровкой . Для этого достаточно доказать знание  такого, что  и , для чего опять же можно применить протокол Чаума — Педерсена.

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

Примечания

Литература

Ссылки 
 Markus Stadler, Publicly Verifiable Secret Sharing
 Berry Schoenmakers, A Simple Publicly Verifiable Secret Sharing Scheme and its Application to Electronic Voting, Advances in Cryptology—CRYPTO, 1999, pp. 148—164

Криптографические протоколы
Разделение секрета