The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem

Goldwasser-Micali cryptosystem

The Goldwasser–Micali cryptosystem is an asymmetric key encryption algorithm developed by Shafi Goldwasser and Silvio Micali in 1982. GM has the distinction of being the first probabilistic public-key encryption scheme which is provably secure under standard cryptographic assumptions...

 (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.

Scheme Definition

Like many public key cryptosystems, this scheme works in the group where n is a product of two large primes

Prime number

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...

. This scheme is homomorphic

Homomorphic encryption

Homomorphic encryption is a form of encryption where a specific algebraic operation performed on the plaintext is equivalent to another algebraic operation performed on the ciphertext. Depending on one's viewpoint, this can be seen as either a positive or negative attribute of the cryptosystem....

 and hence malleable

Malleability (cryptography)

Malleability is a property of some cryptographic algorithms. An encryption algorithm is malleable if it is possible for an adversary to transform a ciphertext into another ciphertext which decrypts to a related plaintext...

.

Key Generation

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) 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.

Message Encryption

To encrypt a message m, where m is taken to be an element in

• Choose a random
• Set

Message Decryption

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

Baby-step giant-step

In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm computing the discrete logarithm. The discrete log problem is of fundamental importance to the area of public key cryptography...

 algorithm, decryption can be done in time .

Security

The security of this scheme rests on the Higher residuosity problem

Higher residuosity problem

In cryptography most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem is one such 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 .