CRYPTOGRAPHY FROM CONSENSUS TO THE COSMOS

This is a thesis in two parts. First, we re-visit the foundations of consensus protocols, arguing that despite 50 years of research, there is room to make them simpler, more secure, and more efficient. As a pillar of distributed systems, consensus algorithms power everything from distributed databases to decentralized infrastructure. The protocols covered in this thesis (Streamlet (Chan and Shi, 2020), Simplex (Chan and Pass, 2023), and variants) are the simplest in the literature, and are now taught in universities and power an increasing number of projects in industry. Second, we re-examine the fundamental meaning of what it means for a protocol to be cryptographically secure -- the basis of Modern Cryptography. Classical "provable security" assumes that the attacker is probabilistic polynomial-time in nature (or perhaps quantum) and stateless. In contrast, our notion of Universal Reductions (Chan, Freitag, and Pass, 2022)) models attackers as arbitrary unbounded stateful algorithms -- agnostic to what computational model is physically realizable by the universe, yielding a more general (and future-proof) notion of security.

Name thesis:degree_name

Ph. D., Computer Science

Level thesis:degree_level

Doctor of Philosophy

Discipline thesis:degree_discipline

Computer Science

Grantor

Cornell University

Year dc:date.issued

2025

Author dc:creator

• Chan, Benjamin

Committee members dc:contributor.committeemember

• Shi, Runting
• Juels, Ari
• Stephens-Davidowitz, Noah

• consensus
• cryptography
• distributed algorithms
• security
• theory of computation

Statement dc:rights

• Attribution-NoDerivatives 4.0 International

Licence dc:rights.uri

• https://creativecommons.org/licenses/by-nd/4.0/

Language dc:language.iso

en

DOI

https://doi.org/10.7298/eqh4-5m80

Dc Identifier Other

ProQuest Submission ID: 15291
ProQuest Publication ID: 32244437

OAI identifier oai:identifier

oai:ecommons.cornell.edu:1813/121130