Новая технология: абсолютно честные выборы
10/04/2006 | Tatarchuk
Ка-ка-я красота! http://avva.livejournal.com/1652769.html
Новая статья Рона Ривеста (знаменитый криптограф такой) о придуманной им системе тайного голосования. Называется "система трех бюллетеней".
Перескажу в двух словах гениальную и очень простую систему Ривеста для тех, кому лень читать 15 страниц его статьи (я правда очень рекомендую) или не читает по-английски.
В чем основная проблема обычного тайного голосования? В том, что несколько важных его целей, взятые вместе, казалось бы противоречат друг другу. Это, во-первых, собственно тайна голосования, т.е. никто не должен знать, как я проголосовал; во-вторых, предотвращение мошенничества, т.е. подделки голосов, подмены бюллетеней итд.
Если бы каждый избиратель мог проверить, что его голос был учтен именно так, как он его заполнил, то мошенничать было бы намного тяжелее, особенно масштабно. Такую проверку можно было бы сделать, опубликовав имена избирателей вместе с их выборами - но тогда теряется тайна голосования. Есть вариант лучше: давайте, например, у каждого бюллетеня будет свой случайный номер, который избиратель сможет записать во время голосования (или просто получить копию бюллетеня), а потом все бюллетени будут опубликованы. Тогда вы не знаете, как я проголосовал, а я знаю, и могу проверить, что все было учтено верно. Но и это не идеально: то, что я могу доказать кому-то, как я проголосовал, это плохо - это значит, что мой голос могут заранее купить, пообещав мне что-то (или пригрозив мне чем-то). Должна быть ситуация, при которой даже я не могу никому доказать, что я проголосовал именно за этого кандидата - но тогда как я могу проверить, что мой голос учли верно? Противоречие, казалось бы.
Вот как остроумно решает эту проблему Ривест. Избиратель получает три бюллетеня, которые соединены в одном бланке для удобства, но после заполнения их можно разорвать по перфорированным краям и получить три отдельных бюллетеня. Вот так примерно:
В обычных выборах, с одним бюллетенем, избиратель заштриховал бы один кружок напротив своего кандидата, а другие не трогал. В системе Ривеста он поступает следующим образом: в строке того кандидата, которого он хочет выбрать, он штрихует два из трех кружков на трех бюллетенях - неважно, какие два из трех; в строках всех остальных кандидатов он штрихует один из трех кружков - тоже неважно какой. После этого специальная (простая) машина проверяет, что он не нарушил правила штрихования, разделяет бланк на три бюллетеня, штампует их официальным штампом и выдает ему официальную копию одного из трех - на его выбор, но только одного. Все три бюллетеня кладутся в ящик и связи между ними больше нет никакой (у каждого есть свой идентификационный номер, но они не последовательные, а случайные).
Что теперь получилось? Во-первых, подсчитать результаты легко: как и в обычных выборах, победил тот, за кого больше всего заштриховали кружков (если избиратель предпочел кандидата X, то на его 3 бюллетенях вместе за X заштриховано на 1 кружок больше, чем за любого другого кандидата). Во-вторых, результаты можно опубликовать: скажем, на публичном веб-сайте, список всех бюллетеней с номерами и кружками. Кто хочет, сам пересчитает результаты, тайна голосования не нарушена. В-третьих, я, избиратель, могу взять свою официальную копию одного из своих бюллетеней и сравнить с опубликованной: если не совпадают, налицо обман. Значит, подменить бюллетени в широком масштабе тяжело, т.к. мошенник не знает, какие из бюллетеней (ровно одна третья часть) могут быть проверены, и многие из них будут проверены. В-четвертых, я не могу никому доказать, что я проголосовал за какого-то конкретного кандидата, т.к. кружки на моей официальной копии ни о чем не говорят: вне зависимости от того, что там проставлено, я мог проголосовать за любого из кандидатов, правильно выбирая кружки на двух оставшихся своих секретных бюллетенях. Поэтому мой голос тяжело купить или вынудить угрозами: я могу даже по желанию "скупщика" голосов принести ему определенным образом заполненную официальную копию, но при этом реально проголосовать все равно по своему желанию.
Очень красиво!
Новая статья Рона Ривеста (знаменитый криптограф такой) о придуманной им системе тайного голосования. Называется "система трех бюллетеней".
Перескажу в двух словах гениальную и очень простую систему Ривеста для тех, кому лень читать 15 страниц его статьи (я правда очень рекомендую) или не читает по-английски.
В чем основная проблема обычного тайного голосования? В том, что несколько важных его целей, взятые вместе, казалось бы противоречат друг другу. Это, во-первых, собственно тайна голосования, т.е. никто не должен знать, как я проголосовал; во-вторых, предотвращение мошенничества, т.е. подделки голосов, подмены бюллетеней итд.
Если бы каждый избиратель мог проверить, что его голос был учтен именно так, как он его заполнил, то мошенничать было бы намного тяжелее, особенно масштабно. Такую проверку можно было бы сделать, опубликовав имена избирателей вместе с их выборами - но тогда теряется тайна голосования. Есть вариант лучше: давайте, например, у каждого бюллетеня будет свой случайный номер, который избиратель сможет записать во время голосования (или просто получить копию бюллетеня), а потом все бюллетени будут опубликованы. Тогда вы не знаете, как я проголосовал, а я знаю, и могу проверить, что все было учтено верно. Но и это не идеально: то, что я могу доказать кому-то, как я проголосовал, это плохо - это значит, что мой голос могут заранее купить, пообещав мне что-то (или пригрозив мне чем-то). Должна быть ситуация, при которой даже я не могу никому доказать, что я проголосовал именно за этого кандидата - но тогда как я могу проверить, что мой голос учли верно? Противоречие, казалось бы.
Вот как остроумно решает эту проблему Ривест. Избиратель получает три бюллетеня, которые соединены в одном бланке для удобства, но после заполнения их можно разорвать по перфорированным краям и получить три отдельных бюллетеня. Вот так примерно:
В обычных выборах, с одним бюллетенем, избиратель заштриховал бы один кружок напротив своего кандидата, а другие не трогал. В системе Ривеста он поступает следующим образом: в строке того кандидата, которого он хочет выбрать, он штрихует два из трех кружков на трех бюллетенях - неважно, какие два из трех; в строках всех остальных кандидатов он штрихует один из трех кружков - тоже неважно какой. После этого специальная (простая) машина проверяет, что он не нарушил правила штрихования, разделяет бланк на три бюллетеня, штампует их официальным штампом и выдает ему официальную копию одного из трех - на его выбор, но только одного. Все три бюллетеня кладутся в ящик и связи между ними больше нет никакой (у каждого есть свой идентификационный номер, но они не последовательные, а случайные).
Что теперь получилось? Во-первых, подсчитать результаты легко: как и в обычных выборах, победил тот, за кого больше всего заштриховали кружков (если избиратель предпочел кандидата X, то на его 3 бюллетенях вместе за X заштриховано на 1 кружок больше, чем за любого другого кандидата). Во-вторых, результаты можно опубликовать: скажем, на публичном веб-сайте, список всех бюллетеней с номерами и кружками. Кто хочет, сам пересчитает результаты, тайна голосования не нарушена. В-третьих, я, избиратель, могу взять свою официальную копию одного из своих бюллетеней и сравнить с опубликованной: если не совпадают, налицо обман. Значит, подменить бюллетени в широком масштабе тяжело, т.к. мошенник не знает, какие из бюллетеней (ровно одна третья часть) могут быть проверены, и многие из них будут проверены. В-четвертых, я не могу никому доказать, что я проголосовал за какого-то конкретного кандидата, т.к. кружки на моей официальной копии ни о чем не говорят: вне зависимости от того, что там проставлено, я мог проголосовать за любого из кандидатов, правильно выбирая кружки на двух оставшихся своих секретных бюллетенях. Поэтому мой голос тяжело купить или вынудить угрозами: я могу даже по желанию "скупщика" голосов принести ему определенным образом заполненную официальную копию, но при этом реально проголосовать все равно по своему желанию.
Очень красиво!