As digital data become central to domains, ranging from personalized medicine and financial services to scientific research and national security, preserving its confidentiality during computation has emerged as a foundational challenge. Recent breaches illustrate the severe consequences of compromised information: privacy violations, identity theft, and loss of public trust. Traditional encryption protects data at rest and in transit, but leaves a critical gap during computation, when sensitive inputs are typically exposed. Secure computation techniques, notably fully homomorphic encryption (FHE) and garbled circuits (GC), close this gap by enabling meaningful computation over encrypted or distributed data without revealing the underlying inputs.
Despite remarkable progress, these protocols still suffer from high computational and communication overheads, limiting their practical deployment. This thesis targets a specific --- but broadly applicable --- scenario: the secure evaluation of Boolean functions using FHE and GC. While these protocols are not inherently restricted to Boolean logic, focusing on Boolean circuits allows us to leverage decades of progress in logic synthesis, a mature subfield of electronic design automation. By casting secure computation as a domain-specific logic synthesis problem --- one governed by cryptographic cost models rather than silicon constraints in the conventional context --- we develop novel circuit optimization techniques that bridge classical logic design and modern cryptography.
We make contributions across five technical directions: (i) For leveled FHE schemes, we formalize the trade-off between multiplicative depth (MD) and multiplicative complexity (MC), and introduce synthesis frameworks that jointly reduce both, enabling tighter cryptographic parameters and faster homomorphic evaluation. (ii) For fast-bootstrapping FHE schemes, represented by the torus FHE (TFHE) scheme, under a fixed-plaintext-space function-evaluation strategy, we develop symmetry- and negacyclicity-aware mapping strategies, combined with a multi-value programmable bootstrapping (MV-PBS)â aware lookup-table (LUT) synthesizer, to minimize PBS count. (iii) For TFHE-based, multi-plaintext-space function evaluation, we propose the first synthesis framework that strategically transitions between binary and large plaintext spaces, using XORs for linear logic and concentrating non-linear operations into compact LUTs. (iv) For GC, we introduce the XORâ OneHotâ inverter graph (X1G), a new intermediate representation that improves ciphertext efficiency and unlocks dedicated optimization passes. (v) Finally, we introduce joint multiplicative complexity (JMC), a garbling-cost-aware cost model that accounts for shared ownership in GC-based secure multi-party computation, and propose the first ownership-aware optimizer that reduces jointly evaluated non-linear gates.
Collectively, these results demonstrate two broad lessons: (1) representat
