Введение в криптографию
[an error occurred while processing this directive]

Поиграем в ``кубики''. Протоколы голосования - часть 3


Мы рассмотрим в качестве примера один из вариантов криптосистемы Эль-Гамаля [], основанной на задаче дискретного логарифмирования. В обозначениях из раздела  пусть - подгруппа , порожденная . Для сообщения выбирается и вычисляется криптограмма , где ,

. Получатель, знающий секретный ключ , вычисляет

Вернемся к протоколу голосования. Пусть - еще один порождающий группы . Тогда для бюллетень вычисляется в виде . После применения алгоритма дешифрования центр получит значение , после чего бит можно извлечь, просто подставляя оба значения 1 и .

В такой схеме голосование, по существу, не может быть тайным, поскольку центр знает, как голосовал каждый избиратель. Но с правильностью подсчета голосов ситуация иная. Предположим, что для проведения голосования создано табло - хранилище информации, в котором для каждого избирателя выделена отдельная строка. Эта строка содержит, например, полные паспортные данные избирателя, и в эту строку он помещает свой бюллетень. Предполагается, что табло доступно на чтение всем участникам голосования, а также сторонним наблюдателям. По истечении срока подачи голосов табло ``закрывается'', т.е. фиксируется его состояние. После этого выделяется некоторое время, в течение которого каждый избиратель проверяет содержимое своей строки на табло. Все претензии разбираются, при необходимости вносятся соответствующие изменения и, когда все избиратели удовлетворены, содержимое табло фиксируется окончательно.

После этого центр вычисляет

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

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

. Проблема в том, что проверяющий не знает значение и не может самостоятельно выяснить, верно ли, что . Но нетрудно проверить, что должно выполняться сравнение . Поэтому проверяющий может потребовать от центра доказательство следующего факта: дискретный логарифм по основанию равен дискретному логарифму по основанию . Мы приводим предназначенный для этой цели протокол Шаума и Педерсена [], цитируя его по работе [].

Next: 3.7. За пределами стандартных

Up: 3. Криптографические протоколы

Previous: 3.5. Еще раз о

Contents:




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]