论文标题
流媒体开关引理的信息理论证明，用于对称加密
An Information-Theoretic Proof of the Streaming Switching Lemma for Symmetric Encryption
论文作者
论文摘要
由密码学中的基本范式的动机，我们考虑了近期经典问题的一种变体，即在随机函数和随机置换之间界定区别优势。具体而言，我们考虑确定$ q $值的序列是否在$ [n] $中均匀替换的序列均匀地采样，在这种情况下，该决定是由限制在最多使用$ s $内部内存的流算法做出的。在这项工作中，这种算法的显着优势是通过在两种情况下诱导的其输出分布之间的KL差异来衡量的。我们表明，对于任何$ s =ω（\ log n）$，当$ o（q \ cdot s / n）$的上限，甚至由$ o（q \ cdot s / n \ log n）$时，当$ q \ leq leq n^{1- iam} $对于任何常数$ε> 0 $与K k kit the Kl ki kl kl kl ki k kintivence for the n constance n n^$ q \ leq n^{1- iam} $。
Motivated by a fundamental paradigm in cryptography, we consider a recent variant of the classic problem of bounding the distinguishing advantage between a random function and a random permutation. Specifically, we consider the problem of deciding whether a sequence of $q$ values was sampled uniformly with or without replacement from $[N]$, where the decision is made by a streaming algorithm restricted to using at most $s$ bits of internal memory. In this work, the distinguishing advantage of such an algorithm is measured by the KL divergence between the distributions of its output as induced under the two cases. We show that for any $s=Ω(\log N)$ the distinguishing advantage is upper bounded by $O(q \cdot s / N)$, and even by $O(q \cdot s / N \log N)$ when $q \leq N^{1 - ε}$ for any constant $ε> 0$ where it is nearly tight with respect to the KL divergence.
