Abstract
We propose new and improved instantiations of lossy trapdoor functions (Peikert and Waters in STOC’08, pp. 187–196, 2008), and correlation-secure trapdoor functions (Rosen and Segev in TCC’09, LNCS, vol. 5444, pp. 419–436, 2009). Our constructions widen the set of number-theoretic assumptions upon which these primitives can be based, and are summarized as follows:
-
Lossy trapdoor functions based on the quadratic residuosity assumption. Our construction relies on modular squaring, and whereas previous such constructions were based on seemingly stronger assumptions, we present the first construction that is based solely on the quadratic residuosity assumption. We also present a generalization to higher-order power residues.
-
Lossy trapdoor functions based on the composite residuosity assumption. Our construction guarantees essentially any required amount of lossiness, where at the same time the functions are more efficient than the matrix-based approach of Peikert and Waters.
-
Lossy trapdoor functions based on the d-Linear assumption. Our construction both simplifies the DDH-based construction of Peikert and Waters and admits a generalization to the whole family of d-Linear assumptions without any loss of efficiency.
-
Correlation-secure trapdoor functions related to the hardness of syndrome decoding.
Article PDF
Similar content being viewed by others
References
M. Bellare, Z. Brakerski, M. Naor, T. Ristenpart, G. Segev, H. Shacham, S. Yilek, Hedged public-key encryption: How to protect against bad randomness, in Advances in Cryptology—ASIACRYPT 2009. LNCS, vol. 5912 (Springer, Berlin, 2009), pp. 232–249
M. Bellare, D. Hofheinz, S. Yilek, Possibility and impossibility results for encryption and commitment secure under selective opening, in Advances in Cryptology—EUROCRYPT 2009. LNCS, vol. 5479 (Springer, Berlin, 2009), pp. 1–35
D.J. Bernstein, List decoding for binary goppa codes, in International Workshop on Coding and Cryptology—IWCC 2011. LNCS, vol. 6639 (Springer, Berlin, 2011), pp. 62–80
M. Blum, P. Feldman, S. Micali, Non-interactive zero-knowledge and its applications, in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (1988), pp. 103–112
A. Boldyreva, S. Fehr, A. O’Neill, On notions of security for deterministic encryption, and efficient constructions without random oracles, in Advances in Cryptology—CRYPTO 2008. LNCS, vol. 5157 (Springer, Berlin, 2008), pp. 335–359
D. Boneh, J. Horwitz, Weak trapdoors from the rth-power-residue symbol. Unpublished manuscript (2002)
D. Boneh, X. Boyen, H. Shacham, Short group signatures, in Advances in Cryptology—CRYPTO 2004. LNCS, vol. 3152 (Springer, Berlin, 2004), pp. 41–55
D. Boneh, S. Halevi, M. Hamburg, R. Ostrovsky, Circular-secure encryption from decision Diffie-Hellman, in Advances in Cryptology—CRYPTO 2008. LNCS, vol. 5157 (Springer, Berlin, 2008), pp. 108–125
D. Boneh, K. Rubin, A. Silverberg, Finding composite order ordinary elliptic curves using the Cocks-Pinch method. J. Number Theory 131, 832–841 (2011)
C. Cachin, S. Micali, M. Stadler, Computationally private information retrieval with polylogarithmic communication, in Advances in Cryptology—EUROCRYPT 1999. LNCS, vol. 1592 (Springer, Berlin, 1999), pp. 402–414
H. Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, vol. 138 (Springer, Berlin, 1993)
D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptol. 10(4), 233–260 (1997)
R. Cramer, V. Shoup, Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, in Advances in Cryptology—EUROCRYPT 2002 (2002), pp. 45–64
I. Damgård, M. Jurik, A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system, in Public Key Cryptography—PKC 2001. LNCS, vol. 1992 (Springer, Berlin, 2001), pp. 119–136. Full version (with additional co-author J.B. Nielsen) available at http://www.daimi.au.dk/~ivan/GenPaillier_finaljour.ps
I. Damgård, J.B. Nielsen, Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor, in Advances in Cryptology—CRYPTO 2002. LNCS, vol. 2442 (Springer, Berlin, 2002), pp. 581–596
I. Damgård, J.B. Nielsen, Universally composable efficient multiparty computation from threshold homomorphic encryption, in Advances in Cryptology—CRYPTO 2003. LNCS, vol. 2729 (Springer, Berlin, 2003), pp. 247–264
R. Dowsley, J. Müller-Quade, A.C.A. Nascimento, A CCA2 secure public key encryption scheme based on the McEliece assumptions in the standard model, in Topics in Cryptology—CT-RSA 2009. LNCS, vol. 5473 (Springer, Berlin, 2009), pp. 240–251
J.-B. Fischer, J. Stern, An efficient pseudo-random generator provably as secure as syndrome decoding, in Advances in Cryptology—EUROCRYPT 1996. LNCS, vol. 1070 (Springer, Berlin, 1996), pp. 245–255
O. Goldreich, Foundations of Cryptography II: Basic Applications (Cambridge University Press, Cambridge, 2004)
S. Goldwasser, V. Vaikuntanathan, New constructions of correlation-secure trapdoor functions and CCA-secure encryption schemes. Manuscript (2008)
V.D. Goppa, A new class of linear correcting codes. Probl. Inf. Transm. 6(3), 207–212 (1970)
V.D. Goppa, Rational representation of codes and (L,g)-codes. Probl. Inf. Transm. 7(3), 223–229 (1971)
B. Hemenway, R. Ostrovsky, Lossy trapdoor functions from smooth homomorphic hash proof systems. Electronic Colloquium on Computational Complexity, Report TR09-127 (2009)
D. Hofheinz, E. Kiltz, Secure hybrid encryption from weakened key encapsulation, in Advances in Cryptology—CRYPTO 2007. LNCS, vol. 4622 (Springer, Berlin, 2007), pp. 553–571
J. Horwitz, Applications of Cayley graphs, bilinearity, and higher-order residues to cryptology. Ph.D. thesis, Stanford University (2004). Available at http://math.scu.edu/~jhorwitz/pubs/horwitz-phd.pdf
K. Ireland, M. Rosen, A Classical Introduction to Modern Number Theory, 2nd edn. Graduate Texts in Mathematics, vol. 84 (Springer, New York, 1990)
E. Kiltz, A. O’Neill, A. Smith, Instantiability of RSA-OAEP under chosen-plaintext attack, in Advances in Cryptology—CRYPTO 2010. LNCS, vol. 6223 (Springer, Berlin, 2010), pp. 295–313
F.J. MacWilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes (North-Holland, Amsterdam, 1983)
R.J. McEliece, A public-key cryptosystem based on algebraic coding theory. DSN Prog. Rep., Jet Prop. Lab., pp. 114–116, Jan 1978
P. Mol, S. Yilek, Chosen-ciphertext security from slightly lossy trapdoor functions, in Public Key Cryptography—PKC 2010. LNCS, vol. 6056 (Springer, Berlin, 2010), pp. 296–377. Full version available at http://eprint.iacr.org/2009/524
M. Naor, G. Segev, Public-key cryptosystems resilient to key leakage, in Advances in Cryptology—CRYPTO 2009. LNCS, vol. 5677 (Springer, Berlin, 2009), pp. 18–35. Full version available at http://eprint.iacr.org/2009/105
J. Neukirch, Algebraic Number Theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 322 (Springer, Berlin, 1999). Translated from the German by N. Schappacher
H. Niederreiter, Knapsack-type cryptosystems and algebraic coding theory. Probl. Control Inf. Theory 15, 159–166 (1986)
R. Nishimaki, E. Fujisaki, K. Tanaka, Efficient non-interactive universally composable string-commitment schemes, in Provable Security—ProvSec’09. LNCS, vol. 5848 (Springer, Berlin, 2009), pp. 3–18
P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, in Advances in Cryptology—EUROCRYPT 1999. LNCS, vol. 1592 (Springer, Berlin, 1999), pp. 223–238
C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem, in 41st ACM Symposium on Theory of Computing (2009), pp. 333–342
C. Peikert, B. Waters, Lossy trapdoor functions and their applications, in 40th ACM Symposium on Theory of Computing (2008), pp. 187–196. Full version available at http://eprint.iacr.org/2007/279
M. Rabin, Digitalized signatures and public-key functions as intractable as factorization. Technical Report MIT/LCS/TR-212, MIT Laboratory for Computer Science (1979)
A. Rosen, G. Segev, Chosen-ciphertext security via correlated products, in Theory of Cryptography Conference—TCC 2009. LNCS, vol. 5444 (Springer, Berlin, 2009), pp. 419–436
H. Shacham, A Cramer-Shoup encryption scheme from the Linear assumption and from progressively weaker Linear variants. Cryptology ePrint Archive, Report 2007/074 (2007). Available at http://eprint.iacr.org/2007/074
D. Squirrel, Computing reciprocity symbols in number fields. Undergraduate thesis, Reed College (1997)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Dan Boneh
An extended abstract of this work appears in Public Key Cryptography—PKC 2010, Springer LNCS, vol. 6056, pp. 279–295 (2010).
Rights and permissions
About this article
Cite this article
Freeman, D.M., Goldreich, O., Kiltz, E. et al. More Constructions of Lossy and Correlation-Secure Trapdoor Functions. J Cryptol 26, 39–74 (2013). https://doi.org/10.1007/s00145-011-9112-3
Received:
Published:
Issue date:
DOI: https://doi.org/10.1007/s00145-011-9112-3