Відкрита мережа голосування

У криптографії відкрита мережа голосування — це захищений протокол багатосторонніх обчислень для обчислення функції логічного підрахунку: а саме, заданий набір двійкових значень 0/1 у вхідних даних, обчислити загальну кількість одиниць без розкриття кожного окремого значення. Цей протокол був запропонований Фен Хао, Пітером Райаном і Пьотром Зелінським у 2010 році. Він розширює мережевий протокол анонімного вето Хао та Зелінського, дозволяючи кожному учаснику підраховувати кількість голосів вето (тобто одиниць на вході логічної функції АБО), зберігаючи при цьому анонімність тих, хто проголосував. Протокол можна узагальнити для підтримки ширшого діапазону вхідних даних, крім двійкових значень 0 і 1.

Опис

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

1 тур : кожен учасник $i$ вибирає випадкове значення $x_{i}\,\in _{R}\,\mathbb {Z} _{q}$ і публікує ефемерний відкритий ключ $g^{x_{i}}$ разом із доведенням з нульовим розголошенням для доказу знання експоненти $x_{i}$ . Такі докази можна реалізувати за допомогою неінтерактивних доказів із нульовим знанням Шнорра, як описано в RFC 8235.

Після цього раунду кожен учасник обчислює:

$g^{y_{i}}=\prod _{j<i}g^{x_{j}}/\prod _{j>i}g^{x_{j}}$

2 тур : кожен учасник $i$ видає $g^{x_{i}y_{i}}g^{v_{i}}$ де $v_{i}$ дорівнює 0 або 1 разом із доведенням з нульовим розголошенням «1 із 2» для доказу того, що $v_{i}$ є одним із $\{0,1\}$ . Такі докази 1 із 2 можуть бути реалізовані за допомогою техніки доказів із нульовим знанням Крамера, Дженнаро та Шенмейкерса.

Після 2 раунду кожен учасник обчислює $\prod _{i}g^{x_{i}y_{i}}g^{v_{i}}=g^{\sum _{i}v_{i}}$ . Зверніть увагу, що всі значення $x_{i}$ зникають, тому що $\sum _{i}{x_{i}y_{i}}=0$ . Показник ступеня $\sum _{i}v_{i}$ представляє кількість одиниць. Оскільки це зазвичай невелике число, кількість можна обчислити шляхом вичерпного пошуку.

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

Максимальна секретність

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

Застосування

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

Існують стандартні методи розширення виборів одного кандидата для підтримки можливості кількох кандидатів. Простий метод полягає в тому, щоб проводити вибори одного кандидата паралельно для кількох кандидатів, і кожен виборець дає відповідь «Так/Ні» кожному з кандидатів. Якщо виборець обмежений голосуванням лише за одного кандидата, необхідні додаткові докази нульового знання. Інший метод полягає в зміні кодування кандидатів: замість використання 0 і 1 для «Ні» і «Так» під час виборів з одним кандидатом, слід закодувати кожного кандидата унікальним номером, щоб можна було однозначно обчислити результат для кожного кандидата. У цьому випадку замість цього використовується більш загальне підтвердження нульового знання 1 з n, де n — кількість кандидатів.

Реалізація

Прототип реалізації відкритої мережі голосування був представлений Маккоррі, Шахандашті та Хао на Financial Cryptography'17 як смарт-контракт на блокчейні Ethereum. Вихідний код є загальнодоступним. Ця реалізація є частиною рішення команди Університету Ньюкасла «Видалення довірених органів підрахунку: самодостатнє електронне голосування через Ethereum», яке посіла третє місце в конкурсі Economist Cybersecurity Challenge 2016, спільно організованому The Economist і «Лабораторією Касперського».