Generic method lifts quantum security from small to large cryptographic oracles
Indistinguishability Lifting for Keyed Oracles, Compressed Ideal Cipher, and More Applications
Cryptography and Security
Summary
Building cryptographic proofs is tricky when attackers can ask many questions at once in quantum ways. The authors found a general method that shows if a small cryptographic building block is secure against quantum attacks, then the bigger system made from many such blocks is also secure, with some bounded loss in security. They applied this to improve quantum security models for compression functions and to design longer message encryptions. Their approach works for both statistical and computational security and matches known quantum attack limits.
What this means in practice
- •For cryptographic engineers: Securely prove that large quantum-resistant keyed oracles maintain their indistinguishability by building on smaller base oracle proofs.
- •For encryption system designers: Design quantum-resistant compression functions and extend quantum-secure permutation constructions using the new indistinguishability lifting technique.
Authors
Ritam Bhaumik, Yu-Hsuan Huang
Abstract
Cryptographic security proofs often involve an adversary interacting with a larger, keyed oracle that consists of (potentially exponentially) many independent instances of a smaller, base oracle. However, showing quantum indistinguishability between two such keyed oracles can be tricky, since a single query made by an adversary may involve a superposition that covers all instances of the base oracles simultaneously. In this paper, we establish a generic indistinguishability lifting theorem of the following form: if the two base oracles are indistinguishable under quantum queries, then their corresponding keyed oracles are too, up to an O(q^2) multiplicative loss in distinguishing advantage, where q is the number of queries made by the adversary. Our lifting theorem applies to both statistical and computational settings, and to oracles that are stateful as well. It is also optimal in that it matches the obvious Grover search attack for a certain (contrived) choice of oracles. As an immediate application, we extend Carolan's compressed permutation oracle to an efficiently implementable compressed ideal cipher, and use it to prove preimage resistance of the Davies-Meyer compression function in the quantum ideal cipher model. Thanks to our lifting theorem, the soundness of our compressed ideal cipher reduces to that of Carolan's oracle, and any further improvement on the latter would automatically carry over to the former. As our second application, we give a modular construction that doubles the message length of any quantum-secure strong pseudorandom permutation. Along the way, we show that an existing two-round tweakable Feistel construction is indistinguishable from a random permutation under quantum bidirectional queries. This is done via a dedicated polynomial-method argument, which may be of independent interest.