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

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

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

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

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

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

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

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

Шифрование

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

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

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

Для начала заметим, что для любых $m\in {\mathbb {Z} }_{r}$ и $u\in {\mathbb {Z} }_{n}^{*}$ выполняется: $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$

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

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

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

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

Гомоморфизм

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

${\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)$, где ${\mathcal {E}}(x)$ является функцией шифрования от сообщения $x$

Стойкость

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

Литература

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