схема голосования без принуждения

Формула изобретения

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

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

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

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

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

6. Читаемый компьютером носитель информации по п.5, в котором зашифрованный бюллетень и вторая подтверждающая избирателя величина принимаются совместно от избирателя.

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

8. Читаемый компьютером носитель информации по п.5, в котором когда принимаются зашифрованный бюллетень и вторая подтверждающая избирателя величина, то каждая связывается с идентичностью избирателя, при этом содержимое читаемого компьютером носителя информации дополнительно приводит к выполнению вычислительной системой отделения идентичности избирателя от зашифрованного бюллетеня и второй подтверждающей избирателя величины; и после отделения, определения, совпадает ли принятая совместно вторая подтверждающая избирателя величина с принятой первой подтверждающей избирателя величиной.

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

10. Способ по п.9, в котором (а) выборы могут быть полностью верифицируются членами общества, без возможности определения (b) членами общества, засчитан ли выбор голосования в компьютерной системе голосования.

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

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

13. Читаемый компьютером носитель информации по п.12, в котором (а) выборы полностью верифицируются членами общества, без возможности определения (b) членами общества, засчитан ли выбор голосования в компьютерной системе голосования.

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

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

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

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

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

Описание изобретения к патенту

Область техники, к которой относится изобретение

Данная заявка относится к области мер защиты для электронно проводимых выборов.

Уровень техники

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

Аналогичные проблемы возникают при использовании систем заочного голосования по почте. Например, муж может принуждать свою жену голосовать определенным образом. Угроза принуждения усиливается в сетевом мире, где люди могут «заглядывать через плечо» на расстоянии в тысячи миль. Эта угроза является достаточно серьезной, чтобы ее часто рассматривать в качестве причины отказа от дистанционного электронного голосования.

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

Краткое описание чертежей

На чертежах изображено:

фиг. 1 - блок-схема подходящей среды для осуществления схемы;

фиг. 2 - графическая схема стадий, обычно выполняемых в соответствии со схемой.

Описание

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

В целом, изобретение работает следующим образом.

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

2. Во время процесса регистрации каждый избиратель выбирает секретный «код подтверждения» или «фразу пароля подтверждения».

3. «Фраза пароля подтверждения» зашифровывается избирателем, и зашифрованная форма публично регистрируется для этого избирателя.

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

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

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

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

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

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

Изобретение может быть реализовано также в распределенной вычислительной среде, где задачи или модули выполняются с помощью устройств дистанционной обработки данных, которые связаны сетью связи, такой как местная вычислительная сеть (LAN), глобальная сеть (WAN) или Интернет. В распределенной вычислительной среде программные модули или подпрограммы могут быть расположены как в местных, так и в удаленных запоминающих устройствах. Аспекты данного изобретения, описание которых приводится ниже, можно хранить или распределять на читаемых компьютером носителях информации, включая магнитные и оптические читаемые и сменные компьютерные диски, храниться в виде аппаратного обеспечения в микросхемах (например, микросхемах EEPROM), а также распределяться электронно по Интернету или другим сетям (включая беспроводные сети). Для специалистов в данной области техники понятно, что части изобретения могут находиться на сервере, в то время как соответствующие части находятся в компьютере клиента. Структуры данных и передача данных, характерные для аспектов данного изобретения, также входят в объем изобретения.

Как показано на фиг. 1, в одном варианте выполнения изобретения используется компьютер 100, такой как персональный компьютер или рабочая станция, имеющая один или более процессоров 101, соединенных с одним или более устройствами 102 ввода пользователя, и одно или более устройств 104 хранения данных. Компьютер соединен также, по меньшей мере, с одним устройством вывода, таким как дисплейное устройство 106, и с одним или более необязательными дополнительными устройствами вывода 108 (например, принтер, плоттер, громкоговорители, сенсорные или обонятельные выходные устройства и т.д.). Компьютер может быть соединен с внешними компьютерами, например, через необязательное сетевое соединение 110 и/или через беспроводной приемопередатчик 112.

Устройство 102 ввода может включать клавиатуру и/или указательное устройство, такое как мышь. Возможны также другие устройства ввода, такие как микрофон, ручка управления, перо, игровая подложка, сканер, цифровая камера, видеокамера и т.п. Устройство 104 хранения данных может включать читаемый компьютером носитель информации любого типа, который может хранить данные, доступные для компьютера 100, такие как устройства с магнитным жестким или гибким диском, приводы оптического диска, магнитные кассеты, ленточные приводы, карты флэш-памяти, цифровые видеодиски (DVD), картриджи Бернулли, ОЗУ, ПЗУ, интеллектуальные карточки и т.д. Действительно, можно использовать любой носитель информации для хранения или передачи читаемых компьютером команд и данных, включая соединительный порт с сетью, такой как местная вычислительная сеть (LAN), глобальная сеть (WAN) или Интернет (не изображен на фиг. 1). Аспекты изобретения можно реализовать также в различных других вычислительных средах.

На фиг. 2 показана графическая диаграмма этапов, обычно выполняемых в соответствии с этой схемой. Подробное описание этих этапов приведено ниже. На этапе 201 избиратели регистрируются для внесения их в списки зарегистрированных избирателей, имеющих право голосования, и обеспечения их выборными верительными данными. На этапе 202 выборы начинаются для определения результатов голосования для кандидатов. На этапе 203 избиратели отдают свои голоса посредством подачи зашифрованных бюллетеней. На этапе 204 табулируют поданные на стадии 203 голоса и добавляют к окончательному результату голосования, если только можно верифицировать правильность полученного бюллетеня. После этапа 204 эти стадии завершаются.

1. Осуществления принуждения в раздельной табуляции

Целью данного раздела является

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

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

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

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

Определение 3. Информация по принуждению является любой информацией, достоверность которой может быть «верифицирована» принуждающим лицом. Если достоверность не может быть верифицирована, то избиратель (или отдельное лицо, подвергаемое принуждению) может лгать о ней принуждающему лицу.

Определение 4. Напомним, что результат является функцией t: C N = Z⁺ {0}, где Г = {c₁,..., c_l} является списком кандидатов. Можно записать

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

Определение 5. Поскольку передача и хранение информации являются ключевыми элементами данного изобретения, чем технологии, которые облегчают передачу и хранение, то в последующем используется более общее понятие - доска объявлений для определения открыто доступного устройства хранения, а действие записи информации на доске объявлений обозначается как занесение (posting) (в контексте голосования это соответствует действию отдачи голоса). Кроме того, строки или записи информации, которые заносятся на доску объявлений, называются отправлениями (posts) (в контексте голосования это соответствует поданным голосам).

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

РР-1. Отправления всегда прикреплены к доске объявлений (ВВ), то есть вычеркивания не разрешены. И занесение является элементарной транзакцией, то есть, в любое заданное время доска объявлений содержит точно k отправлений для некоторого не отрицательного целого k.

РР-2. Любой игрок может присоединить отправление независимо от состояния (содержимого) доски объявлений.

РР-3. В любое заданное время может быть образован итог, и он является однозначным. То есть, невозможно (или по меньшей мере преобладающе невероятно), что доска объявлений находится в некотором состоянии С(ВВ), которое является не действительным для табуляции, а результат С(ВВ): C N является заданным.

РР-4. Группа игроков не может вычислить результат независимо от состояния доски объявлений.

Напомним, что списком О избирателей является по существу публичный список игроков (законных избирателей) {v₁,..., v _k}. C(ВВ) используется также для обозначения содержимого доски объявлений в произвольный момент времени, т.е. последовательности отправлений p₁,..., p_t. Пусть Р будет комплектом всех игроков в протоколе, то есть О Р.

Для простоты представления предположим, что бюллетень состоит из одного вопроса, т.е. что список кандидатов Г задан {c₁,..., c_l}, и каждый избиратель может выбрать (голосовать за) самое большое за одного кандидата. Обобщение этой установки на несколько более общих типов бюллетеней (которые не включают вписывание новых кандидатов) является достаточно оправданным.

Определение 6. Пусть С = С(ВВ) является любым состоянием доски объявлений (последовательностью отправлений). Если является отправлением, то С обозначает состояние доски объявлений после присоединения единственного отправления . Запись t_C используется для обозначения результата итог(С).

Определение 7. Функцией голосования (на доске объявлений) является отображение

: P × C(BB) {0,1}^Г (1)

характеризуемое следующим:

vf-1. Для всех р Р

| (р, С(ВВ)) | {0,1} (2)

vf-2. Для всех С(ВВ), если р О, то (с преобладающей вероятностью)

(р, С(ВВ)) = 0 (3)

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

vf-3. Для всех р Р, если р отправляет , то для всех q Р справедливо следующее (с преобладающей вероятностью)

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

vf-4. Для всех и всех если | (v_i, C(BB))| = 0, то v_i может вычислить (с вероятностью 1) отправление , так что

Интуитивно смысл этого состоит в том, что если v_i еще не проголосовал, то v_i может присоединить голос для любого кандидата. Однако это утверждение не предполагает возможности, что протокол разрешает отдать v_i свой голос, а затем изменить его (несмотря на это, большинство известных из литературы протоколов, которые по существу разрешают избирателю «один и только один раз изменить голос», соответствуют этому критерию).

vf-5. Для всех если | (v_i, C(BB))| = 1, то v_i может вычислить с почти пренебрежимо малой вероятностью отправление , удовлетворяющее условию

|t_C(BB) | > |t_C(BB)| (6)

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

Пусть A_ij является событием вычисления v_i отправления , удовлетворяющего условию

t_C(BB) (c_j) - t_C(BB)(c_j ) = -1 (7)

Пусть B_ij является событием, заключающимся в том, что (v_i, C(BB))(c_j) = 1.

vf-6. Имеется постоянная (0 1), так что для всех и всех условная вероятность Р(A_ij|B_ij ) соответствует условию

Р(A_ij|B_ij ) = (8)

независимо от величины i, j и состояния доски объявлений С(ВВ).

Интуитивно смысл этого состоит в том, что если протокол позволяет избирателю изменить иногда голос, то протокол позволяет любому избирателю изменять голос в любое время. Однако, это не предполагает, что протокол запрещает изменение голоса, что является более обычным.

vf-7. Для всех и всех условная вероятность Р(A_i |B_i ) соответствует условию

Р(A_ij|B _i ) = (9)

где 0 является пренебрежительно малой.

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

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

Определение 8. Протокол выборов считается имеющим разделяемую табуляцию, если и только если он удовлетворяет условиям РР-1 - РР-5. Для краткости в последующем будет использоваться также понятие разделяемый протокол выборов для обозначения любого протокола, имеющего разделяемую табуляцию.

Теорема 1. Если протокол выборов имеет разделяемую табуляцию и принуждающее лицо содержит совокупность игроков, способных вычислять результат, то для любых величина (v_i,C(BB)) является возможной для принуждения.

Доказательство: (схематично) принуждающее лицо может проходить через последовательность изображений урн для голосования, вычисляя в каждой точке результат (смотри предположение РР-4) и требуя от v_i добавления голоса определенного значения. За счет повторного вычисления результата с присоединенным отправлением v_i, принуждающее лицо может определить, какие отправления были добавлены v_i и их совокупное воздействие на результат.

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

1. Исполнить роль избирателя в течение выборов, таким образом добавляя любой выбранный голос к доске объявлений (избирательной урне), и соответственно фальсифицировать часть избирательного протокола.

2. Определить любые попытки избирателя изменить голос.

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

CS-1. Если p P и v_i O, v_i p, тогда p не может вычислить

с вероятностью выше, чем «случайное угадывание + »

CS-2. Результат выборов публично верифицируемый.

Определение 10. Подразделяемый протокол выборов защищен от принуждения, если он стойкий к воздействию принуждающего лица и любых сценариев тайного сговора.

CS-3. Если t_I идеальный результат, тогда верификация выборов гарантирует

| t _C(BB)- t_I| M (10)

2. Защищенный от принуждения протокол выборов

Предположим стандартную криптографическую защиту Эль Гамаля: p и q являются большими первичными величинами, при q|p - 1. Генератор подгрупп g Z*_p при |g| = q и h = g^s, где s совместно используется n лицами, уполномоченными осуществлять табуляцию A₁,...,A_n по пороговой схеме (t, n).

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

2.1. Регистрация

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

Обозначим избирателя как v_i.

R-1. v_i выбирает случайное r_i g и случайное _i Z_q и образует

(U_i0, W_i0 ) = (g ⁱ, h ⁱr_i) (11)

R-2. Для каждого

R-2.1. v_i получает от A_j пару (U_ij,W_ij), заданную

(U _ij, W_ij) = (g ^ij, h ^ij) (12)

где _ij g выбирается случайно A_j.

R-2.2. v _i и A_j выполняют интерактивную проверку Шаум-Педерсена правильности соотношения log_gU_ij = log _hW_ij. То есть, сложность создается случайно v_i, а не с помощью хэш-функции (эвристический метод Фиата-Шамира). Это позволяет v_i позже создавать имитационные доказательства при принуждении.

R-3. После проверки каждого доказательства Шаума-Педерсена, v_i вычисляет

R-4. Для каждого v_i получает от A_j подпись на (U_i,W_i) в качестве подтверждения получения.

R-5. (U_i,W_i) добавляют к списку О избирателей. После окончания периода регистрации каждое полномочное лицо должно подписать список О.

Примечание 1. Когда v_i знает, что конкретное полномочное лицо не является принуждающим лицом и меньше, чем t (число, необходимое для вычисления результата) уполномоченных лиц вступают в сговор для принуждения (хотя v _i может не знать их идентичности), то величина r_i не подвержена принуждению. Это объясняется тем, что v_i может оправдать правильность r_i и _i, солгав принуждающему лицу о величине (U _iJ,V_iJ) и представив поддельное (т.е. имитационное) доказательство Шаума-Педерсена.

Требование того, что v _i знает конкретного честного A_J, можно смягчить, если предположить, что допустимо разоблачение лжи v_i принуждающим лицом. В качестве альтернативного решения, если n>t, то v_i может выбрать J случайно из 1 J n, предполагая, что A_j является честным, и зная, что вероятность уличения во лжи составляет максимально (t-1)/n.

2.2. Инициирование выборов

EI-1. Для каждого и для каждого уполномоченное лицо A_j создает случайно и независимо пару элементов g и ( _ij, _ij). Величины

публично вычисляют. Затем они все публикуются (и подписываются).

EI-2. Возможности выбора в бюллетене g 1 k =| | назначаются с помощью некоторого открытого случайного процесса или посредством процесса совместного использования (величина обозначает голос за кандидата с ).

2.3. Голосование

V-1. v_i выбирает случайное _i1 Z_q и шифрует свой выбор в виде пары Эль Гамаля

(A_i, B_i) = (g ⁱ¹, h ⁱ¹ (i)) (15)

V-2. v_i выбирает случайное _i2 Z_q , вычисляет и шифрует в виде

(C_i, D_i ) = (g ⁱ², h ⁱ²s_i) (16)

V-3. Затем v_i создает неинтерактивные доказательства знания Q_i ^AB и Q_i ^CD для пар (A_i , B_i) и (C_i, D_i) соответственно. Эти доказательства показывают, что пары имеют требуемую форму, и что v_i знает величины s_i и (i).

V-4. v_i передает зашифрованный заполненный бюллетень

E_i = ((A_i, B_i ), (C_i, D_i), Q_i ^AB , Q_i ^CD) (17)

V-5. Хотя и не обязательно, но если используется модель доски объявлений «только для присоединения», то v_i получает подтверждение о приеме E_i .

2.4. Табуляция

В этом разделе предполагается, что назначено подмножество t уполномоченных лиц. Без потери общности можно предположить, что ими являются A₁,...,A _t.

Т-1. Для каждого открыто вычисляются количества

T-2. Уполномоченные лица выполняют проверяемое перемешивание последовательности пар из пар Эль Гамаля что приводит к выдаче набора пар из пар Эль Гамаля

где

Свойства этой смеси состоят в том, что набор расшифрованных пар величин (a_i,b_i) выходной последовательности точно такой же, что и набор расшифрованных пар величин входной последовательности, но в случайно переставленном порядке. Выполнение такого проверяемого перемешивания описано подробно в заявке на патент США № 09/816 869 с названием «Проверяемое, секретное перемешивание зашифрованных данных, таких как зашифрованные данные Эль Гамаля, для защищенных выборов с множеством уполномоченных лиц», поданная 24 марта 2001, и в заявке РСТ № WO02/77929 с названием «Проверяемые секретные перемешивания и их применение для электронного голосования», поданной 25 марта 2002, полное содержание которых включается в данное описание.

Т-3. Пусть

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

Т-4. Для каждого 1 m M открыто вычисляются l пар Эль Гамаля

при

Т-5. Уполномоченные лица совместно расшифровывают все пары и для и Пусть это будут, соответственно, a_m и x _mi.

Т-6. Для каждого добавляют a_m к результату, только и если только

Т-6.1. a_m { ₁,..., _k}

T-6.2. Для некоторых x_mi = 1.

2.5 Табуляция - альтернативный вариант выполнения

В этом разделе предполагается, что назначено подмножество t уполномоченных лиц. Без потери общности можно предположить, что ими являются A₁,...,A_t .

Т2-1. Для каждого открыто вычисляются количества

T2-2. Уполномоченные лица выполняют проверяемое перемешивание последовательности пар Эль Гамаля что приводит к выдаче набора пар Эль Гамаля

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

Т2-3. Для каждого проголосовавшего бюллетеня E_m при с проверенным доказательством правильности открыто вычисляются l пар Эль Гамаля

( _mi, _mi) = (A_mC_{m i},B_mD_{m i}) (24)

Т2-4. Пусть Уполномоченные лица выполняют проверяемое перемешивание последовательности M x l пар из пар Эль Гамаля ((A_m,B_m), ( _mi, _mi)) c получением выходного набора

Т2-5. Уполномоченные лица совместно расшифровывают все пары ( _i, _i), Пусть это будут, соответственно, _i, a_m и x_mi.

Т2-6. Для каждого добавляют a_m к результату, только и если только

Т2-7. a_m { ₁,..., _k)

T2-8. Для некоторых и x_mi = _j.

2.6 Выполнение протокола защищенным от принуждения

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