Quantum Lazy Sampling and Game-Playing Proofs for Quantum Indifferentiability
This work addresses the need for rigorous security proofs in quantum cryptography, specifically for indifferentiability, which is incremental by adapting classical techniques to the quantum setting.
The paper tackles the problem of extending game-playing proofs to quantum cryptography by developing a framework that uses compressed quantum oracles for lazy sampling and applies the one-way-to-hiding lemma, resulting in a proof of quantum indifferentiability for the sponge construction with a random internal function.
Game-playing proofs constitute a powerful framework for non-quantum cryptographic security arguments, most notably applied in the context of indifferentiability. An essential ingredient in such proofs is lazy sampling of random primitives. We develop a quantum game-playing proof framework by generalizing two recently developed proof techniques. First, we describe how Zhandry's compressed quantum oracles~(Crypto'19) can be used to do quantum lazy sampling of a class of non-uniform function distributions. Second, we observe how Unruh's one-way-to-hiding lemma~(Eurocrypt'14) can also be applied to compressed oracles, providing a quantum counterpart to the fundamental lemma of game-playing. Subsequently, we use our game-playing framework to prove quantum indifferentiability of the sponge construction, assuming a random internal function.