Authentication in the Bounded Storage Model
Authentication in the Bounded Storage Model
复制标题
有限存储模型中的身份验证
DOI：
10.1007/978-3-031-07082-2_26
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Daniel Wichs
中科院分区：
文献类型：
--
作者：
Y. Dodis;Willy Quach;Daniel Wichs
我们考虑有界存储模型（BSM）的流变体，其中诚实的各方可以将大量数据流传输给彼此，同时仅保持大小为n的小内存。对手也作为流算法操作，但具有大得多的存储器大小m（cid：29）n。我们的目标是在BSM中构造无条件安全的密码方案，以前的工作是在密钥加密，密钥协商，不经意传输和多方计算中进行的。在这项工作中，我们构造的BSM消息认证和签名。首先，我们考虑密钥设置，其中Alice和Bob共享存储的小密钥。Alice可以通过流式传输大小为k> m的长认证标签来向Bob认证任意多个消息，同时确保标签可以仅使用n位内存生成和验证。我们展示了一个使用本地提取器的解决方案（Vadhan; JoC '04），它允许达到指数级大的对抗内存m = 2 O（n），并且具有大小为k = O（m）的标签。其次，我们考虑与上面相同的设置，但现在额外要求每个单独的标签都很小，大小为k ≤ n。我们发现一个解决方案仍然是可能的，当对手的内存是m = O（n 2），这是最佳的。我们的解决方案依赖于倾斜奇偶校验的空间下限（Raz; FOCS '16）。第三，我们考虑公钥签名设置。一个签名者Alice最初通过一个可信的通道传输一个长的验证密钥，同时只在她的内存中保存一个短的签名密钥。验证者Bob接收流传输的验证密钥，并生成一个简短的验证摘要，并将其保存在内存中。之后，爱丽丝可以使用她的签名密钥对任意多条消息进行签名，方法是将大签名流传输给鲍勃，鲍勃可以使用他的验证摘要来验证它们。我们显示的解决方案m = O（n 2），我们证明是最优的。我们的解决方案依赖于一个新的熵引理，独立的利益。我们表明，如果一个序列的块有sufficiently高的最小熵，那么一个大部分的个别块必须有高的最小熵。这个引理的简单版本是错误的，但我们展示了如何修补它以使其成立。
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 (cid:29) 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.