Streaming Switching Lemma
Streaming Switching Lemma
- What if the adversary is given a stream of query elements produced by a random function/permutation?
- Considered by Jaegar and Tessaro at EUROCRYPT 2019 [JT'19]
- Streaming Switching Lemma: Adversary with \(S\) bits of memory with $1$-pass access to stream of \(q\) elements from random permutation/function has distinguishing advantage of at most \(\sqrt{Q\cdot S/N}\)
- If \(S\approx q\), then this bound is worse than the \(O(q^2/N)\)
Applications
- AES-based counter mode
- \(m_i\) is encrypted to \((r_i, c_i=AES_k(r_i)\oplus m_i)\) for uniform \(r_i\)
- Replace AES by random \(P\)
- Apply streaming switching lemma (several times) to show that \((r_i,c_i)\) indistinguishable from \((r_i,\alpha_i)\) for uniform \(\alpha_i\)