The Naccache–Stern cryptosystem is a homomorphic

public-key cryptosystem Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...

whose security rests on the

higher residuosity problem In cryptography, most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem (also called the n th-residuosity problem) is one such problem. This problem is ''easier'' to solve than ...

. The Naccache–Stern cryptosystem was discovered by

David Naccache David Naccache is a cryptographer, currently a professor at the École normale supérieure and a member of its Computer Laboratory. He was previously a professor at Panthéon-Assas University. Biography He received his Ph.D. in 1995 from the � ...

and

Jacques Stern Jacques Stern (born 21 August 1949) is a cryptographer, currently a professor at the École Normale Supérieure. He received the 2006 CNRS Gold medal. His notable work includes the cryptanalysis of numerous encryption and signature schemes, th ...

in 1998.

Scheme Definition

Like many public key cryptosystems, this scheme works in the group

(\mathbb/n\mathbb)^*

where ''n'' is a product of two large

primes A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...

. This scheme is homomorphic and hence

malleable Ductility is a mechanical property commonly described as a material's amenability to drawing (e.g. into wire). In materials science, ductility is defined by the degree to which a material can sustain plastic deformation under tensile stres ...

Key Generation

*Pick a family of ''k'' small distinct

''p''₁,...,''p''_k. *Divide the set in half and set

u = \prod_^ p_i

and

v = \prod_^k p_i

. *Set

\sigma = uv = \prod_^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 The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem (GM) created in 1985 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 i ...

Message Encryption

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

\mathbb/\sigma\mathbb

. *Pick a random

x \in \mathbb/n\mathbb

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

\sigma

. Given a ciphertext ''c'', to decrypt, we calculate *

c_i \equiv c^ \mod n

. Thus :

\begin c^ &\equiv& x^ g^ \mod n\\ &\equiv& g^ \mod n \\ &\equiv& g^ \mod n \end

where

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

c_i

g^

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 The quadratic residuosity problem (QRP) in computational number theory is to decide, given integers a and N, whether a is a quadratic residue modulo N or not. Here N = p_1 p_2 for two unknown primes p_1 and p_2, and a is among the numbers which are ...

known as the

References

{{DEFAULTSORT:Naccache-Stern cryptosystem Public-key encryption schemes