Нефальсифицируемый референдум

[ewert]

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

[epros]

Trotil писал(а):

Необходимые сведения:

Затемнение сообщения в "подписи вслепую": наложение на сообщение $M$ случайного вектора $k$: $M'=B(M,k)$
Затем сообщение $M'$ подписывается $(S'=S(M'))$ и с подписи затемненного документа вычисляется подпись исходного документа: $S=U(S',k)$. Получается корректная пара $(M,S)$. Подпись вслепую можно реализовать, например, с помощью RSA.

Trotil писал(а):

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

Может я туплю, но:
1. Я не понял алгоритма $S=U(S',k)$, т.е. как избиратель из подписи избиркома на $M'$ получит подпись избиркома на $M$?
2. Я не понял, что помешает избиркому сохранить пару из $M'$ и идентификатора избирателя, и как только будет анонимно получена пара из $M$ и $k$ проверить, какому избирателю они принадлежат?

Trotil писал(а):

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

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

Т.е., правильно ли я понимаю, что тайность данного способа голосования обеспечивается только тем, что первоначальные данные с выбором избирателя ("затемнённые") нигде не сохраняются?

[MaximKat]

epros в сообщении #150392 писал(а):

1. Я не понял алгоритма $S=U(S',k)$, т.е. как избиратель из подписи избиркома на $M'$ получит подпись избиркома на $M$?

алгоритмы подписывания и затемнения такие, что это возможно сделать

epros в сообщении #150392 писал(а):

2. Я не понял, что помешает избиркому сохранить пару из $M'$ и идентификатора избирателя, и как только будет анонимно получена пара из $M$ и $k$ проверить, какому избирателю они принадлежат?

на 4 шаге передается только $M$, без $k$

epros в сообщении #150392 писал(а):

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

они и так не учитываются

epros в сообщении #150392 писал(а):

Т.е., правильно ли я понимаю, что тайность данного способа голосования обеспечивается только тем, что первоначальные данные с выбором избирателя ("затемнённые") нигде не сохраняются?

эти данные бесполезны для всех, кроме самого избирателя, т.к. остальные не могут их "растемнить"

Добавлено спустя 1 минуту 29 секунд:

PAV в сообщении #150213 писал(а):

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

Еще можно послать бессмысленное сообщение, вместо голоса. Будет аналог неприличной надписи, вместо галочки

Добавлено спустя 1 минуту 42 секунды:

Кстати в данном протоколе требование 6 ("Все знают, кто участвовал в голосовании, а кто нет.") все равно не реализовано

[epros]

MaximKat писал(а):

epros в сообщении #150392 писал(а):

1. Я не понял алгоритма $S=U(S',k)$, т.е. как избиратель из подписи избиркома на $M'$ получит подпись избиркома на $M$?

алгоритмы подписывания и затемнения такие, что это возможно сделать

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

MaximKat писал(а):

на 4 шаге передается только $M$, без $k$

Это противоречит написанному:

Trotil писал(а):

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

Или речь идёт о другом случайном числе? Зачем оно тогда нужно? Просто, чтобы убедиться, что это не копия выбора какого-то другого избирателя?

MaximKat писал(а):

epros в сообщении #150392 писал(а):

Т.е., правильно ли я понимаю, что тайность данного способа голосования обеспечивается только тем, что первоначальные данные с выбором избирателя ("затемнённые") нигде не сохраняются?

эти данные бесполезны для всех, кроме самого избирателя, т.к. остальные не могут их "растемнить"

Растемнять их не нужно. Достаточно посмотреть, кому принадлежит подпись.

[MaximKat]

epros в сообщении #150441 писал(а):

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

Это не ко мне. В специфике конкретных алгоритмов не разбираюсь

epros в сообщении #150441 писал(а):

Или речь идёт о другом случайном числе? Зачем оно тогда нужно? Просто, чтобы убедиться, что это не копия выбора какого-то другого избирателя?

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

epros в сообщении #150441 писал(а):

Растемнять их не нужно. Достаточно посмотреть, кому принадлежит подпись

ну и что? подпись есть, а голос то закодирован

[AV_77]

epros писал(а):

MaximKat писал(а):

epros в сообщении #150392 писал(а):

1. Я не понял алгоритма $S=U(S',k)$, т.е. как избиратель из подписи избиркома на $M'$ получит подпись избиркома на $M$?

алгоритмы подписывания и затемнения такие, что это возможно сделать

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

Это есть в книге Б. Шнайера "Прикладная криптография". Там кроме протоколов тайного голосования есть и примеры их реализации.
Один из вариантов с RSA.

Избирком имеет закрытый ключ $(e, n)$, используемый для подписания сообщений, и открытый ключ $(d, n)$, используемый для проверки подписи. Открытый ключ публикуется и есть у всех избирателей. Если избиратель хочет подписать бюллетень $M$, то он случайным образом выбирает число $a$ так, что $(a, n) = 1$ и отправляет в избирком сообщение $A \equiv M a^d \pmod{n}$ вместе со своим именем. Избирком подписывает сообщение $A$ и отправляет избирателю сообщение $B \equiv A^e \equiv M^e a \pmod{n}$. После этого, избиратель вычисляет $M^e \equiv B a^{-1} \pmod{n}$ и отправляет подписанный бюллетень в избирком.

[epros]

MaximKat писал(а):

epros в сообщении #150441 писал(а):

Или речь идёт о другом случайном числе? Зачем оно тогда нужно? Просто, чтобы убедиться, что это не копия выбора какого-то другого избирателя?

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

Хорошо, тогда ещё вопрос: А почему бы избирателю, который получил подпись избиркома на своём выборе, не нагенерировать пятьдесят штук таких случайных чисел и не отправить их в паре со своим выбором как бы от разных избирателей?

[Trotil]

epros писал(а):

Хорошо, тогда ещё вопрос: А почему бы избирателю, который получил подпись избиркома на своём выборе, не нагенерировать пятьдесят штук таких случайных чисел и не отправить их в паре со своим выбором как бы от разных избирателей?

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

[MaximKat]

epros в сообщении #150679 писал(а):

Хорошо, тогда ещё вопрос: А почему бы избирателю, который получил подпись избиркома на своём выборе, не нагенерировать пятьдесят штук таких случайных чисел и не отправить их в паре со своим выбором как бы от разных избирателей?

потому что это число входит в сообщение, которое подписал избирком
изменить число - подпись будет недействительна

[epros]

Наверное я всё-таки туплю...

Trotil писал(а):

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

Как я понял, вторая посылка в избирком уходит анонимно (п. 4), т.е. уже без личной подписи избирателя.

MaximKat писал(а):

потому что это число входит в сообщение, которое подписал избирком
изменить число - подпись будет недействительна

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

Тогда вопрос заключается в том, что помешает избиркому идентифицировать избирателя по этому числу (избирком ведь знает для кого он его сгенерировал)?

AV_77, написанное Вами более-менее понятно. Только опять же возникает вопрос, что помешает избирателю на последнем шаге отправить в избирком 50 копий вычисленного $M^e$ якобы от разных избирателей (ведь эта посылка делается анонимно)?

[MaximKat]

epros в сообщении #150857 писал(а):

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

это другое число, но тоже сгенерировано избирателем и входит в сообщение, вместе с голосом, с самого начала
т.е. само сообщение состоит из голоса и случайного числа

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

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

[AV_77]

epros писал(а):

AV_77, написанное Вами более-менее понятно. Только опять же возникает вопрос, что помешает избирателю на последнем шаге отправить в избирком 50 копий вычисленного $M^e$ якобы от разных избирателей (ведь эта посылка делается анонимно)?

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

1) Каждый избиратель формирует, например, 100 бюллетеней за каждого кандидата $(M_{i1}, M_{i2})$, $i = 1, \ldots, 100$. После этого он формирует 100 случайных чисел $b_i$ и 100 случайных множителей $a_i$. Из всего этого набора он формирует 200 "пакетов" - пар $A_{ij} = (M_{ij}, b_i)$.

2) Избиратель отправляет в ЦИК набор из 100 пар "пакетов": $A_{ij} a_i^d$, $i = 1, \ldots, 100$, $j = 1, 2$.

3) ЦИК просит прислать ему множители от 99 случайно выбранных пар "пакетов", например, с номерами $1, \ldots, 99$. Получив множители $a_1,\ \ldots, a_{99}$ ЦИК проверяет, что избиратель прислал правильно заполненные бюллетени и подписывает оставшуюся пару "пакетов", то есть пару $A_{100,1}$, $A_{100,2}$ и отправляет ее избирателю.

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

5) Если ЦИК получает два бюллетеня с одним и тем же случайным числом, то он их отбрасывает.

Более подробно можно посмотреть вот здесь http://www.ssl.stu.neva.ru/psw/crypto/a ... _01_06.pdf (глава 6 Эзотерические протоколы ~ 600 кБ).

[MaximKat]

AV_77
зачем такие сложности?
в любом случае, в конце избирком получает незашифрованные бюллетени и может проверять, чтобы все они были разными

[epros]

MaximKat писал(а):

это другое число, но тоже сгенерировано избирателем и входит в сообщение, вместе с голосом, с самого начала
т.е. само сообщение состоит из голоса и случайного числа

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

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

Ага, кажется понял. Т.е. алгоритм, описанный в первом сообщении AV_77 можно уточнить таким образом, что $M$ - это не просто выбор, а комбинация из выбора и случайного числа. Затемнение (а потом и растемнение) $M$ производится с помощью другого случайного числа. Избирком получает подписанное им $M$, состоящее из выбора и случайного числа, и учитывает выбор только если случайное число оказалось уникальным.

Но всё же эта система представляется где-то уязвимой для манипуляций. Например, избирком может добавить голосов, причём избиратели не узнают, какие именно голоса - добавленные. Конечно, можно проверить, что количество учтённых голосов не больше количества "зарегистрировавшихся избирателей" (т.е. тех, кто послал затемнённый выбор). Но:
1. Некоторое количество "зарегистрировавшихся избирателей" может забыть или не захотеть послать растемнённый выбор. Если избирком проголосует за них, то никто ничего не узнает.
2. Избирком может "зарегистрировать" какое-то количество либо не существующих, либо заведомо не интересующихся выборами избирателей. Чтобы это обнаружить, нужно докопаться до каждого избирателя и уточнить у него, регистрировался ли он на самом деле.

[AV_77]

MaximKat писал(а):

AV_77
зачем такие сложности?
в любом случае, в конце избирком получает незашифрованные бюллетени и может проверять, чтобы все они были разными

Все эти сложности, на самом деле, просто необходимы. Так как ЦИК не знает, что именно она подписывает (так как используется протокол слепой подписи), то ей желательно как-то удостоверится, что она подписывает именно бюллетень, а не, скажем, банковский чек. Именно для этого избиратель формирует большое число бюллетеней и открывает по требованию ЦИК часть из них. Так как ЦИК выбирает открываемые бюллетени случайно, то вероятность ошибки, то есть подписи чего-то отличного от бюллетеня, можно сделать достаточно малой. В примере вероятность ошибки $0.01$.