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

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

Система является частично гомоморфной . Как и во многих криптосистемах с открытым ключом, эта система работает в группе ${\displaystyle \mathbb {(} {Z}/n\mathbb {Z} )^{*}}$ , где ${\displaystyle n}$ — произведение двух простых чисел .

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

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

1. Выбираются блок размера ${\displaystyle r}$ и два больших различных простых числа ${\displaystyle p}$ и ${\displaystyle q}$ , удовлетворяющие следующим условиям:
   1. ${\displaystyle r}$ и ${\displaystyle (p-1)/r}$ — взаимно простые ;
   2. ${\displaystyle r}$ и ${\displaystyle q-1}$ — взаимно простые.
2. Вычисляется ${\displaystyle n=p\times q}$ , ${\displaystyle \phi =(p-1)(q-1)}$ ;
3. Выбирается ${\displaystyle y\in \mathbb {Z} _{n}^{*}}$ так, что ${\displaystyle y^{\phi /r}\not \equiv 1\mod n}$ .
   Замечание: если ${\displaystyle r}$ составное, то вышеуказанные условия не являются достаточными для обеспечения правильной расшифровки , то есть для того, чтобы всегда выполнялось ${\displaystyle D(E(m))=m}$ . Чтобы избежать подобного, предлагается выполнять следующую проверку: пусть ${\displaystyle r=p_{1}p_{2}\dots p_{k}}$ . Тогда ${\displaystyle y}$ выбирается таким образом, чтобы для каждого ${\displaystyle p_{i}}$ выполнялось ${\displaystyle y^{\phi /p_{i}}\neq 1\mod n}$ .
4. Пусть ${\displaystyle x=y^{\phi /r}\mod n}$ ;

Тогда открытым ключом является ${\displaystyle (y,r,n)}$ , а секретным ключом — ${\displaystyle (\phi ,x)}$ .

Шифрование

Шифрование сообщения ${\displaystyle m\in {\mathbb {Z} }_{r}}$ :

1. Выбирается произвольное ${\displaystyle u\in {\mathbb {Z} _{n}^{*}}}$ ;
2. Тогда ${\displaystyle E_{r}(m)=y^{m}u^{r}\mod n}$ .

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

Для начала заметим, что для любых ${\displaystyle m\in {\mathbb {Z} }_{r}}$ и ${\displaystyle u\in {\mathbb {Z} }_{n}^{*}}$ выполняется: ${\displaystyle a=(c)^{\phi /r}\equiv (y^{m}u^{r})^{\phi /r}\equiv (y^{m})^{\phi /r}(u^{r})^{\phi /r}\equiv (y^{\phi /r})^{m}(u)^{\phi }\equiv (x)^{m}(u)^{0}\equiv x^{m}\mod n}$

Таким образом, чтобы вычислить ${\displaystyle m}$ , зная ${\displaystyle a}$ , проводится операция дискретного логарифмирования из ${\displaystyle a}$ по основанию ${\displaystyle x}$ . Если число ${\displaystyle r}$ небольшое, возможно нахождение ${\displaystyle m}$ через исчерпывающий перебор, то есть проверкой выполнения равенства ${\displaystyle x^{i}\equiv a\mod n}$ для всех ${\displaystyle 0\dots (r-1)}$ . При больших значениях ${\displaystyle r}$ , нахождение ${\displaystyle m}$ можно проводить с помощью алгоритма Гельфонда — Шенкса (алгоритм больших и малых шагов) , получив временную сложность расшифрования ${\displaystyle O({\sqrt {r}})}$ .

Расшифрование шифртекста ${\displaystyle c\in {\mathbb {Z} }_{n}^{*}}$ :

1. Вычисляется ${\displaystyle a=c^{\phi /r}\mod n}$ ;
2. Подбирается ${\displaystyle m=\log _{x}(a)}$ , то есть такое ${\displaystyle m}$ , что ${\displaystyle x^{m}\equiv a\mod n}$

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

Гомоморфизм

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

${\displaystyle {\mathcal {E}}(x_{1})\cdot {\mathcal {E}}(x_{2})=(g^{x_{1}}u_{1}^{r})(g^{x_{2}}u_{2}^{r})=g^{x_{1}+x_{2}}(u_{1}u_{2})^{r}={\mathcal {E}}(x_{1}+x_{2}\;{\bmod {\;}}r)}$ , где ${\displaystyle {\mathcal {E}}(x)}$ является функцией шифрования от сообщения ${\displaystyle x}$

Стойкость

Стойкость криптосистемы Бенало основана на труднорешаемой задаче о вычетах высокой степени. Зная размер блока ${\displaystyle r}$ , модуль ${\displaystyle n}$ и шифртекст ${\displaystyle E(M)}$ , где разложение на множители числа ${\displaystyle n}$ неизвестно, — определить открытый текст вычислительно сложно.

Литература

2. Benaloh, Josh (1994) "Dense Probabilistic Encryption"

Примечания