Security Amplification for the Cascade of Arbitrarily Weak PRPs: Tight Bounds via the Interactive Hardcore Lemma

We consider the task of amplifying the security of a weak pseudorandom permutation (PRP), called an

ε

-PRP, for which the computational distinguishing advantage is only guaranteed to be bounded by some (possibly non-negligible) quantity

ε

< 1. We prove that the cascade (i.e., sequential composition) of

m

ε

-PRPs (with independent keys) is an ((

m

 − (

m

 − 1)

ε

)

ε

m

 + 

ν

)-PRP, where

ν

is a negligible function. In the asymptotic setting, this implies security amplification for all

$\epsilon < 1 - \frac{1}{\textsf{poly}}$

, and the result extends to two-sided PRPs, where the inverse of the given permutation is also queried. Furthermore, we show that this result is essentially tight. This settles a long-standing open problem due to Luby and Rackoff (STOC ’86).

Our approach relies on the first hardcore lemma for computational indistinguishability of

interactive

systems: Given two systems whose states do not depend on the interaction, and which no efficient adversary can distinguish with advantage better than

ε

, we show that there exist events on the choices of the respective states, occurring each with probability at least 1 − 

ε

, such that the two systems are computationally indistinguishable conditioned on these events.