Протоколи таємного голосування

Протоколи таємного голосування — протоколи обміну даними для реалізації безпечного таємного електронного голосування через інтернет за допомогою комп'ютерів, телефонів або інших спеціальних обчислювальних машин. Цей напрямок криптографії все ще розвивається, але вже застосовується на практиці.

Багато країн світу, вже впроваджують електронні голосування на муніципальному рівні і вище. Для впевненості у правильності, надійності та конфіденційності таких виборів і використовують протоколи з доведеною захищеністю, які спираються на перевірені криптографічні системи, наприклад асиметричного шифрування й електронного підпису. Крім того, їм потрібна готова матеріальна та юридична база. Злиття всіх цих чинників утворює безпосередній інструмент електронної демократії.

Огляд

Передумови створення

У зв'язку з бурхливим розвитком комп'ютерних мереж виникає природне «оцифрування» різних областей життя, наприклад, виникнення електронних валют. Аналогічним чином з'явилося цифрове голосування, основний інструмент електронної демократії. Довгий час механічні засоби служили в голосуваннях заміною звичайним бюлетеням або відповідали тільки за автоматичний підрахунок паперових бюлетенів. Основну роботу по перевірці голосуючих і обліку голосів проводили інші люди. При такій системі відсутня потреба у таких протоколах. Однак, в останні роки, завдяки розвитку інтернету, голосування стають повністю автоматизованими. У віддаленого голосування багато плюсів. Передбачається, що вони зручніше для кінцевих користувачів, адже люди можуть голосувати не виходячи з дому, від цього підвищується активність виборців. Підтримка електронного голосування обходиться дешевше: замість постійної друку бюлетенів досить одноразово розробити систему. Крім того, з припущення, що ніхто не може втручатися в програму на пристрої для голосування, випливає, що електронне голосування менш схильне до корупції, впливу адміністративного тиску і людського фактора.

Однак, при цьому виникає ряд специфічних проблем, що перешкоджають чесності виборів. Наприклад, при електронних виборах в Нідерландах та Франції виникли сумніви в істинності результатів, отриманих за допомогою машин. Дистанційно набагато складніше авторизувати виборця або впевнитися, що на хід голосування ніхто не вплинув. З іншого боку, інтернет надає більше можливостей для перевірки рядовими виборцями, чи правильно врахований їх голос. В даний час електронні голосування повністю легальні або частково застосовні в багатьох країнах світу. Через те що до них залучається все більше людей, посилюється необхідність у більш безпечних та ефективних методах їх проведення, для чого і були створені спеціальні криптографічні протоколи.

Досліди регламентації та реалізації

Ключовим елементом регламентації електронного голосування є закріплення його можливості в конституції держави. Такі статті мають конституції США, Швейцарії, Естонії, Великої Британії та деяких інших країн. Є група країн, до якої входять, наприклад, Фінляндія, Німеччина і Росія, які мають досвід в проведенні таких виборів, але ще не ввели їх повну регламентацію в законодавство. Зрозуміло, це не єдина бюрократична перешкода. Також потрібні специфікації на техніку, з допомогою якої голосування проводиться, способи перевірки чесності результатів, протоколи у разі зриву голосування, і створення самої технічної бази. На основі цих параметрів можна обчислити індекс готовності країни до запровадження цифрового голосування (і конкретного його протоколу).

Першою країною, яка реалізувала легальні загальнонаціональні вибори через інтернет, стала Естонія, за нею пішли Нідерланди та Швейцарія.

Поточний стан справ

У всякому разі, ні в одному законодавстві не закріплений сам протокол голосування. Так зроблено з багатьох причин, починаючи від решти недовіри до електронних методів голосування, закінчуючи більш легким переходом з поточного способу проведення на більш ефективний. Прогрес техніки дозволив задуматися про голосування через інтернет тільки близько 20 років тому^[коли?], саме тому даний розділ криптографії все ще розвивається. У нього немає загальновизнаних книг, і жоден протокол ще не отримав переважну підтримку фахівців. Проблема ускладнюється тим, що організації, які мають досвід впровадження цих систем, воліють не публікувати докладні звіти, що описують систему, і проблеми, що виникли при її введенні.

Зараз для простих опитувань або голосувань всередині малих груп застосовується тривіальний алгоритм. У випадку, коли агент підраховує голоси, не має особливої причини вести махінації, цей протокол є оптимальним варіантом. На виборах державного рівня найбільш поширені модифікації протоколу Фудзіоки — Окамото — Охта. Саме він показав найкращі результати на експериментальних виборах і створив позитивний міжнародний прецедент надійного проведення виборів через інтернет. Для нього і деяких його модифікацій існують доступні для використання приватними особами програми і електронні засоби голосування. Крім того багато науковий статей, що описують нові протоколи таємного голосування, беруть за основу саме його. Можливо, завдяки розвитку техніки і зниження ціни на високопродуктивні системи в найближчому майбутньому з'являться прецеденти використання протоколу Хе — Су. Хоча він вже має свої модифікації, на практиці цей протокол був застосований тільки в студентських експериментальних виборах. Те ж саме можна сказати і про протокол ANDOS. Хоча автори багатьох статей стверджують, що його можна ефективно реалізувати, були тільки прецеденти використання на місцевих виборах. Інші протоколи представлені як перехідні від простих до складних або можливі модифікації для досягнення додаткових цілей.

Вимоги до систем таємного голосування

Обов'язкові:

• ніхто, крім голосуючого, не повинен знати його вибір;
• тільки легітимні учасники можуть проголосувати, і притому тільки один раз;
• рішення голосуючого не може бути таємно або явно ким-небудь змінено (крім, можливо, ним самим).

Бажані:

• кожен легітимний учасник може переконатися, що його голос зарахований;
• кожен легітимний учасник може передумати і змінити свій вибір протягом певного періоду часу;
• система повинна бути захищена від продажу голосів виборцями;
• у випадку, якщо голос зараховано неправильно, кожен легітимний учасник може повідомити про це системи, не розкриваючи своєї анонімності;
• неможливо відстежити, звідки дистанційно проголосував виборець;
• автентифікація оператора;
• можна дізнатися, хто брав участь в голосуванні, а хто — ні;
• підтримання системи не повинно вимагати багато ресурсів;
• система повинна бути відмовостійка у разі технічних несправностей (втрата електроживлення), ненавмисних (втрата виборцем ключа) і злочинних (навмисне видавання себе за іншого виборця, DoS/DDoS) атак.

Справа ускладнюється не тільки тим, що учасники голосування і агентство, що його проводить мають підстави не довіряти один одному, але й тим, що сам процес голосування потрібно захищати від втручання ззовні. Якщо провести аналогію з виборами президента, то виборці повинні захиститися від вкидань бюлетенів з боку виборчого комітету, ЦВК зобов'язаний забезпечити неможливість продажу голосів громадянами, і всі разом повинні не допустити втручання агентів інших країн.

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

Простий протокол таємного цифрового голосування

Простий алгоритм електронного голосування по суті являє собою листування з електронними підписами між виборчим комітетом та безліччю виборців. Нехай тут і далі: А — агентство, що проводить електронне голосування (англ. Agency), E — виборець, легітимний учасник голосування (англ. Elector), B — цифровий бюлетень. B може містити число, ім'я кандидата, розгорнутий текст або які-небудь інші дані, що повідомляють про вибір E, які верифікують його або необхідні для посилення безпеки протоколу. Хід голосування виглядає так:

Алгоритм

Крок 1. А викладає списки можливих виборців.

Крок 2. Користувачі, в числі яких і E, повідомляють про бажання брати участь у голосуванні.

Крок 3. А викладає легітимні списки виборців.

Кроки 1-3 обов'язкові. Основна мета — визначення та оголошення числа активних учасників n. Хоча деякі з них можуть не брати участь, а деякі і зовсім не існувати («мертві душі», зловмисно внесені A), можливість маніпулювання голосуванням у A помітно знижена. Надалі ці кроки будуть вважатися за один крок «затвердити списки».

Крок 4. А створює відкритий і закритий ключ $a_{public}$$a_{private}$ викладає в загальний доступ $a_{public}$. Хто завгодно може зашифрувати повідомлення за допомогою $a_{public}$, але розшифрувати його зможе тільки А.

Крок 5. E

• створює власні публічний і приватний ключі ЕЦП $e_{public}$$e_{private}$, потім публікує відкритий ключ. Хто завгодно може перевірити документ E, але підписати його - тільки сам виборець. Цей крок пропускається, якщо A вже знає електронні підписи виборців (наприклад, вони були згенеровані при реєстрації в системі).
• формує повідомлення B, де тим або іншим способом висловлює свою волю
• підписує повідомлення особистим закритим ключем $e_{private}$
• шифрує повідомлення відкритим ключем $a_{public}$
• відправляє шифроване повідомлення A

Крок 6. A

• збирає повідомлення
• розшифровує їх за допомогою лежачого у відкритому доступі$e_{public}$
• підраховує їх і публікує результати

Особливості, переваги та недоліки

Цей протокол надзвичайно простий, тим не менш, його достатньо, щоб захиститися від зовнішнього втручання, підробки голосів і дискредитації легітимних виборців. Однак голосуючим доводиться абсолютно довіряти A, адже його робота ніким не контролюється. З одного боку, E може надати зловмиснику-покупцеві голосів доказ, як він проголосував, а з іншого — не може перевірити, що A правильно врахував або навіть отримав його бюлетень. Тому тривіальний метод можна застосовувати тільки в спільнотах, де всі довіряють один одному і агентству, що відповідає за підрахунок голосів.

Протокол двох агентств

Він же протокол Нурмі — Салома — Сантіна. Основна ідея полягає в тому, щоб замінити одне виборче агентство двома, щоб вони контролювали один одного. Нехай тут і далі V — реєстратор (validator), в обов'язки якого входить підготовка списків, а також допуск або недопуск учасника до голосування. Послідовність дій виглядає так:

Алгоритм

Крок 1. V

• створює набір розпізнавальних міток $t_{i}$
• відправляє по захищеному каналу по одній мітці кожному хто голосує
• відправляє A весь набір міток без інформації про те, яка мітка кому належить

Крок 2. E

• генерує $e_{public}$, $e_{private}$ (для цифрового підпису) и $e_{secret}$ (для того, щоб ні A, ні сторонній зловмисник не міг до потрібного часу дізнатися вміст бюлетеня)
• $e_{public}$ публікуеться
• формує повідомлення B з обраним рішенням
• підписує його $e_{private}$
• прикладає до нього отриманий $t_{i}$
• шифрує за допомогою $e_{secret}$
• знову прикладає до шифротексту $t_{i}$
• відправляє шифротекст$(t_{i},\mathrm {encrypt} \,(e_{secret},(t_{i},\mathrm {sign} \,(e_{private},B))))$ на розгляд до A

Крок 3. A

• отримує шифротекст. За зовнішнім тегом воно визначає, що повідомлення прийшло від легітимного користувача, але не може визначити, ні від якого, ні як він проголосував.
• викладає у відкритий доступ отриману пару тег-шифр

Крок 4. $e_{secret}$

Крок 5. A

• збирає ключі 
• розшифровує повідомлення 
• проводить підрахунок голосів 
• приєднує до опублікованого шифротексту бюлетень без розпізнавального тегу, на чому голосування закінчується.

Особливості, переваги та недоліки

Завдяки викладанню в загальний доступ отриманого файлу на кроці 3, A не може згодом заперечувати отримання повідомлення від E. За допомогою пари шифр-бюлетень кожен виборець може перевірити, чи правильно був врахований його голос, що усуває проблему з браком контролю над A. Однак, такий підхід лише частково вирішує проблему необхідності абсолютної довіри до агентства. У разі, якщо A і V вдається зговориться, A може маніпулювати голосуванням. Якщо агентству відомо, хто ховається під яким розпізнавальним тегом, воно може спеціально не приймати повідомлення від деяких виборців. Крім того, є проблема «мертвих душ». Якщо V внесе до списку завідомо неіснуючих виборців, то A зможе фальсифікувати бюлетені від них. У протоколах з двома агентами голосуючому не обов'язково авторизуватися і перед реєстратором і перед виборчим комітетом. Якщо виборець доведе свою особистість реєстратору, той може поставити підпис на бюлетень або ключ виборця. Саме він надалі буде грати роль допуску до голосування. Крім того, не обов'язково використовувати саме мітки для авторизування користувача. З цих причин, у подальших алгоритмах конкретний спосіб ідентифікації користувача буде опущений.

Протокол Фудзіоки — Окамото — Оти

Схема Фудзіок — Окамото — Оти, розроблена в 1992 році, ґрунтується на протоколі двох агентств та криптографічному підпису наосліп. Несильно ускладнюючи протокол, ця схема частково вирішує проблему змови двох агентств. Для роботи протоколу необхідний заздалегідь вибраний спосіб маскуючого шифрування, під яким виборець надсилає реєстратору бюлетень. Сліпе (маскуюче) шифрування — особливий вид шифрування, що дозволяє упевнитися в тому, що документ справжній і підписаний авторизованим користувачем, але не дає дізнатися, які дані в ньому містяться. Маскуюче шифрування має бути комутативним з електронним підписом, тобто $\mathrm {sign} \,(\mathrm {blind} \,(B))=\mathrm {blind} \,(\mathrm {sign} \,(B))$.

Алгоритм

Крок 1. V затверджує списки легітимних виборців

Крок 2. E

• створює $e_{public}$, $e_{private}$ (для цифрового підпису) і $e_{secret}$ (для того, щоб ні A ні сторонній зловмисник не міг до потрібного часу дізнатися вміст бюлетеня)
• готує повідомлення B з вибраним рішенням 
• шифрує його $e_{secret}$
• накладає шар сліпучого шифрування
• підписує його $e_{private}$
• відправляє V $\mathrm {blind} \,(\mathrm {sign} \,(e_{private},\mathrm {encrypt} \,(e_{secret},B)))$

Крок 3. V

• створює $v_{public}$ и $v_{private}$, публічний ключ викладається в загальний доступ 
• засвідчується, що бюлетень дійсний і належить легітимному виборцю який ще не голосував 
• підписує його $v_{private}$
• повертає його E

Крок 4. E знімає з бюлетені шар маскуючого шифрування (в силу комутативності залишається$\mathrm {sign} \,(v_{private},\mathrm {sign} \,(e_{private},\mathrm {encrypt} \,(e_{secret},B)))$) і надсилає його A

Крок 5. A

• перевіряє підписи E і V
• поміщає все ще зашифровану $e_{secret}$ бюлетень в спеціальний список, який буде опублікований після того як всі виборці проголосують або після закінчення заздалегідь обумовленого терміну

Крок 6. Після того як список з'являється у відкритому доступі, E висилає A $e_{secret}$

Крок 7. A

• розшифровує повідомлення 
• підраховує результати

Протокол Sensus

Лоррі Кранор і Рон Сітрон (Lorrie Faith Cranor, Ron K. Cytron) в 1996 запропонували модифікацію протоколу Фудзіока-Окамото-Охта під назвою Sensus. Відмінність полягає в кроках 5-6. Після того, як A отримало зашифроване повідомлення від E, воно не тільки додає його в список, що публікується, а додатково надсилає підписаний бюлетень назад виборцю як квитанцію. Таким чином E не потрібно чекати, поки проголосують всі інші, і він може закінчити голосування за одну сесію. Це не тільки зручно для кінцевого користувача, але ще і надає додатковий доказ, що E брав участь у виборах. Крім того, в Sensus регламентовані додаткові допоміжні модулі, які спрощують і автоматизують хід голосування.

Особливості, переваги та недоліки

Тепер навіть якщо агентствам вдасться змовитися, A не зможе впізнати виборців до того, як отримає ключ. Хоча воно все ще має можливість не приймати повідомлення, відпадає можливість ігнорувати повідомлення конкретно від «небажаних» виборців. Залишається лише проблема подачі голосів виборців, які не прийшли на вибори. Крім того, щоб дозволити виборцю переголосувати, в тому числі і через технічну помилку, необхідний додатковий модуль.

На даний момент протокол Фудзіока-Окамото-Охта (а також його модифікації, включаючи і Sensus) є одним з найбільш перевірених протоколів дистанційного електронного голосування. Саме його варіація була застосована на електронних виборах в Естонії. Інша модифікація протоколу Фудзіока-Окамото-Охта була використана для проведення виборів до органів самоврядування серед студентів Принстонського університету. Модулі Sensus були написані під системою UNIX з використанням криптографічної бібліотеки RSAREF, так що будь-хто може ними скористатися.

Протокол He-Su

У 1998 році Ци Хе і Чжунмінь Су (Qi He, Zhongmin Su) представили ще більш просунутий порівняно з Sensus протокол голосування. Цей алгоритм задовольняє більшій частині вимог до безпечного протоколу цифрового голосування. Як і Sensus, He-Su використовує ідею сліпого підпису, але підписується не бюлетень виборця, а його ключ. Це дозволяє виборцям змінювати своє рішення до кінця голосування і ще більше звужує можливості реєстратора та виборчого агентства у випадку змови. Для цього протоколу потрібний заздалегідь обумовлений спосіб сліпучого шифрування і хеш-функція $\mathrm {h} \,()$. Як і в протоколі Фудзіока-Окамото-Охта маскуюче шифрування має бути коммутативним з електронним підписом V: $\mathrm {sign} \,(\mathrm {blind} \,(B))=\mathrm {blind} \,(\mathrm {sign} \,(B))$, а також $\mathrm {sign} \,(A*B)=\mathrm {sign} \,(A)*\mathrm {sign} \,(B)$

Алгоритм

Крок 1. V

• затверджує списки легітимних виборців
• створює $v_{public}$ і $v_{private}$ (використовуються для асиметричного шифрування)
• $v_{public}$ викладається у вільний доступ

Крок 2. E

• створює $e_{public}$ і $e_{private}$ (використовуються для підписів)
• обчислює хеш-функцію від публічного ключа: $\mathrm {h} \,(e_{public})$
• накладає шар маскуючого шифрування на $\mathrm {h} \,(e_{public})$. $f=\mathrm {encrypt} \,(v_{public},x)\mathrm {h} \,(e_{public})$
• відсилає $f$ V

Крок 3. V

• перевіряє легітимність виборця
• дешифрує $f$: $g=\mathrm {decrypt} \,(v_{private},\mathrm {encrypt} \,(v_{public},x)\mathrm {h} \,(e_{public}))=x\mathrm {decrypt} \,(v_{private},\mathrm {h} \,(e_{public}))$. Часть $e_{public}^{signed}=\mathrm {decrypt} \,(v_{private},\mathrm {h} \,(e_{public}))$ вважається підписаним ключем
• відсилає $g$ E

Крок 4. E

• знімає шар сліпучого шифрування (множить на зворотний елемент x) і отримує підписаний ключ $e_{public}^{signed}$
• перевіряє справжність підпису реєстратора: чи виконується$\mathrm {encrypt} \,(v_{public},\mathrm {decrypt} \,(v_{private},\mathrm {h} \,(e_{public})))=\mathrm {h} \,(e_{public})$
• відсилає A пару $(e_{public},e_{public}^{signed})$

Крок 5. A

• як і E перевіряє справжність підпису реєстратора
• перевіряє, чи збігається хеш-функція від $e_{public}$ в парі з тією, що зберігається в $e_{public}^{signed}$
• додає $e_{public}$ в список авторизованих ключів і повідомляє про це E

Крок 6. E

• створює $e_{secret}$(використовується для шифровки бюлетенів, щоб ні A ні зовнішній зловмисник до потрібного часу не міг дізнатися вміст бюлетеня) 
• готує повідомлення B з обраним рішенням 
• відправляє A набір: $(e_{public},\mathrm {encrypt} \,(e_{secret},B),\mathrm {sign} \,(e_{private},\mathrm {h} \,(\mathrm {encrypt} \,(e_{secret},B))))$

Крок 7. A

• перевіряє авторизованість ключа
•  перевіряє достовірність повідомлення порівнюючи хеш зашифрованого повідомлення і хеш, отриманий за допомогою $e_{private}$
• публікує трійку у відкритому списку

Крок 8. Поява трійки у відкритому списку сигналізує E відправити A новий набір: $(e_{public},e_{secret},\mathrm {encrypt} \,(e_{private},\mathrm {h} \,(e_{secret})))$

Крок 9. A

• перевіряє достовірність повідомлення, порівнюючи хеші 
• розшифровує раніше отриманий бюлетень 
• публікує інформацію про всі дані
•  підраховує результат

Крок 10. Після голосування V публікує список всіх зареєстрованих виборців, а A - список всіх авторизованих ключів.

Особливості, переваги та недоліки

Схема He-Su відповідає майже всім вимогам до протоколу таємного голосування. Залишається тільки підвищений стимул купівлі/продажу голосів. у A і V тепер немає можливості зшахраювати, так як тепер публікуються всі списки: можливих виборців, зареєстрованих і авторизованих ключів. Відповідно, не можна внести неіснуючих виборців, ні голосувати за існуючих, які не прийшли. При цьому під час складання цих списків ні виборче агентство ні реєстратор додаткової інформації не отримують. У виборців є можливість змінити голос. Основний недолік протоколу He-Su — його порівняльна складність. Так як для підтримки протоколу необхідно велика кількість ресурсів, він вразливий перед DoS-атаками.

Протокол на основі ANDOS

За основу взято протокол ANDOS (англ. All or Nothing Disclosure Of Secrets). Ідея полягає в тому, щоб посилити стійкість протоколу за рахунок заміни заздалегідь обраного шифрування секретним ключем на хешування користувальницькою функцією. Далі описано ядро алгоритму. В описі для стислості опущені заходи безпеки. У разі необхідності можна застосувати методи криптографії на відкритих ключах і електронного підпису. Передбачається, що для захисту від втручання кого-небудь ззовні виборці можуть і змішувати інформацію між собою, але тоді зловмисний виборець може вносити перешкоди до голосування, тому цей крок теж пропущено.

Алгоритм

Крок 1. A

• затверджує список учасників голосування;
• нехай набралося n легітимних виборців. Тоді A вибирає не менше ніж n ідентифікаторів і застосовує ANDOS протокол до голосуючим. Ідентифікатори - великі прості числа, вони пронумеровані від $1,...,n$.

Крок 2. E

• вибирає номер i і отримує i-е просте число $p_{i}$списку (A нічого не знає про взаємозв'язок між i і E )
• вибирає криптографічну геш-функцію $h_{E}(x,y)$ двох змінних
• пересилає A пару $(p_{i},h_{E}(p_{i},v_{E}))$, де $v_{E}$ — вибір (Ім'я кандидата, або в більш загальному вигляді, вибіркова стратегія) виражений чисельно

Крок 3. A публікує $h_{E}(p_{i},v_{E})$.

Крок 4. Після появи $h_{E}(p_{i},v_{E})$E визначає A пару $(p_{i},h_{E}^{-1})$. $h_{E}(x,y),x$ и $h_{E}^{-1}$, A тепер знає зв'язок між $p_{i}$ і $v_{E}$ (але не між E і його вибором $v_{E}$).

Спрощена версія кроків 2-4 може полягати в тому, що E посилає A безпосередньо пару $p_{i},v_{E}$. Проте, в цьому випадку буде неможливо E як перевірити зарахований голос правильно, так і переголосувати на більш пізній стадії. Так може вийти, так як якщо A публікує ідентифікатор $p_{i}$ у списку тих, хто дотримувався стратегії $v_{E}$, то E буде точно знати, що його голос зарахований правильно, однак згодом хто-небудь зможе замаскуватися під володіє ідентифікатором $p_{i}$і змінити голос на угодний йому. З іншого боку, якщо A публікує тільки кількість учасників, які дотримуються певної стратегії $v_{E}$, то учасники не можуть нічого перевірити і A може публікувати будь-які результати виборів. Хеш-функції використовуються для того, щоб зловмисники не могли визначити кількість голосів з певною стратегією $v_{E}$ (ця інформація виявляється корисною), так як задача знаходження початкових значень обчислювально важка з урахуванням характерного часу проведення голосування.

Крок 5. Коли голосування підходить до кінця, A оголошує проміжні результати, публікуючи списки стратегій (кандидатів) з числами $h_{E}(p_{i},v_{E})$, відповідними учасникам, які голосували за $v=v_{E}$.

Крок 6. Якщо учасник E зауважує, що його голос розміщений у невірному списку, то він посилає A скаргу у вигляді трійки $(p_{i},h_{E}(p_{i},v_{E}),h_{E}^{-1})$, яка явно показує вірність або помилковість результату.

Через деякий час можна почати процедуру зміни голосів (див. фінальний крок). Більш простий варіант (Крок 8) може бути використаний для проведення єдиного кола повторного голосування.

Крок 7. Учасник E, який хоче змінити свій вибір, відправляє A трійку $(p_{i},h_{E}(p_{i},v_{E}),v'_{E})$, де $v'_{E}$ — нова стратегія. Коли підходить кінець туру зміни голосів, A публікує змінені результати. Потім повторюється перевірка правильності.

Крок 7'. Все так само як і в кроці 7, але тепер учасник E відправляє пару $(p_{i},h'_{E}(p_{i},v'_{E}))$, де $h'_{E}$ — нова геш-функція, вибрана E. A засвідчує отримання повідомлення, публікуючи $h'_{E}(p_{i},v'_{E})$, після його E відсилає A пару $(p_{i},(h'_{E})^{-1})$. Тепер A знає взаємозв'язок між $p_{i}$ і $v'_{E}$. При повторному підведенні результатів $h_{E}(p_{i},v_{E})$ видаляється з відповідного списку, а $h'_{E}(p_{i},v'_{E})$ додається в список з $v^{'}=v'_{E}$. Учасник E може оскаржити результат як і раніше.

Порівняно з Кроком 8, Крок 8' має перевагу в тому, що учасники, відмінні від E, можуть лише спостерігати, що що-небудь зникло зі списку $v$, але не будуть знати, що воно перемістилося в список $v^{'}$.

Особливості, переваги та недоліки

У протоколі ANDOS можлива ситуація, коли два голосуючих виберуть одне і те ж i, таким чином отримавши однаковий ідентифікатор $p_{i}$. Можливі рішення цієї проблеми:

• A засвідчується, що число ідентифікаційних номерів настільки більше числа голосуючих, що ймовірність колізії мізерно мала.
• При повторному отриманні ідентифікатора $p_{i}$, A публікує пару $(p'_{i},h_{E}(p_{i},v_{E}))$, де $p'_{i}$ — ідентифікатор, який був не «на продаж» в протоколі ANDOS. По другій компоненті учасник E бачить, що він під питанням і відправляє A пару $(p'_{i},h_{E}(p'_{i},v_{E}))$. Інші учасники не можуть цього зробити, так як вони не знають хеш-функції $h_{E}$. Далі процес йде за тією ж схемою: A публікує $h_{E}(p'_{i},v_{E})$ і т. д. Після отримання $h_{E}^{-1}$, A засвідчується, що відгукнувся потрібний учасник.

Протокол ANDOS досить затратний, зате для нього не потрібен незалежний реєстратор V. Виборцям необхідно вибирати і пересилати не тільки ідентифікатори, але і хешуючі функції, що може бути складно або довго. А все ще може шахраювати, розподіляючи за своїм вибором голоси тих, хто заявив про свій намір взяти участь у голосуванні, але так і не зробив свій вибір, а E мають підвищений стимул купівлі/продажу голосів, так як можна переконатися в результаті угоди.

Інші протоколи

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

Наприклад, протокол двох агентств можна поширити на $n$ виборчих центрів, що представляють різні опозиційні, але зацікавлені в чесних виборах фракції. У цьому випадку розподіл голосів може бути підроблено лише якщо всі центри виявляться у змові, що не має сенсу за умовою. Такий алгоритм використовує якусь схему неінтерактивного публічного перевіряємого розділення секрету (англ. NIVSS — Non-Interactive Verifiable Secret Sharing). В залежності від обраного способу поділу секрету (хто за кого проголосував) протокол може мати різну стійкість до різних атак і різну швидкість обробки даних. Хороший результат показує, наприклад, використання проблеми дискретного логарифмування для забезпечення приховування даних.

Головним недоліком системи є те, що хоча сфальсифікувати результати можуть тільки всі виборчі центри разом, зірвати хід виборів може будь-який з них поодинці. Вирішенням дилеми є ще одна модифікація алгоритму, коли розподіл голосів можуть відновити $k<n$ центрів. Але тоді і підробити результати зможуть $k$ центрів, що змовилися, а зірвати вибори — $n-k$. Схема може бути покращена, щоб допускати кілька варіантів відповіді у бюлетені, а також поетапне або паралельне голосування. Додатковий плюс: за такої системи виборець не може довести, за кого він проголосував, що робить надзвичайно важкою купівлю/продаж голосів.

Для роботи даного протоколу необхідний примітив «дошка бюлетенів» — область даних, яку можуть читати всі повністю, а писати тільки кожен у свою частину. По суті це — загальна область пам'яті з доступом по мережі і деякими криптографічними обмеженнями. Якщо у виборах бере участь $n$ центрів голосувань $A_{1},...,A_{n}$ і $m$ виборців $E_{1},...,E_{m}$, то кількість біт, необхідна для дошки бюлетенів — $O(nmk)$, де k — деяка змінна криптостійкості, пропорційна кількості біт ключа.

Серед інших спеціальних криптографічних примітивів можна виділити «збирача» (англ. Pollster) — зручний інтерфейс між користувачем і системою. Ідея в тому, що виборець-людина може віддати бюлетень збирачеві, а той виконає за нього всю роботу по шифруванню та обміну даними з іншими сторонами. Виборець повинен повністю довіряти даному модулю. Це сильне умова, однак його досить просто реалізувати, адже складальник запущений на машині голосуючого.