Отправитель и получатель. Сообщения и шифрование 12 глава

1. У Алисы есть nразличных сообщений. Боб может выбрать одно из них, чтобы Алиса его подписала, и у Алисы не будет способа узнать, что же она подписала.

2. У Алисы есть единственное сообщение. Боб может выбрать один из nключей, которым Алиса подпишет сообщение, и Алиса не сможет узнать, какой ключ она использовала.

Идея изящна, я уверен, что где-нибудь она найдет применение.

5.7 Одновременная подпись контракта

Подпись контракта с помощью посредника

Алиса и Боб хотят заключить контракт. Они достигли согласия на словах, но никто не хочет ставить свою подпись, пока не поставлена подпись другого. При личной встрече это не вызывает затруднений - оба подписывают вместе. На расстоянии они могут обратиться к посреднику.

(1) Алиса подписывает копию контракта и посылает ее Тренту.

(2) Боб подписывает копию контракта и посылает ее Тренту.

(3) Трент посылает сообщение и Алисе, и Бобу, сообщающее, что другой партнер подписал контракт.

(4) Алиса подписывает две копии контракта и посылает их Бобу.

(5) Боб подписывает обе копии контракта, сохраняет одну для себя, и посылает другую Алисе.

(6) Алиса и Боб сообщают Тренту, что у каждого из них есть подписанная обоими партнерами копия контракта.

(7) Трент уничтожает свои две копии контракта, с единственной подписью под каждым.

Этот протокол работает, потому что Трент защищает любую из сторон от мошенничества другой. Если Боб попытается отказаться от подписи под контрактом на этапе (5), Алиса может обратиться к Тренту за копией контракта, уже подписанного Бобом. Если Алиса попытается отказаться от подписи под контрактом на этапе (4), Боб может сделать то же самое. Когда Трент сообщает, что он получил оба контракта на этапе (3), Алиса и Боб узнают, что другой партнер уже подписал контракт. Если Трент не получит оба контракта на этапах (1) и (2), он уничтожает имеющуюся у него копию, и ни одна из сторон не связана более обязательствами контракта.

Одновременная подпись контракта без посредника (лицом к лицу)

Если Алиса и Боб встречаются лицом к лицу, они могут подписать контракт следующим образом [1244]:

(1) Алиса пишет первую букву своего имени и передает контракт Бобу.

(2) Боб пишет первую букву своего имени и передает контракт Алисе.

(3) Алиса пишет вторую букву своего имени и передает контракт Бобу.

(4) Боб пишет вторую букву своего имени и передает контракт Алисе.

(5) Это продолжается до тех пор, пока Алиса и Боб не напишут свои имена полностью.

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

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

Так как ни Алиса, ни Боб не знают точно, с какого момента начинает действовать контракт, то у каждого из них на протяжении всего протокола есть опасение, что для него или для нее контракт уже вступил в силу. Не существует этапа протокола, на котором Боб смог бы сказать: "Вы написали четыре буквы подписи, а я только три. Вы связаны контрактом, а я нет." У Боба нет причин прекращать выполнение протокола. Более того, чем дольше стороны выполняют протокол, тем больше вероятность того, что судья решит, что контракт вступил в силу. И снова, нет причины прерывать протокол. В конце концов, они оба хотели подписать контракт, они просто не хотели подписывать его раньше другого партнера.

Одновременная подпись контракта без посредника (без личной встречи)

В этом протоколе используется такая же неопределенность [138]. Алиса и Боб по очереди движутся детскими шажками к подписанию протокола.

В этом протоколе Алиса и Боб обмениваются рядом подписанных сообщений вида: "Я согласен, что с вероятностью p я связан условиями контракта."

Получатель сообщения может предъявить его судье и, с вероятностью p, судья признает контракт подписанным.

(1) Алиса и Боб согласовывают дату окончания подписания контракта.

(2) Алиса и Боб договариваются о различии вероятностей, которым они собираются пользоваться. Например, Алиса может решить, что ее вероятность быть связанной условиями контракта не должна превышать вероятность Боба больше, чем на 2 процента. Обозначим различие Алисы как a,различие Боба - как b.

(3) Алиса посылает Бобу подписанное сообщение с вероятностью p = a.

(4) Боб посылает Алисе подписанное сообщение с p = a + b.

(5) Пусть p- это вероятность из сообщения, полученного Алисой от Боба на предыдущем этапе. Алиса посылает Бобу подписанное сообщение с p' = p + aили 1, смотря что меньше.

(6) Пусть p- это вероятность из сообщения, полученного Бобом от Алисы на предыдущем этапе. Боб посылает Алисе подписанное сообщение с p' = p + b или 1, смотря что меньше.

(7) Алиса и Боб продолжают выполнять этапы (5) и (6) до тех пор, пока они оба не получат сообщения с p = 1 или пока не наступит согласованная на этапе (1) дата.

По мере выполнения протокола и Алиса, и Боб соглашаются, что они оказываются связанными контрактом со все большей и большей вероятностью. Например, Алиса может определить свое aкак 2 процента, а Боб свое b- как 1 процент. (Лучше бы они выбрали большие приращения, а то мы застрянем на этом месте.) В первом сообщении Алиса сообщает, что она связана контрактом с вероятностью 2 процента. Боб может ответить, что он связан контрактом с вероятностью 3 процента. Следующее сообщение Алисы может утверждать, что она связана контрактом с вероятностью 5 процента и так далее, пока вероятности обоих не достигнут 100 процентов.

Если и Алиса, и Боб завершили протокол к оговоренной дате, то все прекрасно. В противном случае, любая из сторон может предъявить контракт судье вместе с подписанным последним сообщением другой стороны. Прежде, чем просмотреть контракт, судья случайным образом выбирает число между 0 и 1. Если это число меньше вероятности, подписанной второй стороной, то обе стороны связаны контрактом. Если это число больше вероятности, подписанной второй стороной, то обе стороны не связаны контрактом. (Затем судья сохраняет использованное число на случай решения другого вопроса, касающегося того же контракта.) Именно это и означает "быть связанным контрактом с вероятностью p".

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

Одновременная подпись контракта без посредника (с помощью криптографии)

Этот криптографический протокол использует тот же принцип детских шажков [529]. Для определенности используется DES, хотя вместо него может быть любой симметричный алгоритм.

(1) И Алиса, и Боб случайным образом выбирают 2nключей DES, сгруппированных попарно. В парах нет ничего особенного, это просто способ группировки для данного протокола.

(2) И Алиса, и Боб создают nпар сообщений, L_iи R_i,например, "Это левая половина моей i-ой подписи" и "Это правая половина моей i-ой подписи". Идентификатор, i, меняется от 1 до n. В каждое сообщение, вероятно, также будет входить цифровая подпись контракта и метка времени. Контракт считается подписанным, если другая сторона может предъявить обе половины, L_iи R_i,одной пары подписей.

(3) И Алиса, и Боб шифруют свои пары сообщений парами ключей DES, левое сообщение - левым ключом в паре , а правое - правым.

(4) Алиса и Боб посылают друг другу свои пачки из 2n шифрованных сообщений, поясняя, какие сообщения какими половинами каких пар являются.

(5) Алиса и Боб посылают друг другу все пары ключей, используя протокол рассеянной передачи для каждой пары. То есть, Алиса посылает Бобу независимо для каждой из n пар ключей либо ключ, использованный для шифрования левого сообщения, либо ключ, использованный для шифрования правого сообщения. Боб делает то же самое. Они могут посылать свои половинки по очереди, или сначала один может послать все 100, а потом другой - это не имеет значения. Теперь и у Алисы, и у Боба есть по одному ключу из каждой пары, но никто не знает, какие из половинок получил партнер.

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

(7) Алиса и Боб посылают друг другу первые биты всех 2n ключей DES.

(8) Алиса и Боб повторяют этап (7) для вторых битов всех 2n ключей DES, затем третьих битов и так далее, пока все биты всех ключей DES не будут переданы.

(9) Алиса и Боб расшифровывают оставшиеся половинки сообщений, и контракт подписан.

(10) Алиса и Боб обмениваются закрытыми ключами, использованными для протокола рассеянной передачи на этапе (5), и каждый из них убеждается в отсутствии мошенничества.

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

Если бы Алиса была очень хитрой, она могла бы разрушить только половину протокола. Она могла бы послать одну половинку из каждой пары правильно, а вместо второй отправить бессмысленные строки. Вероятность Боба получить правильную половинку составит только 50 процентов, поэтому в половине случаев мошенничество Алисы удастся, но только для одной пары. Если бы использовались только две пары, этот способ мошенничества удастся в 25 процентах случаев. Вот почему n должно быть велико. Алисе необходимо точно угадать результат n протоколов рассеянной передачи, ее вероятность добиться этого составляет 1 шанс из 2ⁿ. Если n= 10, у Алисы 1 шанс из 1024 обмануть Боба.

Алиса также может отправить Бобу случайные биты на этапе (8). Возможно, Боб не узнает, что она послала ему случайные биты, пока не получит весь ключ и не попытается расшифровать половинки сообщения. Но снова вероятность на стороне Боба. Он уже получил половину ключей, и Алиса не знает какую. Если nдостаточно велико, Алиса наверняка пришлет ему бессмысленный бит для ключа, который у него уже есть, и он немедленно узнает, что она пытается его обмануть.

Возможно, Алиса будет выполнять этап (8) до тех пор, пока она не получит достаточно битов ключей для вскрытия грубым взломом, и затем прекратит передачу битов. Длина ключа DES - 56 битов. Если она получила 40 из 56 битов, ей останется перебрать 2¹⁶, или 65536, ключей для дешифровки сообщения, а эта задача, определенно, по силам современным компьютерам. Но Боб получит ровно столько же битов ее ключей (или, в худшем случае, на один бит меньше), следовательно, он сможет сделать то же самое. У Алисы нет другого выбора, кроме как продолжать следовать протоколу.

Идея в том, что Алисе придется играть честно, потому что вероятность обмануть Боба слишком мала. В конце протокола у обеих сторон есть nподписанных пар сообщений, любое из которых достаточно для правильной подписи.

У Алисы есть только один способ смошенничать - она может послать Бобу одинаковые сообщения на этапе (5). Боб не сможет обнаружить этого до окончания протокола, но он сможет использовать стенограмму протокола, чтобы убедить судью в двуличности Алисы.

Протоколы этого типа имеют два слабых места [138]. Во первых, проблема возникает, если вычислительная мощь одной стороны гораздо больше, чем у другой. Если, например, Алиса может выполнить вскрытие грубым взломом быстрее Боба, то она рано прекратит передачу битов на этапе (8) и раскроет ключи Боба самостоятельно. Бобу, которому для таких же действий просто не хватит времени, не повезет.

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

Эти проблемы существуют также для протоколов разделов 5.8 и 5.9.

5.8 Электронная почта с подтверждением

Такой же протокол одновременной рассеянной передачи, использованный для подписания контракта, с небольшими изменениями используется для электронной почты с подтверждением [529]. Пусть Алиса хочет послать сообщение Бобу, но не хочет, чтобы он прочитал его, не расписавшись в получении. В реальной жизни это обеспечивается неприветливыми почтовыми служащими, но то же самое может быть сделано при помощи криптографии. Эту проблему первым рассмотрел Уитфилд Диффи в [490].

На первый взгляд, эту проблему мог бы решить протокол одновременного подписания контракта. Алиса просто копирует свое сообщение ключом DES. Ее половина протокола выглядит примерно так: "Это левая половина ключа DES: 32f5", а половина протокола Боба - так: "Это левая половина моей квитанции." Все остальное не меняется.

Чтобы понять, почему это не работает, вспомните, что протокол опирается на то, что рассеянная передача на этапе (5) предохраняет от мошенничества обе стороны. Оба партнера знают, что они послали другой стороне правильную половину, но никто не знает какую. Они не мошенничают на этапе (8), потому что вероятность выйти сухим из воды чрезвычайно мала. Если Алиса посылает Бобу не сообщение, а половину ключа DES, то Боб не может проверить правильность ключа DES на этапе (6). Алиса же может проверить правильность квитанции Боба, поэтому Бобу придется быть честным. Алиса легко может отправить Бобу неправильный ключ а когда он обнаружит это, его квитанция уже будет у Алисы. Вот невезуха, Боб.

Решение этой проблемы потребует некоторой коррекции протокола:

(1) Алиса шифрует свое сообщение случайным ключом DES и посылает его Бобу.

(2) Алиса создает nпар ключей DES. Первый ключ каждой пары генерируется случайным образом, а второй представляет собой XOR первого ключа и ключа шифрования сообщения.

(3) Алиса шифрует сообщение-заглушку каждым из своих 2nключей.

(4) Алиса посылает Бобу всю пачку шифрованных сообщений, проверяя, что он знает, какие сообщения какими половинами каких пар являются.

(5) Боб создаетn пар случайных ключей DES.

(6) Боб создаетпару сообщений, образующих правильную квитанцию. Хорошим вариантами могут служить "Это левая половина моей квитанции" и "Это левая половина моей квитанции" с добавлением какой-нибудь строки случайных битов. Он создает n пар квитанций, нумеруя каждую. Как и в предыдущем протоколе квитанция считается правильной, если Алиса может предъявить обе половины квитанции (с одним и тем же номером) и все ее ключи шифрования.

(7) Боб шифрует каждую свою пару сообщений парами ключей DES, i-ую пару сообщений - i-ой парой ключей, левое сообщение - левым ключом в паре , а правое - правым. в паре.

(8) Боб посылает Алисе свою пачку шифрованных сообщений, проверяя, что она знает, какие сообщения какими половинами каких пар являются.

(9) Алиса и Боб посылают друг другу все пары ключей, используя протокол рассеянной передачи. То есть, Алиса посылает Бобу независимо для каждой из n пар ключей либо ключ, использованный для шифрования левого сообщения, либо ключ, использованный для шифрования правого сообщения. Боб делает то же самое. Они могут посылать свои половинки по очереди, или сначала один может послать все n, а потом другой - это не имеет значения. Теперь и у Алисы, и у Боба есть по одному ключу из каждой пары, но никто не знает, какие из половинок получил партнер.

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

(11) Алиса и Боб посылают друг другу первые биты всех 2n ключей DES. (Если они беспокоятся, что Ева сможет прочитать эти почтовые сообщения, то они должны шифровать свой обмен битами).

(12) Алиса и Боб повторяют этап (11) для вторых битов всех 2n ключей DES, затем третьих битов и так далее, пока все биты всех ключей DES не будут переданы.

(13) Алиса и Боб расшифровывают оставшиеся половинки сообщений. Алиса получает правильную квитанцию от Боба, а Боб может выполнить "исключающее или" для любой пары ключей и пролучить ключ, которым зашифровано оригинальное сообщение.

(14) Алиса и Боб обмениваются закрытыми ключами, использованными для протокола рассеянной передачи, и каждый из них убеждается в отсутствии мошенничества.

Этапы (5)-(8) для Боба и (9)-(12) для обеих сторон не меняются по сравнению с протоколом подписания контракта. Отличие - в сообщениях-заглушках Алисы. Они предоставляют Бобу возможность проверить правильность ее рассеянной передачи на этапе (10), что заставляет ее оставаться честной на этапах (11)-(13). И, как и для протокола одновременного подписания контракта, для выполнения протокола требуются обе половины одного из сообщений Алисы.

5.9 Одновременный обмен секретами

Алиса знает секрет A, а Боб - секрет B. Алиса собирается сообщить Бобу A, если он расскажет ей B.Боб хочет сообщить Алисе B, если она расскажет ему A. Следующий протокол, подслушанный на школьном дворе, работать не будет:

(1) Алиса: "Я скажу, если ты скажешь мне первым."

(2) Боб: "Я скажу, если ты скажешь мне первой."

(3) Алиса: "Нет, ты первый."

(4) Боб: "Ну, хорошо.'' Боб шепчет Алисе.

(5) Алиса: "Ха, а я тебе не скажу."

(6) Боб: "Это не честно."

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

Алиса выполняет этапы (1)-(4), используя в качестве сообщения A. Боб выполняет эти же действия, используя в качестве своего сообщения B. Алиса и Боб выполняют рассеянную передачу на этапе (9), расшифровывают на этапе (10) те половинки, которые могут, и выполняют необходимые итерации на этапах (11) и (12). Чтобы защититься от Евы, они должны шифровать свои сообщения. Наконец, и Алиса, и Боб расшифровывают оставшиеся половины пар сообщения и выполняют XOR для любой пары ключей, чтобы получить ключи, которыми зашифрованы оригинальные сообщения.

Этот протокол позволяет Алисе и Бобу одновременно обмениваться секретами, но не гарантирует качества переданных секретов. Алиса может пообещать Бобу план лабиринта Минотавра и прислать ему схему Бостонского метро. Боб получит только тот секрет, который Алиса пришлет ему. Другие протоколы описаны в [1286, 195, 991, 1524, 705, 753, 259, 358, 415].

6 Эзотерические протоколы

6.1 Безопасные выборы

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

1. Голосовать могут только те, кто имеет на это право.

2. Каждый может голосовать не более одного раза.

3. Никто не может узнать, за кого проголосовал конкретный избиратель.

4. Никто не может проголосовать вместо другого. (Это оказывается самым тяжелым требованием.)

5. Никто не может тайно изменить чей-то голос.

6. Каждый голосующий может проверить, что его голос учитывался при подведении итогов голосования.

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

7. Каждый знает, кто голосовал, а кто нет.

Прежде чем описывать сложные протоколы, имеющие приведенные характеристики, давайте взглянем на рад протоколов попроще.

Упрощенный протокол голосования №1

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

(2) Каждый голосующий посылает свой бюллетень в ЦИК.

(3) ЦИК расшифровывает бюллетени, подводит итоги и опубликовывает результаты голосования.

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

Упрощенный протокол голосования №2

(1) Каждый голосующий подписывает свой бюллетень своим закрытым ключом.

(2) Каждый голосующий шифрует свой бюллетень открытым ключом ЦИК.

(3) Каждый голосующий посылает свой бюллетень в ЦИК.

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

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

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

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

Голосование со слепыми подписями

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

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

(2) Каждый избиратель лично маскирует все сообщения (см. раздел 5.3) и посылает их в ЦИК вместе с маскирующим множителями.

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

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

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

(6) Избиратель отправляет свой бюллетень.

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

Мэллори, избиратель-жулик, не может обмануть эту систему. Протокол слепой подписи обеспечивает единственность его бюллетени. Если он попытается отправить тот же бюллетень дважды, ЦИК обнаружит дублирование последовательных номеров на этапе (7) и не будет учитывать второй бюллетень. Если он попытается получить несколько бюллетеней на этапе (2), ЦИК обнаружит это на этапе (3). Мэллори не может создать свои собственные бюллетени, потому что он не знает закрытого ключа комиссии. По той же причине он не может перехватить и изменить чужие бюллетени.

Протокол "разрезать и выбрать" на этапе (3) должен обеспечить уникальность бюллетеней. Без этого этапа Мэллори мог бы создать точно такой же, за исключением идентификационного номера, набор бюллетеней и заверить их все в ЦИК.

Мошенническая ЦИК не сможет узнать, как голосовал конкретный избиратель. Так как протокол слепой подписи маскирует последовательные номера бюллетеней до момента подведения итогов, ЦИК не сможет установить связь между подписанным ею замаскированным бюллетенем и подытоживаемым бюллетенем. Опубликование перечня последовательных номеров и связанных с ними бюллетеней позволяет пользователям убедиться, что их бюллетени были правильно учтены.

Но проблемы все еще остаются. Если этап (6) не анонимен, и ЦИК может записать, кто какой бюллетень прислал, то она сможет узнать, кто за кого голосовал. Однако, это невозможно, если комиссия получает бюллетени в запечатанной урне для голосования и считает их позже. Хотя ЦИК и не сможет установить связь между избирателями и их бюллетенями, она сможет создать большое количество подписанных и правильных бюллетеней и смошенничать, прислав их сама себе. И если Алиса обнаружит, что ЦИК подменила ее бюллетень, она не сможет доказать этого. Аналогичный протокол, пытающийся устранить эти проблемы, описан в [1195, 1370].

Голосование с двумя Центральными комиссиями

Одним из решений является разделить ЦИК пополам. Ни у одной из них не будет достаточно власти, чтобы смошенничать по своему усмотрению.

В следующем протоколе используется Центральное управление регистрации (ЦУР), занимающееся проверкой пользователей, и отдельная ЦИК для подсчета бюллетеней [1373].

(1) Каждый избиратель отправляет письмо в ЦУР, запрашивая регистрационный номер.

(2) ЦУР возвращает избирателю случайный регистрационный номер. ЦУР ведет список регистрационных номеров. Кроме того, ЦУР хранит список получателей регистрационных номеров на случай, если кто-то попытается проголосовать дважды.

(3) ЦУР отправляет список регистрационных номеров в ЦИК.

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

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

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

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

ЦИК не может изменить бюллетени, потому что каждый избиратель будет искать свой регистрационный номер. Если избиратель не находит свой регистрационный номер или находит его в итоговом списке с другим результатом голосования, он немедленно узнает, что произошел обман. ЦИК не может добавить бюллетень в урну, которая находится под наблюдением ЦУР. ЦУР знает, сколько избирателей зарегистрировалось, их регистрационные номера и обнаружит любые изменения.

Мэллори, не обладающий избирательными правами, может попытаться смошенничать, угадав правильный регистрационный номер. Угроза этого может быть минимизирована, если множество возможных регистрационных номеров намного больше, чем множество реальных регистрационных номеров: 100-битовое число для миллиона избирателей. Конечно же, регистрационные номера должны генерироваться случайным образом.