A Time-Success Ratio Analysis of wPRF-based Leakage-Resilient Stream Ciphers
This work addresses a gap in cryptographic security proofs for practitioners, but it is incremental as it builds on existing analyses without introducing new methods.
The paper compares security bounds for leakage-resilient stream ciphers based on weak pseudorandom functions and identifies a flaw in a recent analysis, showing that provable security with standard primitives remains uncertain.
Weak pseudorandom functions (wPRFs) found an important application as main building blocks for leakage-resilient ciphers (EUROCRYPT'09). Several security bounds, based on different techniques, were given to these stream ciphers. The security loss in these reduction-based proofs is always polynomial, but has not been studied in detail. The aim of this paper is twofold. First, we present a clear comparison of quantitatively different security bounds in the literature. Second, we revisit the current proof techniques and answer the natural question of how far we are from meaningful and provable security guarantees, when instantiating weak PRFs with standard primitives (block ciphers or hash functions). In particular, we demonstrate a flaw in the recent (TCC'14) analysis of the EUROCRYPT'09 stream cipher, which means that we still don't know if it offers provable security when instantiated with a standard block cipher. Our approach is a \emph{time-to-success Ratio} analysis, a universal measure introduced by Luby, which allow us to compare different security bounds.