Криптографические алгоритмы

Функциональность системы реализуется с использованием надежных, современных криптографических методов. В основе взаимодействия компонентов системы лежит MPC-протокол (Multi-Party Computation). Это криптографический протокол, позволяющий нескольким участникам произвести вычисление, зависящее от тайных входных данных каждого из них, таким образом, чтобы ни один участник не смог получить никакой информации о чужих тайных входных данных. Данный протокол обеспечивает процесс шифрования, в котором несколько сторон сначала участвуют в вычислении общего публичного ключа и соответствующего ему набора приватных ключей, а затем производят пошаговую расшифровку данных.

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

Процедура шифрования данных

Процедура шифрования данных

Протокол DKG Pedersen 91 на эллиптических кривых

DKG (Distributed Key Generation) - протокол, позволяющий N DecryptService:

  • формировать общий публичный ключ голосования MainPublicKey;

  • публиковать в блокчейн данные, необходимые для вычисления MainPublicKey всеми сторонами голосования;

  • согласованный набор приватных ключей, соответствующих MainPublicKey.

Важно

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

После публикации нового голосования, MasterServer опрашивает доступные DecryptService и формирует индексированный список N сервисов, после чего каждый DecryptService получает свой порядковый номер. Это необходимо для реализации протокола DKG Pedersen 91.

Каждый DecryptService генерирует публичный и приватный ключи (PUBi и PRIVi) для участия в голосовании. Чтобы избежать публикации публичных ключей в блокчейн DecryptService вычисляют и публикуют Pedersen commit и соответствующий скаляр (Ci и ri). Это позволяет всем участникам голосования вычислить публичные ключи каждого DecryptService и общий ключ голосования MainPublicKey.

Для реализации схемы «K из N», DecryptServices обмениваются дополнительной информацией. При этом ключи не передаются по сети, и каждый DecryptService знает только свой приватный ключ Si. Для этого каждый DecryptService генерирует случайным образом полином fi(x) степени K-1, вычисляет для каждого из N серверов значение полинома, соответствующее его порядковому номеру - Fi,j. Это значение называется «тенью». «Тень», а также значения коэффициентов полинома, вычисляются и публикуются в блокчейн каждым DecryptService для всех остальных серверов, что позволяет восстановить зашифрованные итоги выборов, даже если некоторые DecryptService будут недоступны. Обмен дополнительной информацией необходим для согласованного формирования приватных ключей для расшифровки итогов голосования.

После проверки корректности опубликованных «теней», каждый DecryptService вычисляет приватный ключ Si.

Важно

Приватный ключ не покидает пределов сервера и позволяет в последствии произвести «предварительную» расшифровку итогов выборов.

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

ElGamal шифрование на эллиптических кривых

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

Схема шифрования ElGamal позволяет реализовать гомоморфное относительно сложения шифрование.

\[ENCRYPTED (1) + ENCRYPTED (1) = ENCRYPTED (2)\]

Чтобы использовать указанное выше свойство алгоритма, заполненный бюллетень в электронном виде представляется как строка нулей и единиц. Количество символов соответствует количеству вариантов выбора, выбранный вариант представляется единицей, остальные нулями.

Пример использования ElGamal шифрования

Пример использования ElGamal шифрования

Для предотвращения ошибок пользователя или ПО, либо злонамеренных попыток испортить бюллетень, система осуществляет проверку зашифрованных голосов, опираясь на алгоритмы доказательства с нулевым разглашением - ZKP (Zero-Knowledge Proofs).

Заполненный бюллетень FILLED_FORMu шифруется в приложении пользователя ключом MainPublicKey и публикуется в блокчейн (E(Fu)). Шифрование происходит на стороне клиентского приложения, таким образом в открытом виде голос пользователя не покидает его устройства (смартфон либо персональный компьютер).

После завершения голосования DecryptService получает возможность произвести подсчет голосов в зашифрованном виде E(∑(Fu)) и выполнить «частичное снятие» криптографической защиты. Расшифровка данных секретными ключами Si каждого отдельного DecryptService не дает «читаемых» итогов голосования, это предварительные результаты, которые каждый сервер публикует в блокчейн. Помимо этого, каждый DecryptService прикладывает ZKP того, что он корректно произвел расшифровку. Это позволяет предотвратить срыв подведения итогов голосования злонамеренным DecryptService.

После того как К или более серверов опубликовали результат «частичного» расшифрования, MasterServer агрегирует эти данные и производит окончательную расшифровку. Расшифрованные данные не содержат информации по голосам конкретных участников, что обеспечивает их анонимность.

Итоги голосования RESULTS публикуются в блокчейн.

Важно

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

Доказательства с нулевым разглашением

ZKP - Zero-Knowledge Proofs - это криптографическая техника, позволяющая предоставить доказательство обладания некоторой информацией без разглашения самой информации. Ниже представлена иллюстрация концепции ZKP.

Иллюстрация концепции ZKP

Иллюстрация концепции ZKP

Участник «A» обладает ключом, открывающим дверь в лабиринте, и хочет доказать это участнику «B», но не хочет показывать ключ. Чтобы «В» мог убедиться в верности утверждения «А», они организуют серию испытаний:

  1. «А» заходит в лабиринт пока «В» отвернулся. «В» не знает в какую сторону пошел «А».

  2. «В» дает «А» указание выйти с какой-либо стороны, например слева.

  3. Если «А» действительно обладает ключом, он может появиться с любой стороны и выполняет указание «В».

Шанс того, что «А» просто повезло, и он, не имея ключа, изначально пошел налево составляет 50/50. Поэтому они повторяют испытание еще раз и еще, пока вероятность «везения» не станет пренебрежимо малой, и «В» не признает, что «А» действительно обладает ключом. При этом «В» не увидит самого ключа, не получит никакой информации, которой обладает А (направление, которое «А» выбирает в каждом испытании), но в результате серии испытаний он получит достоверное (вероятностное, но с любой необходимой «В» точностью) доказательство.

ZKP разделяют на 2 типа:

  1. ZK Range Proofs.

  2. ZK Decryption Proofs.

ZK Range Proofs

ZK Range Proofs - это доказательство диапазона. Используется при публикации зашифрованного бюллетеня.

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

  1. Участник не зашифровал в бюллетене значение 100 000, что повлияло бы на итог голосования при «зашифрованном суммировании».

  2. По каждому вопросу отмечен только один вариант (единственный ответ «да» = 1).

Это достигается проверкой того, что сумма всех значений бюллетеня по указанному вопросу равна 1, а значение каждого отдельного варианта находится в диапазоне от 0 («нет») до 1 («да»).

ZK Decryption Proofs

ZK Decryption Proofs - доказательство расшифровки. Используется при публикации каждым DecryptService результатов предварительной расшифровки итогов голосования.

В связи с необходимостью получения не менее K корректных сообщений с предварительными результатам, для того чтобы MasterServer мог получить и опубликовать итоги выборов, необходимо убедиться, что каждый DecryptService на самом деле опубликовал расшифровку именно суммы зашифрованных бюллетеней, а не произвольного текста. Это достигается формированием и проверкой Chaum-Pedersen Zero-Knowledge Proofs.