Authentication in the Bounded Storage Model

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 stored. 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(n 2 ), 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(n 2 ), 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.