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

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

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

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

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

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

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

  1. и - две циклические группы конечного порядка .
  2. — генератор .
  3. — билинейное отображение . Другими словами, для всех и мы имеем . Мы также требуем выполнение условия : является генератором

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

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

Генерация_Ключа( ) :

  • Подавая на вход параметр безопасности , вычисляем алгоритм , чтобы получить кортеж . Алгоритм работает следующим образом:
    1. Сгенерируем два случайных — битовых числа и и положим .
    2. Создадим билинейную группу порядка , где > 3 — заданное число, которое не делится на 3:
      1. Найдём наименьшее натуральное число , такое что — простое число и .
      2. Рассмотрим группу точек на эллиптической кривой опреленную над . Поскольку кривая имеет точек в . Поэтому группа точек на кривой имеет подруппу порядка , которую обозначим через .
      3. Пусть подгруппа в порядка . Модифицированный алгоритм (Спаривание Вейля является билинейным, кососимметричным, невырожденным отображением ) на кривой выдаёт билинейное отображение , удовлетворяющее заданным условиям
    3. На выходе получим .
  • Пусть . Выберем два случайных генератора и определим , как . Тогда это случайный генератор подгруппы порядка . Открытый ключ : . Закрытый ключ : .

Шифрование

Шифр( ):

Мы предполагаем, что пространство сообщений состоит из целых чисел в наборе . Чтобы зашифровать сообщение с помощью открытого ключа выбираем случайный параметр и вычисляем

.

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

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

Расшифр( ):

Чтобы расшифровать шифротекст используя закрытый ключ , рассмотрим следующее выражение

.

Пусть . Чтобы восстановить достаточно вычислить дискретный логарифм по основанию .

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

Примеры

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

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

.

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

.

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

которое определяется над полем для некоторого простого числа . В этом примере мы устанавливаем

.

Следовательно, кривая суперсингулярна с # рациональными точками, которая содержит подгруппу с порядком . В группе мы выбираем два случайных генератора

,

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

где порядка . Мы вычисляем зашифрованный текст сообщения

.

Возьмём и вычислим

.

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

и

.

Теперь найдём дискретный логарифм, перебирая все степени следующим образом

.

Обратите внимание, что . Следовательно, расшифровка зашифрованного текста равна , что соответствует исходному сообщению.

Оценка 2-ДНФ

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

На входе: У Алисы есть 2-ДНФ формула , а у Боба есть набор переменных . Обе стороны на входе содержат параметр безопасности .

  1. Боб выполняет следующие действия:
    1. Он исполняет алгоритм Генерация_Ключа( ) , чтобы вычислить и отправляет Алисе.
    2. Он вычисляет и отправляет Шифр( ) для .
  2. Алиса выполняет следующие действия:
    1. Она выполняет арифметизацию заменяя « » на « », « » на « » и « » на « ».Отметим, что это полином степени 2.
    2. Алиса вычисляет шифрование для случайно выбранного используя гомоморфные свойства системы шифрования. Результат отправляется Бобу.
  3. Если Боб получает шифрование « », он выводит « »; в противном случае, он выводит « ».

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

Система является аддитивно гомоморфной. Пусть — открытый ключ. Пусть — шифротексты сообщений соответственно. Любой может создать равномерно распределённое шифрование вычисляя произведение для случайного чила в диапазоне .

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

Таким образом, является равномерно распределённым шифрованием , но только в группе , а не в (поэтому допускается только одно умножение).

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

Стойкость данной схемы основана на задаче Бернсайда : зная элемент группы составного порядка , невозможно определить его приналежность к подгруппе порядка .

Пусть , а — кортеж, созданный , где . Рассмотрим следующую задачу. Для заданного и элемента , выведем « », если порядок равен , в противном случае, выведем « ». Другими словами, без знания факторизации группы порядка , необходимо узнать, находится ли элемент в подгруппе группы . Данная задача называется задачей Бёрнсайда .

Понятно, что если мы можем учесть групповой порядок в криптосистеме, то мы знаем закрытый ключ , и в результате система взломана. Кроме того, если мы можем вычислить дискретные логарифмы в группе , то мы можем вычислить и . Таким образом, необходимые условия для безопасности: сложность факторинга и сложность вычисления дискретных логарифмов в .

Примечания

  1. Pascal Paillier. (англ.) // Advances in Cryptology — EUROCRYPT ’99 / Jacques Stern. — Springer Berlin Heidelberg, 1999. — P. 223–238 . — ISBN 9783540489108 . — doi : . 26 июня 2019 года.
  2. Tatsuaki Okamoto, Shigenori Uchiyama. (англ.) // Advances in Cryptology — EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlin Heidelberg, 1998. — P. 308–318 . — ISBN 9783540697954 . — doi : . 29 августа 2018 года.
  3. Mihir Bellare, Juan A. Garay, Tal Rabin. (англ.) // Advances in Cryptology — EUROCRYPT'98 / Kaisa Nyberg. — Springer Berlin Heidelberg, 1998. — P. 236–250 . — ISBN 9783540697954 . — doi : . 7 июня 2018 года.
  4. Dan Boneh, Matt Franklin. (англ.) // Advances in Cryptology — CRYPTO 2001 / Joe Kilian. — Springer Berlin Heidelberg, 2001. — P. 213–229 . — ISBN 9783540446477 . — doi : . 22 февраля 2020 года.
  5. . Дата обращения: 20 февраля 2021. 8 августа 2017 года.
  6. Secure Computation II // . — Berlin: Springer, 2005. — С. 326. — 1 online resource (xii, 619 pages) с. — ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
  7. Takuho Mitsunaga, Yoshifumi Manabe, Tatsuaki Okamoto. . — 2010-11-22. — Т. E96A . — С. 149–163 . — doi : .
  8. О.Н. Василенко. // Тр. по дискр. матем.. — М. : ФИЗМАТЛИТ, 2007. — Т. 10. — С. 18—46.
  9. Antoine Joux. . — 2006-12-30. — Т. 17 . — С. 385–393 . — doi : .
  10. Victor Miller. // J. Cryptology. — 2004-09-01. — Т. 17 . — С. 235–261 . — doi : .
  11. Secure Computation II // . — Berlin: Springer, 2005. — С. 329. — 1 online resource (xii, 619 pages) с. — ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
  12. Yi, Xun (College teacher),. . — Cham. — 1 online resource (xii, 126 pages) с. — ISBN 978-3-319-12229-8 , 3-319-12229-0.
  13. . — Berlin: Springer, 2005. — С. 332. — 1 online resource (xii, 619 pages) с. — ISBN 9783540305767 , 3540305769, 3540245731, 9783540245735.
  14. EUROCRYPT 2010 (2010 : Riveria, France). . — Springer, 2010. — ISBN 9783642131905 , 3642131905.

Литература

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

Ссылки

  • С. И. Адян. // УМН. — 2010. — Сентябрь ( т. 65 , вып. 5 ).
Источник —

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