Projects per year
Abstract
We study key agreement in the bounded-storage model, where the participants and the adversary can use an a priori fixed bounded amount of space, and receive a large stream of data. While key agreement is known to exist unconditionally in this model (Cachin and Maurer, Crypto’97), there are strong lower bounds on the space complexity of the participants, round complexity, and communication complexity that unconditional protocols can achieve. In this work, we explore how a minimal use of cryptographic assumptions can help circumvent these lower bounds. We obtain several contributions:Assuming one-way functions, we construct a one-round key agreement in the bounded-storage model, with arbitrary polynomial space gap between the participants and the adversary, and communication slightly larger than the adversarial storage. Additionally, our protocol can achieve everlasting security using a second streaming round.In the other direction, we show that one-way functions are necessary for key agreement in the bounded-storage model with large space gaps. We further extend our results to the setting of fully-streaming adversaries, and to the setting of key agreement with multiple streaming rounds. Assuming one-way functions, we construct a one-round key agreement in the bounded-storage model, with arbitrary polynomial space gap between the participants and the adversary, and communication slightly larger than the adversarial storage. Additionally, our protocol can achieve everlasting security using a second streaming round. In the other direction, we show that one-way functions are necessary for key agreement in the bounded-storage model with large space gaps. We further extend our results to the setting of fully-streaming adversaries, and to the setting of key agreement with multiple streaming rounds. Our results rely on a combination of information-theoretic arguments and technical ingredients such as pseudorandom generators for space-bounded computation, and a tight characterization of the space efficiency of known reductions between standard Minicrypt primitives (from distributional one-way functions to pseudorandom functions), which might be of independent interest.
Original language | English |
---|---|
Title of host publication | Theory of Cryptography - 22nd International Conference, TCC 2024, Proceedings |
Editors | Elette Boyle, Elette Boyle, Mohammad Mahmoody |
Publisher | Springer |
Pages | 287-318 |
Number of pages | 32 |
ISBN (Print) | 9783031780103 |
DOIs | |
Publication status | Published - 2025 |
MoE publication type | A4 Conference publication |
Event | Theory of Cryptography Conference - Milan, Italy Duration: 2 Dec 2024 → 6 Dec 2024 Conference number: 22 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 15364 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | Theory of Cryptography Conference |
---|---|
Abbreviated title | TCC |
Country/Territory | Italy |
City | Milan |
Period | 02/12/2024 → 06/12/2024 |
Fingerprint
Dive into the research topics of 'On Bounded Storage Key Agreement and One-Way Functions'. Together they form a unique fingerprint.Projects
- 1 Active
-
Brzuska ICT: Limits of Lattice-based Cryptography: A New Era of Hinted and Structured Assumptions
Brzuska, C. (Principal investigator), Woo, I. K. Y. (Project Member), Karanko, P. (Project Member) & Puniamurthy, K. (Project Member)
01/01/2024 → 31/12/2026
Project: Academy of Finland: Other research funding