Paper 2023/207
On Quantum Secure Compressing Pseudorandom Functions
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 asks at most $ 2^{n/4} $ (possibly superposition) queries \[ \begin{array}{rcl} \mathsf{TNT}(x_1,x_2) &:=& f_3(x_2 \oplus f_2(x_2 \oplus f_1(x_1)))\\ \mathsf{LRQ}(x_1,x_2) &:=& f_2(x_2) \oplus f_3(x_2 \oplus f_1(x_1))\\ \mathsf{LRWQ}(x_1,x_2) &:=& f_3( f_1(x_1) \oplus f_2(x_2)). \end{array} \] 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.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 A major revision of an IACR publication in ASIACRYPT 2023
 DOI
 10.1007/9789819987276\_2
 Keywords
 QPRFTNTLRWQcompressed oracleSimon's algorithm
 Contact author(s)

ritam bhaumik @ epfl ch
benoit cogliati @ gmail com
jordan ethan @ cispa de
letterstoashwin @ gmail com  History
 20240527: last of 2 revisions
 20230216: received
 See all versions
 Short URL
 https://ia.cr/2023/207
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/207, author = {Ritam Bhaumik and Benoît Cogliati and Jordan Ethan and Ashwin Jha}, title = {On Quantum Secure Compressing Pseudorandom Functions}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/207}, year = {2023}, doi = {10.1007/9789819987276\_2}, url = {https://eprint.iacr.org/2023/207} }