Криптосистема Боне — Го — Ниссима (Tjnhmkvnvmybg >kuy — Ik — Unvvnbg)

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

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

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

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

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

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

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

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

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

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

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

Шифрование

Шифр($OK,M$):

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

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

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

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

Расшифр($SK,C$):

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

${p=307}$.

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

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

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

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

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

${M}{=2}$ .

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

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

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

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

и

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оценка 2-ДНФ

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

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

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

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

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

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

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

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

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

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

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

Литература

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

Ссылки

• С. И. Адян. Проблема Бернсайда и связанные с ней вопросы // УМН. — 2010. — Сентябрь (т. 65, вып. 5).