Abstract
dc:description.abstractWhether secure Cryptography exists is one of the most importantopen problems in Computer Science; consequently, cryptographic schemes today rely on unproven computational hardness assumptions. We will survey a recent thread of work showing equivalences betweenthe existence of some of the most basic cryptographic primitives, and the hardness of various computational problems related to the notion of time-bounded Kolmogorov Complexity (dating back to the 1960s). These results yield the first natural computational problemscharacterizing the feasibility of central primitives and protocols in Cryptography, as well as the first unstructured computational problems enabling public-key cryptography.
Degree
thesis:*- 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 and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Liu, Yanyi
- Chair dc:contributor.chair
-
- Pass, Rafael
- Committee members dc:contributor.committeemember
-
- Shi, Runting
- Kozen, Dexter
- Chattopadhyay, Eshan
- Stephens-Davidowitz, Noah
Subjects
dc:subject × 2Rights
dc:rights- Statement dc:rights
-
- Attribution 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 17422438
- Dc Identifier Other
-
ProQuest Submission ID: 15256
ProQuest Publication ID: 32171526