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

[Dims]

В порядке безумной идеи.

Допустим, проводится референдум, в котором каждый должен проголосовать за один из N пунктов p_1, p_2, ... p_N

Каждому гражданину выдётся огромное простое число. Составляется N произведений, каждое произведение соответствует одному из вариантов. Если человек голосует за i-й пункт, то произведение p_i домножается на его число.

В конце голосования:

1) каждое произведение можно легко проверить на наличие в нём голоса данного человека; кроме того, его можно проверить на присутствие всех голосов

2) если простые числа выдаются из заданного интервала, то, наверное, по величине произведения можно судить о количестве голосов, содержащихся в нём

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

Интересно обсудить достоинства и ошибки этой системы, а так же пути её совершенствования.

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

[maxal]

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

[epros]

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

[TOTAL]

Dims писал(а):

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

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

[epros]

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

epros писал(а):

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

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

[Бодигрим]

Красивая схема. Но, увы, множество допущенных к голосованию и множество голосовавших не совпадают даже в теории.

[Trotil]

Цитата:

Т.е. никак невозможно обеспечить общедоступную проверку того, что голос каждого правильно учтён и в то же время - тайность голосования.

У нас в курсе криптографии приводилась схема тайного электронного голосования. Если интересно, могу выложить.

[Dims]

TOTAL писал(а):

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

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

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

Добавлено спустя 16 секунд:

Trotil писал(а):

Цитата:

Т.е. никак невозможно обеспечить общедоступную проверку того, что голос каждого правильно учтён и в то же время - тайность голосования.

У нас в курсе криптографии приводилась схема тайного электронного голосования. Если интересно, могу выложить.

Да, интересно.

[Trotil]

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

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

Тайное электронное голосование

Требования к системе:
1) Голосовать может только имеющий право голоса.
2) Никто не может голосовать более одного раза.
3) Никто не может определить, кто конкретно за кого голосовал.
4) Никто не может подменить чей-либо выбор.
5) Любой проголосовавший может проверить, что его голос правильно учтен.
6) Все знают, кто участвовал в голосовании, а кто нет.

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

[ewert]

Trotil в сообщении #150171 писал(а):

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

а оно это нужно, голосующему-то?

[Trotil]

ewert писал(а):

а оно это нужно, голосующему-то?

Если он заинтересован в соблюдении принципов 1-6 голосования, очевидно да.

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

[ewert]

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

[вздымщик Цыпа]

Trotil в сообщении #150171 писал(а):

6) Все знают, кто участвовал в голосовании, а кто нет.

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

[ewert]

а я вот краем уха слыхал, что в некоторых ну очень европейских странах за неявку почти расстреливают

[PAV]

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