2019-04-25
Quantum Lazy Sampling and Game-Playing Proofs for Quantum Indifferentiability
Publication
Publication
Game-playing proofs constitute a powerful framework for classical 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 [Zha18] can be used to do quantum lazy sampling from non-uniform function distributions. Second, we observe how Unruh's one-way-to-hiding lemma [Unr14] 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 or a random permutation. Our results upgrade post-quantum security of SHA-3 to the same level that is proven against classical adversaries.
Additional Metadata | |
---|---|
arXiv.org e-Print archive | |
Organisation | Algorithms and Complexity |
Czajkowski, J.M, Majenz, C, Schaffner, C, & Zur, S.A. (2019). Quantum Lazy Sampling and Game-Playing Proofs for Quantum Indifferentiability. arXiv.org e-Print archive.
|