(Quantum) Indifferentiability and Pre-Computation

Indifferentiability is an important cryptographic paradigm for analyzing the security of ideal objects—both in a classical and quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what it means for a construction to be “as good as” an ideal object. A paradigmatic application of the framework is showing that a hash function does not have structural weaknesses, by proving it to be indifferentiable from a random oracle.

Despite its generality, indifferentiability is not known to offer security against pre-processing attacks, in which the adversary gains access to classical or quantum advice that is relevant to the particular construction. In this work, we show that indifferentiability is generically insufficient for capturing pre-computation. To accommodate this shortcoming, we propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account. As an application, we show that the one-round sponge is indifferentiable with pre-computation from a random oracle. This yields the first, and tight, quantum space-time trade-offs for one-round sponge inversion.