Frontiers in Lattice Cryptography and Program Obfuscation

Thumbnail Image


Publication or External Link





In this dissertation, we explore the frontiers of theory of cryptography along two lines. In the first direction, we explore Lattice Cryptography, which is the primary sub-area of post-quantum cryptographic research.

Our first contribution is the construction of a deniable attribute-based encryption scheme from lattices. A deniable encryption scheme is secure against

not only eavesdropping attacks as required by semantic security, but also stronger coercion attacks performed after the fact. An attribute-based encryption

scheme allows ``fine-grained'' access to ciphertexts, allowing for a decryption access policy to be embedded in ciphertexts and keys. We achieve both properties

simultaneously for the first time from lattices.

Our second contribution is the construction of a digital signature scheme that enjoys both short signatures and a completely tight security reduction from lattices. As a matter of independent interest, we give an improved method of randomized inversion of the G gadget matrix, which reduces the noise growth rate in homomorphic evaluations performed in a large number of lattice-based cryptographic schemes, without incurring the high cost of sampling discrete Gaussians.

In the second direction, we explore Cryptographic Program Obfuscation. A program obfuscator is a type of cryptographic software compiler that outputs executable code with the guarantee that whatever can be hidden about the internal workings of program code, is hidden.'' Indeed, program obfuscation can be viewed as a universal and cryptographically-complete'' tool.

Our third contribution is the first, full-scale implementation of secure program obfuscation in software. Our toolchain takes code written in a C-like programming

language, specialized for cryptography, and produces secure, obfuscated software.

Our fourth contribution is a new cryptanalytic attack against a variety of ``early'' program obfuscation candidates. We provide a general, efficiently-testable

property for any two branching programs, called partial inequivalence, which we show is sufficient for launching an ``annihilation attack'' against

several obfuscation candidates based on Garg-Gentry-Halevi multilinear maps.