Naccache-Stern cryptosystem

Note: this is not to be confused with the Naccache-Stern knapsack 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.

cheme Definition

Like many public key cryptosystems, this scheme works in the group $(mathbb\{Z\}/nmathbb\{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 $u\; =\; prod\_\{i=1\}^\{k/2\}\; p\_i$ and $v\; =\; prod\_\{k/2+1\}^k\; p\_i$.
*Set $sigma\; =\; uv\; =\; prod\_\{i=1\}^k\; p\_i$
*Choose large primes "a" and "b" such that both "p" = 2"au"+1 and "q"=2"bv"+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 $mathbb\{Z\}/sigmamathbb\{Z\}$.

*Pick a random $x\; in\; mathbb\{Z\}/nmathbb\{Z\}$.
*Calculate $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 "n".

Given a ciphertext "c", to decrypt, we calculate

*$c\_i\; equiv\; c^\{phi(n)/p\_i\}\; mod\; n$. Thus:where $m\_i\; equiv\; m\; mod\; p\_i$.
*Since "p"_"i" is chosen to be small, "m"_"i" can be recovered be exhaustive search, i.e. by comparing $c\_i$ to $g^\{jphi(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.

ecurity

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

References

[http://citeseer.ist.psu.edu/naccache98new.html Original paper]