Back to search

Cornell University

On Cryptography and Kolmogorov Complexity

Abstract

dc:description.abstract

Whether 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 × 2

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
17422438
Dc Identifier Other
ProQuest Submission ID: 15256
ProQuest Publication ID: 32171526

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Liu, Yanyi. On Cryptography and Kolmogorov Complexity. Doctor of Philosophy thesis, Cornell University, 2025. https://hdl.handle.net/1813/120888