On Quantum Secure Compressing Pseudorandom.pdf (728.75 kB)

On Quantum Secure Compressing Pseudorandom Functions

Download (728.75 kB)
conference contribution
posted on 2024-02-05, 07:44 authored by Ritam Bhaumik, Benoît Cogliati, Jordan EthanJordan 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 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 (possibly superposition) queries: 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


Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)


Advances in Cryptology – ASIACRYPT 2023



Page Range



Springer Nature

Open Access Type

  • Not Open Access


@inproceedings{Bhaumik:Cogliati:Ethan:Jha:2023, title = "On Quantum Secure Compressing Pseudorandom Functions", author = "Bhaumik, Ritam" AND "Cogliati, Benoît" AND "Ethan, Jordan" AND "Jha, Ashwin", year = 2023, month = 1, journal = "Advances in Cryptology – ASIACRYPT 2023", pages = "34--66", publisher = "Springer Nature", issn = "1611-3349", doi = "10.1007/978-981-99-8727-6_2" }