UC Berkeley

Secure computation enables a set of mutually distrustful parties to collaboratively compute a public function over their private data without leaking anything apart from the output. In this thesis, we present improvements towards obtaining secure computation with optimal computation, communication, and round complexity, in both theory and practice.

\textbf{In Theory.} We introduce a novel primitive called laconic oblivious transfer (or laconic OT for short), which allows an OT receiver to commit to a large input $D$ (of length $M$) via a short message. Subsequently, a single short message from an OT sender allows the receiver to learn $m_D[L]$, where the messages $m_0, m_1$ and the location $L \in [M]$ are dynamically chosen by the sender. We present a construction of this primitive based on the Decisional Diffie-Hellman (DDH) assumption, which makes is an innovative use of somewhere statistically binding (SSB) hashing in conjunction with hash proof systems.

Since its introduction, laconic OT has proved to be an extremely powerful tool towards achieving optimal computation and communication complexity in secure computation and beyond. In this thesis, we show a few of its very first applications including non-interactive secure computation and multi-hop homomorphic encryption for RAM programs.

\textbf{In Practice.} As a specific application of secure computation, we introduce a new notion called password-based threshold token authentication, which protects password-based authentication against single point of failures. Specifically, we distribute the role of a single server among $n$ servers and allow any $t$ servers to collectively verify clients' passwords and generate tokens, while no $t - 1$ servers can forge a valid token or mount offline dictionary attacks. We then introduce PASTA, a general framework wherein clients can sign on using a two-round (optimal) protocol that meets our strong security guarantees.

Our experiments show that the overhead of PASTA, compared to a na\"ive single-server solution, is extremely low (1-5\%) in the most likely setting where parties communicate over the internet. The overhead is higher for certain MAC tokens over a LAN (though still only a few milliseconds) due to inherent public-key operations in PASTA. We show, however, that public-key operations are necessary by proving a symmetric-key-only solution impossible.