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

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

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

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

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

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

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

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

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

Генерация_Ключа( τ {displaystyle au } ):

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

Шифрование

Шифр( O K , M {displaystyle OK,M} ):

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

C = g M h r ∈ G {displaystyle {C}={g}^{M}{h}^{r}in mathbb {G} } .

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

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

Расшифр( S K , C {displaystyle SK,C} ):

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

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

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

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

Примеры

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

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

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

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

n = q 1 q 2 = 7 × 11 = 77 {displaystyle {{n}={q}_{1}{q}_{2}=7 imes 11=77}} .

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

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

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

p = 307 {displaystyle {p=307}} .

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

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

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

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

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

M = 2 {displaystyle {M}{=2}} .

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

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

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

g ^ = g q 1 = [ 182 , 240 ] 7 = [ 146 , 60 ] {displaystyle {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 ] {displaystyle {C}^{q_{1}}=({g}^{M}{h}^{r})^{q_{1}}=({g}^{q_{1}})^{M}={[256,265]^{7}=[299,44]}} .

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

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

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

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

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

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

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

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

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

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

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

g ^ 11 = ∞ {displaystyle {hat {g}}^{11}={infty }} .

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

Оценка 2-ДНФ

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

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

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

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

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

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

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

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

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

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