Top

Journal of Cryptology

Published in:

26-04-2016

Efficient Cryptosystems From \(\mathbf{2}^{{\varvec{k}}}\)-th Power Residue Symbols

Authors: Fabrice Benhamouda, Javier Herranz, Marc Joye, Benoît Libert

Published in: Journal of Cryptology | Issue 2/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Goldwasser and Micali (J Comput Syst Sci 28(2):270–299, 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 \ge 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.

previous article The Security of Tandem-DM in the Ideal Cipher Model

next article Photonic Side-Channel Analysis of Arbiter PUFs

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

This notion refers to an attack scenario where the adversary is given t encryptions of possibly correlated messages, opens t / 2 out of these (and thereby obtains the messages and encryption coins) before attempting to harm the security of the remaining ciphertexts.

M. Abdalla, F. Ben Hamouda, and D. Pointcheval. Tighter reductions for forward-secure signature schemes. In PKC 2013, LNCS 7778, pp. 292–311. Springer, February/March 2013.

M. Bellare, Z. Brakerski, M. Naor, T. Ristenpart, G. Segev, H. Shacham, and S. Yilek. Hedged public-key encryption: How to protect against bad randomness. In ASIACRYPT 2009, LNCS 5912, pp. 232–249. Springer, December 2009.

M. Bellare, A. Boldyreva, and A. O’Neill. Deterministic and efficiently searchable encryption. In CRYPTO 2007, LNCS 4622, pp. 535–552. Springer, August 2007.

L. Blum, M. Blum, and M. Shub. Comparison of two pseudo-random number generators. In CRYPTO’82, pp. 61–78. Plenum Press, New York, USA, 1982.

L. Blum, M. Blum, and M. Shub. A simple unpredictable pseudo-random number generator. SIAM J. Comput., 15(2):363–383, 1986.

J. D. C. Benaloh. Verifiable Secret-Ballot Elections. PhD thesis, Yale University, New Haven, CT, USA, 1987.

A. Boldyreva, S. Fehr, and A. O’Neill. On notions of security for deterministic encryption, and efficient constructions without random oracles. In CRYPTO 2008, LNCS 5157, pp. 335–359. Springer, August 2008.

M. Blum and S. Goldwasser. An efficient probabilistic public-key encryption scheme which hides all partial information. In CRYPTO’84, LNCS 196, pp. 289–302. Springer, August 1984.

M. Bellare, D. Hofheinz, and S. Yilek. Possibility and impossibility results for encryption and commitment secure under selective opening. In EUROCRYPT 2009, LNCS 5479, pp. 1–35. Springer, April 2009.

10.

Z. Brakerski and G. Segev. Better security for deterministic public-key encryption: The auxiliary-input setting. In CRYPTO 2011, LNCS 6841, pp. 543–560. Springer, August 2011.

11.

J. D. Cohen and M. J. Fischer. A robust and verifiable cryptographically secure election scheme (extended abstract). In 26th FOCS, pp. 372–382. IEEE Computer Society Press, October 1985.

12.

D. Catalano, R. Gennaro, N. Howgrave-Graham, and P. Q. Nguyen. Paillier’s cryptosystem revisited. In ACM CCS 01, pp. 206–214. ACM Press, November 2001.

13.

D. Coppersmith. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptology, 10(4):233–260, 1997.

14.

I. Damgård, M. Jurik, and J. B. Nielsen. A generalization of Paillier’s public-key system with applications to electronic voting. Int. J. Inf. Sec., 9(6):371–385, 2010.

15.

C. Dwork, M. Naor, O. Reingold, and L. Stockmeyer. Magic functions. J. ACM, 50(6):852–921, 2003.

16.

Y. Dodis, L. Reyzin, and A. Smith. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In EUROCRYPT 2004, LNCS 3027, pp. 523–540. Springer, May 2004.

17.

ECRYPT II. Yearly report on algorithms and keysizes, 2012.

18.

D. M. Freeman, O. Goldreich, E. Kiltz, A. Rosen, and G. Segev. More constructions of lossy and correlation-secure trapdoor functions. In PKC 2010, LNCS 6056, pp. 279–295. Springer, May 2010.

19.

D. M. Freeman, O. Goldreich, E. Kiltz, A. Rosen, and G. Segev. More constructions of lossy and correlation-secure trapdoor functions. J. Cryptology, 26(1):39–74, January 2013.

20.

S. Goldwasser and S. Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270–299, 1984.

21.

O. Goldreich. Foundations of Cryptography. Cambridge University Press, 2004.

22.

J. Groth. Cryptography in subgroups of \({\mathbb{Z}}_n\). In TCC 2005, LNCS 3378, pp. 50–65. Springer, February 2005.

23.

J. A. Horwitz. Applications of Cayley Graphs, Bilinearity, and Higher-Order Residues to Cryptology. PhD thesis, Stanford University, Stanford, CA, USA, 2004.

24.

D. Hofheinz, E. Kiltz, and V. Shoup. Practical chosen ciphertext secure encryption from factoring. J. Cryptology, 26(1):102–118, January 2013.

25.

B. Hemenway and R. Ostrovsky. Extended-DDH and lossy trapdoor functions. In PKC 2012, LNCS 7293, pp. 627–643. Springer, May 2012.

26.

K. Ireland and M. Rosen. A Classical Introduction to Modern Number Theory, Graduate Texts in Mathematics 84. Springer, 2nd edition, 1990.

27.

ISO/IEC 18033-2. Information technology – Security techniques – Encryption algorithms – Part 2: Asymmetric ciphers. International Organization for Standardization, May 2006.

28.

M. Joye and P. Paillier. Fast generation of prime numbers on portable devices: An update. In CHES 2006, LNCS 4249, pp. 160–173. Springer, October 2006.

29.

M. Joye, P. Paillier, and S. Vaudenay. Efficient generation of prime numbers. In CHES 2000, LNCS 1965, pp. 340–354. Springer, August 2000.

30.

K. Kurosawa, Y. Katayama, W. Ogata, and S. Tsujii. General public key residue cryptosystems and mental poker protocols. In EUROCRYPT’90, LNCS 473, pp. 374–388. Springer, May 1990.

31.

J. Katz and Y. Lindell. Introduction to Modern Cryptography. CRC Press, 2007.

32.

E. Kiltz, A. O’Neill, and A. Smith. Instantiability of RSA-OAEP under chosen-plaintext attack. In CRYPTO 2010, LNCS 6223, pp. 295–313. Springer, August 2010.

33.

E. Kiltz, K. Pietrzak, M. Stam, and M. Yung. A new randomness extraction paradigm for hybrid encryption. In EUROCRYPT 2009, LNCS 5479, pp. 590–609. Springer, April 2009.

34.

F. Lemmermeyer. Reciprocity Laws. Springer Monographs in Mathematics. Springer, 2000.

35.

J. Monnerat and S. Vaudenay. Generic homomorphic undeniable signatures. In ASIACRYPT 2004, LNCS 3329, pp. 354–371. Springer, December 2004.

36.

J. Monnerat and S. Vaudenay. Undeniable signatures based on characters: How to sign with one bit. In PKC 2004, LNCS 2947, pp. 69–85. Springer, March 2004.

37.

P. Mol and S. Yilek. Chosen-ciphertext security from slightly lossy trapdoor functions. In PKC 2010, LNCS 6056, pp. 296–311. Springer, May 2010.

38.

P. Q. Nguyen. Public-key cryptanalysis. In Recent Trends in Cryptography, Contemporary Mathematics. AMS–RSME, 2009.

39.

D. Naccache and J. Stern. A new public key cryptosystem based on higher residues. In ACM CCS 98, pp. 59–66. ACM Press, November 1998.

40.

T. Okamoto and D. Pointcheval. The gap-problems: A new class of problems for the security of cryptographic schemes. In PKC 2001, LNCS 1992, pp. 104–118. Springer, February 2001.

41.

T. Okamoto and S. Uchiyama. A new public-key cryptosystem as secure as factoring. In EUROCRYPT’98, LNCS 1403, pp. 308–318. Springer, May/June 1998.

42.

P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT’99, LNCS 1592, pp. 223–238. Springer, May 1999.

43.

S. H. Pohlig and M. E. Hellman. An improved algorithm for computing logarithms over \({\rm GF}(p)\) and its cryptographic significance. IEEE Tran. Inf. Theory, 24(1):106–110, 1978.

44.

S. J. Park, B. Y. Lee, and D. H. Won. A probabilistic encryption using very high residuosity and its applications. In Global Telecommunications Conference (GLOBECOM ’95), pp. 1179–1182. IEEE Press, 1995.

45.

C. Peikert and B. Waters. Lossy trapdoor functions and their applications. In 40th ACM STOC, pp. 187–196. ACM Press, May 2008.

46.

O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6), 2009. Earlier version in STOC 2005.

47.

R. Scheidler. A public-key cryptosystem using purely cubic fields. J. Cryptology, 11(2):109–124, 1998.

48.

V. Shoup. A Computational Introduction to Number Theory and Algebra. Cambridge University Press, 2nd edition, 2010.

49.

R. Scheidler and H. C. Williams. A public-key cryptosystem utilizing cyclotomic fields. Des. Codes Cryptography, 6(2):117–131, 1995.

50.

H. Wee. Dual projective hashing and its applications - lossy trapdoor functions and more. In EUROCRYPT 2012, LNCS 7237, pp. 246–262. Springer, April 2012.

51.

S. Y. Yan. Number Theory for Computing. Springer, 2nd edition, 2002.

52.

Y. Zheng, T. Matsumoto, and H. Imai. Residuosity problem and its applications to cryptography. Trans. IEICE, E-71(8):759–767, 1988.

Title: Efficient Cryptosystems From -th Power Residue Symbols
Authors: Fabrice Benhamouda
Javier Herranz
Marc Joye
Benoît Libert
Publication date: 26-04-2016
Publisher: Springer US
Published in: Journal of Cryptology / Issue 2/2017
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-016-9229-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2017

Security of Blind Signatures Revisited

Secret-Sharing for NP

Photonic Side-Channel Analysis of Arbiter PUFs

The Security of Tandem-DM in the Ideal Cipher Model

Jacobian Coordinates on Genus 2 Curves

Acoustic Cryptanalysis

Premium Partner