Key-expanding weak PRF ⇒ Leakage-resilient stream cipher

Standard model · Pie09 · security loss: for an -secure weak PRF with , leakage of bits per round and next-block advantage at most after rounds

Statement

Let be a key-expanding weak PRF: a weak PRF secure against non-uniform adversaries, with , whose samples . The stream cipher with initial state , for uniform and , whose round computes and outputs , is -leakage-resilient — Pie09. Round reads only ; the key of the next round is not accessed. Quantitatively, if is -secure, with , against circuits within the size and query bounds of Pie09’s Theorem 2, the cipher tolerates bits of leakage per round, and the next block after rounds is distinguishable with advantage at most — Pie09. For a weak PRF secure against all polynomial-size circuits, this leakage is logarithmic in — Pie09.

Notes

  • The proof rests on the seed-incompressibility of weak PRFs on a domain of size : on random inputs such a weak PRF’s outputs stay pseudorandom when bounded information about its key is leaked — Pie09.
  • The construction uses a single primitive, in place of the PRG and randomness extractor of PRG ⇒ Leakage-resilient stream cipher — Pie09, DP08.
  • The condition is necessary. In each round , computes from and outputs the first bit of the -part of . Once some output , which takes about rounds, requests the challenge and compares its first bit with . For this gives advantage about in rounds — standard.