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

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

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

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

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

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

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

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}}$ и билинейное отображение, определённое выше.^[7]

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

Генерация_Ключа(${\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}}$. Модифицированный алгоритм спаривания Вейля (Спаривание Вейля является билинейным, кососимметричным, невырожденным отображением^{[8][4][9][10]}) на кривой выдаёт билинейное отображение ${\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}}}$.^[11][7]

Шифрование

Шифр(${\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} }$ .

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

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

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

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

Примеры

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

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

${\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}}$, что соответствует исходному сообщению.^[12]

Оценка 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}$».^[13]

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

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

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

Стойкость данной схемы основана на задаче Бернсайда: зная элемент группы составного порядка ${\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} }$. Данная задача называется задачей Бёрнсайда^[7].

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

Примечания

1. Pascal Paillier. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes (англ.) // Advances in Cryptology — EUROCRYPT ’99 / Jacques Stern. — Springer Berlin Heidelberg, 1999. — P. 223–238. — ISBN 9783540489108. — doi:10.1007/3-540-48910-x_16. Архивировано 26 июня 2019 года.
2. Tatsuaki Okamoto, Shigenori Uchiyama. A new public-key cryptosystem as secure as factoring (англ.) // Advances in Cryptology — EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlin Heidelberg, 1998. — P. 308–318. — ISBN 9783540697954. — doi:10.1007/bfb0054135. Архивировано 29 августа 2018 года.
3. Mihir Bellare, Juan A. Garay, Tal Rabin. Fast batch verification for modular exponentiation and digital signatures (англ.) // Advances in Cryptology — EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlin Heidelberg, 1998. — P. 236–250. — ISBN 9783540697954. — doi:10.1007/bfb0054130. Архивировано 7 июня 2018 года.
4. Dan Boneh, Matt Franklin. Identity-Based Encryption from the Weil Pairing (англ.) // Advances in Cryptology — CRYPTO 2001 / Joe Kilian. — Springer Berlin Heidelberg, 2001. — P. 213–229. — ISBN 9783540446477. — doi:10.1007/3-540-44647-8_13. Архивировано 22 февраля 2020 года.
5. Evaluating 2-DNF Formulas on Ciphertexts  (неопр.). Дата обращения: 20 февраля 2021. Архивировано 8 августа 2017 года.
6. Secure Computation II // Theory of cryptography : Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005 : proceedings. — Berlin: Springer, 2005. — С. 326. — 1 online resource (xii, 619 pages) с. — ISBN 9783540305767, 3540305769, 3540245731, 9783540245735.
7. Takuho Mitsunaga, Yoshifumi Manabe, Tatsuaki Okamoto. Efficient Secure Auction Protocols Based on the Boneh-Goh-Nissim Encryption. — 2010-11-22. — Т. E96A. — С. 149–163. — doi:10.1007/978-3-642-16825-3_11.
8. О.Н. Василенко. О вычислении спариваний Вейля и Тейта // Тр. по дискр. матем.. — М.: ФИЗМАТЛИТ, 2007. — Т. 10. — С. 18—46.
9. Antoine Joux. A One Round Protocol for Tripartite Diffie–Hellman. — 2006-12-30. — Т. 17. — С. 385–393. — doi:10.1007/10722028_23.
10. Victor Miller. The Weil Pairing, and Its Efficient Calculation // J. Cryptology. — 2004-09-01. — Т. 17. — С. 235–261. — doi:10.1007/s00145-004-0315-8.
11. Secure Computation II // Theory of cryptography : Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005 : proceedings. — Berlin: Springer, 2005. — С. 329. — 1 online resource (xii, 619 pages) с. — ISBN 9783540305767, 3540305769, 3540245731, 9783540245735.
12. Yi, Xun (College teacher),. Homomorphic encryption and applications. — Cham. — 1 online resource (xii, 126 pages) с. — ISBN 978-3-319-12229-8, 3-319-12229-0.
13. Theory of cryptography : Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005 : proceedings. — Berlin: Springer, 2005. — С. 332. — 1 online resource (xii, 619 pages) с. — ISBN 9783540305767, 3540305769, 3540245731, 9783540245735.
14. EUROCRYPT 2010 (2010 : Riveria, France). Advances in cryptology--EUROCRYPT 2010 : 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, May 30-June 3, 2010 : proceedings. — Springer, 2010. — ISBN 9783642131905, 3642131905.

Литература

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

Ссылки

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