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

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

Разработана Джошем Бенало в 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$, $\varphi =(p-1)(q-1)$;
3. Выбирается $y\in {\mathbb{Z}}_n^{*}$ так, что $y^{\varphi /r}\equiv ̸1modn$.
   Замечание: если $r$ составное, то вышеуказанные условия не являются достаточными для обеспечения правильной расшифровки, то есть для того, чтобы всегда выполнялось $D(E(m))=m$. Чтобы избежать подобного, предлагается выполнять следующую проверку: пусть $r=p_1{p}_2\dots p_k$. Тогда $y$ выбирается таким образом, чтобы для каждого $p_i$ выполнялось $y^{\varphi /p_i}\ne 1modn$ .
4. Пусть $x=y^{\varphi /r}modn$;

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

Шифрование

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

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

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

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

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

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

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

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

Гомоморфизм

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

$ℰ(x_1)\cdot ℰ(x_2)=(g^{x_1}{u}_1^r)(g^{x_2}{u}_2^r)=g^{x_1+x_2}(u_1{u}_2{)}^r=ℰ(x_1+x_{2}modr)$, где $ℰ(x)$ является функцией шифрования от сообщения $x$

Стойкость

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

Литература

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