The Benaloh Cryptosystem is an extension of the Goldwasser-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 many public key cryptosystems, this scheme works in the group
(Z/nZ)*
Given block size r, a public/private key pair is generated as follows:
r\vert(p-1),\operatorname{gcd}(r,(p-1)/r)=1,
\operatorname{gcd}(r,(q-1))=1
n=pq,\phi=(p-1)(q-1)
y\in
| * | |
| Z | |
| n |
y\phi/r\not\equiv1\modn
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
D(E(m))=m
r=p1p2...pk
y\in
| * | |
| Z | |
| n |
pi
| \phi/pi | |
| y |
\ne1\modn
x=y\phi/r\modn
The public key is then
y,n
\phi,x
To encrypt message
m\inZr
u\in
| * | |
| Z | |
| n |
Er(m)=ymur\modn
To decrypt a ciphertext
| * | |
| c\inZ | |
| n |
a=c\phi/r\modn
m=logx(a)
xm\equiva\modn
To understand decryption, first notice that for any
m\inZr
| * | |
| u\inZ | |
| n |
a=(c)\phi/r\equiv(ymur)\phi/r\equiv(ym)\phi/r(ur)\phi/r\equiv(y\phi/r)m(u)\phi\equiv(x)m(u)0\equivxm\modn
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
xi\equiva\modn
0...(r-1)
O(\sqrt{r})
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
z\equivxr\modn