Криптосистема Боне — Го — Ниссима — частично гомоморфная криптосистема , являющаяся модификацией криптосистемы Пэйе и криптосистемы Окамото — Утиямы . Разработана Дэном Боне совместно с и в 2005 году . Основывается на конечных группах составного порядка и билинейных на эллиптических кривых; система позволяет оценить многовариантные квадратичные полиномы на шифротекстах (например, дизъюнктивная нормальная форма второго порядка (2- ДНФ )).

Система обладает аддитивным гомоморфизмом (поддерживает произвольные добавления и одно умножение (за которым следуют произвольные добавления) для зашифрованных данных).

Используемый в криптосистеме БГН алгоритм основан на задаче Бернсайда . .

Алгоритм работы

Как и все системы гомоморфного шифрования, КБГН включает следующие процессы: Генерация ключа, шифрование и расшифрование.

Конструкция использует некоторые конечные группы составного порядка, которые поддерживают билинейное отображение. Используются следующие обозначения:

1. ${\displaystyle \mathbb {G} }$ и ${\displaystyle \mathbb {G} _{1}}$ - две циклические группы конечного порядка ${\displaystyle {n}}$ .
2. ${\displaystyle {g}}$ — генератор ${\displaystyle \mathbb {G} }$ .
3. ${\displaystyle {f}}$ — билинейное отображение ${\displaystyle {f}:\mathbb {G} \times \mathbb {\mathbb {G} } \rightarrow \mathbb {G} _{1}}$ . Другими словами, для всех ${\displaystyle {u},{v}\in \mathbb {G} }$ и ${\displaystyle {a},{b}\in \mathbb {Z} }$ мы имеем ${\displaystyle {f}({u}^{a},{v}^{b})={f}({u},{v})^{{a}{b}}}$ . Мы также требуем выполнение условия : ${\displaystyle {f}({g},{g})}$ является генератором ${\displaystyle \mathbb {G} _{1}}$

Мы говорим, что ${\displaystyle \mathbb {G} }$ — билинейная группа, если существует группа ${\displaystyle \mathbb {G} _{1}}$ и билинейное отображение, определённое выше.

Генерация ключа

Генерация_Ключа( ${\displaystyle \tau }$ ) :

• Подавая на вход параметр безопасности ${\displaystyle \tau \in \mathbb {Z} ^{+}}$ , вычисляем алгоритм ${\displaystyle X(\tau )}$ , чтобы получить кортеж ${\displaystyle ({q}_{1},{q}_{2},\mathbb {G} ,\mathbb {G} _{1},{f})}$ . Алгоритм работает следующим образом:
  1. Сгенерируем два случайных ${\displaystyle \tau }$ — битовых числа ${\displaystyle {q}_{1}}$ и ${\displaystyle {q}_{2}}$ и положим ${\displaystyle {n}={q}_{1}{q}_{2}\in \mathbb {Z} }$ .
  2. Создадим билинейную группу ${\displaystyle \mathbb {G} }$ порядка ${\displaystyle {n}}$ , где ${\displaystyle {n}}$ > 3 — заданное число, которое не делится на 3:
     1. Найдём наименьшее натуральное число ${\displaystyle \ell \in \mathbb {Z} }$ , такое что ${\displaystyle {p}=\ell {n}-1}$ — простое число и ${\displaystyle {p=3{\bmod {4}}}}$ .
     2. Рассмотрим группу точек на эллиптической кривой ${\displaystyle {y^{2}=x^{3}+x}}$ опреленную над ${\displaystyle \mathbb {F} _{p}}$ . Поскольку ${\displaystyle {p=3{\bmod {4}}}}$ кривая имеет ${\displaystyle {p}+1=\ell {n}}$ точек в ${\displaystyle \mathbb {F} _{p}}$ . Поэтому группа точек на кривой имеет подруппу порядка ${\displaystyle {n}}$ , которую обозначим через ${\displaystyle \mathbb {G} }$ .
     3. Пусть ${\displaystyle \mathbb {G} _{1}}$ подгруппа в ${\displaystyle \mathbb {F} _{{p}^{2}}^{*}}$ порядка ${\displaystyle {n}}$ . Модифицированный алгоритм (Спаривание Вейля является билинейным, кососимметричным, невырожденным отображением ) на кривой выдаёт билинейное отображение ${\displaystyle {f}:\mathbb {G} \times \mathbb {\mathbb {G} } \rightarrow \mathbb {G} _{1}}$ , удовлетворяющее заданным условиям
  3. На выходе получим ${\displaystyle ({q}_{1},{q}_{2},\mathbb {G} ,\mathbb {G} _{1},{f})}$ .
• Пусть ${\displaystyle {n}={q}_{1}\times {q}_{2}}$ . Выберем два случайных генератора ${\displaystyle {g},{u}{\xleftarrow {R}}\mathbb {G} }$ и определим ${\displaystyle {h}}$ , как ${\displaystyle {h}={u}^{q_{2}}}$ . Тогда ${\displaystyle {h}}$ это случайный генератор подгруппы ${\displaystyle \mathbb {G} }$ порядка ${\displaystyle {q_{1}}}$ . Открытый ключ : ${\displaystyle {O}{K}=({n},\mathbb {G} ,\mathbb {G_{1}} ,{f},{g},{h})}$ . Закрытый ключ : ${\displaystyle {S}{K}={q_{1}}}$ .

Шифрование

Шифр( ${\displaystyle OK,M}$ ):

Мы предполагаем, что пространство сообщений состоит из целых чисел в наборе ${\displaystyle \{0,T\}}$ . Чтобы зашифровать сообщение ${\displaystyle M}$ с помощью открытого ключа ${\displaystyle OK}$ выбираем случайный параметр ${\displaystyle {r}{\xleftarrow {R}}\{0,1,...,{n}-1\}}$ и вычисляем

${\displaystyle {C}={g}^{M}{h}^{r}\in \mathbb {G} }$ .

Полученный результат и есть шифротекст.

Расшифрование

Расшифр( ${\displaystyle SK,C}$ ):

Чтобы расшифровать шифротекст используя закрытый ключ ${\displaystyle SK=q_{1}}$ , рассмотрим следующее выражение

${\displaystyle {C}^{q_{1}}=({g}^{M}{h}^{r})^{q_{1}}=({g}^{q_{1}})^{M}}$ .

Пусть ${\displaystyle {\hat {g}}={g}^{q_{1}}}$ . Чтобы восстановить ${\displaystyle {M}}$ достаточно вычислить дискретный логарифм ${\displaystyle {C}^{q_{1}}}$ по основанию ${\displaystyle {\hat {g}}}$ .

Следует отметить, что дешифрование в этой системе занимает полиномиальное время в размере пространства сообщений.

Примеры

Пример работы алгоритма

Сначала мы выбираем два различных простых числа

${\displaystyle {{q}_{1}=7}}$ ${\displaystyle {{q}_{2}=11}}$ .

Вычислим произведение

${\displaystyle {{n}={q}_{1}{q}_{2}=7\times 11=77}}$ .

Далее мы строим группу эллиптических кривых с порядком ${\displaystyle {n}}$ , которая имеет билинейное отображение. Уравнение для эллиптической кривой

${\displaystyle {y^{2}=x^{3}+x}}$

которое определяется над полем ${\displaystyle \mathbb {F} _{p}}$ для некоторого простого числа ${\displaystyle {p=3{\bmod {4}}}}$ . В этом примере мы устанавливаем

${\displaystyle {p=307}}$ .

Следовательно, кривая суперсингулярна с # ${\displaystyle {(E(p))=p+1=308}}$ рациональными точками, которая содержит подгруппу ${\displaystyle \mathbb {G} }$ с порядком ${\displaystyle {{n}=77(=308/4)}}$ . В группе ${\displaystyle \mathbb {G} }$ мы выбираем два случайных генератора

${\displaystyle {g=[182,240]}}$ , ${\displaystyle {u=[28,262]}}$

где эти два генератора имеют порядок ${\displaystyle {n}}$ и вычислим

${\displaystyle {h=u^{q_{2}}=[28,262]^{11}=[99,120]}}$

где ${\displaystyle {h}}$ порядка ${\displaystyle {q_{1}=7}}$ . Мы вычисляем зашифрованный текст сообщения

${\displaystyle {M}{=2}}$ .

Возьмём ${\displaystyle {r=5}}$ и вычислим

${\displaystyle {C={g}^{M}{h}^{r}=[182,240]^{2}\oplus [99,120]^{5}=[256,265]}}$ .

Для расшифровки мы сначала вычислим

${\displaystyle {\hat {g}}={g^{q_{1}}=[182,240]^{7}=[146,60]}}$

и

${\displaystyle {C}^{q_{1}}=({g}^{M}{h}^{r})^{q_{1}}=({g}^{q_{1}})^{M}={[256,265]^{7}=[299,44]}}$ .

Теперь найдём дискретный логарифм, перебирая все степени ${\displaystyle {\hat {g}}={g}^{q_{1}}}$ следующим образом

${\displaystyle {\hat {g}}^{1}={[146,60]}}$

${\displaystyle {\hat {g}}^{2}={[299,44]}}$

${\displaystyle {\hat {g}}^{3}={[272,206]}}$

${\displaystyle {\hat {g}}^{4}={[191,151]}}$

${\displaystyle {\hat {g}}^{5}={[79,171]}}$

${\displaystyle {\hat {g}}^{6}={[79,136]}}$

${\displaystyle {\hat {g}}^{7}={[191,156]}}$

${\displaystyle {\hat {g}}^{8}={[272,101]}}$

${\displaystyle {\hat {g}}^{9}={[299,263]}}$

${\displaystyle {\hat {g}}^{10}={[146,247]}}$

${\displaystyle {\hat {g}}^{11}={\infty }}$ .

Обратите внимание, что ${\displaystyle {\hat {g}}^{2}={C^{q_{1}}}}$ . Следовательно, расшифровка зашифрованного текста равна ${\displaystyle {2}}$ , что соответствует исходному сообщению.

Оценка 2-ДНФ

Частично гомоморфная система позволяет оценить 2- ДНФ .

На входе: У Алисы есть 2-ДНФ формула ${\displaystyle \phi (x_{1},...,x_{n})=\lor _{i=1}^{k}(l_{i,1}\land l_{i,2})}$ , а у Боба есть набор переменных ${\displaystyle {a=a_{1},...,a_{n}\in \{0,1\}^{n}}}$ . Обе стороны на входе содержат параметр безопасности ${\displaystyle \tau }$ .

1. Боб выполняет следующие действия:
   1. Он исполняет алгоритм Генерация_Ключа( ${\displaystyle \tau }$ ) , чтобы вычислить ${\displaystyle {O}{K},{SK}}$ и отправляет ${\displaystyle {O}{K}}$ Алисе.
   2. Он вычисляет и отправляет Шифр( ${\displaystyle {O}{K},{a_{j}}}$ ) для ${\displaystyle {j=1,...,n}}$ .
2. Алиса выполняет следующие действия:
   1. Она выполняет арифметизацию ${\displaystyle \Phi (\phi )}$ заменяя « ${\displaystyle \lor }$ » на « ${\displaystyle +}$ », « ${\displaystyle \land }$ » на « ${\displaystyle \times }$ » и « ${\displaystyle {\bar {x_{j}}}}$ » на « ${\displaystyle (1-x_{j})}$ ».Отметим, что ${\displaystyle \Phi }$ это полином степени 2.
   2. Алиса вычисляет шифрование ${\displaystyle {r}\times \Phi ({a})}$ для случайно выбранного ${\displaystyle {r}}$ используя гомоморфные свойства системы шифрования. Результат отправляется Бобу.
3. Если Боб получает шифрование « ${\displaystyle 0}$ », он выводит « ${\displaystyle 0}$ »; в противном случае, он выводит « ${\displaystyle 1}$ ».

Гомоморфные свойства

Система является аддитивно гомоморфной. Пусть ${\displaystyle ({n},\mathbb {G} ,\mathbb {G_{1}} ,{f},{g},{h})}$ — открытый ключ. Пусть ${\displaystyle {C_{1}},{C_{2}}\in \mathbb {G} _{1}}$ — шифротексты сообщений ${\displaystyle {m_{1}},{m_{2}}\in \{0,1\}}$ соответственно. Любой может создать равномерно распределённое шифрование ${\displaystyle {m_{1}}+{m_{2}}{\bmod {n}}}$ вычисляя произведение ${\displaystyle {C}={C_{1}}{C_{2}}{h}^{r}}$ для случайного чила ${\displaystyle {r}}$ в диапазоне ${\displaystyle \{0,1,...,{n}-1\}}$ .

Более важно то, что любой может умножить два зашифрованных сообщения один раз, используя билинейное отображение. Определим ${\displaystyle {g_{1}}={f}({g},{g})}$ и ${\displaystyle {h_{1}}={f}({g},{h})}$ . Тогда ${\displaystyle {g_{1}}}$ порядка ${\displaystyle {n}}$ , а ${\displaystyle {h_{1}}}$ порядка ${\displaystyle {q_{1}}}$ . Кроме того, для некоторого (неизвестного) параметра ${\displaystyle \alpha \in \mathbb {Z} }$ , напишем ${\displaystyle {h}={g}^{\alpha {q_{2}}}}$ . Предположим, что нам известны два шифротекста ${\displaystyle {C_{1}}={g}^{m_{1}}{h}^{r_{1}}\in \mathbb {G} }$ , ${\displaystyle {C_{2}}={g}^{m_{2}}{h}^{r_{2}}\in \mathbb {G} }$ . Чтобы построить шифрование произведения ${\displaystyle {m_{1}}\times {m_{2}}{\bmod {n}}}$ , выберем случайное число ${\displaystyle {r}\in \mathbb {Z_{n}} }$ и положим ${\displaystyle {C}={f}({C_{1}},{C_{2}}){h_{1}^{r}}\in \mathbb {G} _{1}}$ . Получаем ${\displaystyle {C=f(C_{1},C_{2})h_{1}^{r}=f(g^{m_{1}}h^{r_{1}},g^{m_{2}}h^{r_{2}})h_{1}^{r}=g^{m_{1}m_{2}}h^{m_{1}r_{2}+r_{2}m_{1}+\alpha q_{2}r_{1}r_{2}+r}=g_{1}^{m_{1}m_{2}}h_{1}^{\tilde {r}}}\in \mathbb {G} _{1}}$ , где ${\displaystyle {{\tilde {r}}=m_{1}r_{2}+r_{2}m_{1}+\alpha q_{2}r_{1}r_{2}+r}}$ — распределено равномерно в ${\displaystyle \mathbb {Z_{n}} }$ , как и необходимо.

Таким образом, ${\displaystyle {C}}$ является равномерно распределённым шифрованием ${\displaystyle {m_{1}}\times {m_{2}}{\bmod {n}}}$ , но только в группе ${\displaystyle \mathbb {G} _{1}}$ , а не в ${\displaystyle \mathbb {G} }$ (поэтому допускается только одно умножение).

Стойкость системы

Стойкость данной схемы основана на задаче Бернсайда : зная элемент группы составного порядка ${\displaystyle {n}={q}_{1}{q}_{2}}$ , невозможно определить его приналежность к подгруппе порядка ${\displaystyle {q_{1}}}$ .

Пусть ${\displaystyle \tau \in \mathbb {Z} ^{+}}$ , а ${\displaystyle ({q}_{1},{q}_{2},\mathbb {G} ,\mathbb {G} _{1},{f})}$ — кортеж, созданный ${\displaystyle X}$ , где ${\displaystyle {n}={q}_{1}{q}_{2}}$ . Рассмотрим следующую задачу. Для заданного ${\displaystyle ({n},\mathbb {G} ,\mathbb {G} _{1},{f})}$ и элемента ${\displaystyle {x}\in \mathbb {G} }$ , выведем « ${\displaystyle 1}$ », если порядок ${\displaystyle {x}}$ равен ${\displaystyle {q_{1}}}$ , в противном случае, выведем « ${\displaystyle 0}$ ». Другими словами, без знания факторизации группы порядка ${\displaystyle {n}}$ , необходимо узнать, находится ли элемент ${\displaystyle {x}}$ в подгруппе группы ${\displaystyle \mathbb {G} }$ . Данная задача называется задачей Бёрнсайда .

Понятно, что если мы можем учесть групповой порядок ${\displaystyle {n}}$ в криптосистеме, то мы знаем закрытый ключ ${\displaystyle {q_{1}}}$ , и в результате система взломана. Кроме того, если мы можем вычислить дискретные логарифмы в группе ${\displaystyle \mathbb {G} }$ , то мы можем вычислить ${\displaystyle {q_{2}}}$ и ${\displaystyle {q_{1}=n/q_{2}}}$ . Таким образом, необходимые условия для безопасности: сложность факторинга ${\displaystyle {n}}$ и сложность вычисления дискретных логарифмов в ${\displaystyle \mathbb {G} }$ .

Примечания

Литература

• С. М. Владимиров, Э. М. Габидулин, А. И. Колыбельников, А. С. Кшевецкий. Криптографические методы защиты информации. — 2-е изд. — МФТИ, 2016. — С. 225—257. — 266 с. — ISBN 978-5-7417-0615-2 .

Ссылки

• С. И. Адян. // УМН. — 2010. — Сентябрь ( т. 65 , вып. 5 ).