Non-Black Box Use Of Code In Cryptography

Abstract

In this thesis, I broadly explore how we can incorporate program code in cryptography, both in terms of improving existing cryptographic primitives, and in constructing and analyzing completely new primitives. Most classical cryptography models adversaries as a "black-box", meaning that the security argument only uses the input-output behavior of the adversaries, without using their actual code. I show, along the lines of [7], how to use "non-black-box" techniques, using the program code of adversaries to improve constructions of resettably-sound zero-knowledge protocols (RSZK), and to reduce the required security assumption to the minimum possible (one-wayfunctions). I also show how the code of adversaries can be used more directly, to construct what we believe is the first practical candidate RSZK protocol. In a very different way of leveraging code in cryptography, I also investigate several new cryptographic primitives: indistinguishability obfuscators (IO), randomized encoding (RE), and functional encryption (FE). These primitives inherently leverage program code to provide new functionality beyond that offered by classical primitives, and they have allowed novel applications like delegatable computation. In particular, I investigate the security of multilinear maps, the crucial building block for many of these new primitives, and give the first construction of IO that has a security reduction to a concrete hardness assumption on multilinear maps. I also consider the interrelations between these new primitives. In particular, I investigate how "compact" RE can be used to build IO, a qualitatively stronger primitive. Using very different techniques, I also study how a very weak and inefficient version of IO can be bootstrapped to "standard" IO, by using FE as an intermediate primitive.