Naccache–Stern cryptosystem

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.

Contents

Scheme Definition

Like many public key cryptosystems, this scheme works in the group (\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 p1,...,pk.
  • 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 = 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 \mathbb{Z}/\sigma\mathbb{Z}.

  • Pick a random x \in \mathbb{Z}/n\mathbb{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 pi for each i, and then we apply the Chinese remainder theorem to calculate m mod σ.

Given a ciphertext c, to decrypt, we calculate

  • c_i \equiv c^{\phi(n)/p_i} \mod n. Thus
 \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_ip_i)\phi(n)/p_i} \mod n \\ &\equiv& g^{m_i\phi(n)/p_i} \mod n \end{matrix}

where m_i \equiv m \mod p_i.

  • Since pi is chosen to be small, mi can be recovered be exhaustive search, i.e. by comparing ci to g^{j\phi(n)/p_i} for j from 1 to pi-1.
  • Once mi 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

Original paper


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • 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… …   Wikipedia

  • Naccache–Stern knapsack cryptosystem — Note: this is not to be confused with the Naccache–Stern cryptosystem based on the higher residuosity problem. The Naccache–Stern Knapsack Cryptosystem is an atypical public key cryptosystem developed by David Naccache and Jacques Stern in 1997.… …   Wikipedia

  • Naccache-Stern knapsack cryptosystem — Note: this is not to be confused with the Naccache Stern cryptosystem based on the higher residuosity problem.The Naccache Stern Knapsack Cryptosystem is an atypical Public Key Cryptosystem developed by David Naccache and Jacques Stern in 1997.… …   Wikipedia

  • David Naccache — (2011) David Naccache is a cryptographer, currently a professor at the Pantheon Assas Paris II University and member of the École normale supérieure s Computer Laboratory. He is also a visiting professor at Royal Holloway University of London s… …   Wikipedia

  • Jacques Stern — (born 1949) is a cryptographer, currently a professor at the École Normale Supérieure, where he is Director of the Computer Science Laboratory. He received the 2006 CNRS Gold Medal. His notable work includes the cryptanalysis of numerous… …   Wikipedia

  • Jacques Stern (Kryptologe) — Jacques Stern (* 21. August 1949 in Paris) ist ein französischer Kryptologe, Informatiker und Mathematiker. Jacques Stern Inhaltsverzeichnis 1 …   Deutsch Wikipedia

  • McEliece cryptosystem — In cryptography, the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece.[1] It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance… …   Wikipedia

  • Cramer–Shoup cryptosystem — The Cramer–Shoup system is an asymmetric key encryption algorithm, and was the first efficient scheme proven to be secure against adaptive chosen ciphertext attack using standard cryptographic assumptions. Its security is based on the… …   Wikipedia

  • Niederreiter cryptosystem — In cryptography, the Niederreiter cryptosystem is a variation of the McEliece Cryptosystem developed in 1986 by Harald Niederreiter [1]. It applies the same idea to the parity check matrix H of a linear code. Niederreiter is equivalent to… …   Wikipedia

  • Damgård–Jurik cryptosystem — The Damgård–Jurik cryptosystem[1] is a generalization of the Paillier cryptosystem. It uses computations modulo ns + 1 where n is an RSA modulus and s a (positive) natural number. Paillier s scheme is the special case with s = 1. The order φ(ns + …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”