Paper 2008/119

Linear Bandwidth Naccache-Stern Encryption

Benoit Chevallier-Mames, David Naccache, and Jacques Stern


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.

Note: To appear in SCN 2008

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Encryption schemesNaccache-Stern cryptosystem
Contact author(s)
benoit chevallier-mames @ sgdn gouv fr
2008-06-18: last of 2 revisions
2008-03-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benoit Chevallier-Mames and David Naccache and Jacques Stern},
      title = {Linear Bandwidth Naccache-Stern Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2008/119},
      year = {2008},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.