Протокол Шаума и Педерсена

1. Доказывающий выбирает к вычисляет и посылает проверяющему.

2. Проверяющий выбирает запрос и посылает доказывающему.

3. Доказывающий вычисляет и посылает s проверяющему.

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

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

В принципе центр может доказать утверждение каждому желающему. Неудобство в том, что протокол интерактивный. Но используя тот же прием, которым схема аутентификации Шнорра преобразуется в схему электронной подписи (см. раздел 2), можно и этот протокол сделать неинтерактивным. В таком случае центр может просто опубликовать неинтерактивное доказательство вместе с итогом

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

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

и передает долю центру Далее, выполняя вычисления над долями (см. раздел 5), центры вычисляют Если при этом хотя бы центров честные, то остальные не смогут восстановить ни одно из значений Полученный результат S проверяется: должно выполняться сравнение Если оно выполнено, то значение S публикуется, и этого значения достаточно для вычисления итога голосования. В самом деле, Правда, для того чтобы получить итог необходимо вычислить дискретный логарифм полученной величины. Но поскольку абсолютное значение невелико (заведомо не превосходит количества избирателей I) это можно сделать простым перебором.

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

Все проблемы решены? Отнюдь! Если в случае одного центра последний расшифровывал все бюллетени и проверял их правильность, отбрасывая недействительные, то в случае центров нечестный избиратель может попытаться с помощью недействительного бюллетеня сорвать выборы или исказить их итог. Эту проблему можно решить, если потребовать, чтобы вместе с бюллетенем каждый избиратель публиковал доказательство, что бюллетень построен правильно. Другими словами, требуется протокол, с помощью которого для данного бюллетеня избиратель доказывал, что он знает такие, что При этом протокол не должен давать проверяющему никакой полезной для него информации о значениях Пример такого протокола дан в работе [22]; мы его не воспроизводим здесь ввиду громоздкости.

Теперь, наконец, все? Опять нет! ... Впрочем, поставим на этом точку. Надеемся, что читатель уже убедился в том, что протоколы голосования — нетривиальный объект и всевозможные его технические

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

Дальнейшие подробности протоколов голосования см. в работах [22], [23], из которых заимствованы изложенные выше идеи построения таких протоколов.

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