Cryptology ePrint Archive: Report 2013/435

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

Marc Joye and Benoit 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.

Category / Keywords: public-key cryptography / public-key encryption, quadratic residuosity, Goldwasser-Micali cryptosystem, homomorphic encryption, standard model

Publication Info: A preliminary version of this paper appears in the proceedings of EUROCRYPT 2013. This is the full version.

Date: received 10 Jul 2013, last revised 6 May 2014

Contact author: marc joye at technicolor com

Available format(s): PDF | BibTeX Citation

Note: As stated in the proceedings version ([28]), Theorem 3 is incomplete for the construction of LTDFs. It additionally requires the DDH assumption. This is corrected in this full version. We also correct in this version the statement of Theorem 1; the SJS assumption (see Definition 3) is missing in [28]. Finally, we note that the faster decryption algorithms of Appendix B are not present in the proceedings version. This is a new contribution.

Version: 20140506:172631 (All versions of this report)

Short URL: ia.cr/2013/435

Discussion forum: Show discussion | Start new discussion