Post-quantum lattice-based E-voting for multiple candidates.pdf Введение В работе [1] представлена схема электронного голосования, безопасность которой основана на сложности задач на решётках: M-SIS и M-LWE [2]. Считается, что эти задачи являются сложными как для классического, так и для квантового компьютера, то есть получившаяся схема является постквантовой. Предложенная в [1] схема обеспечивает конфиденциальность голоса и проверяемость результатов, в качестве голоса выступает значение из {0. 1}, то есть голосование производится за одного кандидата. Авторы предлагают способ расширения схемы при участии в голосовании нескольких кандидатов, однако их способ неэффективен. Настоящая работа посвящена эффективному расширению постквантовой схемы электронного голосования из [1] для нескольких кандидатов. В связи с этим модель безопасности схемы и доказательство безопасности аналогичны оригинальной. Основные отличия заключаются в следующем: - В качестве голоса выступает вектор v G {0.1}Nc (Nc - количество кандидатов), для которого можно потребовать, чтобы его вес был равен единице. Основной сложностью такого расширения схемы для нескольких кандидатов является возможность доказательства, что голос в отправляемом бюллетене правильно сформирован. - Так как голос уже не элемент из {0.1}, то для данной схемы разработано новое доказательство корректности голоса в публикуемом бюллетене, именуемое в дальнейшем VProof. Соответственно, доказательство OR-proof заменено на VProof. - Используется более эффективное амортизированное доказательство открытия. В основе схемы лежат такие криптографические конструкции, как доказательства с нулевым разглашением и схема обязательства (commitment scheme). 1. Криптографические конструкции В эффективных криптографических схемах на решётках вычисления обычно проводятся в кольце Rq = Zq[X]/(Xd+1) для простого q и целого d, являющегося степенью двойки. Для различных q. d многочлен Xd + 1 может разлагаться в кольце Zq на произведение многочленов меньшей степени. Пусть l|d и q - 1 = 2l mod 4l, тогда, согласно [3, Theorem 2.3], xd +1 = П (Xd/l - zi). iez2i где Xd/l - Zi является неприводимым над Zq многочленом, а Zi пробегает все 2l корней из единицы. В Zq не существует элементов, порядок которых больше 2l. Подобное разложение позволяет работать с многочленами аналогично Китайской Теореме об остатках. Определим такое отображение NTT, которое переводит многочлен m G Rq в набор многочленов NTT(m) = (-0..... -l-1), где -i = - mod (Xd/l - Z2i+1). Многочлены mo,...,mi-1 будем называть NTT-коэффициентами m. Вектор v можно разбить на блоки из l коэффициентов и представить его в виде многочленов mx,... ,m^Nc/i'] E Rq, таких, что NTT-коэффициенты mi являются i-м блоком вектора v (последний блок дополняется нулями). В таком представлении NTT-коэффициентами являются многочлены нулевой степени. Определение 1 [4]. Для открытой случайной матрицы Bo E r^'-''1А 1") и открытых случайных векторов bx,... , bn E Rq^ + х +l, а также секретного короткого вектора r x(x+A+n)d из распределения шума х обязательством к сообщениям mx,... , mn E Rq является t0 = B0r, t = (bx, r) + mi, tn = (bn, r) + mn, где размер открытых векторов и матрицы зависит от количества сообщений n и параметров к и Л, от которых зависит сложность задач M-SIS и M-LWE соответственно (стоит отметить, что сложность зависит и от других параметров, например d и х). Чтобы открыть данное обязательство, достаточно опубликовать вектор r, для которого выполняется равенство t0 = Bor. Сообщения mi находятся как ti - (bx, r). Задача нахождения mi из обязательства сводится к задаче M-LWE, задача получения другого открытия r* -к M-SIS. Наиболее эффективные схемы получаются при таком выборе параметров, что обе задачи имеют примерно одинаковую стойкость. Схема обладает важным гомоморфным свойством: при сложении обязательств получается обязательство к сообщению, равному сумме исходных сообщений, однако в этом случае используется вектор r с большими коэффициентами, из-за чего стойкость одной из задач ниже. То есть параметры в этом случае необходимо выбрать так, чтобы как исходное обязательство, так и их сумма были безопасными. Соответственно при суммировании большого числа обязательств схема может стать неэффективной. Иногда возникает необходимость доказать, что опубликовавший обязательство действительно может предоставить короткий r (не опубликовывая его), которое открывает обязательство. Такое доказательство называется доказательством открытия (opening proof ). Определение 2. Амортизированным доказательством открытия для обязательств (toПtiП ... ||tn)i, i = 1,... ,p, является протокол между доказывающим и проверяющим, в результате которого проверяющий убеждается, что доказывающий знает ri*, такие, что ct0,i = Bor* для короткого обратимого многочлена с и вектора r* с несколько большими по сравнению с ri коэффициентами. В результате амортизированного доказательства открытия доказывается более слабое относительно желаемого утверждение. Выбирать параметры необходимо так, чтобы найти такие ri* было трудно. Так как для всех обязательств используется один и тот же фиксированный многочлен с, эти обязательства можно гомоморфно складывать. В работе используется амортизированное доказательство открытия из [5, Section 3], которое является более эффективным по сравнению с используемым в [1]. Доказательство VProof, позволяющее доказать, что голос является правильно сформированным в предоставленном обязательстве, реализуется на основе доказательства произведения [6] и доказательства неструктурированной линейной связи (unstructured linear relation) [7]. Доказательство произведения для обязательства к сообщениям m1, m2, m3 направлено на доказательство m1 • m2 = m3. Модифицируем его таким образом, чтобы доказывать mi(mi - 1) = 0 (эта модификация достаточно простая и не влияет на безопасность доказательства, однако конкретные детали опустим). При умножении многочленов из Rq их NTT-коэффициенты умножаются покоординатно. В итоге для каждого NTT-коэффициента m выполняется m(m - 1) = 0 (mod Xd/l - zj), а так как Xd/l - Zj является неприводимым многочленом, то m равняется либо 0, либо 1. В итоге для обязательства можно доказать, что NTT-коэффициенты его сообщений являются двоичной строкой. Так как вектор v дополняется нулями до кратности l, то для mn уравнение изменяется на mn(mn - m') = 0, где NTT-коэффициенты m' сначала единицы, а потом нули, причём количество нулей равно l- (Nc mod l). То есть в итоге доказывается принадлежность NTT-коэффициентов {0,1}Nc. С помощью доказательства неструктурированной линейной связи для открытой матрицы A G Zq'^'11 и открытого вектора u G Za можно доказать Av = и. Нас интересует случай a = 1, A = (1... 1), u = (1), то есть сумма коэффициентов вектора v должна быть равна единице. Доказательство VProof можно воспринимать как одновременное применение этих двух доказательств. Стоит заметить, что доказательство неструктурированной линейной связи используется для классического понимания голосования, то есть выбор ровно одного кандидата из многих. Это доказательство можно опустить, тогда правильным голосом будет считаться голос за любое подмножество кандидатов. Или можно в качестве A и u брать более сложные конструкции для обеспечения каких-то нетривиальных требований на голоса. Доказательства произведения и неструктурированной линейной связи в оригинальных работах представлены как интерактивные протоколы, для которых доказаны свойства корректности и полноты, а также нулевого разглашения, если проверяющий является честным. Приведём (неформальную) теорему о свойствах интерактивного протокола для VProof. Теорема 1. Интерактивный протокол для доказательства VProof обладает следующими свойствами: - Полнота (Completeness): честный доказывающий убеждает честного проверяющего с вероятностью, близкой к единице. - Корректность (Soundness): существует извлекатель знания (knowledge extractor), который, имея доступ к детерминированному доказывающему P*, представленному в виде чёрного ящика с возможностью перемотки, либо выдаёт открытие обязательства к сообщению m*, являющемуся корректным голосом, либо решение задачи M-SIS. - Нулевое разглашение с честным проверяющим (honest verifier zero-knowldge): существует симулятор, который способен симулировать успешные взаимодействия между доказывающим и проверяющим. Способность различать реальное взаимодействие от симулированного сводится к решению задачи M-LWE. Свойство нулевого разглашения применяется только в случае честного проверяющего, это ограничение можно нивелировать, преобразовав интерактивный протокол в неинтерактивный с помощью замены проверяющего на случайный оракул. Строгая формулировка теоремы 1, а также её доказательство аналогичны работам [6, 7]. 2. Набросок схемы электронного голосования В данной работе разработана схема электронного голосования со множеством голосующих, администраций (authority) и кандидатов. В наброске мы опишем схему для п = 1. Схема легко расширяется для большего числа сообщений, но усложняется индексация. Чтобы опубликовать бюллетень, голосующий i делает следующее: - Пусть mi G Rq - сообщение, являющееся правильным голосом. - Голосующий разделяет голос между Na администрациями: xi1),... , xiNa) _$ Rq : Na (j) xi(j) = mi. j=1 - Голосующий создаёт Na обязательств к x(j) с секретными векторами r(j) _ _ x(K+^+1)d - Используя VProof, он доказывает, что обязательство к mi для секретного вектора Na (j) ri(j) содержит в себе корректный голос. j=1 i - Голосующий зашифровывает rij) с помощью открытого ключа j-й администрации и публикует его вместе со всеми обязательствами и доказательством. Сумма всех случайных многочленов xi(j) является финальным результатом голосования. Эта сумма находится по частям: каждая j-я администрация находит сумму xi(j) и публикует промежуточную сумму. i Порядок действий каждой администрации: - Администрация расшифровывает все секретные векторы пользователей, предназначенных для неё. - Амортизированно доказывает открытие обязательств для этих секретных векторов. - Администрация находит сумму этих обязательств и сумму соответствующих секретных векторов и публикует эти суммы вместе с амортизированным доказательством открытия. При сложении обязательств коэффициенты секретного вектора растут, что снижает безопасность схемы и может привести к неэффективному выбору параметров. Для решения этой проблемы вводится параметр u. Администрация может складывать не более u обязательств. Так как администрация знает все сообщения, она может создать новое обязательство (со «свежим» секретным вектором) к сообщению, являющемуся суммой сообщений в этих u обязательствах. Дальше необходимо доказать, что сообщение в свежем обязательстве корректно, для этого используется доказательство открытия к нулю для обязательства, равного разности свежего обязательства и сумме и старых. Доказательство открытия к нулю показывает, помимо ct0 = В0г*, ещё ct1 = (b1, г*), то есть в этом обязательстве нулевое сообщение. В итоге u старых обязательств заменяются на одно новое. Этот процесс можно продолжать сколько угодно, пока не останется u или меньше обязательств. Порядок действий для подведения результатов голосования и его проверки: - Для вычисления результата голосования необходимо сложить промежуточные суммы всех администраций. - Для проверки результата необходимо проверить доказательства всех участников, а также правильность сложения администраций. Конфиденциальность голосующего сохраняется, если хотя бы одна администрация является честной. Проверяемость результатов достигается благодаря доказательствам с нулевым разглашением. Взлом схемы подразумевает собой решение задачи M-SIS или M-LWE. Заключение Разработана постквантовая схема электронного голосования на основе решёток для любого количества кандидатов. В схеме участвует множество администраций, конфиденциальность каждого голоса сохраняется до тех пор, пока хотя бы одна администрация остаётся честной. Проверить финальный результат голосования может любой участник, так как для этого необходимо проверить опубликованные голосующими и администрациями доказательства. Безопасность предложенной схемы основывается на сложности решения задач M-SIS и M-LWE.

Скачать электронную версию публикации