UC Berkeley

A program obfuscator is a compiler that renders code unintelligible without harming its functionality. The ability to obfuscate computation is an immensely powerful cryptographic tool and, as such, developing techniques for program obfuscation is one of the central goals of modern cryptography.

This thesis presents the first known methods for obfuscating useful classes of quantum computations. We propose several obfuscation schemes and prove their security in the classical oracle model, obtaining the following results.

- Obfuscation for null quantum circuits. This yields several novel applications, including witness encryption for QMA and succinct non-interactive zero-knowledge arguments for QMA.

- Obfuscation for pseudo-deterministic quantum circuits. We obfuscate any quantum circuit that takes a classical input and computes a (nearly) deterministic classical output. Thus, we obtain the first scheme that is powerful enough to obfuscate Shor's algorithm.

Quantum state obfuscation. A quantum state obfuscator supports obfuscation of (pseudo-deterministic) quantum circuits with auxiliary quantum input. This result gives the first candidate ``best-possible'' copy-protection scheme for general-purpose software.

Along the way, we present the first constructions of several quantum cryptographic primitives, including publicly-decodable X-measurable commitments, publicly-verifiable quantum fully-homomorphic encryption, and publicly-verifiable linearly-homomorphic authentication of quantum data.