On Bounded Storage Key Agreement and One-Way Functions

Chris Brzuska*, Geoffroy Couteau, Christoph Egger, Willy Quach

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

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 languageEnglish
Title of host publicationTheory of Cryptography - 22nd International Conference, TCC 2024, Proceedings
EditorsElette Boyle, Elette Boyle, Mohammad Mahmoody
PublisherSpringer
Pages287-318
Number of pages32
ISBN (Print)9783031780103
DOIs
Publication statusPublished - 2025
MoE publication typeA4 Conference publication
EventTheory of Cryptography Conference - Milan, Italy
Duration: 2 Dec 20246 Dec 2024
Conference number: 22

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume15364 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceTheory of Cryptography Conference
Abbreviated titleTCC
Country/TerritoryItaly
CityMilan
Period02/12/202406/12/2024

Fingerprint

Dive into the research topics of 'On Bounded Storage Key Agreement and One-Way Functions'. Together they form a unique fingerprint.

Cite this