Криптосистема Бенало

Криптосистема Бенало — модификация криптосистемы Гольдвассер — Микали. Основное их отличие состоит в том, что криптосистема позволяет зашифровывать блок данных единовременно, в то время как в схеме Гольдвассера и Микали каждый бит данных шифруется отдельно[1].

Разработана Джошем Бенало в 1988 году. Получила применение в системах электронного голосования[2].

Система является частично гомоморфной. Как и во многих криптосистемах с открытым ключом, эта система работает в группе , где  — произведение двух простых чисел.

Описание алгоритма

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

  1. Выбираются блок размера и два больших различных простых числа и , удовлетворяющие следующим условиям:
    1. и  — взаимно простые ;
    2. и  — взаимно простые.
  2. Вычисляется , ;
  3. Выбирается так, что .
    Замечание: если составное, то вышеуказанные условия не являются достаточными для обеспечения правильной расшифровки[3], то есть для того, чтобы всегда выполнялось . Чтобы избежать подобного, предлагается выполнять следующую проверку: пусть . Тогда выбирается таким образом, чтобы для каждого выполнялось .
  4. Пусть ;

Тогда открытым ключом является , а секретным ключом — .

Шифрование

Шифрование сообщения :

  1. Выбирается произвольное ;
  2. Тогда .

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

Для начала заметим, что для любых и выполняется:

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

Расшифрование шифртекста :

  1. Вычисляется ;
  2. Подбирается , то есть такое , что

Свойства криптосистемы

Гомоморфизм

Криптосистема Бенало гомоморфна относительно операции сложения:

, где является функцией шифрования от сообщения

Стойкость

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

Литература

  1. А. И. Трубей «Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор)»
  2. Benaloh, Josh (1994) "Dense Probabilistic Encryption"

Примечания

  1. Benaloh, Josh (1994) "Dense Probabilistic Encryption"
  2. Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор) (А.И.Трубей)
  3. Fousse, Laurent; Lafourcade, Pascal; Alnuaimi, Mohamed (2011). "Benaloh's Dense Probabilistic Encryption Revisited"