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

Криптосистема Боне-Го-Ниссима — частично гомоморфная криптосистема, являющаяся модификацией криптосистемы Пэйе и криптосистемы Окамото-Учиямы, разработанная Дэном Бонех совместно с Ю Чжин Го и Коби Ниссимом в 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}$ — билинейное отображение.
3. На выходе получим $({\boldsymbol {q}}_{1},{\boldsymbol {q}}_{2},\mathbb {G} ,\mathbb {G} _{1},{\boldsymbol {f}})$.

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

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

Система является аддитивно гомоморфной. Пусть $({\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}$ (поэтому допускается только одно умножение).

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

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

Требования к стойкости для модели "Алиса - Боб"

Поскольку только одна сторона моет узнать результат (в нашем случае - Боб):

• Безопасность Боба - Мы требуем, чтобы Алиса не могла видеть разницу между различными возможными входными данными Боба.
• Безопасность Алисы - Безопасность Алисы формируется требованием о не получением Бобом никакой информации помимо того, удовлетворяет ли ${\boldsymbol {a}}$ $\phi ()$.

Литература

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