Welcome to the resource topic for 2008/119
Title:
Linear Bandwidth Naccache-Stern Encryption
Authors: Benoit Chevallier-Mames, David Naccache, 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.
ePrint: https://eprint.iacr.org/2008/119
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .