Криптосистема Бенало — модификация криптосистемы Гольдвассер — Микали. Основное их отличие состоит в том, что криптосистема позволяет зашифровывать блок данных единовременно, в то время как в схеме Гольдвассера и Микали каждый бит данных шифруется отдельноBenaloh, Josh (1994) "Dense Probabilistic Encryption".
Разработана Джошем Бенало в 1988 году. Получила применение в системах электронного голосованияГомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор) (А.И.Трубей).
Система является частично гомоморфной. Как и во многих криптосистемах с открытым ключом, эта система работает в группе , где — произведение двух простых чисел.
Описание алгоритма
Генерация ключа Выбираются блок размера и два больших различных простых числа и , удовлетворяющие следующим условиям: и — взаимно простые ; и — взаимно простые. Вычисляется , ; Выбирается так, что .Замечание: если составное, то вышеуказанные условия не являются достаточными для обеспечения правильной расшифровкиFousse, Laurent; Lafourcade, Pascal; Alnuaimi, Mohamed (2011). "Benaloh's Dense Probabilistic Encryption Revisited", то есть для того, чтобы всегда выполнялось . Чтобы избежать подобного, предлагается выполнять следующую проверку: пусть . Тогда выбирается таким образом, чтобы для каждого выполнялось . Пусть ;
Тогда открытым ключом является , а секретным ключом — .
Шифрование Шифрование сообщения :
Выбирается произвольное ; Тогда .
Расшифрование Для начала заметим, что для любых и выполняется:
Таким образом, чтобы вычислить , зная , проводится операция дискретного логарифмирования из по основанию . Если число небольшое, возможно нахождение через исчерпывающий перебор, то есть проверкой выполнения равенства для всех . При больших значениях , нахождение можно проводить с помощью алгоритма Гельфонда — Шенкса (алгоритм больших и малых шагов), получив временную сложность расшифрования .
Расшифрование шифртекста :
Вычисляется ; Подбирается , то есть такое , что
Свойства криптосистемы
Гомоморфизм
Криптосистема Бенало гомоморфна относительно операции сложения:
, где является функцией шифрования от сообщения
Стойкость
Стойкость криптосистемы Бенало основана на труднорешаемой задаче о вычетах высокой степени. Зная размер блока , модуль и шифртекст , где разложение на множители числа неизвестно, — определить открытый текст вычислительно сложно.
Литература
А. И. Трубей «Гомоморфное шифрование: безопасность облачных вычислений и другие приложения (обзор)» Benaloh, Josh (1994) "Dense Probabilistic Encryption"
Примечания
Категория:Криптография с открытым ключом