Обнаружение фальсифицированных избирательных бюллетеней

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

 

Данное изобретение испрашивает приоритет временной заявки США №60/270182, поданной 20 февраля 2001, временной заявки США № (номер реестра патентного ведомства 32462-8006US02), поданной 11 февраля 2002, и является частичным продолжением заявки на патент США №09/534836, поданной 24 марта 2000; заявки на патент США №09/535927, поданной 24 марта 2000; и заявки на патент США №09/816869, поданной 24 марта 2001. Полное содержание этих пяти заявок включается в данное описание.

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

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

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

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

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

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

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

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

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

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

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

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

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

Описание наилучших вариантов осуществления изобретения

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

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

Некоторые типичные криптографические признаки избирательных установочных параметров заключаются в следующем:

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

(а) Шифровальная группа, G может быть Z_p, где р является большой первичной группой или группой эллиптической кривой.

(b) Генератор, g∈G. В случае G=Z_p, g должно генерировать подгруппу <g> из G*, которая имеет большой первичный порядок q. В случае эллиптической кривой предполагается, что <g>=G и q=p.

(c) Открытый ключ выборов, h∈(g).

(d) Схема кодирования решения: разделение <g> на «назвать представителей». То есть <g>=S₀∪S₁∪...S_K, где S_к являются парными несвязанными подмножествами <g>. Для каждого 1≤k≤K любое сообщение m∈S_k представляет голосование за a_k. Остальные сообщения рассматриваются как недействительные. Обычно каждое S_k при 1≤k≤K состоит из одного элемента μ_k, хотя это в принципе не является обязательным. Однако для защиты схемы в целом необходимо, чтобы μ_k генерировались независимо или случайно с использованием некоторого открытого случайного источника или с помощью приемлемой схемы совместного пользования.

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

2. Представление голосования: каждый избиратель ν_i шифрует свой выбор или решение в виде пары ЭльГамаля (X_i,Y_i)=(g^αi,h^αi,m_i), где α_i∈Z_q выбирается произвольно избирателем, и m_i∈S_k, если ν_i; желает выбрать ответ а_k. Эта зашифрованная величина затем передается в центр сбора голосов, обычно с присоединением цифровой подписи, созданной избирателем ν_i.

Если избиратель ν_i вычислял бы эти величины сам, например, с помощью карандаша и бумаги, то этот протокол был бы по существу достаточным для осуществления тайного голосования, универсально проверяемой системы выборов. (В зависимости от способа табуляции была бы необходима некоторая дополнительная информация, такая как подтверждение личности избирателя.) Однако, поскольку на практике избиратель ν_i выполняет лишь выбор с помощью какого-либо интерфейса пользователя, то не имеет смысла ожидать, что он будет следить за действительной величиной переданных битов и будет проверять их на предмет соответствия своему задуманному выбору. Короче говоря, исполнитель голосования может игнорировать замысел и передавать «выбираю μ_j», когда избиратель в действительности хотел передать «выбираю μ_k».

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

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

2. Избиратель и исполнитель голосования должны быть в состоянии выполнять специальный набор стадий, которые позволяют избирателю привязать С исключительно к выбору (или голосу) μ_k, который был принят.

3. Для исполнителя голосования должно быть невозможным вести себя так, что избиратель является обманутым. То есть исполнитель не должен убеждать избирателя, что было принято μ_k, если в действительности было принято μ≠μ_k.

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

В качестве части процесса голосования обычно выполняются следующие стадии.

СС-1. Исполнитель голосования М_i, приводимый в действие избирателем ν_i, создает зашифрованный избирательный бюллетень от имени избирателя ν_i, как и прежде. Обозначим это как (X_i,Y_i)=(g^αi,h^αi,m_i) для некоторой величины m_i∈〈g〉 и α_i∈Z_q.

СС-2. M_i должен также создать доказательство достоверности Р_i, которое является доказательством с нулевым знанием, что m_i∈{μ₁,...,μ_k} (такое доказательство легко создать из основного доказательства Чаум-Педерсона для равенства дискретных логарифмов с использованием технологии, указанной в [CDS94]. Специальный пример можно найти в [CGS97]).

СС-3. Затем М_i передает как Р_i, так и (подписанный) выбор (X_i,Y_i) в центр сбора голосов.

СС-4. Перед признанием зашифрованного избирательного бюллетеня центр сбора голосов сначала проверяет доказательство Р_i. Если верификация Р_i потерпит неудачу, то искажение уже обнаружено, и центр сбора голосов может либо не выдать цепочку подтверждения или выдать некоторую случайную цепочку по умолчанию.

Сс-5. Если верификация Р_i прошла удачно, то центр сбора голосов вычисляет величины W_i и U_i в виде

,

где K_i∈G и β_i∈Z_q обычно генерируются произвольно и независимо (от избирателя к избирателю).

СС-6. Затем центр сбора голосов возвращает (W_i,U_i) к М_i.

СС-7. Исполнитель М_i вычисляет

и отображает эту цепочку (или более вероятно ее хеш-функцию Н(С_i)) для избирателя ν_i.

Избиратель должен знать, какую следует искать цепочку подтверждения. Это можно выполнять двумя разными путями. Наиболее прямым путем является получение избирателем ν_i величин К_i и β_i из центра сбора голосов. Это осуществимо, требует передачи очень небольшого количества данных и может подходить для некоторых случаев осуществления. Однако в других ситуациях это может быть непривлекательным подходом, поскольку в этом случае необходимо вычислять С_i или (Н(С_i)). Поскольку запрос исполнителя М_i на выполнение этих вычислений разрушает защиту схемы, то избиратель ν_i должен иметь доступ к дополнительным вычислительным устройствам, а также доступ к независимому каналу связи.

В качестве альтернативного решения центр сбора голосов вычисляет все возможные цепочки подтверждения для ν_i и передает результаты в словарь подтверждений избирателя ν_i через независимый канал. Обычно словарь подтверждений избирателя ν_i будет состоять из следующей таблицы в любом разумном формате:

Ответ	Цепочка подтверждения
α1	Н(Сi1)
α2	H(Ci2)
· ·	· ·
αк	H(CiK)

где Н является открытой (опубликованной) хеш-функцией выборов (возможно, функцией идентичности) и С_ij=К_iμ_j ^βi.

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

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

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

Некоторые протоколы электронных выборов содержат дополнительные признаки, такие как:

- Информация сертификации избирателя и администрации (открытый ключ) для аутентификации и контроля;

- Параметры стиля страницы избирательного бюллетеня;

- Стандарты кодирования данных;

- Протокол и параметры табуляции.

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

В этом примере предполагается, что электронный протокол, который кодирует ответы избирателя, является единичной парой ЭльГамаля. Однако на основе последующего описания можно легко составить обмен закрытого подтверждения величин для других протоколов выборов с использованием шифрования ЭльГамаля для избирательных бюллетеней. Например, некоторые варианты выполнения средства включают гомоморфный протокол выборов, описанный в заявке на патент США №09/535927. В этом протоколе ответ избирателя представлен несколькими парами ЭльГамаля. Словарь подтверждений, используемый в этом примере, легко модифицировать для отображения сочленения соответствующих цепочек подтверждения или для отображения хеш-функции их последовательности.

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

Криптографические параметры

- арифметика групп: целочисленная мультипликативная модульная арифметика;

первичный модуль: р = 47;

- модуль подгруппы: q = 23;

- генератор: g = 2;

- открытый ключ: h = gs, где s является закрытым. Для данного примера принимается, что h = gl2 = 7.

Избирательный бюллетень

- один вопрос

- текст 1 вопроса: Каким должен быть цвет нашего флага (можно выбрать максимально 1 цвет);

- число ответов/выбора: 4

* текст 1 ответа: синий

* текст 2 ответа: зеленый

* текст 3 ответа: красный

* текст 4 ответа: я воздерживаюсь.

Схема кодирования решений

Выбор	Величина ответа
Синий	9(μ1)
Зеленый	21(μ2)
Красный	36(μ3)
Я воздерживаюсь	17(μ4)

В некоторый момент времени перед выдачей подтверждения и перед распределением словарей подтверждения центр сбора голосов (или агентство) генерирует для каждого избирателя V_i случайные, независимые β_i и К_i. Если словарь подтверждений должен рассылаться после приема голоса, то эти параметры можно генерировать для каждого избирателя сразу после признания каждого проголосованного избирательного бюллетеня. В качестве альтернативного решения их можно генерировать заранее перед выборами. В данном примере агентство по сбору избирательных бюллетеней имеет доступ к этим параметрам как непосредственно после признания проголосованного избирательного бюллетеня, так и непосредственно перед передачей соответствующему избирателю словаря подтверждений.

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

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

Шифрование выбора

Пара целых чисел (X,Z), где 0≤X,Z<47, указывающих (в зашифрованном виде) выбор, или ответ, избирателя. Например, для того чтобы ответ был действительным, он должен быть дан в виде (X,Y)=(2^α,7^α _μ), где 0≤α<23 и μ∈{9,21,36,17}.

Доказательство достоверности

Доказательство достоверности должно показывать, что (X,Y) имеет вид, описанный на стадии шифрования выбора (в данном примере, необходимо видеть, что это доказательство состоит из 15 модульных целых чисел, расположенных в специальной последовательности).

В данном примере предполагается, что избиратель V желает отдать голос за «зеленый».

1. Избиратель генерирует по случайному закону α∈Z₂₃. В данном примере α = 5. Поскольку кодированием «зеленого» является 21, то выбор избирателя V вычисляется как

Эта пара является тем, что должно быть передано в центр сбора голосов.

Возможной опасностью является то, что компьютер избирателя V может попытаться изменить эти величины.

Избиратель V (или точнее компьютер избирателя V) должен доказать, что соблюдается одно из следующих условий

1. (X,Y)=(2^α,7^αx9), то есть выбор (отданный голос) означает «синий»;

2. (X,Y)=(2^α,7^αx21), то есть выбор (отданный голос) означает «зеленый»;

3. (X,Y)=(2^α,7^αlx36), то есть выбор (отданный голос) означает «красный»;

4. (X,Y)=(2^α,7^αx21), то есть выбор (отданный голос) означает «я воздерживаюсь»

для некоторой неуказанной величины α без раскрытия ее действительного значения.

Для осуществления этого имеется множество стандартных способов. Смотри, например, R. Cramer, I. Damgard, В. Schoenmakers «Доказательства частичного знания и упрощенная конструкция протоколов сокрытия свидетеля», Advances in Criptology - CRYPTO'94, Lecture Notes in Computer Science, страницы 174-187, издательство Springer-Verlag, Берлин, 1994. Технология закрытого подтверждения величин, используемая средством, работает также хорошо с любым способом, который соответствует абстрактным критериям предыдущего параграфа. Хотя ниже приведены детали одного такого способа доказательства достоверности, в вариантах выполнения средства можно использовать доказательства достоверности другого типа.

Состав доказательства достоверности

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

1. V устанавливает α2=α=5.

2. V генерирует ω₂∈_RZ₂₃,r₁,r₃,r₄∈_RZ₂₃,S₁,S₃,S₄∈_RZ₂₃, все по случайному закону и независимо. Для данного примера принимается

3. V вычисляет соответствующие величины

4. V использует опубликованную хеш-функцию для вычисления c∈Z₂₃ как

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

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

5. V вычисляет интерполяционный многочлен Р(х) степени 4-1=3.

Заданными свойствами Р являются

P(x)=Σ³ _j=0 Z_j X_j вычисляется с использованием стандартной теории многочленной интерполяции с получением:

или

6. V вычисляет величины

r₂=ω₂+α₂s₂=4+5х5=6

7. Доказательство достоверности V состоит из 12 чисел

и трех чисел

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

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

Как указывалось выше, специфичные случайные параметры для избирателя V (β и К) являются доступными в центре сбора голосов. В данном примере это

После получения проголосованного избирательного бюллетеня избирателя (не обязательно подписанного) в центре сбора голосов выполняются следующие стадии:

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

2. Если проверка подписи на стадии 1 верифицирована как правильная, то центр сбора голосов проверяет затем доказательство достоверности. Для частного типа доказательства достоверности, который выбран для использования в данном примере, это состоит в следующем:

(a) Используется хеш-функция Н для вычисления величины

P(0)=z₀

(Напоминаем, что остальные коэффициенты Р, z₁, z₂, z₃ являются частью переданного проголосованного (не обязательно подписанного) избирательного бюллетеня избирателя V).

(b) Для каждого 1≤j≤4 оцениваются обе стороны уравнений

(В данном случае, как указывалось выше, μ_j берется из схемы кодирования решений). Если уравнение не сходится в любом из случаев, то верификация не состоится. Этот избирательный бюллетень не признается, и к избирателю V обратно передается произвольная цепочка (указатель) отказа.

3. При успешно выполненной предыдущей стадии ответная цепочка (W, U) вычисляется как

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

4. Система избирателя V вычисляет

и отображает эту цепочку избирателю (в качестве альтернативного решения протокол может определять, что открытую хеш-функцию следует вычислять из С. В данном примере отображается сама С). Если компьютер избирателя V попытается передать выбор, отличающийся от «зеленого», то вычисленная выше величина С будет другой. Более того, правильная величина С не может быть вычислена из неправильной величины без решения проблемы Диффи-Хеллмана (для небольших величин р и q, которые выбраны в данном примере, это возможно. Однако для реальных криптографических параметров, компьютер избирателя V не способен выполнить это). Таким образом, если компьютер избирателя V передал зашифрованный избирательный бюллетень, который не соответствует выбору избирателя V, то имеются лишь две возможности в тот момент времени, когда от него ожидается отображение подтверждения. Он может отобразить что-нибудь, или же он может ничего не отобразить. В случае, когда не отображается ничего, то избиратель V может воспринимать это как указание на то, что избирательный бюллетень фальсифицирован. В случае, когда отображается что-нибудь, то это наверное будет неправильным, и избиратель V снова может сделать вывод, что избирательный бюллетень был сфальсифицирован.

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

Словарь подтверждений для каждого избирателя вычисляет центр сбора голосов, поскольку, как указывалось выше, он является органом, который располагает знанием специфичной для избирателя величины α и К. В случае рассматриваемого избирателя V словарь вычисляется в виде

Выбор	Цепочка подтверждения
Синий	Cl=Kμ1 β=37x918=16
Зеленый	C2=Kμ2 β=37х2118=18
Красный	C3=Kμ3 β=37х3618=36
Я воздерживаюсь	C4=Kμ4 β=37xl718=8

Описание уровня защиты, обеспечиваемого средством при использовании схемы закрытого подтверждения величин, приводится ниже: предположим, что А является противником исполнителя голосования, и ∈₀ является верхним пределом вероятности того, что А способен подделать доказательство достоверности для любого заданного μ_i,...,μ_k (мы знаем, что ∈₀ является пренебрежительно малым).

Теорема 1. Предположим, что схема закрытого подтверждения величин выполняется с Н=Id. При этом 1≤k₁≠k₂≤K. Предположим, что для некоторого ∈>0 можно с вероятностью ∈ передать b_i=(g^αih^αiμ_k1) и отобразить С_ik2=K_iμ_k2 ^βi, где вероятность принята равномерной по всей комбинации величин для μ₁,...,μ_kg,h,β_i и К_i. Тогда А может решить случайный пример а проблемы Диффи-Хеллмана с вероятность ∈ и дополнительной работой О(К).

Доказательство. Предположим, что А имеет X,Y,Z∈_R<g>. А может имитировать выборы и обмен закрытого подтверждения величин посредством выбора независимо по случайному закону C_ik1<g> и μ_k∈〈g〉 для всех устанавливая h=X,h^βi=Y и μ_k2=μ_k1Z. Полученное распределение параметров выборов и C_ik1 очевидно является идентичными с распределением, которое получается в результате действительных выборов. С вероятностью ∈ противник А может отобразить С_ik2 и может тем самым вычислить

Таким образом, log_xC=β_ilog_xYlog_xZ и С является решением примера проблемы Диффи-Хеллмана, представленного тройной величиной (X,Y,Z).

Следствие 1. Предположим снова, что схема закрытого подтверждения величин выполняется с Н=Id. При этом 1≤k₁≠k₂≤K. Предположим, что для некоторого ∈₁>0 противник А может с вероятностью ∈₁ выбрать k₁≠k₂, передать b_i=(g^αih^αiμ_k1) и отобразить C_ik2=K_iμ_k2 ^βi, где вероятность принята равномерной по всей комбинации величин для μ₁,...,μ_K,g,h,β_i и К_i. Тогда А может решить случайный пример а проблемы Диффи-Хеллмана с вероятность ∈₁/(K-l) и дополнительной работой 0(К).

Доказательство: необходимо следовать доказательству теоремы 1, но относительно проблемы нахождения решения для по меньшей мере одной проблемы К-1 Диффи-Хеллмана.

Следствие 2. Предположим, что является верхней границей вероятности того, что А может решить случайный пример проблемы Диффи-Хеллмана. Тогда в случае H=Id верхней границей вероятности того, что А может передать выбор а, который отличается от выбора избирателя, и тем не менее отобразить правильную цепочку подтверждения, является ∈₀+(K-l)∈_DH.

Если хеш-функция Н является не тривиальной, то нельзя надеяться на сравнение возможности решения проблемы Диффи-Хеллмана без значительного специального знания свойств Н. Вместо того чтобы оценивать защиту схемы для специально выбранных Н, предположим лишь, что Н имеет пренебрежительно малую вероятность совпадения, и вместо этого оценим защищенность проблемы Диффи-Хеллмана для принятия решений. Вариантом этой проблемы может служить следующее. А имеет последовательность набора чисел (X_n,Y_n,Z_n,C_n), где X_n,Y_n,Z_n генерированы независимо по случайному закону. С вероятностью 1/2 С_n является решением примера (X_n,Y_n,Z_n) проблемы Диффи-Хеллмана, и с вероятностью 1-1/2=1/2 С_n генерирована по случайному закону и независимо. Говорится, что А имеет преимущество ∈-DDH, если А может с вероятностью 1/2+е получить ответ на вопрос logx_nC_n=logx_nZ_nlogx_nZ_n?

Теорема 1 и следствия 1 и 2 очевидно имеют аналоги в случае H≠Id (только при предположении, что Р имеет пренебрежительно малую вероятность совпадения). Оба утверждения и доказательства выполняются с небольшими вариациями, поэтому можно подвести итог следующим образом:

Следствие 3. Предположим, что является верхней границей преимущества DDH противника А. Тогда, если Н является любой хеш-функцией с пренебрежительно малой вероятностью совпадения, то верхней границей вероятности того, что А может передать выбор а, который отличается от выбора избирателя, и тем не менее отобразить правильную цепочку подтверждения, является ∈₀+(К-1)∈_DDH.

Схема закрытого подтверждения величин не может обеспечить какой-либо защиты, если противник А контролирует также центр сбора голосов. Если это так, то А имеет доступ к К_i и β_i и таким образом может легко отображать любую правильную цепочку подтверждения по своему выбору. Это представляется маловероятным, поскольку центр сбора голосов будет неопровержимо изобличен в случае раскрытия таких действий. Тем не менее, в случае, когда недопустимо доверять центру сбора голосов в этом отношении, ответственность за подтверждение можно распределять между многими выбранными администрациями.

Для распределения ответственности за подтверждение каждая администрация A_j при 1≤j≤J, генерирует (для избирателя ν_i) независимо и по случайному закону К_ij и β_ij. Администрации могут их комбинировать двумя общими способами.

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

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

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

Всегда желательно сократить размер данных, которые необходимо передавать избирателю через независимый канал. Как было описано в части 3, словарь подтверждений уже является небольшим по стандартам современной технологии связи, однако может быть предпочтительным с точки зрения стоимости передавать еще меньше данных. Как указывалось выше, один подход может заключаться в передаче закрытых К_i и β_i непосредственно избирателю, однако это имеет тот недостаток, что на избирателя перекладывается слишком большая вычислительная нагрузка, которую он не может выполнить в уме или на бумаге. Следующая вариация схемы закрытого подтверждения величин обеспечивает достижение обеих целей - меньше данных для передачи через независимый канал связи и меньше устного счета для избирателя. Это осуществляется за счет того, что повышается вероятность обмана избирателя противником, однако это может быть приемлемым с точки зрения всех выборов. Даже если вероятность того, что противник останется незамеченным, составляет, например, 1/2, при изменении значительной части голосов, вероятность того, что это будет обнаружено статистически значительной частью избирателей, очень высока. Как указывалось выше во вступительной части, возможны исправительные меры.

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

Как и прежде, выполняются стадии, указанные в части 3.1. Дополнительно к этому центр сбора голосов передает исполнителю М_i рандомизированный словарь D_i. Центр сбора голосов осуществляет это следующим образом:

RD-1. Как и прежде, вычисляются К (специфичные для избирателей) цепочек подтверждения

RD-2. Дополнительно к этому генерируют L дополнительных цепочек в виде

где e₁,...,e_L генерируются по случайному закону в Z_q.

RD-3. Генерируется случайная перестановка σ_i∈Σ_к+L.

RD-4. С устанавливает Q_ij=S_iσi(j) для 1≤j≤K+L и устанавливает D_i в качестве последовательности цепочек (Q_i1,...Q_i(K+L)).

Если С передает некоторое «читаемое человеком» представление σ_i к избирателю ν_i через независимый канал, то избиратель ν_i может теперь проверить свое голосование посредством нахождения цепочки подтверждения с правильным индексом. Обозначим эту схему как закрытое подтверждение величин 0 (SCVO).

Относительно уровня защиты SVCO рассмотрим следующую форму проблемы Диффи-Хеллмана по принятию решений: А имеет последовательность набора чисел (X_n,Y_n,Z_n,C_n,D_n), где X_n,Y_n, Z_n генерированы независимо по случайному закону. Предположим, что R_n генерировано по случайному закону, и O_n является решением уравнения logX_nO_n=log_XnY_nlog_XnZn. С вероятностью 1/2 (C_n,D_n)=(O_n,R_n) и с вероятностью 1-1/2=1/2(C_n,D_n)=(Rn,On). Утверждается, что А имеет преимущество ∈-DDHP, если А может с вероятностью 1/2+∈ получить ответ на вопрос logx_nC_n=logx_nZ_nlogx_nZ_n? To есть противник А должен ответить на тот же вопрос, что и в первоначальной версии проблемы, однако проблема может быть более простой, поскольку доступна большая информация.

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

Доказательство: так же как в доказательстве теоремы 1, противник А может имитировать выборы и обмен SCVO. Однако в данном случае А должен также имитировать список цепочек подтверждения, которые были недоступны в схеме закрытого подтверждения величин (SVC). Для заданных k₁,k₂ А может выбрать C_ik1∈〈g〉 по случайному закону, и для всех k₁≠k₂ выбрать Θ_k∈Z_q независимо по случайному закону. Затем А устанавливает μ_k=X^Θk. Для k₁≠k₂,k₂ противник А устанавливает C_ik=C_iklY^Θk-Θk1. A устанавливает μ_k2=μ_k1Z и генерирует L дополнительных случайных μ_l и l-1 дополнительных С_il по случайному закону. Наконец, А устанавливает C_ik2=C_ik1 и последний остающийся С_il=C_iklD_n. Как и прежде, нахождение правильной цепочки подтверждения является эквивалентным принятию решения, какая из величин C_n,D_n является правильным решением проблемы Диффи-Хеллмана. Получение среднего по всем перестановкам с равномерной вероятностью дает результат.

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

1. Дополнительно к открытому ключу h центр сбора голосов публикует другой открытый ключ в виде h=h^d, где d∈Z_q является секретом, известным лишь центру сбора голосов.

2. Исполнитель М_i передает зашифрованный избирательный бюллетень от имени ν_i, как и прежде, однако избыточно зашифрованный с помощью как h, так и h. Запишем второе шифрование как

где α_i выбирается независимо от α_i.

3. M_i также создает простое доказательство достоверности (по существу единичное доказательство Чаум-Педерсена), что две величины являются шифровками одной и той же величины.

4. Если доказательство достоверности не было признано центром сбора голосов, то фальсификация обнаружена, как и прежде.

5. Центр сбора голосов выбирает по случайному закону K_i∈〈g〉; β_i∈Z_q и вычисляет

6. Центр сбора голосов возвращает h^βi и V_i к M_i.

7. М_i вычисляет S_i=K_im^(d+l)βi с помощью уравнения

и отображает эту величину на дисплее (или Н(S_i)) для избирателя ν_i.

8. Избиратель, как и прежде, запрашивает словарь подтверждений и проверяет по нему отображенную величину.

В случае обнаружения фальсификации корректировочные действия принимаются как прежде.

В приведенном выше описании средство использует единственную d (и поэтому единственную ) для всех избирателей и публикует эту величину заранее перед выборами.

В качестве альтернативного решения центр сбора голосов (или распределенный набор «администрации подтверждения») выдает независимую, случайную d_i (и поэтому ) для каждого избирателя ν_i. Величина d_i всегда держится в секрете, а величина сообщается избирателю ν_i.

В одном варианте выполнения средство сообщает величину h_i избирателю v_i следующим образом:

А-1: избиратель ν_i вступает в контакт с центром сбора голосов и аутентифицирует себя;

А-2: если аутентификация прошла успешно, то центр сбора голосов:

1. Генерирует по случайному закону d_i.

2. Вычисляет

3. Передает избирателю ν_i.

А-3: затем избиратель v_i обрабатывает, как указывалось выше, вместо h.

В другом варианте выполнения средство сообщает величину избирателю ν_i следующим образом:

В-1: избиратель ν_i вступает в контакт с центром сбора голосов (и не обязательно аутентифицирует себя);

В-2: избиратель ν_i делает выбор m_i в избирательном бюллетене и возвращает зашифрованный избирательный бюллетень (g^αi,h^αim_i).

В-3: центр сбора голосов в этот момент времени:

1. Генерирует по случайному закону d_i.

2. Вычисляет

3. Передает избирателю ν_i.

В-4: затем избиратель ν_i:

1. Генерирует вторую шифровку m_i в виде (g^αi, )

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

3. Передает как вторую шифровку, так и доказательство достоверности в центр сбора голосов.

В-5: остаток процесса выполняется, как указывалось выше.

На фиг.1-3 показаны определенные аспекты средства. На фиг.1 показана обобщенная блок-схема типичных условий, в которых работает средство. На фиг.1 показано несколько компьютерных систем 110 избирателей, каждую из которых избиратель может использовать для передачи избирательного бюллетеня и верификации его не искаженного приема. Каждая из компьютерных систем избирателей соединена через Интернет 120 с компьютерной системой 150 центра сбора голосов. Для специалистов в данной области техники понятно, что компьютерные системы избирателей могут быть соединены с компьютерной системой центра сбора голосов с помощью систем, отличных от Интернета. Средство передает избирательные бюллетени из компьютерных систем избирателей в компьютерную систему центра сбора голосов, которая возвращает зашифрованное подтверждение голосования. В каждой компьютерной системе избирателей средство использует это зашифрованное подтверждение голосования для определения, был ли сфальсифицирован переданный избирательный бюллетень. Хотя предпочтительные варианты выполнения описаны применительно к этим условиям, для специалистов в данной области техники понятно, что средство можно реализовать в различных других условиях, включая единую, монолитную компьютерную систему, а также различные другие комбинации компьютерных систем или аналогичных устройств, соединенных различным образом.

На фиг.2 показана блок-схема, изображающая компоненты, обычно содержащиеся по меньшей мере в некоторых компьютерных системах и других устройствах, с которыми работает средство, такие как компьютерные системы 110 и 130. Эти компьютерные системы и устройства 200 могут включать один или более центральных процессоров 201 (СРИ) для выполнения компьютерных программ; компьютерную память 202 для хранения программ и данных во время использования; постоянное запоминающее устройство 203, такое как жесткий дисковод для постоянного хранения программ и данных; привод 204 для считываемого компьютером носителя информации, такой как привод CD-ROM, для считывания программ и данных, хранящихся в считываемом компьютером носителе информации; и сетевое соединение 205 для соединения компьютерной системы с другими компьютерными системами, например, через Интернет. Хотя компьютерные системы, выполненные, как указывалось выше, предпочтительно используются для поддержки работы средства, для специалистов в данной области техники понятно, что средство можно реализовать с использованием устройств различных типов и конфигураций, и имеющих различные компоненты.

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

На стадии 301 средство обнаружения кодирует в компьютерной системе избирателя выбор в избирательном бюллетене, сделанный избирателем для формирования избирательного бюллетеня. На стадии 302 средство обнаружения шифрует этот избирательный бюллетень. В некоторых вариантах выполнения зашифрованный избирательный бюллетень является парой ЭльГамаля, генерированной с использованием открытого ключа и секрета, удерживаемого в компьютерной системе избирателя. На стадии 303 средство обнаружения, не обязательно, подписывает избирательный бюллетень с помощью личного ключа, принадлежащего избирателю. На стадии 304 средство обнаружения создает доказательство достоверности, которое показывает, что зашифрованный избирательный бюллетень является шифровкой избирательного бюллетеня, в котором правильно выполнен выбор. На стадии 305 средство обнаружения передает зашифрованный, подписанный избирательный бюллетень и доказательство достоверности в компьютерную систему центра сбора голосов.

На стадии 321 средство обнаружения принимает эту передачу в компьютерной системе центра сбора голосов. На стадии 322 средство обнаружения верифицирует принятое доказательство достоверности. На стадии 323, если верификация доказательства достоверности прошло успешно, то средство обнаружения переходит на стадию 324, в противном случае средство обнаружения не переходит на стадию 324. На стадии 324 средство обнаружения генерирует зашифрованное подтверждение зашифрованного избирательного бюллетеня. Средство обнаружения делает это без расшифровки избирательного бюллетеня, что обычно невозможно в компьютерной системе центра сбора голосов, где нет секрета, используемого для шифрования избирательного бюллетеня. На стадии 325 средство обнаружения передает зашифрованное подтверждение в компьютерную систему избирателя.

На стадии 341 средство обнаружения принимает зашифрованное подтверждение в компьютерной системе избирателя. На стадии 342 средство обнаружения использует секрет, удерживаемый в компьютерной системе избирателя, для расшифровки зашифрованного подтверждения голосования. На стадии 343 средство обнаружения отображает расшифрованное подтверждение голосования для пользователя. На стадии 344, если отображенное подтверждение голосования переведено в выбор на избирательном бюллетене, сделанный избирателем, с помощью словаря подтверждений, находящегося в собственности избирателя, средство обнаружения переходит на стадию 345, в противном случае средство обнаружения переходит на стадию 346. На стадии 345 средство обнаружения определяет, что избирательный бюллетень избирателя не был фальсифицирован, в то время как на стадии 346 средство обнаружения определяет, что избирательный бюллетень был фальсифицирован. В этом случае варианты выполнения средства обнаружения поддерживают избирателя в отзыве и повторной передаче избирательного бюллетеня.

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

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

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

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

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

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

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

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

8. Способ по п.6, отличающийся тем, что шифрование величины избирательного бюллетеня содержит генерирование пары ЭльГамаля, представляющей величину избирательного бюллетеня.

9. Способ по п.6, отличающийся тем, что пару ЭльГамаля генерируют посредством оценки выражений g^α и h^αm, где р является первичным; g∈Z_p, которое имеет первичный множительный порядок q, со свойством, что q является кратным 1, деленной на р-1; h∈〈g〉; a∈Z_q выбраны случайно в избирательном узле; m является величиной избирательного бюллетеня.

10. Способ по п.9, отличающийся тем, что пару ЭльГамаля генерируют посредством оценки выражений αg и αh+m, где g и h являются оба элементами группы эллиптической кривой ξ первичного порядка q и α∈Z_p выбрано случайно в избирательном узле; m является величиной избирательного бюллетеня.

11. Способ по п.6, отличающийся тем, что применение секрета, хранящегося в избирательном узле, для определения, отражает ли зашифрованное подтверждение голосования принятую величину избирательного бюллетеня, выбранную избирателем, в точке сбора голосов, содержит определение величины избирательного бюллетеня, соответствующей зашифрованной величине избирательного бюллетеня, принятой в точке сбора голосов, посредством оценки выражения W₁/U₁ ^α1, где α₁ является секретом, хранящимся в избирательном узле, и i W₁ и U₁ вместе содержат зашифрованное подтверждение голосования; сравнение определенной величины избирательного бюллетеня с величиной избирательного бюллетеня, выбранной избирателем.

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

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

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

15. Компьютерные устройства памяти по п.14, отличающиеся тем, что зашифрованный выбор в избирательном бюллетене является парой ЭльГамаля.

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

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

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

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

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

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

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

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

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

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

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

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

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

29. Способ по п.27, отличающийся тем, что дополнительно содержит

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

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

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

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

определения произведения вторых величин, содержащихся в первом и втором сообщениях подтверждения

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

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

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

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

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

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

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

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

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

41. Способ по п.40, отличающийся тем, что первый зашифрованный компонент избирательного бюллетеня генерируют посредством оценки g^α и h^αm, где р является первичным; g∈Z_p, которое имеет первичный множительный порядок q, со свойством, что q является кратным 1, деленной на р-1; h∈〈g〉; a∈Z_q выбраны случайно в избирательном узле; m является выбором в избирательном бюллетене, и в котором второй зашифрованный компонент избирательного бюллетеня генерируют посредством оценки выражений g^α и h^αm, где h∈〈g〉; a∈Z_q выбраны случайно и независимо в избирательном узле; m является выбором в избирательном бюллетене.

42. Способ по п.41, отличающийся тем, что дополнительно содержит генерирование подтверждения голосования посредством оценки выражения V_i=K_ih^{(βi(αi+αi)}m^(d+1)βI,

где р является первичным; g∈Zp, которое имеет первичный множительный порядок q со свойством, что q является кратным 1, деленной на р-1; h∈〈g〉; h∈ является h, возведенному в степень d, которое хранится как секрет; α∈Z_q и α∈Z_q выбраны случайно в избирательном узле; Ki∈〈g〉; β_i∈Z_q; m является выбором в избирательном бюллетене,

и посредством оценки выражения h^βI,

и в котором эти два оцененных выражения передают в исполнительную компьютерную систему в качестве подтверждения голосования.

43. Способ по п.42, отличающийся тем, что подтверждение голосования расшифровывают посредством оценки

V_i/((h^βi)^(αi+αi)),

где р является первичным; g∈Z_p, которое имеет первичный множительный порядок q, со свойством, что q является кратным 1, деленной на р-1; h∈〈g〉; h∈ является h, возведенным в степень d, которое хранится как секрет; a α∈Z_q и α∈Z_q выбраны случайно в избирательном узле; Ki∈〈g〉; β_i∈Z_q и V_i принимают как часть подтверждения голосования.

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

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

доказательства, и

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

Приоритеты:

20.02.2001 - по пп.1-26, 40-45;

11.02.2002 - по пп.27-39.