Naccache–Stern Knapsack Cryptosystem
   HOME

TheInfoList



OR:

The Naccache–Stern Knapsack cryptosystem is an atypical
public-key cryptosystem Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic a ...
developed by
David Naccache David Naccache is a cryptographer, currently a professor at the École normale supérieure and a member of its Computer Laboratory. He was previously a professor at Panthéon-Assas University. Biography He received his Ph.D. in 1995 from the ...
and
Jacques Stern Jacques Stern (born 21 August 1949) is a cryptographer, currently a professor at the École Normale Supérieure. He received the 2006 CNRS Gold medal. His notable work includes the cryptanalysis of numerous encryption and signature schemes, the ...
in 1997. This cryptosystem is
deterministic Determinism is the metaphysical view that all events within the universe (or multiverse) can occur only in one possible way. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping mo ...
, and hence is not
semantically secure In cryptography, a semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext. Specifically, any PP (complexity), probabilistic, polynomial-time algorithm (PPTA) that ...
. While unbroken to date, this system also lacks
provable security Provable security refers to any type or level of computer security that can be proved. It is used in different ways by different fields. Usually, this refers to mathematical proofs, which are common in cryptography. In such a proof, the capabilit ...
.


System overview

This system is based on a type of
knapsack problem The knapsack problem is the following problem in combinatorial optimization: :''Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given lim ...
. Specifically, the underlying problem is this: given integers ''c'',''n'',''p'' and ''v''0,...,''v''''n'', find a vector x \in \^n such that :c \equiv \prod_^n v_i^ \mod p The idea here is that when the ''v''''i'' are
relatively prime In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...
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 A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
modulus ''p''. *Pick a positive integer ''n'' and for ''i'' from 0 to ''n'', set ''p''''i'' to be the ''i''th prime, starting with ''p''0 = 2 and such that \prod_^np_i < p. *Pick a secret integer ''s'' < ''p''-1, such that gcd(''p''-1,''s'') = 1. *Set v_i = \sqrt \mod p. The public key is then ''p'',''n'' and ''v''0,...,''v''''n''. The private key is ''s''.


Encryption

To encrypt an ''n''-bit long message ''m'', calculate :c = \prod_^n v_i^ \mod p where ''m''''i'' is the ''i''th bit of the message ''m''.


Decryption

To decrypt a message ''c'', calculate :m = \sum_^n \frac \times \left( \gcd(p_i,c^s \mod p) -1 \right) This works because the fraction :\frac 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 The knapsack problem is the following problem in combinatorial optimization: :''Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given lim ...
: given c = \prod_^n v_i^\pmod p, recover the m_i. 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 In mathematics, for given real numbers a and b, the logarithm \log_b(a) is a number x such that b^x=a. Analogously, in any group G, powers b^k can be defined for all integers k, and the discrete logarithm \log_b(a) is an integer k such that b^k=a ...
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 theorem to partially invert the function without knowing the trapdoor, assuming that the message has a very low
Hamming weight The Hamming weight of a string (computer science), string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the mo ...
.


References


Original PaperRecent bandwidth improvement


See also

*
Merkle–Hellman knapsack cryptosystem The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems. It was published by Ralph Merkle and Martin Hellman in 1978. A polynomial time attack was published by Adi Shamir in 1984. As a result, the cryptosystem is ...
* Graham–Shamir knapsack cryptosystem {{DEFAULTSORT:Naccache-Stern knapsack cryptosystem Public-key encryption schemes