Benaloh cryptosystem

Scheme Definition

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

Key Generation

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

1. Choose large primes p and q such that r \vert (p-1), \operatorname{gcd}(r, (p-1)/r)=1, and \operatorname{gcd}(r, (q-1))=1
2. Set n=pq, \phi=(p-1)(q-1)
3. Choose y \in \mathbb{Z}^_n such that y^{\phi/r} \not \equiv 1 \mod n. :: Note: If r is composite, it was pointed out by Fousse et al. in 2011 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 in all cases (as should be the case). To address this, the authors propose the following check: let r=p_1p_2\dots p_k be the prime factorization of r. Choose y \in \mathbb{Z}^_n such that for each factor p_i, it is the case that y^{\phi/p_i}\ne 1\mod n.
4. Set x=y^{\phi/r}\mod n

The public key is then y,n, and the private key is \phi,x.

Message Encryption

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

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

Message Decryption

To decrypt a ciphertext c\in\mathbb{Z}^*_n:

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

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

: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 x^i\equiv a \mod n for all 0\dots (r-1). For larger values of r, the Baby-step giant-step algorithm can be used to recover m in O(\sqrt{r}) time and space.

Security

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 \equiv x^r \mod n.

References

References

1. (1985). "A Robust and Verifiable Cryptographically Secure Election Scheme".
2. Benaloh, Josh. (1987). "Verifiable Secret-Ballot Elections (Ph.D. thesis).".
3. Benaloh, Josh. (1994). "Dense Probabilistic Encryption.".
4. (2011). "Benaloh's Dense Probabilistic Encryption Revisited".