Криптосистема Боне — Го — Ниссима — частично гомоморфная криптосистема, являющаяся модификацией криптосистемы Пэйе и криптосистемы Окамото — Утиямы. Разработана Дэном Боне совместно с Ю Чжин Го и Коби Ниссимом в 2005 году. Основывается на конечных группах составного порядка и билинейных спариваний на эллиптических кривых; система позволяет оценить многовариантные квадратичные полиномы на шифротекстах (например, дизъюнктивная нормальная форма второго порядка (2-ДНФ)).
Система обладает аддитивным гомоморфизмом (поддерживает произвольные добавления и одно умножение (за которым следуют произвольные добавления) для зашифрованных данных).
Используемый в криптосистеме БГН алгоритм основан на задаче Бернсайда..
Алгоритм работы Как и все системы гомоморфного шифрования, КБГН включает следующие процессы: Генерация ключа, шифрование и расшифрование.
Конструкция использует некоторые конечные группы составного порядка, которые поддерживают билинейное отображение. Используются следующие обозначения:
и - две циклические группы конечного порядка . — генератор . — билинейное отображение . Другими словами, для всех и мы имеем . Мы также требуем выполнение условия : является генератором
Мы говорим, что — билинейная группа, если существует группа и билинейное отображение, определённое выше.
Генерация ключа Генерация_Ключа(): Подавая на вход параметр безопасности , вычисляем алгоритм , чтобы получить кортеж . Алгоритм работает следующим образом: Сгенерируем два случайных — битовых числа и и положим . Создадим билинейную группу порядка , где > 3 — заданное число, которое не делится на 3: Найдём наименьшее натуральное число , такое что — простое число и . Рассмотрим группу точек на эллиптической кривой определённую над . Поскольку кривая имеет точек в . Поэтому группа точек на кривой имеет подгруппу порядка , которую обозначим через . Пусть подгруппа в порядка . Модифицированный алгоритм спаривания Вейля (Спаривание Вейля является билинейным, кососимметричным, невырожденным отображением) на кривой выдаёт билинейное отображение , удовлетворяющее заданным условиям На выходе получим . Пусть . Выберем два случайных генератора и определим , как . Тогда это случайный генератор подгруппы порядка . Открытый ключ : . Закрытый ключ : .
Шифрование Шифр():
Мы предполагаем, что пространство сообщений состоит из целых чисел в наборе . Чтобы зашифровать сообщение с помощью открытого ключа выбираем случайный параметр и вычисляем
.
Полученный результат и есть шифротекст.
Расшифрование Расшифр():
Чтобы расшифровать шифротекст используя закрытый ключ , рассмотрим следующее выражение
.
Пусть . Чтобы восстановить достаточно вычислить дискретный логарифм по основанию .
Дешифрование в этой системе занимает полиномиальное время в размере пространства сообщений.
Примеры
Пример работы алгоритма Сначала мы выбираем два различных простых числа
.
Вычислим произведение
.
Далее мы строим группу эллиптических кривых с порядком , которая имеет билинейное отображение. Уравнение для эллиптической кривой
которое определяется над полем для некоторого простого числа . В этом примере мы устанавливаем
.
Следовательно, кривая суперсингулярна с # рациональными точками, которая содержит подгруппу с порядком . В группе мы выбираем два случайных генератора
,
где эти два генератора имеют порядок и вычислим
где порядка . Мы вычисляем зашифрованный текст сообщения
.
Возьмём и вычислим
.
Для расшифровки мы сначала вычислим
и
.
Теперь найдём дискретный логарифм, перебирая все степени следующим образом
.
Обратите внимание, что . Следовательно, расшифровка зашифрованного текста равна , что соответствует исходному сообщению.
Оценка 2-ДНФ Частично гомоморфная система позволяет оценить 2-ДНФ.
На входе: У Алисы есть 2-ДНФ формула , а у Боба есть набор переменных . Обе стороны на входе содержат параметр безопасности .
Боб выполняет следующие действия: Он исполняет алгоритм Генерация_Ключа(), чтобы вычислить и отправляет Алисе. Он вычисляет и отправляет Шифр() для . Алиса выполняет следующие действия: Она выполняет арифметизацию заменяя «» на «», «» на «» и «» на «».Отметим, что это полином степени 2. Алиса вычисляет шифрование для случайно выбранного используя гомоморфные свойства системы шифрования. Результат отправляется Бобу. Если Боб получает шифрование «», он выводит «»; в противном случае, он выводит «».
Гомоморфные свойства Система является аддитивно гомоморфной. Пусть — открытый ключ. Пусть — шифротексты сообщений соответственно. Любой может создать равномерно распределённое шифрование вычисляя произведение для случайного чила в диапазоне .
Более важно то, что любой может умножить два зашифрованных сообщения один раз, используя билинейное отображение. Определим и . Тогда порядка , а порядка . Кроме того, для некоторого (неизвестного) параметра , напишем . Предположим, что нам известны два шифротекста , . Чтобы построить шифрование произведения , выберем случайное число и положим . Получаем , где — распределено равномерно в , как и необходимо.
Таким образом, является равномерно распределённым шифрованием , но только в группе , а не в (поэтому допускается только одно умножение).
Стойкость системы Стойкость данной схемы основана на задаче Бернсайда: зная элемент группы составного порядка , невозможно определить его принадлежность к подгруппе порядка .
Пусть , а — кортеж, созданный , где . Рассмотрим следующую задачу. Для заданного и элемента , выведем «», если порядок равен , в противном случае, выведем «». Другими словами, без знания факторизации группы порядка , необходимо узнать, находится ли элемент в подгруппе группы . Данная задача называется задачей Бёрнсайда.
Понятно, что если мы можем учесть групповой порядок в криптосистеме, то мы знаем закрытый ключ , и в результате система взломана. Кроме того, если мы можем вычислить дискретные логарифмы в группе , то мы можем вычислить и . Таким образом, необходимые условия для безопасности: сложность факторинга и сложность вычисления дискретных логарифмов в .
Примечания
Литература
Ссылки
Категория:Криптография с открытым ключом