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 epsilon-PR.P, for which the computational distinguishing advantage is only guaranteed to be bounded by some (possibly non-negligible) quantity epsilon < 1. We prove that the cascade (i.e., sequential composition) of in epsilon-PRPs (with independent keys) is an ((m - (m - 1)epsilon)epsilon(m) + nu)-PRP, where nu is a negligible function. In the asymptotic setting, this implies security amplification for all epsilon < 1 -1/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 clue 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 epsilon, we show that there exist events on the choices of the respective states, occurring each with probability at least 1 - epsilon, such that the two systems are computationally indistinguishable conditioned on these events.