TheBenaloh Cryptosystem is an extension of theGoldwasser-Micali cryptosystem (GM) created in 1985 by Josh (Cohen) Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in GM each bit is encrypted individually.^[1][2][3]

Like manypublic key cryptosystems, this scheme works in the group${\displaystyle (\mathbb{Z}/n\mathbb{Z}{)}^{\ast }}$ wheren is a product of two largeprimes. This scheme ishomomorphic and hencemalleable.

Given block sizer, a public/private key pair is generated as follows:

1. Choose large primesp andq such that${\displaystyle r|(p-1),\gcd (r,(p-1)/r)=1,}$ and${\displaystyle \gcd (r,(q-1))=1}$
2. Set${\displaystyle n=pq,\varphi =(p-1)(q-1)}$
3. Choose${\displaystyle y\in {\mathbb{Z}}_n^{\ast }}$ such that${\displaystyle y^{\varphi /r}\not\equiv 1\mathrm{mod}n}$.

Note: Ifr is composite, it was pointed out by Fousse et al. in 2011^[4] that the above conditions (i.e., those stated in the original paper) are insufficient to guarantee correct decryption, i.e., to guarantee that${\displaystyle D(E(m))=m}$ in all cases (as should be the case). To address this, the authors propose the following check: let${\displaystyle r=p_1{p}_2\dots p_k}$ be the prime factorization ofr. Choose${\displaystyle y\in {\mathbb{Z}}_n^{\ast }}$ such that for each factor${\displaystyle p_i}$, it is the case that${\displaystyle y^{\varphi /p_i}\ne 1\mathrm{mod}n}$.

1. Set${\displaystyle x=y^{\varphi /r}\mathrm{mod}n}$

The public key is then${\displaystyle y,n}$, and the private key is${\displaystyle \varphi ,x}$.

To encrypt message${\displaystyle m\in {\mathbb{Z}}_r}$:

1. Choose a random${\displaystyle u\in {\mathbb{Z}}_n^{\ast }}$
2. Set${\displaystyle E_r(m)=y^m{u}^r\mathrm{mod}n}$

To decrypt a ciphertext${\displaystyle c\in {\mathbb{Z}}_n^{\ast }}$:

1. Compute${\displaystyle a=c^{\varphi /r}\mathrm{mod}n}$
2. Output${\displaystyle m={\log }_x(a)}$, i.e., findm such that${\displaystyle x^m\equiv a\mathrm{mod}n}$

To understand decryption, first notice that for any${\displaystyle m\in {\mathbb{Z}}_r}$ and${\displaystyle u\in {\mathbb{Z}}_n^{\ast }}$ we have:

${\displaystyle 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\mathrm{mod}n}$

To recoverm froma, we take thediscrete log ofa basex. Ifr is small, we can recover m by an exhaustive search, i.e. checking if${\displaystyle x^i\equiv a\mathrm{mod}n}$ for all${\displaystyle 0\dots (r-1)}$. For larger values ofr, theBaby-step giant-step algorithm can be used to recoverm in${\displaystyle O(\sqrt{r})}$ time and space.

The security of this scheme rests on theHigher residuosity problem, specifically, givenz,r andn where the factorization ofn is unknown, it is computationally infeasible to determine whetherz is anrth residue modn, i.e. if there exists anx such that${\displaystyle z\equiv x^r\mathrm{mod}n}$.

• Public-key encryption schemes