Adam O'Neill

School of Computer Science

College of Computing

Georgia Institute of Technology

Date: Monday, August 9, 2010

Time: 1:00 pm - 3:00 pm EDT

Location: TBD

Committee

• Dr. Alexandra Boldyreva (Advisor, School of Computer Science)
• Dr. Mihir Bellare (Computer Science and Engineering, University of California at San Diego)
• Dr. Richard Lipton (School of Computer Science)
• Dr. Chris Peikert (School of Computer Science)
• Dr. Dana Randall (School of Computer Science)
• Dr. Patrick Traynor (School of Computer Science)

Abstract

Trapdoor functions, introduced in the seminal paper of Diffie and Hellman (IEEE Trans. Inf. Theory, 1976), are a fundamental notion in modern cryptography.  Informally, trapdoor functions are easy to evaluate but hard to invert unless given an additional input called the trapdoor.  Specifically, the classical security notion considered for trapdoor functions is {\em one-wayness}, which asks that it be hard to invert a uniformly random point in the range without the trapdoor.

Motivated by the demands of emerging applications of cryptography as well as stronger security properties desired from higher-level cryptographic primitives constructed out of trapdoor functions, this thesis studies new strengthenings to the notion of one-way trapdoor functions and their applications.  Our results are organized along two separate threads, wherein we introduce two new cryptographic primitives that strengthen the notion of one-wayness for trapdoor functions in different ways:

*** Deterministic Encryption:  Our notion of deterministic public-key encryption addresses the weaknesses of using trapdoor functions directly for encryption articulated by Goldwasser and Micali (J. Comput. Syst. Sci., 1984) to the extent possible {\em without} randomizing the encryption function (whereas Goldwasser and Micali address them using randomized encryption).  Specifically, deterministic encryption ensures no partial information is leaked about a high-entropy plaintext or even multiple correlated such plaintexts.  Deterministic encryption has applications to fast search on encrypted data, securing legacy protocols, and ``hedging'' randomized encryption against bad randomness.  We show a secure construction of deterministic encryption in the random oracle model of Bellare and Rogaway (CCS 1993) meeting our security notion for an unbounded number of arbitrarily correlated plaintexts based on any randomized encryption scheme, as well as a more efficient such construction based on RSA.  We also show a secure construction of deterministic encryption without random oracles meeting our security notion for a {\em bounded} number of arbitrarily correlated plaintexts based on the notion of lossy trapdoor functions introduced by Peikert and Waters (STOC 2008).

*** Adaptive Trapdoor Functions: Our notion of adaptive trapdoor functions asks that one-wayness be preserved in the presence of an inversion oracle that can be queried on some range points.  The main application we give is the construction of black-box chosen-ciphertext secure public-key encryption (meaning the code of the underlying primitive is not used in the construction besides running it) from weaker general assumptions.  Namely, we show such a construction of chosen-ciphertext secure public-key encryption from adaptive trapdoor functions.  We then show that adaptive trapdoor functions can be realized from lossy trapdoor functions introduced by Peikert and Waters (STOC 2008) and from correlated-product secure trapdoor functions introduced by Rosen and Segev (TCC 2009); in fact, we show adaptivity is strictly {\em weaker} than the latter notions (in a black-box sense).  Notably, by slightly extending our framework and considering ``tag-based'' adaptive trapdoor functions we obtain exactly the chosen-ciphertext secure encryption schemes proposed in the these works, thereby unifying them, although the schemes we obtain via adaptive trapdoor functions are actually more efficient.