CryptoDB
On Quantum Secure Compressing Pseudorandom Functions
Authors: 


Download:  
Presentation:  Slides 
Conference:  ASIACRYPT 2023 
Abstract:  In this paper we characterize all $2n$bitto$n$bit Pseudorandom Functions (PRFs) constructed with the minimum number of calls to $n$bitto$n$bit PRFs and arbitrary number of linear functions. First, we show that all tworound constructions are either classically insecure, or vulnerable to quantum periodfinding attacks. Second, we categorize threeround 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 blockcipher due to Bao et al., and the third construction was shown to be a quantumsecure tweakable blockcipher 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 classicallooking proofs as compared to HosoyamadaIwata interpretation of Zhandry's compressed oracle. 
BibTeX
@inproceedings{asiacrypt202333644, title={On Quantum Secure Compressing Pseudorandom Functions}, publisher={SpringerVerlag}, author={Ritam Bhaumik and Benoît Cogliati and Jordan Ethan and Ashwin Jha}, year=2023 }