Naccache-Stern cryptosystem
Encyclopedia
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.
where n is a product of two large primes
. This scheme is homomorphic
and hence malleable
.
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
.
.
Then E(m) is an encryption of the message m.
to calculate m mod
.
Given a ciphertext c, to decrypt, we calculate
where
.
of the Naccache–Stern cryptosystem rests on an extension of the quadratic residuosity problem
known as the higher residuosity problem
.
The Naccache–Stern cryptosystem is a homomorphic
Homomorphic encryption
Homomorphic encryption is a form of encryption where a specific algebraic operation performed on the plaintext is equivalent to another algebraic operation performed on the ciphertext. Depending on one's viewpoint, this can be seen as either a positive or negative attribute of the cryptosystem....
public-key cryptosystem whose security rests on the higher residuosity problem
Higher residuosity problem
In cryptography most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem is one such problem...
. The Naccache–Stern cryptosystem was discovered by David Naccache
David Naccache
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 Information Security Group. He received his Ph.D. in 1995...
and Jacques Stern
Jacques Stern
Jacques Stern 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...
in 1998.
Scheme Definition
Like many public key cryptosystems, this scheme works in the group where n is a product of two large primesPrime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
. This scheme is homomorphic
Homomorphic encryption
Homomorphic encryption is a form of encryption where a specific algebraic operation performed on the plaintext is equivalent to another algebraic operation performed on the ciphertext. Depending on one's viewpoint, this can be seen as either a positive or negative attribute of the cryptosystem....
and hence malleable
Malleability (cryptography)
Malleability is a property of some cryptographic algorithms. An encryption algorithm is malleable if it is possible for an adversary to transform a ciphertext into another ciphertext which decrypts to a related plaintext...
.
Key Generation
- Pick a family of k small distinct primesPrime numberA prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
p1,...,pk. - 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 φ(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
Benaloh cryptosystem
The Benaloh Cryptosystem is an extension of the Goldwasser-Micali cryptosystem created in 1994 by Josh Benaloh. The main improvement of the Benaloh Cryptosystem over GM is that longer blocks of data can be encrypted at once, whereas in GM each bit is encrypted individually.-Scheme...
.
Message Encryption
This system allows encryption of a message m in the group.- Pick a random
. - Calculate
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 theoremChinese remainder theorem
The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra.In its most basic form it concerned with determining n, given the remainders generated by division of n by several numbers...
to calculate m mod
.Given a ciphertext c, to decrypt, we calculate
. Thus
where
.
- Since pi is chosen to be small, mi can be recovered be exhaustive search, i.e. by comparing
to 
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 securitySemantic security
Semantic security is a widely used definition for security in an asymmetric key encryption algorithm. For a cryptosystem to be semantically secure, it must be infeasible for a computationally bounded adversary to derive significant information about a message when given only its ciphertext and...
of the Naccache–Stern cryptosystem rests on an extension of the quadratic residuosity problem
Quadratic residuosity problem
The quadratic residuosity problem in computational number theory is the question of distinguishing by calculating the quadratic residues modulo N, where N is a composite number...
known as the higher residuosity problem
Higher residuosity problem
In cryptography most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem is one such problem...
.