Naccache–Stern cryptosystem

The Naccache–Stern cryptosystem is a homomorphic public-key cryptosystem whose security rests on the higher residuosity problem. The Naccache–Stern cryptosystem was discovered by David Naccache and Jacques Stern in 1998.

Scheme Definition

Like many Public [key cryptography|public key cryptosystems], this scheme works in the group where n is a product of two large primes. This scheme is homomorphic and hence malleable.

Key Generation

Pick a family of k small distinct primes p₁,...,p_k.
Divide the set in half and set and.
Set
Choose large primes a and b such that both p = 2au+1 and q=2bv+1 are prime.
Set n=''pq.
Choose a random g'' mod n such that g has order φ/4.

The public key is the numbers σ,n,''g and the private key is the pair p'',q.
When k=1 this is essentially the Benaloh cryptosystem.

Message Encryption

This system allows encryption of a message m in the group.

Pick a random.
Calculate

Then E is an encryption of the message m.

Message Decryption

To decrypt, we first find m mod p_i for each i, and then we apply the Chinese [remainder theorem] to calculate m mod.
Given a ciphertext c, to decrypt, we calculate

. Thus

where.

Since p_i is chosen to be small, m_i can be recovered by exhaustive search, i.e. by comparing to for j from 1 to p_i-1.
Once m_i is known for each i, m can be recovered by a direct application of the Chinese remainder theorem.

Security

The semantic security of the Naccache–Stern cryptosystem rests on an extension of the quadratic residuosity problem known as the higher residuosity problem.