### Efficient Cryptosystems From $2^k$-th Power Residue Symbols

Fabrice Benhamouda, Javier Herranz, Marc Joye, and Benoît Libert

##### Abstract

Goldwasser and Micali (1984) highlighted the importance of randomizing the plaintext for public-key encryption and introduced the notion of semantic security. They also realized a cryptosystem meeting this security notion under the standard complexity assumption of deciding quadratic residuosity modulo a composite number. The Goldwasser-Micali cryptosystem is simple and elegant but is quite wasteful in bandwidth when encrypting large messages. A number of works followed to address this issue and proposed various modifications. This paper revisits the original Goldwasser-Micali cryptosystem using 2^k-th power residue symbols. The so-obtained cryptosystems appear as a very natural generalization for k >= 2 (the case k = 1 corresponds exactly to the Goldwasser-Micali cryptosystem). Advantageously, they are efficient in both bandwidth and speed; in particular, they allow for fast decryption. Further, the cryptosystems described in this paper inherit the useful features of the original cryptosystem (like its homomorphic property) and are shown to be secure under a similar complexity assumption. As a prominent application, this paper describes an efficient lossy trapdoor function based thereon.

Note: This is the full version. It also covers the case q = 3 (mod 4).

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. A preliminary version of this paper appears in the proceedings of EUROCRYPT 2013. This is the full version.
Keywords
public-key encryptionquadratic residuosityGoldwasser-Micali cryptosystemhomomorphic encryptionstandard model
Contact author(s)
marc joye @ technicolor com
History
2015-11-12: last of 5 revisions
See all versions
Short URL
https://ia.cr/2013/435

CC BY

BibTeX

@misc{cryptoeprint:2013/435,
author = {Fabrice Benhamouda and Javier Herranz and Marc Joye and Benoît Libert},
title = {Efficient Cryptosystems From $2^k$-th Power Residue Symbols},
howpublished = {Cryptology ePrint Archive, Paper 2013/435},
year = {2013},
note = {\url{https://eprint.iacr.org/2013/435}},
url = {https://eprint.iacr.org/2013/435}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.