4.4.2. Криптографическая поддержка государственно- правовых отношений. Электронные выборы

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

Одной из задач, активно изучаемых криптографами, является задача честного проведения «электронных выборов». В отличие от традиционных выборов должностных лиц органов государственной власти, когда голоса подаются избирателями путем заполнения бюллетеней на избирательных участках, а подсчет голосов осуществляется избирательными комиссиями, здесь избиратели подают свои голоса «в электронном виде», например, через Интернет, а их под-счет и подведение итогов выборов выполняется специально уполно-моченными органами. До недавнего времени электронное голосование рассматривалось скорее как занимательная игровая задача из области криптографии. В последние несколько лет положение дел резко поменялось. В США и в странах Европейского союза активно обсуждаются возможности проведения президентских выборов и выборов в парламенты этих государств с использованием возможностей, предоставляемых сетью Интернет.

Сформулируем задачу электронных выборов более строго. Пусть имеется т участников многостороннего протокола - избирателей V^i = 1, т, каждый из которых вырабатывает свой секрет xt.

Необходимо вычислить функцию/, зависящую от этих величин, не разглашая ни одной из них, но делая значение функции / общедос-

4. Криптографические протоколы в электронной колшерции и в докуліеитообороте 283

тупным. Для определенности каждый отдельно взятый случай применения схемы электронных выборов (т. е. каждый сеанс основного протокола этой схемы) будем называть электронным голосование.

Схема электронных выборов должна удовлетворять следующим очевидным требованиям:

голосовать на выборах могут только авторизованные избиратели;

никто не может проголосовать на выборах более одного раза;

голос каждого отдельного избирателя хранится в секрете;

никто не может дублировать голоса других избирателей;

итоги выборов должны быть подведены корректно;

справедливость выполнения условия 5 может быть проверена публично;

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

должно быть невозможно принуждать избирателей к разглашению своего голоса.

Обычно в схемах электронных выборов бывает нежелательно вовлекать всех избирателей У/ в процесс подсчета голосов. Мы предполагаем, что, кроме избирателей, в крипто схеме участвует п государственных избирательных комиссий С15...,С„, их задача заключается в сборе голосов и подведении итогов голосований.

Одно из простых решений этой задачи - схема электронных выборов Merritt. Каждая избирательная комиссия С, публикует открытый ключ pi некоторой схемы открытого шифрования, а соответствующий ему секретный ключ s-t сохраняет у себя в тайне. Чтобы отдать свой голос у,, каждый избиратель К- выбирает случайное число rj и вычисляет функцию ЕР] (Ерг [.Ер (ур г.

284 Запечников С. В. Криптографические протоколы и их применение

yitj' = Epi (yi+Uj,qLj). Новый индекс - / вычисляется как случайная

перестановка %і на множестве целых чисел {1,2,...,«}, т.е.

Ґ -ni(j) ¦ Каждая Q хранит свою перестановку в секрете. В итоге мы имеем:

Уи=еР>

С этого момента начинается этап проверки. Он состоит из двух циклов расшифровки полученных величин в порядке от С, к С„. Расшифрованные величины опубликовываются, а итог выборов под-водится как суммы всех v.,y = l,m, отсортированных как голоса

«за» или «против».

Требования 1 и 2 в этой схеме очевидным образом удовлетворяются. Требование 3 тоже удовлетворяется: даже если какие-либо голоса разглашаются, невозможно установить связь между голосом и подавшим его избирателем. Чтобы восстановить эту связь, нужно знать все случайные перестановки щ. Требование 4 здесь не удовлетворяется, так как избиратель Vx легко может копировать голос избирателя V2> опубликовывая ту же самую двоичную строку шифртекста. Условия 5 и 6 удовлетворяются благодаря использованию случайных строк: в первом цикле расшифровки каждая комиссия проверяет, что выбранные ею случайные строки появляются в рас-шифрованных текстах. Это дает ей уверенность в том, что все ее шифртексты были подсчитаны. Точно так же в конце второго цикла расшифровки каждый избиратель видит свою случайную строку что дает ему уверенность в том, что его личный голос был подсчитан. Чтобы снизить вероятность повтора случайных строк, их длина должна быть достаточно большой. Заметим: для того, чтобы проверить корректность подведения итогов выборов, необходима кооперация всех избирателей - это отрицательное свойство протокола, особенно заметное в условиях большого количества избирателей.

4. Криптографические протоколы в электрошюй коммерции и в докумешпообороте 285

именно из избирателей какой голос подал. Для этого нужно было бы знать все случайные перестановки лі, для чего потребовалось бы

скомпрометировать все избирательные комиссии. Однако подобная схема крайне ненадежна: если хотя бы одна избирательная комиссия перестанет функционировать, вся система выборов выходит из строя и требуется проводить повторные выборы. Условие 8 в этой схеме вообще не удовлетворяется: избирателя могут принудить разгласить и свой голос V;, и случайное число /). Если же он попытается обмануть, ложь будет обнаружена, так как заявленная величина не будет соответствовать шифртексту yn+l j.

Более эффективна и надежна схема электронных выборов Cramer - Franklin - Schoenmakers - Yung, основанная на идее Бе- нало (J. Benaloh, 1987). Эта схема, в отличие от предыдущей, удовлетворяет требованию 4, т. е. делает невозможным копирование чужих голосов. Она не требует кооперации всех избирателей для публичной проверки итогов выборов, предлагая более эффективное решение, удовлетворяющее требованию 6. Кроме того, эта схема является робастной: мы можем зафиксировать порог t и, если число скомпрометированных избирательных комиссий не превысит порога t, схема все же будет позволять корректно подсчитывать итоги голосования и сохранять секретность каждого отдельного голоса. Тем не менее схема по-прежнему не удовлетворяет требованию 8, т. е. допускает контроль над волей избирателей.

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

286 Запечников С. В. Криптографические протоколы и их прішеиеиие

Н(х) - хеш-функция с трудно-обнаруживаемыми коллизиями. В не может извлечь А* из у, так как функция Н однонаправленная. Чтобы «открыть» депонированную величину, А пересылает В саму величину х, и он проверяет, что Щх) = у. Но А не может найти такое х Ф х, чтобы Н (/) = у, следовательно, не может обмануть В. Можно построить и другие примеры схем депонирования сообщений.

Пример гомоморфной схемы депонирования сообщений, основанный на функции дискретного логарифмирования, построен Пе- дерсеном. Эта схема базируется на той же идее, что и схема проверяемого разделения секрета Педерсена, рассмотренная в под- разд. 1.5. Пусть р - простое число вида р = kq+1 и пусть g, h - два элемента подгруппы порядка q. Мы предполагаем, что никто не умег ет вычислять дискретные логарифмы по основаниям g и h. Чтобы депонировать сообщение те {1,2,...,^}, необходимо вычислить

функцию Ba(jn)= g"h"}, где ає Z0 - случайное число. Чтобы «открыть» депонированную величину, необходимо знать а и т. Эта схема обладает свойством гомоморфизма относительно операций сложения и умножения, так как

-g^-h"" -К"* =В„,+„!Ц + тг).

Далее такую (+, х) -гомоморфную схему депонирования сообщений будем обозначать символом Е.

Для простоты рассмотрим сначала схему электронных выборов с одной избирательной комиссией, а потом обобщим ее на случай, когда итоги голосований подводятся несколькими комиссиями. Итак, пусть С - избирательная комиссия, Е - выбранная ею гомоморфная схема депонирования сообщений.

Протокол голосования. Предположим, что голоса «за» и «против» выражаются символами «-1» и «1».

Теперь избиратель должен доказать, что его голос подан корректно, т. е. что он представляет собой величину «-1» либо «1». Для этого каждый избиратель должен выполнить с избирательной комиссией протокол доказательства знания Vj с нулевым разглашением знания.

Для гомоморфной схемы депонирования Педерсена, основанной на функции дискретного логарифмирования, протокол голосования оказывается очень эффективным. Для удобства представления протокол приводится в табл. 4.10 и 4.11 для двух случаев: когда голос Vj = 1 и когда Vj = -1, хотя по форме они ничем не отличаются. Индексы j для простоты везде опущены. Далее мы будем обозначать этот протокол Proof(BJv)).

Таблица 4.10. Протокол голосования для v = 1 У С 1 a,rl,dl,w2 є Zq - случайное число, Bu(v) = g"h, 2 се Zn- случайное число 3 d2 = с - d{, r2=w2 + ad2 4 dt + d2=с, h

\ /

Таблица 4.11. Протокол голосования для v = -1

V С 1 a,r2,d2,wx є Z - случайное число,

а, «г4.

п

\ / [Be(v),a,,a2] 2 <- с є Zq — случайное число 3 dx = с —d2, ry = + adx [dltd2,rltr2] 4 7

dx +d2=c,

г? іЧМЇ1 8 ~а2 -Т2

п

\ /

Протокол подсчета голосов. В конце предыдущего протокола для каждого Vj стала известна величина Baj (vj j. Центр опубликовывает итог голосования T = ^Vj и дополнительно величину

j

A = ^aj. Каждый может проверить, что итог корректен, выполняя j

следующую операцию:

j

что должно выполняться для любого правильно подсчитанного Т вследствие свойства гомоморфизма схемы Е.

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

Рассмотрим теперь схему электронных выборов со множеством избирательных комиссий С\, Пусть Е| - гомоморфные схемы

депонирования, выбранные комиссиями Ct, і = 1, п.

Протокол голосования. Каждый избиратель V. депонирует свой голос v;e{-l;l}, опубликовывая В- -Ba{yj] для Zqi после

чего доказывает корректность своего голосования, выполняя протокол Proof Затем он разделяет величины а^ и между из-бирательными комиссиями, используя для этого ([+1 ,и)-пороговую схему разделения секрета Шамира. Для этого он выбирает случайные многочлены Rj(X),Sj(X)e Zq\X\ степени t, такие, что

Rj (0) = Vj и Sj (0) = aj. Пусть:

Rj(x) = vj + rljX+... + rtjXt, S^aj+s^X+... + ^Х'.

Теперь избиратель посылает значения ui . - Rj(i) и wt . = Sj(i) в КОМИССИЮ С;, ДЄПОНИрОВаННЬІЄ При ПОМОЩИ схемы Е|. Наконец, он депонирует коэффициенты многочлена Rj\ Bt j = BSl. Чтобы

убедиться, что доли депонированы корректно, комиссия выполняет следующую проверку:

gw,J-ti*'=Bj-il(B,J.

/=1

Протокол подсчета голосов. Каждая комиссия С,- опубликовывает частичные суммы:

1) Tj = - сумму долей голосов, полученных от каждого из

j

участников;

2) Д = ^ Wj j - сумму долей случайных строк ар использовав- j

шихся для депонирования голосов, поданных избирателями.

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

j=1 ^ 1=1

Заметим, что корректно подсчитанные Г/ - это доли величины Т в (/+1,п)-пороговой схеме разделения секрета Шамира. Таким образом, достаточно взять любые /+1 из них, чтобы интерполировать величину Т, которая и является итогом голосования.

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

Требованиям 1 и 2 эта схема, очевидно, удовлетворяет. Требование 3 выполняется в предположении, что не более г избирательных комиссий могут объединиться для того, чтобы узнать голоса избирателей. Если объединятся М-1 комиссий, то тайна голосования уже будет утрачена. Требование 4 выполняется по следующим причинам. Предположим, Vx пытается копировать действия V2. Когда он доходит до доказательства корректности голоса, Vx получает запрос с, отличный от запроса, который получает V2. Он не будет способен ответить на него и, следовательно, будет исключен из числа участ-ников голосования. Свойство 5 справедливо в предположении о вычислительной сложности задачи дискретного логарифмирования. Условие 6 выполнено, так как все протоколы доказательства с нулевым разглашением знания и проверочные уравнения избирательных комиссий могут быть публично проверены. Свойство 7 тоже справедливо, так как, чтобы подвести итоги голосования, достаточно t+1 честных избирательных комиссий. Легко видеть, что, поскольку нам необходимо f+І честных комиссий и не более t из них могут быть скомпрометированы, максимальное число скомпрометированных избирательных комиссий, при которых протокол сохраняет свою

71

функциональность, равно Но свойство 8 здесь по-прежнему

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

Вообще, проблема контроля над избирателями в схемах электронных выборов (оставляющая возможности принуждения или подкупа избирателей) одна из самых сложных. Какими способами возможно принуждение избирателей?

Рассмотрим две потенциально возможные ситуации.

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

Вторая ситуация реализуется, когда кто-то пытается контролировать волю избирателя после голосования. Предположим, от него требуют разгласить свой голос v и значения случайных величин р, использованных в протоколе. В лучшем случае ему удастся подобрать другие значения v' и р', подходящие для протокола. Но, например, в приведенной выше схеме это невозможно, пока никто не умеет решать задачу дискретного логарифмирования. Недавно предложен новый метод решения этой задачи - отказуемое шифрование (deniable encryption); это вероятностная схема открытого шифрования, обладающая следующим свойством. Пусть т - открытый текст сообщения, г ~ случайное число. Отправитель вычисляет шифртекст с = Ег (in). Затем, если кто-либо просит его разгласить значение т, он всегда сможет сгенерировать другие т и /, такие, что Е, (т) = с.

292 Запечников С. В. Криптографические протоколы и их применение

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

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