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 cryptosystems, this scheme works in the group ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*}}$ 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 ${\displaystyle u=\prod _{i=1}^{k/2}p_{i}}$ and ${\displaystyle v=\prod _{k/2+1}^{k}p_{i}}$.
• Set ${\displaystyle \sigma =uv=\prod _{i=1}^{k}p_{i}}$
• 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 φ(n)/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 ${\displaystyle \mathbb {Z} /\sigma \mathbb {Z} }$.

• Pick a random ${\displaystyle x\in \mathbb {Z} /n\mathbb {Z} }$.
• Calculate ${\displaystyle E(m)=x^{\sigma }g^{m}\mod n}$

Then E(m) 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 ${\displaystyle \sigma }$.

Given a ciphertext c, to decrypt, we calculate

• ${\displaystyle c_{i}\equiv c^{\phi (n)/p_{i}}\mod n}$. Thus

${\displaystyle {\begin{matrix}c^{\phi (n)/p_{i}}&\equiv &x^{\sigma \phi (n)/p_{i}}g^{m\phi (n)/p_{i}}\mod n\\&\equiv &g^{(m_{i}+y_{i}p_{i})\phi (n)/p_{i}}\mod n\\&\equiv &g^{m_{i}\phi (n)/p_{i}}\mod n\end{matrix}}}$

where ${\displaystyle m_{i}\equiv m\mod p_{i}}$.

• Since p_i is chosen to be small, m_i can be recovered by exhaustive search, i.e. by comparing ${\displaystyle c_{i}}$ to ${\displaystyle g^{j\phi (n)/p_{i}}}$ 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.

References[]

Naccache, David; Stern, Jacques (1998). "A New Public Key Cryptosystem Based on Higher Residues". Proceedings of the 5th ACM Conference on Computer and Communications Security. CCS '98. ACM. pp. 59–66. doi:10.1145/288090.288106. ISBN 1-58113-007-4.