Cryptology ePrint Archive: Report 2022/442

Quantum Attacks on PRFs Based on Public Random Permutations

Tingting Guo and Peng Wang and Lei Hu and Dingfeng Ye

Abstract: We proposed three general frameworks F1,F2, and F3 for n-to-n-bit PRFs with one, two parallel, and two serial public permutation calls respectively, where every permutation is preceded and followed by any bitwise linear mappings. We analyze them in the Q2 model where attackers have quantum-query access to PRFs and permutations. Our results show F1 is not secure with O(n) quantum queries while its PRFs achieve n/2-bit security in the classical setting, and F2,F3 are not secure with O(2^{n/2}n) quantum queries while their PRFs, such as SoEM, PDMMAC, and pEDM, achieve 2n/3-bit security in the classical setting. Besides, we attack three general instantiations XopEM, EDMEM, and EDMDEM of F2,F3, which derive from replacing the two PRPs in Xop, EDM, and EDMD with two independent EM constructions, and concrete PRF instantiations DS-SoEM, PDMMAC, and pEDM, SoKAC21 of F2,F3, with at most O(2^{n/2}n) quantum queries.

Category / Keywords: secret-key cryptography / PRF, Permutation, Quantum Attack

Date: received 6 Apr 2022, last revised 8 Apr 2022

Contact author: w rocking at gmail com, guotingting at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20220412:074126 (All versions of this report)

Short URL: ia.cr/2022/442


[ Cryptology ePrint archive ]