Paper 2019/428

Quantum Lazy Sampling and Game-Playing Proofs for Quantum Indifferentiability

Jan Czajkowski, Christian Majenz, Christian Schaffner, and Sebastian Zur


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.

Available format(s)
Publication info
Preprint. MINOR revision.
game-playing proofsQROMindifferentiabilitysponge construction
Contact author(s)
j czajkowski @ uva nl
c majenz @ uva nl
c schaffner @ uva nl
zursebastian @ gmail com
2021-05-12: last of 3 revisions
2019-04-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jan Czajkowski and Christian Majenz and Christian Schaffner and Sebastian Zur},
      title = {Quantum Lazy Sampling and Game-Playing Proofs for Quantum Indifferentiability},
      howpublished = {Cryptology ePrint Archive, Paper 2019/428},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.