Геометрическая реализация метода проведения электронных выборов, основанного на пороговом разделении секрета

Автор: Мазуренко Александр Вадимович, Стукопин Владимир Алексеевич

Журнал: Вестник Донского государственного технического университета @vestnik-donstu

Рубрика: Информатика, вычислительная техника и управление

Статья в выпуске: 2 т.18, 2018 года.

Бесплатный доступ

Введение. Среди актуальных задач криптографии можно выделить задачу обеспечения безопасного и честного проведения электронного голосования. В настоящей работе описан метод проведения электронных выборов с точки зрения обеспечения криптографической безопасности. Материалы и методы. При решении поставленной исследовательской задачи использованы теоретические результаты из теории конечных полей, проективной геометрии и линейной алгебры. Разработанная криптосистема основана на применении геометрических объектов, рассматриваемых в проективной геометрии над конечными полями. Результаты исследования. Разработанный алгоритм основан на схеме шифрования Эль-Гамаля и на новом геометрическом способе разделения секрета между избирательными комиссиями. Данный способ использует особенности построения аффинных пространств над конечными полями для создания подходящих геометрических конструкций и генерации секрета, поиск которого, с точки зрения злоумышленника, является сложной алгоритмической задачей. Использование порогового метода разделения секрета обосновывается необходимостью исключить возможность фальсификации результатов голосования со стороны членов избирательной комиссии. Авторами определено, с какой вероятностью злоумышленнику удастся сгенерировать верную секретную долю в случае, когда ему известна лишь ее некоторая часть. Обсуждение и заключения. Предложенная криптографическая система может быть применена для проведения электронных выборов, а также в тех областях, где возникает необходимость в использовании методов пороговой криптографии.

Еще

Криптография, криптосистема с открытым ключом, схема эль-гамаля, конечные поля, пороговая криптография, разделение секрета, аффинная геометрия, проективные пространства, электронные выборы, задача диффи-хеллмана

Короткий адрес: https://sciup.org/142214949

IDR: 142214949   |   DOI: 10.23947/1992-5980-2018-18-2-246-255

Текст научной статьи Геометрическая реализация метода проведения электронных выборов, основанного на пороговом разделении секрета

2Don State Technical University, Rostov-on-Don, Russian Federation

Введение. Авторами разработана криптосистема, основанная на пороговом разделении секрета, которую возможно применить при разработке протокола электронного голосования. Для шифрования и дешифрования голосов используется усиленная схема Эль-Гамаля. Согласно данной схеме генерируется некий секретный параметр, далее называемый секретом, являющийся элементом определенной циклической группы. Для разделения секрета между проверяющими авторами разработан способ, заключающийся в следующем: секрету взаимно однозначно ставится в соответствие некоторая прямая аффинного пространства, ассоциированного с векторным пространством кп над конечным полем к , где n е N . Это аффинное пространство будем считать объемлющим пространством для всех рассматриваемых геометрических объектов. Далее проводится некоторая фиксированная плоскость через эту прямую. Эта плоскость объявляется каждому из проверяющих. Затем строится некоторое аффинное подпространство M , размерность которого совпадает с количеством проверяющих, и выделяется семейство подпространств, вложенных в M и образующих полный флаг. При этом M должно удовлетворять следующему свойству: результатом его пересечения с «публичной» плоскостью является в точности «секретная» прямая, причем данная прямая не лежит ни в каком собственном подпространстве, принадлежащем построенному семейству подпространств M . Итак, в качестве секретных долей используются попарно различные аффинные прямые, лежащие в аффинном подпространстве M , так что их число совпадает с размерностью M , а сами они порождают M . Для восстановления секрета необходимо найти прямую сумму секретных долей, что позволяет восстановить аффинное подпространство M , пересечение которого с «публичной» плоскостью дает «секретную» прямую, соответствующую в силу построенной биекции искомому секрету. Обладая секретным ключом, проверяющие могут расшифровать, согласно схеме ЭльГамаля, голоса избирателей и в дальнейшем подвести итог голосования. В данной работе в качестве геометрии, при помощи которой будут реализованы описанные идеи, выбрана проективная геометрия.

На сегодняшний день существует множество работ, посвященных вопросам проведения электронного голосования. Многие из них нашли применение в странах, где такое голосование широко используется.

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

Постановка задачи. Построим криптосистему, основанную на пороговом разделении секрета [1], для обеспечения легитимных электронных выборов [2–5]. Можно выделить три стороны, которые будут участвовать в моделируемом процессе: администратор, проверяющие и избиратели. Администратор — доверенное лицо, которое обладает наибольшими полномочиями и является аналогом центра сертификации.

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

Основная часть. В работе будут использоваться следующие стандартные обозначения: N — множество натуральных чисел, X — линейная оболочка подмножества X некоторого линейного пространства V , Ord ( R ) — порядок произвольной группы R , A T — транспонированная матрица для матрицы A .

Предположим, что общее количество проверяющих z = Nt, где z , N eN . Пусть S = { sbs 2 ,..sz } — множество проверяющих. Разделим их на команды из t человек. Пусть далее S i обозначает i -ю команду, где i = 1, N , состоящую из определенных t проверяющих, то есть S i = { s i i , s i 2 ,..., sit }, U N 1 S i = S , S i n S j = 0 , где i * j, i , j = 1, N . Предположим, что все необходимые параметры генерирует администратор, за исключением оговоренных случаев.

В основе разработанной криптосистемы лежит усиленный вариант схемы Эль-Гамаля [6–8]. Согласно данной схеме, по известному алгоритму генерируются параметры ( p , g ) , где p — простое число, а g

Информатика, вычислительная техника и управление

порождающий элемент мультипликативной абелевой группы G с Zp , причем порядок Ord ( G) = q , где q — такое простое число, что q = ( p - 1 ) /2. Пара ( p , g ) объявляется частью открытого ключа.

Этап генерации секретного ключа. Сначала при помощи некоторого генератора псевдослучайных чисел необходимо получить случайное число x e 1, q - 1, принимаемое в качестве секретного ключа. Опишем разработанный метод, позволяющий разделить x на секретные доли, которые раздадут каждому из проверяющих.

Пусть 5 e N, r — некоторое простое число, m e N : t < m . Обозначим проективное пространство размерности m над полем ф , индуцированное векторным пространством ф^,, над полем ф , через PG(m, r5) или PG(ф5 (m+1) ) [9]. Пусть PG(m, r5) состоит из множества точек, однородные координаты которых определяются как   (a0:a1:...:am), a eф ,   3 j e 0,m ■   aj ^ 0. Всего в  PG(m,r5)   существует i          rs

( r ( m + 1) 5 - 1 ) / ( r5 - 1 ) = 1 + r5 + r 2 5 + ... + r m 5 различных точек.

Положим далее, что w = r5, a — примитивный элемент поля ^w-.1, p = an — примитивный элемент поля ф», где n = (wm+1 -1)/(w -1), а также q < wm+1, где, как было указано выше, x e 1, q -1. Легко увидеть, что верна

Лемма 1. Рассмотрим множество A = { a , а

,...,

a }, где n = ( w m + 1 - 1 ) / ( w - 1 ) . Тогда для всех a i , a j e A ,

i * j , выполняется условие a i ^ ya j , где Y e®, i , j e 0, n - 1.

Рассмотрим векторное пространство ^ w - * 1 над полем ф . Выделим подпространство

L   {00( a 0 . pa 0 .... p w - 2 a 0 ), ..., ( a i , pa i ,... p w - 2 a i )..j( a n - 1 , pa n - 1 ,... p w - 2 a n - 1 )^

векторного пространства фТ-+ над полем ф, где i e 0, n -1, n = (wm+1 -1)/(w -1). Заметим, что dim(L) = m + 1. Действительно, L содержит n(w -1) +1 = wm+1 точек. Тогда dim(L) = logww  = m + 1. Рассмотрим разбиение D множества L \{0}, определяемое семейством множеств: Ai = {X(ai,pai,...pw-2ai)| XeфW}, где i e 0,n-1, n = (wm+1 -1)/(w -1). Из леммы 1 следует, что Ai nAj = 0, где i ^ j. Действительно, согласно лемме 1 для всех ai, aj е A, i, j e 0, n -1, i * j, выполняется условие prai^pkaj, где r, к = 0, w - 2 . Обозначим фактормножество множества L \ {0} по отношению эквивалентности RD , соответствующее разбиению D, через PG (m, w). Итак, PG (m, w) является проективным пространством размерности m над полем Ф w, индуцированным векторным пространством L над полем Ф w . однородные координаты которых имеют вид: (аi) = (аi: pai:

'

Будем говорить, что PG ( m , w) состоит из точек,

...

: в w 2 a i ), где а — примитивный элемент поля

Ф w m + 1 , p = a n , i = 0, n - 1, n = ( w m + 1 - 1 ) / ( w - 1 ) . Таким образом, верна

Лемма 2. Количество точек в PG ( m , w ) равно n = ( w m + 1 - 1 ) / ( w - 1 ) .

Рассмотрим произвольное векторное пространство V над некоторым полем к . Назовем каноническим проектированием отображение ^ ( V \{0}) ^ PG(V ),

^ ( v ) = [ v ] ,

сопоставляющее вектору v e V \{0} класс эквивалентности, определенный элементом v [9].

Пусть a — примитивный элемент поля  ф wm+1, где  фw / m+1 = фw[x]/(f (X)), f (x) eФw[x]  — минимальный многочлен a над полем ф w . Пусть, v ■ PG (m, w) ^ PG(m, w)

v ( ( a 1 ) ) = ( a 0 a 1 ■...■ a m ),

где a j e ф w — коэффициенты многочлена, являющегося представителем класса эквивалентности,

соответствующего a i в

ф w [ x ]/ ( f ( x ) ) с точностью до изоморфизма, i = 0, n - 1,

n = ( w m + 1 - 1 ) / ( w - 1 ) , j = 0, m .

Теорема 1. Отображение V является взаимно однозначным соответствием между множествами PG ( m , w ) и PG ( m , w ) . Более того, V отображает проективные подпространства PG ( m , w ) на проективные подпространства PG ( m , w ) .

Доказательство. Положим, что fi (x) = ^ m q aix1  — представитель класса эквивалентности, соответствующий ai в Фw[x]/(f (x)). Тогда

v((a . ва .....e a )k(w_]) )= (a0. а1.....am)k(m +0’ где i = 0,n -], n = (wm+1 -])/(w-]). Легко проверить, что V есть биекция. Действительно, из рассуждений перед леммами 1 и 2 следует, что достаточно проверить инъективность отображения V. Пусть (a0 : a1:...: am) = (b0: b1:...: bm), то есть ь,=Х ai, где i = 0, m , XeФw. Поскольку fi- (x) = £ i=0 aix1 и Xf(x) = ^i=0Xpx* — представители классов эквивалентности, соответствующие a7' и Xaj в Фw[x]/(f(x)), то v((aj)) =(aq.a]....:am) и v((Xaj)) =(b0:bV-.bm), где j = 0,n-1, n = (wm+1 -1)/(w-1). Но (aj) =(Xaj) в силу построения PG (m, w).

Пусть Z — векторное подпространство Ф w [ x ]/ ( f ( x ) ) , £ ( Z \{0}) — проективное подпространство PG ( m , w ). Зафиксируем базис Z : {t 1 ,1 2,-4k }, где k = dim ( Z ) . Тогда точки V- 1 ( ^ ( t , ) ) , где i = 1, k , являются проективно независимыми, то есть, образуют некоторое проективное подпространство H с PG ( m , w ): К Z \{0}) =v ( H).

Таким образом, проективные пространства PG ( m , w ) и PG ( m , w ) над полем Ф w изоморфны. В дальнейшем вместо PG ( m , w ) будем использовать обозначение PG ( m , w ) , отождествляя эти два множества.

Пусть a — примитивный элемент поля Ф w m + 1 , p = a n , где n = ( wm + 1 - 1 ) / ( w - 1 ) . Рассмотрим

*

отображение т . Ф w m + 1 ^ PG ( m , w ),

т(а iPj) = (ai), где i e 0, n -1, j e 0, w - 2. Из леммы 1 легко увидеть, что верна

Лемма 3. Отображение т является сюръективным.

Пусть a — примитивный элемент поля Ф w m + 1 , р = a n , где n = ( wm + 1

- 1 ) / ( w - 1 ) . Рассмотрим

произвольное конечное поле Ф p , где pz — положительная степень некоторого

простого числа p , z eN ,

pz wm + 1 , d — примитивный элемент поля Ф pZ . Рассмотрим отображение ц : O p ц ( dy ) = a y ,

*

w m + 1 ,

где y e 0, pz - 2. Очевидно, что ц является инъективным отображением. Заметим, что любой элемент *

a w m + 1 может быть единственным образом представлен в виде a = a i р j , где i e 0, n - 1, j e 0, w - 2. Определим отображение 8 : Ф*pz ^ Ф * ^ ,

5 ( b ) = p j , где ц ( b ) = a i в j для некоторых i e 0, n - 1, j e 0, w - 2 .

z    m + 1

Рассмотрим произвольное конечное поле Ф pZ , где p — простое число, z e N , p w . Определим

φ

Ф p z ^ PG ( m , w ) x ^ Ф w

ф ( b ) = ( т ( Ц ( b )X 5 ( b ) ) ,

Информатика, вычислительная техника и управление

где используются ранее определенные отображения т (3), ц (4), 8 (5). Из лемм 1 и 3 легко увидеть, что верна

Теорема 2. Отображение ф является инъективным.

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

*

проективного пространства. Секретный ключ x представляет собой элемент мультипликативной группы Zq, где q — простое число, так что x el,q-1. Для генерации секрета зафиксируем случайный порождающий

*

элемент b циклической группы Zq и некоторое целое число i е 0, q - 2 , а затем положим b = x. Далее зафиксируем примитивный элемент a

поля Ф w m + 1 . Поскольку q wm + 1 , то можно рассмотреть ранее

*

г-            п *      *

определенное инъективное отображение ц. Zq ^ Фwm+1 (4). Итак, ц(bi) = ai, где i е 0, q - 2. Поскольку можно легко вычислить элемент a n, где n = (wm+1

-

1 ) / ( w - 1 ) , то a i = a vn + r , где v eZ , r eN , согласно алгоритму

*

Евклида. Таким образом, используя отображение т. Фwm+1 ^ PG(m, w) (3) получаем T(ai) = T(avn+r) = (ar). Также, исходя из определения

*       *

§ : Z q > Ф w

(5),   вычисляем    § ( b ) = a vn .

ф .Z * ^ PG ( m , w ) х F* (6) сопоставляет секретному ключу ф ( x ) = ( ( a r Xa

Следовательно, отображение ■ vn ) . Публикуем значение v е Z .

Случайным образом строим

проективную

прямую l е PG ( m, w ): ( a r ) e l . Полученная проективная прямая l

публикуется. Итак, будем обозначать «секретную» точку, то есть точку, которая сопоставляется секрету при помощи отображения ф , через ( c ) е PG ( m , w ).

Далее администратор генерирует систему попарно различных проективных подпространств { M i } N с PG ( m , w ) размерности t - 1, таких что M i - n l = ( c ), где i = 1, N , N — количество команд проверяющих. Так как число людей в одной команде 2 t m , то размерность d создаваемых проективных подпространств в зависимости от t может принимать значения 1 d m - 1, то есть создаваемое проективное пространство может быть некоторой проективной прямой в случае t = 2, а при t = m — проективной гиперплоскостью в PG ( m , w ).

Пусть одним из построенных проективных подпространств будет M с PG ( m , w ). Пусть M есть t -мерное векторное подпространство векторного пространства Ф w m + 1 над полем Ф w , для которого выполняется условие ^ ( m ) = M , где ^ — ранее определенное каноническое проектирование (1). Рассмотрим максимальный флаг длины t , получаемый при помощи базисных векторов M { Р 1 , в 2 ,... в t } сФ w m + 1 :

M 0 = 0 с M , =0.)

с ... с Mt =(р , , р 2,..., рJ . Тогда для «секретной» точки ( c ) е PG ( m, w) и элемента c еФ w m + 1 :

£ ( c ) = ( c ) , должно выполняться условие c е Mt \ Mt - 1 . Необходимость соблюдения этого условия будет ясна из дальнейших рассуждений.

Существует несколько способов сгенерировать искомое ( t - 1)-мерное проективное подпространство

M с PG ( m , w ). Опишем один из таких методов, который заключается в переходе от одного базиса к другому.

Зафиксируем некоторый базис в = { Р 1 , Р 2 ,... в m + 1 } векторного пространства Ф w m + 1 над полем Ф w .

Рассмотрим разложение элемента c ^ 0, c е Фwm+1 по этому базису: с = Еm11 viвi , где vi е Фw. Пусть в этом разложении ровно j е1,m + 1 коэффициентов v^ , v^,..., v^ отличны от нуля, где ki е1,m +1, i = 1, j. Перенумеруем элементы базиса в так, что для нового базиса в j выполняется условие: в j := в к. и li := lk. , где i = 1, j, то есть в разложении c по базису вj все коэффициенты отличные от нуля находятся на первых j позициях: c = Еj=11/вj =Еm11 viвi. Заметим, что в качестве такого начального базиса в удобнее всего выбрать полиномиальный базис, в силу построения PG(m, w) .

Если для рассматриваемого базиса в j выполняется условие: j = t , то достигли желаемого результата.

Пусть 1 j < t - 1. Зафиксируем некоторый элемент i / ^ еФ ^ . Приведем пример матрицы перехода

Aj +1 е GLm+1(Фw) от j-го базиса {вj} m4 к (j + 1)-му {в j+1}m+1 базису векторного пространства Ф wm+1 над полем Ф w, такому что c

где li+1 = li, i = 1, j, вJk+1 = вJk, где k = 1, m + 1, k £ j, j + 1, вj+1 =вj--у1вj+1, вj+1 =nвj+1, где neФw — произвольный, но зафиксированный, элемент- Пусть ljj+ в V+1 = j в^1,--^ m+1) T, единичную матрицу, за тем

в V = (в1 х-в m+1) T. Матрица  Aj+1: вV+1 = Aj+1вV , представляет собой исключением что в ее j +1 столбце единственными ненулевыми элементами являются aj j+i =

-

n l j +

j

и

a j + 1, j + i = n , находящиеся в j -ой и ( j + 1)-ой строках соответственно. Тогда

в j+1 =в j--^ в j+1, в j+1 =nв j+1 и в Jk+1 =в Jk, где k = 1, m + 1, k £ j, j +1- Таким образом, проделывая ljj описанную процедуру t - j раз, начиная с базиса вj, получаем базис вt = {в1 ,в2,---,вm+1} векторного пространства Ф wm+1 над полем Ф w: c = £ t-1 lit в t , где lt еФ*^, i = 1, t -

Пусть t + 1 < j < m +1. Опишем матрицу перехода Bj-1 е GLm+1(Фw) от j-го базиса {вj}m+y к (j -1)- му {вj1}m=\ базису векторного пространства Фwm+1 над полем Фw, такому что c = ^j-11/ 1вj-1, где lj                  βj l/-1 = li, i = 1, j-1, вj-1 =вj, где k = 1, m + 1, k £ j-1, j, вj-1 =в j_ 1+ -у вj, вj' = j , где neOw l-n

произвольный, но зафиксированный, элемент. Пусть вV 1 = (в/ 1,в2 1,---,вm +\)T , вj= (в1',в2,---вm+1)T -Матрица Bj-1: вV 1 = Bj+1вV, представляет собой единичную матрицу, за тем исключением что в ее j столбце lj единственными ненулевыми элементами являются bj-1 j =     и

b j j = — , находящиеся в ( j - 1)-ой и j -ой

n

ljβj строках соответственно. Тогда вj-1 =вj , + — вj , вj-1 = j-1 j-1 lj -11 j j n образом, проделывая описанную процедуру j -1  раз, вt = {в1 ,в2,---вm+1} векторного пространства Фwm+1 над полем

Таким образом, если с еФ w m + 1 :   £ ( c ) = ( c ), где

и в k 1 = в k , где к = 1, m + 1, k £ j 1, j - Таким

начиная с базиса   в j , получаем базис

Ф w - c = l it = 1 l t в i , где l‘i е ° w , i = 1 t .

( c ) е PG ( m , w ) — «секретная» точка, ^

отображение (1), то, применяя вышеописанный метод, находим базис в t = { в t , в 2 ,---, в m + 1 } векторного пространства Ф wm + 1 над полем Ф w : c =^ t =1 l t в t , где l i е ф’ ^ , i = 1, t . Отсюда можно построить t -мерное векторное подпространство M = ^в 1 , в 2 ,---, в tt^ СФ w m + 1 - c ' е M t \ M t - 1 , где Mt - 1 =(в 1 , в 2 ,-, Р t - 1) , M t = M -Рассмотрим линейно независимые элементы у и c векторного пространства Ф w m + 1 над полем Ф w , причем у £ M . Зафиксируем двумерное подпространство l = ( c , у у сФ w + 1 , Тогда проективно независимые точки

^ ( в t ) е PG ( m , w ), где i = 1, t , являются секретными долями, раздаваемые одной из команд, а проективная прямая ^ ( l ) = l с PG ( m , w ) - частью открытого ключа, где ^ — ранее определенное каноническое проектирование (1)-

Информатика, вычислительная техника и управление

Открытый ключ. Открытый ключ состоит из последовательности ( p , g , y = gx ), где p — простое *

число, g — порождающий элемент мультипликативной абелевой группы G с Z p , причем порядок группы Ord ( G ) = q , где q — такое простое число, что q = ( p - 1)/2, x — секретный ключ: x e 1, q - 1. Также параметрами открытого ключа являются а — примитивный элемент поля Ф wm + 1 , пара ( w, m ), где w — положительная степень некоторого простого числа, m e N , проективная прямая l с PG ( m , w) , которой принадлежит «секретная» точка, целое число v e Z , используемое при восстановлении секрета, описание инъективного отображения р : Ф z ^ G , где r z q , r — простое число, z e N — число кандидатов.

Этап голосования и шифрования «голоса». Пусть выборы проходят по следующим правилам: 1. всего участвуют z e N кандидатов; 2. проголосовать можно только за одного кандидата. Все голоса будут представлять собой некоторые элементы векторного пространства Ф r над полем Ф r , где r — простое число (см. описание строения открытого ключа). Поскольку r z q , то можно построить инъективное отображение из

Ф Z в G, которое будем обозначать через р: ФZ ^ G. Положим, что избиратель проголосовал за i -го кандидата, где i = 1,z . Тогда u = (ai,a2,...,ai-1,1,ai+1,...,az) eФr, где aj eФr : Uj ^ 1, j = 1,z, j ^ i, является открытым текстом. Далее происходит сопоставление вектору и некоторого элемента h e G: р(и) = h . Затем

*

избиратель генерирует произвольное число k e 1, q - 1, равномерно распределенное в Z q , и на основе публичного ключа применяет отображение E : G 2 ^ G 2 , E ( k , h ) = ( g k , y k h ), задающее шифрование по схеме Эль-Гамаля. E ( k , z ) является шифротекстом, который отправляется проверяющим.

Этап дешифрования «голоса». Все множество голосов можно разбить среди N команд, чтобы уменьшить время подсчета голосов.

Определим отображение D : G 2 ^ G , D ( ( g k , y k h ) ) = g - xky k h = h , задающее дешифрование по схеме Эль-Гамаля, где x — секретный ключ.

Перед тем как расшифровать полученные шифротексты проверяющим понадобится восстановить секретный ключ x e 1, q -1. Пусть какая-то из команд Si, где i = 1, N, пытается восстановить x. Для этого каждый из участников sij e Si публикует свою секретную долю (вij) e PG(m, w), где j = 1, t. Прямая сумма системы проективно независимых точек {(pj)}t=1 равна проективному подпространству Mi с PG(m, w): Mi n l = (c), где l с PG(m, w) — известная проективная прямая, (c) — «секретная» точка. Опишем один из способов нахождения данного пересечения.

Пусть { Р 1 , Р 2 ,..., Р m + 1 } — базис векторного пространства Ф w m + 1 над полем Ф w , построенный на этапе генерации секретных долей. Тогда M =(P 1 , P 2 ,---= t ) — векторное подпространство Ф w m + 1 над полем Ф w : ^ ( M ) — проективное подпространство PG ( m , w ), равное прямой сумме секретных долей. Рассмотрим двумерное векторное подпространство l сФ w m + 1 , такое что £ ( l ) = l с PG ( m , w ), где l — известная из публичного ключа проективная прямая, содержащая «секретную» точку. Векторное подпространство, получаемое в результате пересечения M n l , должно быть одномерным подпространством векторного пространства Ф w m + 1 над полем Ф w . Зафиксируем некоторое множество базисных векторов { y , h }, порождающих подпространство l = ( y , h ), где y , h e O w m + 1 . Следовательно, не нарушая общность *

рассуждений, можно положить, что y £ M , а координата вектора y : y t + 1 e Ф w . Для вектора, принадлежащего v e M n l , выполняется условие: v = £ t = 1 v i в i =^ 1 y + ^ 2 h , где X 1 , X 2 w . Таким образом, для нахождения пересечения необходимо решить следующую систему линейных уравнений:

f- 1 0

0    ••

- 1  

0

0

У 1

У 2

h 1 ' h 2

f v 1 ' v 2

' :i

0

0      ••

- 1

yt

h t

v -

X 1

=

.

0

0      ••

0

y t + 1

h t + 1

0

1 0

0   -

0

y m + 1

ri m + 1 7

lX 2 )

0

l 0 7

Ранг данной матрицы должен равняться t + 1, что возможно тогда и только тогда, когда ( yt + 1 h i - yih * + i ) / y * + 1 = 0, i е t + 2, m + 1. Легко увидеть, что если A — линейное отображение, соответствующее матрице данной СЛАУ, то

T

X е ker(A) ^ х = Х21 y+1 h - У h+1   y+1 h2 - У2h*+1 „. yt+1h* - yh+1 _ h, 1] , l У*+1                У*+1                      У*+1            У*+1

где X 2 е Ф. w . Рассмотрим элемент х = Z * =1 У * + 1 h i y i h * + 1 Р i = а 5 е Ф m + 1, а — примитивный элемент поля

  • У*+1

Фwm+1 , 5 е 0, wm+1 - 2. Итак, х = а5 = аrаnl, где r е 0, n -1, n = (wm+1 -1)/(w -1), l eZ. Следовательно, при помощи отображения т (3) получаем т(х) = т(аrаnl) = (аr) е PG(m, w) — «секретную» точку. Далее

  • -1    *.^*

применяем левое обратное отображение ф : PG ( m , w ) х Ф w ^ Z q к (6), и — ц : Ф w m + 1 ^ Z q к (4), а также известное из публичного ключа v е Z : ф - 1 ( ( а r ), а nv ) = ц - 1 ( а r а nv ) = ц - 1 ( а i ) = bl = х , где i е 0, q - 2, b —

*

порождающий элемент Z q , х — секретный ключ.

Предположим, что необходимо расшифровывать шифротекст E(k, h) е G2 . Для этого используем отображение D(E(k, h)) = h е G. Для того чтобы восстановить вектор и е ФZ , являющийся открытым текстом, применим отображение у-1 : G ^ ФZ , которое является левым обратным к общеизвестному инъективному отображению Y, то есть у-1(h) = и .

Определение результатов голосования. Пусть U = {ui }d=1 сФz — множество всех «голосов», где d eN , X: ФZ ^Фz, X(u) = (0,0,...:,1i,0,...0) , если i -й элемент вектора и равен 1, i е1,z . После дешифрования «голосов» находим вектор R = Zd= 1 X(ui) eZz , где j -ый элемент R в силу предыдущих рассуждений представляет собой количество голосов за j -го кандидата, j е 1, z. Вектор R публикуется и объявляется результатом выборов.

Теорема 3. Если злоумышленнику известно множество проективных точек U с PG ( m , w ) , являющихся секретными долями, где | U | <  t - 1, то вероятность того, что он правильно сгенерирует «секретную» точку равна 1/( w + 1).

Доказательство . Поскольку злоумышленнику известна проективная прямая l с PG ( m , w ) , которой принадлежит искомая «секретная» точка ( c ), то вероятность сгенерировать верную «секретную» точку перед началом каких-либо преобразований равна 1/( w + 1). Действительно, произвольная проективная прямая, принадлежащая PG ( m , w ), содержит w + 1 точек. Имея в своем распоряжении публичный ключ, злоумышленник знает элемент v е Z : c = а i а vn , где т ( c ) = т ( а i а vn ) = ( а i ) = ( c ) (3), i е 0, n - 1, n = ( wm + 1 - 1 ) / ( w - 1 ) . Но в силу построения сюръективного отображения т для любого из n элементов вида а j , где j е 0, n - 1, т ( а j а vn ) = ( а j ) , то есть вероятность сгенерировать верный «секретный» ключ по элементу а vn еФ и ? равна 1/ n = ( w - 1)/( wm + 1 - 1). Пусть злоумышленник, используя проективно независимые точки, из которых состоит множество U с PG ( m , w ) , строит проективное подпространство W с PG ( m , w ), размерность

Информатика, вычислительная техника и управление

которого строго меньше t - 1 . Поскольку при восстановлении «секретной» точки ищется прямая сумма всех секретных долей, то проективное подпространство W не пересекается с проективной прямой l в силу построения множества U . Итак, злоумышленнику известно, что искомая «секретная» точка не принадлежит U . Для любой точки ( s ) l проективное подпространство ( U ( s )) PG ( m , w ) имеет размерность меньшую либо равную t - 1 . Тогда вероятность того, что ( s ) является искомой точкой, равна 1/( w + 1) .

Выводы. В работе описан разработанный авторами способ организации электронных выборов, в основе которых лежит использование схемы Эль-Гамаля и метода порогового разделения секрета, опирающегося на свойства проективных пространств, заданных над конечными полями. Построен полиномиальный детерминированный алгоритм, криптографическая стойкость которого опирается на общепризнанно трудноразрешимую проблему Диффи-Хеллмана в конечном поле [10]. Доказано, что предложенные методы позволяют защитить передаваемые от нечестных проверяющих данные за счет особенности способа генерации секретных долей, представляющих собой точки некоторого проективного пространства. Таким образом, определена вероятность создания злоумышленником верной секретной доли при условии, что ему известна лишь некоторая часть секретных долей.

Список литературы Геометрическая реализация метода проведения электронных выборов, основанного на пороговом разделении секрета

  • Могилевская, Н. С. Пороговое разделение файлов на основе битовых масок: идея и возможное применение/Н. С. Могилевская, Р В. Кульбикаян, Л. А. Журавлев//Вестник Дон. гос. техн. ун-та. -2011 -Т. 11, 10. -С. 1749-1755.
  • Rubin, A. D. Security considerations for remote electronic voting/A. D. Rubin//Communications of the ACM. -2002. -V. 45(12). -P. 39-44.
  • Kiayias, A. An Internet voting system supporting user privacy/A. Kiayias, M. Korman, D. Walluck//ACSAC’06: Proceedings of the 22nd Annual Computer Security Applications Conference. -2006. -P. 165-174.
  • Jefferson, D. Analyzing internet voting security/D. Jefferson, A. D. Rubin, B. Simons, D. Wagner//Communications of the ACM. -2004. -V. 47(10). -P. 59-64.
  • Chaum, D. Secret-ballot receipts: True voter-verifiable elections/D. Chaum//IEEE Security and Privacy. -2004. -V. 2(1). -P. 38-47.
  • Алферов, А. П. Основы криптографии: учебное пособие/А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин. -Москва: Гелиос-АРВ, 2001. -480 с.
  • Рябко, Б. Я. Криптографические методы защиты информации/Б. Я. Рябко, А. Н. Фионов. -Москва: Горячая линия-Телеком, 2005. -229 с.
  • Коблиц, Н. Курс теории чисел и криптографии/Н. Коблиц. -Москва: ТВП, 2001. -254 с.
  • Кострикин, А. И. Введение в алгебру/А. И. Кострикин. -Москва: МЦНМО, 2009. -368 с.
  • Ian, F. Blake. On the complexity of the discrete logarithm and Diffie-Hellman problems/F. Blake Ian, Theo Garefalakis//J. Complex. -2004. -V. 20(2-3). -P. 148-170.
Еще
Статья научная