International Association for Cryptologic Research

International Association
for Cryptologic Research


On Quantum Secure Compressing Pseudorandom Functions

Ritam Bhaumik , EPFL, Lausanne, Switzerland
Benoît Cogliati , Thales DIS France SAS, Meudon, France
Jordan Ethan , CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Ashwin Jha , CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2023
Abstract: In this paper we characterize all $2n$-bit-to-$n$-bit Pseudorandom Functions (PRFs) constructed with the minimum number of calls to $n$-bit-to-$n$-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 makes at most $ 2^{n/4} $ (possibly superposition) queries: \begin{align*} TNT(x_1,x_2) &:= f_3(x_2 \oplus f_2(x_2 \oplus f_1(x_1)));\\ LRQ(x_1,x_2) &:= f_2(x_2) \oplus f_3(x_2 \oplus f_1(x_1));\\ LRWQ(x_1,x_2) &:= f_3( f_1(x_1) \oplus f_2(x_2)). \end{align*} Note that the first construction is a classically secure tweakable block-cipher due to Bao et al., and the third construction was shown to be a 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 the indistinguishability setup, which could be of independent interest. This framework gives very compact and mostly classical-looking proofs as compared to Hosoyamada-Iwata interpretation of Zhandry's compressed oracle.
  title={On Quantum Secure Compressing Pseudorandom Functions},
  author={Ritam Bhaumik and Benoît Cogliati and Jordan Ethan and Ashwin Jha},