## Cryptology ePrint Archive: Report 2008/119

**Linear Bandwidth Naccache-Stern Encryption**

*Benoit Chevallier-Mames and David Naccache and Jacques Stern*

**Abstract: **The Naccache-Stern (NS) knapsack cryptosystem is an original yet
little-known public-key encryption scheme. In this scheme, the
ciphertext is obtained by multiplying public-keys indexed by the
message bits modulo a prime $p$. The cleartext is recovered by
factoring the ciphertext raised to a secret power modulo $p$.

NS encryption requires a multiplication per two plaintext bits on
the average. Decryption is roughly as costly as an RSA decryption.
However, NS features a bandwidth sublinear in $\log p$, namely $\log
p/\log \log p$. As an example, for a $2048$-bit prime $p$, NS
encryption features a 233-bit bandwidth for a 59-kilobyte public key
size.

This paper presents new NS variants achieving bandwidths {\sl
linear} in $\log p$. As linear bandwidth claims a public-key of size
$\log^3 p/\log \log p$, we recommend to combine our scheme with
other bandwidth optimization techniques presented here.

For a $2048$-bit prime $p$, we obtain figures such as 169-bit
plaintext for a 10-kilobyte public key, 255-bit plaintext for a
20-kilobyte public key or a 781-bit plaintext for a 512-kilobyte
public key. Encryption and decryption remain unaffected by our
optimizations: As an example, the 781-bit variant requires 152
multiplications per encryption.

**Category / Keywords: **public-key cryptography / Encryption schemes, Naccache-Stern cryptosystem

**Date: **received 16 Mar 2008, last revised 18 Jun 2008

**Contact author: **benoit chevallier-mames at sgdn gouv fr

**Available format(s): **PDF | BibTeX Citation

**Note: **To appear in SCN 2008

**Version: **20080618:085024 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]