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

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

10.11.2020

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

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

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

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

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

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

  • G {displaystyle mathbb {G} } и G 1 {displaystyle mathbb {G} _{1}} - две циклические группы конечного порядка n {displaystyle {n}} .
  • g {displaystyle {g}} — генератор G {displaystyle mathbb {G} } .
  • f {displaystyle {f}} — билинейное отображение f : G × G → G 1 {displaystyle {f}:mathbb {G} imes mathbb {mathbb {G} } ightarrow mathbb {G} _{1}} . Другими словами, для всех u , v ∈ G {displaystyle {u},{v}in mathbb {G} } и a , b ∈ Z {displaystyle {a},{b}in mathbb {Z} } мы имеем f ( u a , v b ) = f ( u , v ) a b {displaystyle {f}({u}^{a},{v}^{b})={f}({u},{v})^{{a}{b}}} . Мы также требуем выполнение условия : f ( g , g ) {displaystyle {f}({g},{g})} является генератором G 1 {displaystyle mathbb {G} _{1}}
  • Мы говорим, что 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 } .

  • Боб выполняет следующие действия:
  • Он исполняет алгоритм Генерация_Ключа( τ {displaystyle au } ), чтобы вычислить O K , S K {displaystyle {O}{K},{SK}} и отправляет O K {displaystyle {O}{K}} Алисе.
  • Он вычисляет и отправляет Шифр( O K , a j {displaystyle {O}{K},{a_{j}}} ) для j = 1 , . . . , n {displaystyle {j=1,...,n}} .
  • Алиса выполняет следующие действия:
  • Она выполняет арифметизацию Φ ( ϕ ) {displaystyle Phi (phi )} заменяя « ∨ {displaystyle lor } » на « + {displaystyle +} », « ∧ {displaystyle land } » на « × {displaystyle imes } » и « x j ¯ {displaystyle {ar {x_{j}}}} » на « ( 1 − x j ) {displaystyle (1-x_{j})} ».Отметим, что Φ {displaystyle Phi } это полином степени 2.
  • Алиса вычисляет шифрование r × Φ ( a ) {displaystyle {r} imes Phi ({a})} для случайно выбранного r {displaystyle {r}} используя гомоморфные свойства системы шифрования. Результат отправляется Бобу.
  • Если Боб получает шифрование « 0 {displaystyle 0} », он выводит « 0 {displaystyle 0} »; в противном случае, он выводит « 1 {displaystyle 1} ».
  • Гомоморфные свойства

    Система является аддитивно гомоморфной. Пусть ( 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} } .