Frontiers in Lattice Cryptography and Program Obfuscation
dc.contributor.advisor | Katz, Jonathan | en_US |
dc.contributor.author | Apon, Daniel Christopher | en_US |
dc.contributor.department | Computer Science | en_US |
dc.contributor.publisher | Digital Repository at the University of Maryland | en_US |
dc.contributor.publisher | University of Maryland (College Park, Md.) | en_US |
dc.date.accessioned | 2018-01-23T06:36:46Z | |
dc.date.available | 2018-01-23T06:36:46Z | |
dc.date.issued | 2017 | en_US |
dc.description.abstract | 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. | en_US |
dc.identifier | https://doi.org/10.13016/M23R0PV71 | |
dc.identifier.uri | http://hdl.handle.net/1903/20317 | |
dc.language.iso | en | en_US |
dc.subject.pqcontrolled | Mathematics | en_US |
dc.subject.pqcontrolled | Horticulture | en_US |
dc.subject.pquncontrolled | Cryptography | en_US |
dc.subject.pquncontrolled | Lattices | en_US |
dc.subject.pquncontrolled | Obfuscation | en_US |
dc.title | Frontiers in Lattice Cryptography and Program Obfuscation | en_US |
dc.type | Dissertation | en_US |
Files
Original bundle
1 - 1 of 1