Relating space and time in cryptography

Abstract

This thesis studies the interplay between space and time in cryptography. It explores trade-offs between these two resources for honest parties and shows how fine-grained constraints on an adversary's capabilities can unlock new cryptographic functionalities. Adopting this perspective, we present results in four subfields of cryptography: 2PC: We prove tight lower bounds on the cost of oblivious transfer protocols, a central primitive for two-party computation, revealing a fundamental trade-off between communication and public-key operations. SNARG: We construct designated-verifier SNARGs with very short proofs, highlighting a novel trade-off between proof size and verifier efficiency. Incompressible Encryption: We construct a new incompressible encryption scheme. Incompressible encryption remains secure even after key exposure, assuming adversaries had limited space when the ciphertext was transmitted. This offers a lightweight alternative to forward secrecy for long messages. Space-Hard Functions: We define and construct verifiable space-hard functions and space-lock puzzles, space-based analogues of verifiable delay functions and time-lock puzzles. These enable new applications such as deniable proofs and leverage space limitations of the adversary. Together, these results demonstrate how a careful study of space-time trade-offs yields both foundational insights and practical cryptographic tools.

Diese Arbeit untersucht das Zusammenspiel von Raum und Zeit in der Kryptographie. Sie analysiert Kompromisse zwischen diesen Ressourcen für ehrliche Parteien und zeigt, wie gezielte Beschränkungen der Fähigkeiten eines Angreifers neue Möglichkeiten eröffnen. Aus dieser Sicht liefern wir Beiträge in vier Bereichen: 2PC: Wir beweisen untere Schranken für die Kosten von Oblivious-Transfer-Protokollen, einem zentralen Primitive für Zwei-Parteien-Berechnung, und zeigen einen grundlegenden Trade-off zwischen Kommunikation und Public-Key-Operationen. SNARG: Wir konstruieren Designated-Verifier-SNARGs mit sehr kurzen Beweisen und demonstrieren einen neuen Trade-off zwischen Beweisgröße und Verifizierer-Effizienz. Inkomprimierbare Verschlüsselung: Wir stellen ein neues Schema vor, das auch nach Schlüsselkompromittierung sicher bleibt, solange der Angreifer beim Empfang nur begrenzten Raum hatte. Es bietet eine leichte Alternative zur Vorwärtsgeheimhaltung bei langen Nachrichten. Raum-Harte Funktionen: Wir definieren und konstruieren die ersten verifizierbaren raum-harte Funktionen und Raum-Lock-Rätsel, raumbasierte Gegenstücke zu Time-Lock-Rätseln. Diese ermöglichen neue Anwendungen wie ableugbare Beweise und nutzen Raumbeschränkung des Angreifers. Diese Resultate zeigen, dass eine gezielte Analyse Kompromissen zwischen Raum und Zeit sowohl theoretische Einsichten als auch praxisnahe Werkzeuge liefert.