Benaloh cryptosystem

Like many public key cryptosystems, this scheme works in the group ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ where n is a product of two large primes. This scheme is homomorphic and hence malleable.

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

1. Choose large primes p and q such that ${\displaystyle r\vert (p-1),\operatorname {gcd} (r,(p-1)/r)=1,}$ and ${\displaystyle \operatorname {gcd} (r,(q-1))=1}$
2. Set ${\displaystyle n=pq,\phi =(p-1)(q-1)}$
3. Choose ${\displaystyle y\in \mathbb {Z} _{n}^{*}}$ such that ${\displaystyle y^{\phi /r}\not \equiv 1\mod n}$.

Note: If r 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 of r. Choose ${\displaystyle y\in \mathbb {Z} _{n}^{*}}$ such that for each factor ${\displaystyle p_{i}}$, it is the case that ${\displaystyle y^{\phi /p_{i}}\neq 1\mod n}$.

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

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

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

1. Choose a random ${\displaystyle u\in \mathbb {Z} _{n}^{*}}$
2. Set ${\displaystyle E_{r}(m)=y^{m}u^{r}\mod n}$

To decrypt a ciphertext ${\displaystyle c\in \mathbb {Z} _{n}^{*}}$:

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

To understand decryption, first notice that for any ${\displaystyle m\in \mathbb {Z} _{r}}$ and ${\displaystyle u\in \mathbb {Z} _{n}^{*}}$ we have:

${\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}$

To recover m from a, we take the discrete log of a base x. If r is small, we can recover m by an exhaustive search, i.e. checking if ${\displaystyle x^{i}\equiv a\mod n}$ for all ${\displaystyle 0\dots (r-1)}$. For larger values of r, the Baby-step giant-step algorithm can be used to recover m in ${\displaystyle O({\sqrt {r}})}$ time and space.

The security of this scheme rests on the Higher residuosity problem, specifically, given z,r and n where the factorization of n is unknown, it is computationally infeasible to determine whether z is an rth residue mod n, i.e. if there exists an x such that ${\displaystyle z\equiv x^{r}\mod n}$.