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) Short URL: ia.cr/2008/119 Discussion forum: Show discussion | Start new discussion