How to keep a secret and share a public key (using polynomial commitments)

Despite 40+ years of amazing progress, cryptography is constantly plagued by two simple problems: keeping secret keys secret and making public keys public. For example, public-key encryption is secure only if each user (1) keeps his secret key out of the hands of the adversary and (2) correctly distributes his public key to all other users. This thesis seeks to address these two fundamental problems. First, we introduce communication-efficient, fully-untrusted append-only logs, which can be used to correctly distribute public keys. Our constructions have logarithmic-sized proofs for the two key operations in append-only logs: looking up public keys and verifying the log remained append-only. In contrast, previous logs either have linear-sized proofs or need extra trust assumptions. Our logs can also be used to secure software distribution and, we hope, to increase transparency in any institution that wants to do so. Second, we speed up threshold cryptosystems, which protect secret keys by splitting them up across many users. We introduce threshold signatures, verifiable secret sharing and distributed key generation protocols that can scale to millions of users. Our protocols drastically reduce execution time, anywhere from 2x to 4500x, depending on the scale. For example, at large scales, we reduce time from tens of hours to tens of seconds. At the core of most of our contributions lie new techniques for computing evaluation proofs in constant-sized polynomial commitments. Specifically, we show how to decrease the time to compute n proofs for a degree-bound n polynomial from O(n²) to O(n log n), at the cost of increasing proof size from O(1) to O(log n). Our techniques could be of independent interest, as they give rise to other cryptographic schemes, such as Vector Commitments (VCs).

Name thesis:degree_name

Doctoral

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2020

Author dc:creator

• Tomescu Nicolescu, Ioan Alin.

Advisor dc:contributor.advisor

• Srinivas Devadas.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/128298

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/128298