?

Log in

голосование - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

голосование [окт. 3, 2006|08:58 pm]
Anatoly Vorobey

Ка-ка-я красота!

Новая статья Рона Ривеста (знаменитый криптограф такой) о придуманной им системе тайного голосования. Называется "система трех бюллетеней".

Перескажу в двух словах гениальную и очень простую систему Ривеста для тех, кому лень читать 15 страниц его статьи (я правда очень рекомендую) или не читает по-английски.

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

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

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

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

Что теперь получилось? Во-первых, подсчитать результаты легко: как и в обычных выборах, победил тот, за кого больше всего заштриховали кружков (если избиратель предпочел кандидата X, то на его 3 бюллетенях вместе за X заштриховано на 1 кружок больше, чем за любого другого кандидата). Во-вторых, результаты можно опубликовать: скажем, на публичном веб-сайте, список всех бюллетеней с номерами и кружками. Кто хочет, сам пересчитает результаты, тайна голосования не нарушена. В-третьих, я, избиратель, могу взять свою официальную копию одного из своих бюллетеней и сравнить с опубликованной: если не совпадают, налицо обман. Значит, подменить бюллетени в широком масштабе тяжело, т.к. мошенник не знает, какие из бюллетеней (ровно одна третья часть) могут быть проверены, и многие из них будут проверены. В-четвертых, я не могу никому доказать, что я проголосовал за какого-то конкретного кандидата, т.к. кружки на моей официальной копии ни о чем не говорят: вне зависимости от того, что там проставлено, я мог проголосовать за любого из кандидатов, правильно выбирая кружки на двух оставшихся своих секретных бюллетенях. Поэтому мой голос тяжело купить или вынудить угрозами: я могу даже по желанию "скупщика" голосов принести ему определенным образом заполненную официальную копию, но при этом реально проголосовать все равно по своему желанию.

Очень красиво!

СсылкаОтветить

Comments:
Страница 1 из 2
<<[1] [2] >>
[User Picture]From: arbat
2006-10-03 07:07 pm
А самое главное достоинство системы - что она проводит определенный ценз. Проголосовать смогут только те, кто в состоянии осилить инструкции. 5% населения. Сливки интеллектуального общества.
(Ответить) (Thread)
[User Picture]From: avva
2006-10-03 07:10 pm
На это г-н Дракон соизволил ответить, что можно сделать так, чтобы машина была, нажимаешь в ней свой выбор, а она случайным образом выбирает кружки так, чтобы по правилам, и выдает заполненный бланк. Этот бланк проверяется во втором автомате, разрезается, штампуется итд. Тем, для кого эти правила - непосильная натуга, не надо и напрягаться, хотя с 95% вы зажгли, конечно.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: vadda
2006-10-03 07:10 pm
Да, красиво выходит.

Одна проблема - 90% избирателей будут не в состоянии понять, почему бюллетеней не один, а три, и почему надо штриховать "неправильных" кандидатов.

А так да, все замечательно.
(Ответить) (Thread)
[User Picture]From: avva
2006-10-03 07:11 pm
См. ответ выше :)
(Ответить) (Parent) (Thread)
[User Picture]From: igorbor
2006-10-03 07:11 pm
Система очень красивая, но я не понимаю - а как она защищает от подлога путем вброса лишних бюллетеней?
(Ответить) (Thread)
[User Picture]From: amigofriend
2006-10-03 07:14 pm
Все случайные номера могут быть запомнены предварительно.
Невозможно будет создать "новый" бюллетень, только дубликатный.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: olleke_bolleke
2006-10-03 07:13 pm
ну, избиратель может уведомлять своего "скупщика" о сделанном выборе СРАЗУ после голосования, сообщая при этом номера ВСЕХ ТРЕХ талонов. Это должно служить весомой гарантией его правдивости .
(Ответить) (Thread)
[User Picture]From: avva
2006-10-03 07:24 pm
Отличное возражение, но против этого есть свой прием: не печатать номера заранее. Номера печатает проверяющая бюллетени машина, при этом она же их прикрывает (сгибает край итп.) так, что избиратель увидит только номер того бюллетеня, от которого ему дадут официальную копию (на копии и увидит). После того, как бюллетени проверены и выданы ему для подачи в ящик, он не может уже ничего с ними делать, только взять и положить в ящик. Он не может отогнуть край и увидеть номера двух других бюллетеней, поэтому он их не знает и скупщику сказать не может.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: nameless__one
2006-10-03 07:25 pm
Честно скажу, что поленился пока прочесть всю статью, но ваше описание оставляет одну неясность.

Если я не могу никому доказать как я голосовал, то что стоят мои утверждения о том что мой голос учли неправильно? Доказательств ведь нет.
(Ответить) (Thread)
[User Picture]From: avva
2006-10-03 07:37 pm
Доказательства есть: если ваша официальная копия не совпадает с тем, что опубликовано на веб-сайте, то это и есть доказательство. С этим идем в избирательную комиссию, суд итд.
(Ответить) (Parent) (Thread)
[User Picture]From: avnik
2006-10-03 07:51 pm
Во первых система подразумевает доверие организаторам.
Во вторых никак не предусмотрена защита, от обмана при подсчете.
Во третьих я не верю что система обеспечит какой-то разумный фидбэк в случае нарушений. А вообще было бы интересно почитать, что про нее скажет и/или напигет Шнайер или кто нибудь еще из признынх авторитетов безопасности.
(Ответить) (Thread)
[User Picture]From: dbg
2006-10-03 08:09 pm
Шнайер хвалебно отблогался еще вчера
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: pussbigeyes
2006-10-03 07:55 pm
Умный скупщик голосов "за Алекса" предупредит электорально озабоченного гражданина: "Ты, мил человек, за Алекса голосуй в первом и втором бюллетненях, а за всех остальных - в третьем. Иначе, денежки - тю-тю."
(Ответить) (Thread)
[User Picture]From: rakshas
2006-10-03 10:07 pm
Это ничего не даст, потому что избиратель сам выбирает, какую из трех ему распечатать.

Если бы ему выдавали случайную копию одного из 3 — ваше замечание было бы справедливо.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: sbks
2006-10-03 08:01 pm
Несмотря на то, что не врубился до конца, уверен: доступ к фальсификации будет у организаторов, программистов, в конце концов - у, образно говоря, электрика, который видя хреновый ход событий (например по экзит-полам) сорвёт условно выражаясь стоп-кран.
(Ответить) (Thread)
[User Picture]From: sanches
2006-10-03 08:06 pm
Любопытная идея.

Хотя это и далеко не единственный возможный вариант.

Пару лет назад я опубликовал в "Компьютерре" две статьи на эту тему, - см. и см.. Тоже вариант системы, исключающий фальсификации и допускающий правильность учета каждого отданного голоса.
(Ответить) (Thread)
[User Picture]From: rakshas
2006-10-03 08:20 pm
Интересно, умно, но мне кажется идея довольно очевидной, до такого наверняка могло додуматься множество криптографов, если бы была поставлена такая задача.

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

Потому что, если выяснится, что люди, голоса которых куплены, в 90+% случаев все равно голосуют за нужного кандидата, даже если это нельзя проверить, то покупать голоса все равно имеет смысл; и система с тремя бюллетенями не сильно лучше системы с одним номерным бюллетенем, который публикуется.
(Ответить) (Thread)
[User Picture]From: avva
2006-10-03 08:42 pm
У Ривеста есть такое качество - придумывать штуки, которые в его изложении оказываются очень простыми, но до него никто не придумал.
Задача-то ставилась - исследование систем голосования это вполне себе область исследования такая, на стыке социологии и криптографии.

Про покупку голосов это интересный вопрос, тут, мне кажется, дело в том, насколько серьезно избиратели относятся к собственно выборам, и насколько в их глазах купля их голоса - "честная" сделка. В стране с достаточно сильной демократической системой и традициями свободных выборов, реально влияющих на жизнь, обычно выходит так, что избиратель, голос которого покупают, смотрит на это как на нечестный, но не очень, поступок - но нечестный, что значит, что он не считает себя связанным требованием этикета проголосовать именно так, и если к тому же он понимает, что итог этих выборов реально может повлиять на качество его жизни, то вполне может быть, что проголосует по своему усмотрению того, где его польза, а не по договоренности, которую невозможно проверить.
Так мне кажется. Насчет исследований в этой области не осведомлен, хотя социологи и политологи наверняка об этом кучу работ понаписали.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: mi_b
2006-10-03 08:21 pm
на практике, при имплементации алгоритма в ГАС Выборы, будет записываться номер копируемого бюллетеня, а потом будут подделываться два бюллетеня с другими номерами.
(Ответить) (Thread)
[User Picture]From: atly
2006-10-05 07:10 am
+1
(Ответить) (Parent) (Thread)
[User Picture]From: reut
2006-10-03 09:07 pm
слушай, а ведь гениально. и просто. кайф.
(Ответить) (Thread)
[User Picture]From: angerona
2006-10-03 09:22 pm
Никак не защищает от коррумпированной машины, которая знает, какой из бюллетеней был выпечатан и может манипулировать двумя другими полностью изменив результат голосования.

А это как раз и есть одна из проблем -- то, что source code всех этих бюлетенных машин недоступен и неизвестно чем напичкан.
(Ответить) (Thread)
[User Picture]From: avva
2006-10-03 10:11 pm
Машина, которая это знает, не есть та машина, которая считывает голоса, это две разные машины. К тому же она ничем не манипулирует, она не меняет сами бланки, только штампует их и копирует один из них. Там выше был комментарий lzh о том, что все же махинации между этими двумя машинами возможны напр. через стеганографию бланков, но это не так совершенно тривиально.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: oxfv
2006-10-03 09:25 pm
А можно и с нынешними бюлетенями, где один крестик за и ни одного против: достаточно выдавать на руки копию одной трети информации, вместе с номером бюлетеня :) Типа, если голосование за одного из трех кандидатов в президенты, то в копии будет квадратик за одного из них, чекнутый или нет. Который квадратик - а случайный, чтобы у избирателя не было возможности продать свой голос заранее.
(Ответить) (Thread)
[User Picture]From: rakshas
2006-10-03 09:57 pm
В вашей системе, если ты продал голос и голосуешь за другого, ты с вероятностью 2/3 — получишь шиш.

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

В системе же Ривеста выданная на руки копия не говорит вообще ничего.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: boghdan
2006-10-03 09:48 pm
в ЦИК! =)
(Ответить) (Thread)
[User Picture]From: novikov
2006-10-03 10:05 pm
а если избиратель заполнит все три бюллетеня за одного кандидата чтобы повысить его шансы и не давать очков соперникам?
уверен, большинство так и сделают...
(Ответить) (Thread)
[User Picture]From: avva
2006-10-03 10:06 pm
Не сможет - машина проверяет, что он своему ровно два кружка отдал, а другим ровно по одному, до того, как разъединяет бюллетени.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: erez
2006-10-03 10:06 pm
Гораздо проще выдавать копию квитанции случайным образом определённому проценту избирателей (с номером и их выбором, все из которых публикуются). Они, при желании, и будут контролировать неподтасованность результатов. Правда, найдутся недовольные тем, что им не выпал шанс стать контролёром...

Всё, что требуется - показать ("наглядно"), что машина, принимающая квитанции (и выдающая их случайные копии) никак не связанна с машиной для собственно голосования, то есть, сначала учитывается результат, а затем, когда он уже напечатан и находится во второй машине, крутится нечто вроде рулетки "Спортлото", определяющей, какому счастливчику выдать копию. Поскольку заранее неизвестно, какие копии попадут на руки избирателям, невозможно вычислить и подделать те, что не попадут.
(Ответить) (Thread)
[User Picture]From: avva
2006-10-03 10:09 pm
Нет, это оставляет дырку купли голосов (по схеме - проголосуй за такого-то, и если ты получишь квитанцию, я тебе заплачу $X; чем меньше процент контролеров среди всех избирателей, тем больше я сделаю $X, повышая твою мотивацию все же голосовать, как я прошу, и не повышая мои конечные расходы).
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: karakal
2006-10-03 10:22 pm
Схема красивая, но...

Если государственный аппарат хочет обеспечить честные выборы, то он найдет способы с этим справиться и при существующей системе.
А если не хочет, то никакая красота не заставит его внедрять то, что станет мешать ему жить.
(Ответить) (Thread)
[User Picture]From: russian_bob
2006-10-04 12:04 am
"найдет способы с этим справиться" - это как раз один из них
(Ответить) (Parent) (Thread)
[User Picture]From: r_l
2006-10-03 10:36 pm
А для каких обществ разрабатывалась модель?
Я к тому, что в обществе вроде, например, белорусского, те 67 (допусти)%, которые реально голосуют за Лукашенка, вполне рады увидеть в окончательных результатах цифру (допустим) 90%.
Разруха у тебя в штанах, как говорил герой М. Булгакова.
(Ответить) (Thread)
[User Picture]From: avva
2006-10-03 11:12 pm
Да, не для всяких обществ такие модели вообще сильно имеют значение, это точно.
(Ответить) (Parent) (Thread)
[User Picture]From: russian_bob
2006-10-03 11:53 pm

Идея хорошая.

Добавить к ней обязательную регистрацию и рассылку бюллетеней с уже напечатанными номерами по почте тем кто зарегистрировался. Списки всех зарегистрированных, по точкам голосования, также должны публиковаться с пометками "голосовал" / "не голосовал". Таким образом не должно быть мертвы душ и лишних бюллетеней.
Бланки всех трёх бюллетеней - это ваше доказательство что вы не голосовали.

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

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

Одна проблема правда с покупкой голосов - если у вас купят все три незаполненных бюллетеня и сами понесут их в избирательный участок, и коррумпированные чиновники не станут проверять ID - система не сработает.
Но это пожалуй слишком сложно. Или нет?
(Ответить) (Thread)
[User Picture]From: russian_bob
2006-10-04 12:03 am

Re: Идея хорошая.

О! Забыл...

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

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

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

И ещё нужно установить:
1. Публичный доступ к базам данных (интернет)
2. Процедуру обжалования нарушений
3. Процедуру расследования заявок граждан.

Во...
(Ответить) (Parent) (Thread)
From: vasja_iz_aa
2006-10-04 12:08 am
Какой замечательный способ покрыть умным текстом 15 страниц бумаги. А он там не упоминает, чем его способ лучше, чем выдавать каждому обычным образом проголосовавшему завереную копию случайного бюлетеня? Я так предполагаю, что любой бюлетень имеет номер, но не фамилию.
(Ответить) (Thread)
[User Picture]From: avva
2006-10-04 12:13 am
Он обсуждает такой способ отдельно (только не случайно выдавать, а случайно меняться своими копиями у выхода). См. статью.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: averros
2006-10-04 03:44 am
Cryptography (and cryptographers) are overrated - because, just like a person with a hammer seeing everyting as a nail, they tend to see everything as a crypto or protocol problem.

The fairness of elections is a total non-issue, for several reasons:

1. Every election is a sort of an advance auction in stolen goods (this brilliant definition is due to H.L.Mencken).

2. Every election offers only false choices between candidates no person in his right mind would trust hundred bucks for a day. Electorate does not get a say on the selection of candidates.

3. Representative democracy is a fraud anyway: in which exactly sense the winning candidate can be claimed to "represent" those who didn't vote for him?

4. Electorate is totally brainwashed and misled with regard to the issues they are supposed to be voting on. Most people are utterly ignorant of basics of economics, for example. The garbage-in garbage-out principle applies.

5. Finally, no elections can be fair (the Arrow theorem).

Elaborate schemes to improve the electoral ritual miss completely that the ritual is a sham; an elaborate lock on a barn missing the back wall.
(Ответить) (Thread)
[User Picture]From: talash
2006-10-04 05:26 am

this gives the phrase "vote for jesus" a whole new perspective...
(Ответить) (Thread)
(Удалённый комментарий)
(Удалённый комментарий)
(Удалённый комментарий)
[User Picture]From: white_lee
2006-10-04 06:30 am
Очень своевременная статья - как раз пишу работу об Insight problems. Может использую в качестве иллюстрации :).
(Ответить) (Thread)
[User Picture]From: avva
2006-10-04 12:33 pm
Расскажите тогда, что такое Insight problems :)
(Ответить) (Parent) (Thread) (Развернуть)
Страница 1 из 2
<<[1] [2] >>