Paper 2024/1727
(Quantum) Indifferentiability and Pre-Computation
Abstract
Indifferentiability is a popular cryptographic paradigm for analyzing the security of ideal objects---both in a classical as well as in a quantum world. It is typically stated in the form of a composable and simulation-based definition, and captures what it means for a construction (e.g., a cryptographic hash function) to be ``as good as'' an ideal object (e.g., a random oracle). Despite its strength, indifferentiability is not known to offer security against pre-processin} 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) classical/quantum space-time trade-off for one-round sponge inversion.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- indifferentiabilitypre-computationspace-time trade-offsponge hashing
- Contact author(s)
-
jcarolan @ umd edu
poremba @ mit edu
mzhandry @ gmail com - History
- 2024-10-25: approved
- 2024-10-22: received
- See all versions
- Short URL
- https://ia.cr/2024/1727
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1727,
author = {Joseph Carolan and Alexander Poremba and Mark Zhandry},
title = {(Quantum) Indifferentiability and Pre-Computation},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1727},
year = {2024},
url = {https://eprint.iacr.org/2024/1727}
}
