Paper 2020/1589

Unifying Presampling via Concentration Bounds

Siyao Guo and Qian Li and Qipeng Liu and Jiapeng Zhang

Abstract

Auxiliary-input idealized models, such as the auxiliary-input random oracle model and the auxiliary-input random permutation model, play a critical role in assessing non-uniform security of symmetric-key and hash-function constructions. However, obtaining security bounds in these models are often much more challenging than in traditional idealized models. The presampling technique, introduced by Unruh (CRYPTO' 07), generically reduces security proofs in the auxiliary-input models to a much simpler bit-fixing models. This technique has been further optimized by Coretti, Dodis, Guo, Steinberger (EUROCRYPT' 18), and generalized by Coretti, Dodis, Guo (CRYPTO' 18), resulting in powerful tools for proving non-uniform security bounds in various idealized models, including random oracle models (ROM), random permutation models (RPM), ideal cipher models (ICM) and generic group models (GGM). We study the possibility of unifying and leveraging the presampling technique to the quantum world. To this end, * We show that such leveraging will resolve a major open problem in quantum computing, which is closely related with the famous Aaronson-Ambainis conjecture (ITCS' 11). * Faced with this barrier, we give a new but equivalent bit-fixing model and a simple proof of presampling techniques for arbitrary oracle distribution and access in the classical setting, including AI-ROM and AI-RPM. Our security loss matches the security loss of the best known presampling technique by Coretti et al. (EUROCRYPT' 18) for both indistinguishability and unpredictability applications. Our new proof unifies previous results by Coretti et al. (EUROCRYPT' 18) and Coretti et al. (CRYPTO' 18). * We leverage our new classical presampling techniques to a novel ``quantum bit-fixing version'' of presampling. The security loss of our quantum bit-fixing presampling also matches the optimal security loss of the classical presampling. Using our techniques, we give the first post-quantum non-uniform security bounds for salted Merkle-Damgard hash functions.