Криптосистема Боне — Го — Ниссима

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

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

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

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

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

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

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

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

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

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

• Подавая на вход параметр безопасности $\tau \in {\mathbb{Z}}^{+}$, вычисляем алгоритм $X(\tau )$, чтобы получить кортеж $(q_1,q_2,𝔾,{𝔾}_1,f)$. Алгоритм работает следующим образом:
  1. Сгенерируем два случайных $\tau$ — битовых числа $q_1$ и $q_2$ и положим $n=q_1{q}_2\in \mathbb{Z}$.
  2. Создадим билинейную группу $𝔾$ порядка $n$, где $n$ > 3 — заданное число, которое не делится на 3:
     1. Найдём наименьшее натуральное число $\ell \in \mathbb{Z}$ , такое что $p=\ell n-1$ — простое число и $p=3mod4$.
     2. Рассмотрим группу точек на эллиптической кривой $y^2=x^3+x$ определённую над ${𝔽}_p$. Поскольку $p=3mod4$ кривая имеет $p+1=\ell n$ точек в ${𝔽}_p$. Поэтому группа точек на кривой имеет подгруппу порядка $n$, которую обозначим через $𝔾$.
     3. Пусть ${𝔾}_1$ подгруппа в ${𝔽}_{p^2}^{*}$порядка $n$. Модифицированный алгоритм спаривания Вейля (Спаривание Вейля является билинейным, кососимметричным, невырожденным отображением) на кривой выдаёт билинейное отображение $f:𝔾\times 𝔾\to {𝔾}_1$, удовлетворяющее заданным условиям
  3. На выходе получим $(q_1,q_2,𝔾,{𝔾}_1,f)$.
• Пусть $n=q_1\times q_2$. Выберем два случайных генератора $g,u\stackrel{R}{\leftarrow }𝔾$ и определим $h$, как $h=u^{q_2}$. Тогда $h$ это случайный генератор подгруппы $𝔾$ порядка $q_1$. Открытый ключ : $OK=(n,𝔾,{𝔾}_{\mathrm{𝟙}},f,g,h)$. Закрытый ключ : $SK=q_1$.

Шифрование

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

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

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

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

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

Расшифр($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$

которое определяется над полем ${𝔽}_p$ для некоторого простого числа $p=3mod4$. В этом примере мы устанавливаем

$p=307$.

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

$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}=\mathrm{\infty }$.

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

Оценка 2-ДНФ

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

На входе: У Алисы есть 2-ДНФ формула $\varphi (x_1,...,x_n)=\underset{i=1}{\overset{k}{\vee }}(l_{i,1}\wedge l_{i,2})$, а у Боба есть набор переменных $a=a_1,...,a_n\in \{0,1{\}}^n$ . Обе стороны на входе содержат параметр безопасности $\tau$.

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

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

Система является аддитивно гомоморфной. Пусть $(n,𝔾,{𝔾}_{\mathrm{𝟙}},f,g,h)$ — открытый ключ. Пусть $C_1,C_2\in {𝔾}_1$ — шифротексты сообщений $m_1,m_2\in \{0,1\}$ соответственно. Любой может создать равномерно распределённое шифрование $m_1+m_{2}modn$ вычисляя произведение $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 𝔾$, $C_2=g^{m_2}{h}^{r_2}\in 𝔾$. Чтобы построить шифрование произведения $m_1\times m_{2}modn$, выберем случайное число $r\in {\mathbb{Z}}_{𝕟}$ и положим $C=f(C_1,C_2)h_1^r\in {𝔾}_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 {𝔾}_1$, где$\tilde{r}=m_1{r}_2+r_2{m}_1+\alpha q_2{r}_1{r}_2+r$ — распределено равномерно в ${\mathbb{Z}}_{𝕟}$, как и необходимо.

Таким образом, $C$ является равномерно распределённым шифрованием $m_1\times m_{2}modn$, но только в группе ${𝔾}_1$, а не в $𝔾$ (поэтому допускается только одно умножение).

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

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

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

Понятно, что если мы можем учесть групповой порядок $n$ в криптосистеме, то мы знаем закрытый ключ $q_1$, и в результате система взломана. Кроме того, если мы можем вычислить дискретные логарифмы в группе $𝔾$, то мы можем вычислить $q_2$ и $q_1=n/q_2$. Таким образом, необходимые условия для безопасности: сложность факторинга $n$ и сложность вычисления дискретных логарифмов в $𝔾$.

Литература

• Шаблон:Книга

Ссылки

• Шаблон:Статья