The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1994 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.
A public/private key pair is generated as follows:
- Choose a blocksize r.
- Choose large primes p and q such that r divides (p-1), gcd(r, (p-1)/r) = 1 and gcd(q-1,r) = 1.
- Set n = pq
- Choose such that .
The public key is then y,n, and the private key is the two primes p,q.
To encrypt a message m, where m is taken to be an element in
- Choose a random
To understand decryption, we first notice that for any m,u we have
Since m < r and , we can conclude that if and only if m = 0.
So if is an encryption of m, given the secret key p,q we can determine whether m=0. If r is small, we can decrypt z by doing an exhaustive search, i.e. decrypting the messages y-iz for i from 1 to r. By precomputing values, using the Baby-step giant-step algorithm, decryption can be done in time .
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 .
Original Paper (ps)