Note: this is not to be confused with the Naccache–Stern cryptosystem based 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 Knapsack Cryptosystem is an atypical public-key cryptosystem developed 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 1997. This cryptosystem is deterministic

Deterministic encryption

A deterministic encryption scheme is a cryptosystem which always produces the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm...

, and hence is not semantically secure

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

. This system also lacks provable security

Provable security

In cryptography, a system has provable security if its security requirements can be stated formally in an adversarial model, as opposed to heuristically, with clear assumptions that the adversary has access to the system as well as enough computational resources...

.

System Overview

This system is based on a type of knapsack problem

Knapsack problem

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as...

. Specifically, the underlying problem is this: given integers c,n,p and v₀,...,v_n, find a vector such that

The idea here is that when the v_i are relatively prime and much smaller than the modulus p this problem can be solved easily. It is this observation which allows decryption.

Key Generation

To generate a public/private key pair

• Pick a large prime
  Prime 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...
  
  modulus p.
• Pick a positive integer n.
• For i from 0 to n, set p_i to be the ith prime, starting with p₀ = 2.
• Pick a secret integer s < p-1, such that gcd(p-1,s) = 1.
• Set .

The public key is then p,n and v₀,...,v_n. The private key is s.

Encryption

To encrypt an n-bit long message m, calculate


where m_i is the ith bit of the message m.

Decryption

To decrypt a message c, calculate


This works because the fraction


is 0 or 1 depending on whether p_i divides c^s mod p.