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

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

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

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

Першою країною, яка реалізувала легальні загальнонаціональні вибори через інтернет, стала Естонія[12], за нею пішли Нідерланди та Швейцарія. У Росії протоколи таємного електронного голосування застосовувалися поки що тільки на експериментальному рівні (наприклад, на форумі " Селігер-2009), але в ЦВК була висловлена ініціатива про розвиток електронного голосування, зокрема, в інтересах громадян РФ за кордоном[13].

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

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

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

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

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

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

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

Крок 5. E

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

Крок 6. A

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

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

Крок 1. V

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

Крок 2. E

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

Крок 3. A

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

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

Крок 5. A

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

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

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

Крок 2. E

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

Крок 3. V

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

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

Крок 5. A

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

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

Крок 7. A

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

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

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

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

Крок 1. V

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

Крок 2. E

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

Крок 3. V

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

Крок 4. E

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

Крок 5. A

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

Крок 6. E

• створює ${\displaystyle e_{secret}}$(використовується для шифровки бюлетенів, щоб ні A ні зовнішній зловмисник до потрібного часу не міг дізнатися вміст бюлетеня) 
• готує повідомлення B з обраним рішенням 
• відправляє A набір:https://wikimedia.org/api/rest_v1/media/math/render/svg/686ecd1d215bcb5f532d4557c42ba9ce3ccda8c8

Крок 7. A

• перевіряє авторизованість ключа
•  перевіряє достовірність повідомлення порівнюючи хеш зашифрованого повідомлення і хеш, отриманий за допомогоюhttps://wikimedia.org/api/rest_v1/media/math/render/svg/80c685e05754f0c1ddd813fbc2f4ee83bcc04d97
  
• публікує трійку у відкритому списку

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

Крок 9. A

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

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

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

Крок 1. A

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

Крок 2. E

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

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

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

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

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

Крок 6. Якщо учасник E зауважує, що його голос розміщений у невірному списку, то він посилає A скаргу у вигляді трійки ${\displaystyle }$, яка явно показує вірність або помилковість результату.

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

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

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

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

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

• A засвідчується, що число ідентифікаційних номерів настільки більше числа голосуючих, що ймовірність колізії мізерно мала.
• При повторному отриманні ідентифікатора ${\displaystyle }$, A публікує пару ${\displaystyle }$, де ${\displaystyle }$ — ідентифікатор, який був не «на продаж» в протоколі ANDOS. По другій компоненті учасник E бачить, що він під питанням і відправляє A пару ${\displaystyle }$. Інші учасники не можуть цього зробити, так як вони не знають хеш-функції ${\displaystyle }$. Далі процес йде за тією ж схемою: A публікує ${\displaystyle }$ і т. д. Після отримання ${\displaystyle }$, A засвідчується, що відгукнувся потрібний учасник.

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