More Constructions of Lossy and Correlation-Secure Trapdoor Functions

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)