Paper 2023/207

On Quantum Secure Compressing Pseudorandom Functions

Abstract

In this paper we characterize all $$-bit-to-$$-bit Pseudorandom Functions (PRFs) constructed with the minimum number of calls to $$-bit-to-$$-bit PRFs and arbitrary number of linear functions. First, we show that all two-round constructions are either classically insecure, or vulnerable to quantum period-finding attacks. Second, we categorize three-round constructions depending on their vulnerability to these types of attacks. This allows us to identify classes of constructions that could be proven secure. We then proceed to show the security of the following three candidates against any quantum distinguisher that asks at most $$ (possibly superposition) queries $$ Note that the first construction is a classically secure tweakable block cipher due to Bao et al., and the third construction is shown to be quantum secure tweakable block cipher by Hosoyamada and Iwata with similar query limits. Of note is our proof framework, an adaptation of Chung et al.'s rigorous formulation of Zhandry's compressed oracle technique in indistinguishability setup, which could be of independent interests. This framework gives very compact and mostly classical looking proofs as compared to Hosoyamada and Iwata interpretation of Zhandry's compressed oracle.

Note: In a follow-up work (IACR Cryptology ePrint Archive 2024/1478) on the quantum security of the Luby-Rackoff cipher, we also identified some errors in this paper. An erratum detailing these errors, along with any necessary updates, has been added to the revision.