Naccache–Stern knapsack cryptosystem

System overview

This system is based on a type of knapsack problem. Specifically, the underlying problem is this: given integers c,n,p and v0,...,v**n, find a vector x \in {0,1}^n such that :c \equiv \prod_{i=0}^n v_i^{x_i} \mod p

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 modulus p.
• Pick a positive integer n and for i from 0 to n, set p**i to be the ith prime, starting with p0 = 2 and such that \prod_{i=0}^np_i .
• Pick a secret integer s
• Set v_i = \sqrt[s]{p_i} \mod p.

The public key is then p,n and v0,...,v**n. The private key is s.

Encryption

To encrypt an n-bit long message m, calculate

:c = \prod_{i=0}^n v_i^{m_i} \mod p

where m**i is the ith bit of the message m.

Decryption

To decrypt a message c, calculate

:m = \sum_{i=0}^n \frac{2^i}{p_i-1} \times \left( \gcd(p_i,c^s \mod p) -1 \right)

This works because the fraction

:\frac{ \gcd(p_i,c^s \mod p) - 1 }{p_i - 1}

is 0 or 1 depending on whether p**i divides c**s mod p.

Security

The security of the trapdoor function relies on the difficulty of the following multiplicative knapsack problem: given c = \prod_{i=0}^n v_i^{m_i}\pmod p, recover the m_i. Unlike additive knapsack-based cryptosystems, such as Merkle-Hellman, techniques like [[LLL algorithm|Euclidean lattice reduction]] do not apply to this problem.

The best known generic attack consists of solving the discrete logarithm problem to recover s from p, p_i, v_i, which is considered difficult for a classical computer. However, the quantum algorithm of Shor efficiently solves this problem. Furthermore, currently (2023), there is no proof that the Naccache-Stern knapsack reduces to the discrete logarithm problem.

The best known specific attack (in 2018) uses the [[Birthday paradox|birthday theorem]] to partially invert the function without knowing the trapdoor, assuming that the message has a very low Hamming weight.

References

• Original Paper
• Recent bandwidth improvement

References

1. (October 2018). "Birthday type attacks to the Naccache–Stern knapsack cryptosystem". Information Processing Letters.