We continue to investigate fundamental theoretical questions about Complexity-Based Cryptography. Some of the foundational areas we are active on include black-box constructions and impossibility results, exploring new hardness assumptions, pseudorandomness, collision-resistant hashing, etc.
Separating succinct non-interactive arguments from all falsifiable assumptions. C.Gentry, D.Wichs, ACM STOC. 2011.
Almost optimal bounds for direct product threshold theorem. C.Jutla, 2010 Theory of Cryptography Conference TCC'10.
The Geometry of Provable Security: some proofs of Security in which Lattices make a Surprise Appearance. C.Gentry, The LLL Algorithm, Springer, 2010.
Testing low-degree polynomials over prime fields. C.S.Jutla, A.C.Patthak, A.Rudra, D.Zuckerman, IEEE FOCS, 2009.
On seed-incompressible functions. S.Halevi, S.Myers, C.Rackoff, 2008 Theory of Cryptography Conference, TCC'08.
Degradation and amplification of computational hardness. S.Halevi, T.Rabin, 2008 Theory of Cryptography Conference, TCC'08.
Trapdoors for hard lattices and new cryptographic constructions. C.Gentry, C.Peikert, V.Vaikuntanathan, ACM STOC 2008.
Provably good codes for hash function design. C.Jutla, A.Patthak, Selected Areas in Cryptography, Springer, 2007.
PRF domain extension using dags. C.Jutla, 2006 Theory of Cryptography Conference, TCC'06.
Bounds on the efficiency of generic cryptographic constructions. R.Gennaro, Y.Gertner, J.Katz, L.Trevisan, SIAM Journal on Computing, 2006.
Hardness amplification of weakly verifiable puzzles. R.Canetti, S.Halevi, M.Steiner, 2005 Theory of Cryptography Conference, TCC'05.