Authentication in the Bounded Storage Model

Yevgeniy Dodis, Willy Quach, Daniel Wichs

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We consider the streaming variant of the Bounded Storage Model (BSM), where the honest parties can stream large amounts of data to each other, while only maintaining a small memory of size n. The adversary also operates as a streaming algorithm, but has a much larger memory size m≫ n. The goal is to construct unconditionally secure cryptographic schemes in the BSM, and prior works did so for symmetric-key encryption, key agreement, oblivious transfer and multiparty computation. In this work, we construct message authentication and signatures in the BSM. First, we consider the symmetric-key setting, where Alice and Bob share a small secret key. Alice can authenticate arbitrarily many messages to Bob by streaming long authentication tags of size k≫ m, while ensuring that the tags can be generated and verified using only n bits of memory. We show a solution using local extractors (Vadhan; JoC ’04), which allows for up to exponentially large adversarial memory m= 2 O(n), and has tags of size k= O(m). Second, we consider the same setting as above, but now additionally require each individual tag to be small, of size k≤ n. We show a solution is still possible when the adversary’s memory is m= O(n2), which is optimal. Our solution relies on a space lower bound for leaning parities (Raz; FOCS ’16). Third, we consider the public-key signature setting. A signer Alice initially streams a long verification key over an authentic channel, while only keeping a short signing key in her memory. A verifier Bob receives the streamed verification key and generates a short verification digest that he keeps in his memory. Later, Alice can sign arbitrarily many messages using her signing key by streaming large signatures to Bob, who can verify them using his verification digest. We show a solution for m= O(n2), which we show to be optimal. Our solution relies on a novel entropy lemma, of independent interest. We show that, if a sequence of blocks has sufficiently high min-entropy, then a large fraction of individual blocks must have high min-entropy. Naive versions of this lemma are false, but we show how to patch it to make it hold.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022, Proceedings
EditorsOrr Dunkelman, Stefan Dziembowski
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages30
ISBN (Print)9783031070815
StatePublished - 2022
Event41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022 - Trondheim, Norway
Duration: May 30 2022Jun 3 2022

Publication series

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


Conference41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2022

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Authentication in the Bounded Storage Model'. Together they form a unique fingerprint.

Cite this