On Quantum Secure Compressing Pseudorandom Functions

ePrint Report: On Quantum Secure Compressing Pseudorandom Functions

Ritam Bhaumik, Benoît Cogliati, Jordan Ethan, Ashwin Jha

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 …

attacks eprint report functions insecure jordan period quantum quantum secure report types vulnerability vulnerable