Leakage-resilient stream cipher
A leakage-resilient stream cipher is a stateful generator whose next output block is pseudorandom given the previous blocks and, for every earlier round, bits of adversarially chosen information about the part of the state that round read; the total leakage over all rounds is unbounded — DP08, Pie09.
Syntax
A stream cipher is a pair of efficient algorithms with state space and block length :
- , a randomized algorithm sampling an initial state ,
- , a deterministic algorithm computing round : it outputs the next state and an output block .
Round reads only a part of , its active state, fixed by the description of ; the rest of is carried into unchanged. Leakage in round is a function of alone, the axiom that only computation leaks information — MR04.
Properties
Correctness
is deterministic, so the stream is a function of , and two parties holding compute the same stream — standard.
Leakage resilience
Before each round , chooses an efficiently computable leakage function with output bits and receives together with . After any number of rounds, receives either or a uniform block. The challenge round leaks nothing: could compute from and output its first bit. Leakage on all of is likewise excluded: determines , so for every , could output a bit of the next round’s block — standard.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{lr\text{-}sc}}_{\mathsf{SC},\ell,\calA}(\secpar)$}
\begin{algorithmic}
\State $S_0 \gets \KeyGen(1^\secpar)$; $b \getsr \bits$; $i \gets 0$
\State $\stA \gets \calA^{\calO}(1^\secpar)$
\Comment{Each $f$ queried to $\calO$ has $\ell$ output bits}
\State $(S_{i+1}, X_{i+1}) \gets \mathsf{Next}(S_i)$
\Comment{Challenge round: no leakage}
\State $X^*_0 \gets X_{i+1}$; $X^*_1 \getsr \bits^n$
\State $b' \gets \calA(X^*_b, \stA)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\algname{Oracle}
\caption{$\calO(f)$}
\begin{algorithmic}
\State $i \gets i + 1$
\State $\Lambda_i \gets f(S^{+}_{i-1})$
\Comment{$f$ sees only the active state of round $i$}
\State $(S_i, X_i) \gets \mathsf{Next}(S_{i-1})$
\Return $(X_i, \Lambda_i)$
\end{algorithmic}
\end{algorithm}
A stream cipher is -leakage-resilient if for all efficient ,
is negligible. As an object, a leakage-resilient stream cipher is -leakage-resilient for some ; each result states its bound.
Variations
Stream ciphers without leakage
For the game asks that each block be pseudorandom given the previous ones. The iterated PRG meets it, and is not -leakage-resilient: round reads all of , from which computes and then — standard. The constructions of DP08 and Pie09 therefore split the state into parts read in alternate rounds.
Other results
- The output of any PRG has high HILL pseudoentropy even when bounded information about its seed is leaked; DP08 prove this lemma and combine it with alternating extraction to build a leakage-resilient stream cipher from any PRG secure against non-uniform adversaries (PRG ⇒ Leakage-resilient stream cipher).
- Weak PRFs on a domain of size are seed-incompressible: the output of such a weak PRF on random inputs stays pseudorandom when a bounded amount of information about the key is leaked — Pie09. PRF security does not survive one bit of leakage: the first bit of , with a query at , distinguishes; with a polynomial-size domain the same bit breaks weak-PRF security, since a sample at arrives after an expected samples — standard. A simple mode of operation of any key-expanding weak PRF is a leakage-resilient stream cipher (Weak PRF ⇒ Leakage-resilient stream cipher) — Pie09.
Participates in
Produces Leakage-resilient stream cipher