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

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

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

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

Генерация_Ключа($\tau$): Учитывая параметр безопасности $\tau \in \mathbb {Z} ^{+}$, вычисляем $\Im (\tau )$, чтобы получить кортеж $({\boldsymbol {q}}_{1},{\boldsymbol {q}}_{2},\mathbb {G} ,\mathbb {G} _{1},{\boldsymbol {f}})$. Пусть ${\boldsymbol {n}}={\boldsymbol {q}}_{1}{\boldsymbol {q}}_{2}$. Выберем два случайных генератора ${\boldsymbol {g}},{\boldsymbol {u}}{\xleftarrow {R}}\mathbb {G}$ и определим ${\boldsymbol {h}}$, как ${\boldsymbol {h}}={\boldsymbol {u}}^{\boldsymbol {q_{2}}}$. Тогда ${\boldsymbol {h}}$ это случайный генератор подгруппы $\mathbb {G}$ порядка ${\boldsymbol {q_{1}}}$. Открытый ключ : ${\mathcal {O}}{\mathcal {K}}=({\boldsymbol {n}},\mathbb {G} ,\mathbb {G_{1}} ,{\boldsymbol {f}},{\boldsymbol {g}},{\boldsymbol {h}})$. Закрытый ключ : ${\mathcal {S}}{\mathcal {K}}={\boldsymbol {q_{1}}}$.

Работа в режиме шифрования

Шифрование

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

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

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

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

Расшифр(${\mathcal {S}}{\mathcal {K}},{\mathcal {C}}$): Чтобы расшифровать шифротекст используя закрытый ключ ${\mathcal {S}}{\mathcal {K}}={\boldsymbol {q_{1}}}$, рассмотрим следующее выражение

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

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

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

Пример

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

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

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

Вспомогательные данные о группах

Краткое рассмотрение основных групп, лежащих в основе данной системы шифрования.

Билинейные группы

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

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

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

Построение билинейных групп заданого порядка ${\boldsymbol {n}}$

Пусть ${\boldsymbol {n}}$ > 3 — заданное число, которое не делится на 3. Построим билинейную группу $\mathbb {G}$ порядка ${\boldsymbol {n}}$ следующим образом:

1. Найдем наименьшее натуральное число $\ell \in \mathbb {Z}$ , такое что ${\boldsymbol {p}}=\ell {\boldsymbol {n}}-1$ — простое число и $p=2{\bmod {3}}$.
2. Рассмотрим группу точек на эллиптической кривой $y^{2}=x^{3}+1$ опреленную над $\mathbb {F} _{\boldsymbol {p}}$. Поскольку $p=2{\bmod {3}}$ кривая имеет ${\boldsymbol {p}}+1=\ell {\boldsymbol {n}}$ точек в $\mathbb {F} _{\boldsymbol {p}}$. Поэтому группа точек на кривой имеет подруппу порядка ${\boldsymbol {n}}$, которую обозначим через $\mathbb {G}$.
3. Пусть $\mathbb {G} _{1}$ подгруппа в $\mathbb {F} _{{\boldsymbol {p}}^{2}}^{*}$порядка ${\boldsymbol {n}}$. Модифицированный алгоритм спаривания Вейля (Спаривание Вейля является билинейным, кососимметричным, невырож­денным отображением) на кривой выдает билинейное отображение ${\boldsymbol {f}}:\mathbb {G} \times \mathbb {\mathbb {G} } \rightarrow \mathbb {G} _{1}$, удовлетворяющее заданным условиям.

Алгоритм, основанный на задаче Бёрнсайда

Определим алгоритм $\Im$, который при заданном параметре безопасности $\tau \in \mathbb {Z} ^{+}$ выводит кортеж $({\boldsymbol {q}}_{1},{\boldsymbol {q}}_{2},\mathbb {G} ,\mathbb {G} _{1},{\boldsymbol {f}})$, где $\mathbb {G}$ и $\mathbb {G} _{1}$ группы порядка ${\boldsymbol {n}}={\boldsymbol {q}}_{1}{\boldsymbol {q}}_{2}$ и ${\boldsymbol {f}}:\mathbb {G} \times \mathbb {\mathbb {G} } \rightarrow \mathbb {G} _{1}$ — билинейное отображение. На входе известен параметр $\tau$, алгоритм $\Im$ работает следующим образом:

1. Сгенерируем два случайных $\tau$ — битовых числа ${\boldsymbol {q}}_{1}$ и ${\boldsymbol {q}}_{2}$ и положим ${\boldsymbol {n}}={\boldsymbol {q}}_{1}{\boldsymbol {q}}_{2}\in \mathbb {Z}$.
2. Создадим билинейную группу $\mathbb {G}$ порядка ${\boldsymbol {n}}$, как описанно в разделе выше. Пусть ${\boldsymbol {g}}$ — генератор $\mathbb {G}$, а ${\boldsymbol {f}}:\mathbb {G} \times \mathbb {\mathbb {G} } \rightarrow \mathbb {G} _{1}$ — билинейное отображение.

На выходе получим $({\boldsymbol {q}}_{1},{\boldsymbol {q}}_{2},\mathbb {G} ,\mathbb {G} _{1},{\boldsymbol {f}})$.

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

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

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

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

Литература

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