Doctoral Thesis: How to Keep a Secret and Share a Public Key (Using Polynomial Commitments)


Event Speaker: 

Alin Tomescu

Event Location: 


Event Date/Time: 

Thursday, November 7, 2019 - 2:00pm


The last 40+ years have seen mind-blowing progress in cryptography, from protecting communications via public-key encryption, to computing on encrypted data via fully-homomorphic encryption.  Yet, with all its power, cryptography is constantly plagued by two fundamental problems: keeping \textit{secret keys} secret and making \textit{public keys} public.  For example, encryption schemes and cryptocurrencies require participants to maintain some secret information to thwart adversaries from reading messages or stealing coins.  At the same time, these schemes also require participants to distribute identifying information, such as public keys, to thwart adversaries from impersonating players (and thus from reading messages or stealing coins).
This thesis makes two contributions towards these two fundamental problems.

First, we show how to keep secret keys \textit{secret} by splitting them among very large groups of players such that only a large threshold number of players can reconstruct them.
Specifically, we introduce scalable versions of threshold signatures, verifiable secret sharing (VSS) and distributed key generation protocols (DKG).
All of our protocols can scale (at least computationally) to millions of players.  Furthermore, our protocols start outperforming previous work quite early, even at the scale of hundreds of players.
We hope our protocols will spark new interest in designing truly large-scale distributed systems.

Second, we show how to make public keys \textit{public} by publishing them in an append-only log managed by a single, fully-adversarial server.
Specifically, we formalize and instantiate communication-efficient append-only logs.  Our logs offer logarithmic-sized proofs for \textit{all} operations: looking up public keys and ensuring the log remains append-only.  In contrast, previous logs either have linear-sized proofs or require additional trust assumptions.  Our logs are not just useful for distributing public keys correctly, but also for securing software updates and, we hope, for increasing transparency in any institution that wants to do so.

At the core of (most of) our contributions lie new techniques for computing evaluation proofs in constant-sized polynomial commitments.
For example, computing these proofs is the bottleneck of communication-efficient VSS and DKG protocols.  We remove this bottleneck by decreasing the time to compute $n$ proofs for a degree-bound $n$ polynomial from $O(n^2)$ to $O(n\log{n})$.  The trade-off is we increase the proof size from $O(1)$ to $O(\log{n})$, which increases communication complexity, but within reason.
We use similar precomputation techniques for building communication-efficient append-only logs.  We believe our techniques could also be of independent interest, as they give rise to other cryptographic schemes, such as Vector Commitments (VCs).
Thesis Supervisor: Prof. Srinivas Devadas