голосование

[avva]

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

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

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

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

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

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

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

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

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

Comments

Re: оффтоп

[arbat.livejournal.com]

И Вы были бы правы, если бы могли представить ЛУЧШИЙ фильтр, чем данный. Тогда ваш аргумент был бы - "видите, есть фильтр, который позволяет снизить чизло подозреваемых до 100 человек, а они используют фильтр, который позволяет сузить круг расследуемых только до 30,000 - как глупо с их стороны". Вы этого не делаете и этого не делает Шнейдер. Вместо этого Вы с ним говорите - "ах, но этот фильтр позволяет только сузить круг подозреваемых, а не определить точно - кто террорист... не будем его применять!"

Отказ применять какой-то фильтр потому, что он не дает точного результата, несмотря на то, что он снижает число подозреваемых НА НЕСКОЛЬКО ПОРЯДКОВ - не свидетельствует ни об уме, ни о здравом смысле. Более того, это свидетельствует, что вы оба не понимаете, что подобные фильтры есть ОСНОВА любой криминалистики. Расследование начинается не с того, что следовартель смотрит в лупу на отпечаток подошвы и говорит - "Ба, да это же Никаноров Иван Тимофеевич, Зеленый проезд, 13, квартира 5!" - а с того, что свидетель говорит, что видел "синюю машину". После чего полиция составляет список владельцев синих машин, которые были в пределах досягаемости и начинает их перебирать. А вставать в позу "в списке 100 синих машин! Это непостижимо много! Вероятность всего 1 процент! Я отказываюсь использовать это свидетельство для работы!" - это, извините, дурость.

Но с Вами я не знаком, а вот от Шнейдера - я не ожидал.

Re: оффтоп

[konstant1n.livejournal.com]

Более того, это свидетельствует, что вы оба не понимаете, что подобные фильтры есть ОСНОВА любой криминалистики
Ух ты, a вы я вижу криминалист: сравним что свидетель говорит, что видел "синюю машину" и туева хуча машин, в них 1000 преступников, с вероятностью 0.01 процент "доподлинно" известно что 400 преступников уехали на машинах синего цвета, коих имеется всего навсего 30 тысяч. Поздравляю с успешным началом расследования.

PS: а еще и Шнейдер в вас дурак.. мде

Re: оффтоп

[arbat.livejournal.com]

Я даже не знаю, что меня удивляет более - то, что Вы и Шнейдер не понимаете, что "1 из 75" это ГОРАЗДО более хорошие шансы, чем "1 из 300,000"; или то, что вы настаиваете, что нужно применять только такие способы ловли преступников, которые дают сразу окончательный ответ - кого надо арестовывать.

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

Re: оффтоп

[konstant1n.livejournal.com]

Опять двадцать-пять,

"1 из 75" vs. "400 из 30000, при 600 пропущенных" нет разницы, да? Незадача с фильтром есть небольшая: “фильтровать” надо не из 1000 подозреваемых а из 300 000 000, отсюда и проблемы описанные в статье.

Для тех кто в танке повторяю еще раз: в статье говорится о проблемах с глобальной электронной слежки за всем населением, упрямая статистика показывает что такие системы НИКОГДА не станут эффективными в поиске террористов просто потому что террористов мало а населения довольно много. (Математика в статье ).

Уменьшить круг подозреваемых до 1 из 100 -- замечательно, уменьшить круг до 30 000 , при 600 террористов за “за бортом” -- не вижу большого смыла. Опознать предполагаемого террориста с вероятностью 0.01 можно и другими, более дешевыми методами.

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

Я только считаю что средства лучше потратить по другому: не на неэффективные и жутко дорогие “системы глобальной слежки” , на более традиционные методы, которые вам как специалисту-[любителю] по криминалистике должны быть известны.

Re: оффтоп

[arbat.livejournal.com]

говорится о проблемах с глобальной электронной слежки за всем населением, упрямая статистика показывает что такие системы НИКОГДА не станут эффективными в поиске террористов просто потому что террористов мало а населения довольно много

Ничего подобного статистика у Шнейдера не показывает. У него есть расчет, который показывает, что применив некоторые методы, можно резко сузить круг подозреваемых, увеличив "концентрацию" в нем террористов на несколько порядков. Он говорит, что в этом нет никакой пользы. Это утверждение глупо, по той простой причине, что вся криминалистика ПОСТРОЕНА на методах, которые сужают круг подозреваемых, увеличивая вероятность того, что один из них - "наш" человек.

уменьшить круг до 30 000 , при 600 террористов за “за бортом” -- не вижу большого смыла.

Без фильтрации ожидаемое количество человек, которое надо будет изучить для поимки одного террориста, - 300,000, после фильтрации - всего 75. Мне смысл очевиден сразу.

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

Или приведите пример такого метода опознания террориста, или сознайтесь, что не имеете ни малейшего представления, о том, о чем говорите.

П.С. Кстати, "глобальная слежка за всем населением", "упрямая статистика" и прочая беллетристика - ничуть не делает Ваш текст более убедительным. По крайней мере в печатном виде. Эти приемы работают только при устной речи, будучи подкреплены жестами: оратор должен ежиться от ужаса перед глобальной слежкой, пучить глаза и разводить руками, показывая, как она упрямая - эта статистика.

Re: оффтоп

[ai1eron.livejournal.com]

Брюс Шнайер.
Шнейдер - это кандидат, не прошедший в КС.