posted on 2024-02-05, 07:44authored byRitam 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
History
Primary Research Area
Algorithmic Foundations and Cryptography
Name of Conference
International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)
Journal
Advances in Cryptology – ASIACRYPT 2023
Volume
14440
Page Range
34-66
Publisher
Springer Nature
Open Access Type
Not Open Access
BibTeX
@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"
}