Naccache–Stern knapsack cryptosystem
Security
Security
--------

The security of the trapdoor function relies on the difficulty of the following 
multiplicative [knapsack problem](/wiki/Knapsack_problem "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](/wiki/Merkle-Hellman_knapsack_cryptosystem "Merkle-Hellman knapsack cryptosystem"), techniques like [Euclidean 
lattice reduction](/wiki/LLL_algorithm "LLL algorithm") do not apply to this problem.

The best known generic attack consists of solving the [discrete logarithm problem](/wiki/Discrete_logarithm_problem "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](/wiki/Shor%27s_algorithm "Shor's algorithm") 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 
theorem](/wiki/Birthday_paradox "Birthday paradox") to partially invert the function without knowing the trapdoor, assuming that the message has 
a very low [Hamming weight](/wiki/Hamming_weight "Hamming weight").


How does the birthday theorem relate to the security of the trapdoor function?