While unbroken to date, this system also lacks provable security.
Specifically, the underlying problem is this: given integers c,n,p and v0,...,vn, find a vector
such that The idea here is that when the vi are relatively prime and much smaller than the modulus p this problem can be solved easily.
The private key is s. To encrypt an n-bit long message m, calculate where mi is the ith bit of the message m. To decrypt a message c, calculate This works because the fraction is 0 or 1 depending on whether pi divides cs mod p. The security of the trapdoor function relies on the difficulty of the following multiplicative knapsack problem: given
Unlike additive knapsack-based cryptosystems, such as Merkle-Hellman, techniques like Euclidean lattice reduction do not apply to this problem.
The best known generic attack consists of solving the discrete logarithm problem to recover
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 theorem to partially invert the function without knowing the trapdoor, assuming that the message has a very low Hamming weight.