Cryptology ePrint Archive: Report 2019/428

Quantum Lazy Sampling and Game-Playing Proofs for Quantum Indifferentiability

Jan Czajkowski and Christian Majenz and Christian Schaffner and Sebastian Zur

Abstract: 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.

Category / Keywords: foundations / game-playing proofs, QROM, indifferentiability, sponge construction

Date: received 25 Apr 2019, last revised 12 May 2021

Contact author: j czajkowski at uva nl,c majenz@uva nl,c schaffner@uva nl,zursebastian@gmail com

Available format(s): PDF | BibTeX Citation

Version: 20210512:193017 (All versions of this report)

Short URL: ia.cr/2019/428


[ Cryptology ePrint archive ]