 #jsDisabledContent { display:none; } My Account | Register | Help Flag as Inappropriate This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate?          Excessive Violence          Sexual Content          Political / Social Email this Article Email Address:

Naccache–Stern knapsack cryptosystem

Article Id: WHEBN0006157535
Reproduction Date:

 Title: Naccache–Stern knapsack cryptosystem Author: World Heritage Encyclopedia Language: English Subject: Collection: Publisher: World Heritage Encyclopedia Publication Date:

Naccache–Stern knapsack cryptosystem

Note: this is not to be confused with the Naccache–Stern cryptosystem based on the higher residuosity problem.

The Naccache–Stern Knapsack Cryptosystem is an atypical public-key cryptosystem developed by David Naccache and Jacques Stern in 1997. This cryptosystem is deterministic, and hence is not semantically secure. This system also lacks provable security.

Contents

• System Overview 1
• Key Generation 1.1
• Encryption 1.2
• Decryption 1.3
• References 3

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,...,vn, 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 vi 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 pi to be the ith prime, starting with p0 = 2 and such that \prod_{i=0}^np_i < p.
• Pick a secret integer s < p-1, such that gcd(p-1,s) = 1.
• Set v_i = \sqrt[s]{p_i} \mod p.

The public key is then p,n and v0,...,vn. 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 mi 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 pi divides cs mod p.