Paper 2022/442

Quantum Attacks on PRFs Based on Public Random Permutations

Tingting Guo, Peng Wang, Lei Hu, and Dingfeng Ye


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.

Available format(s)
Secret-key cryptography
Publication info
PRFPermutationQuantum Attack
Contact author(s)
w rocking @ gmail com
guotingting @ iie ac cn
2022-04-12: received
Short URL
Creative Commons Attribution


      author = {Tingting Guo and Peng Wang and Lei Hu and Dingfeng Ye},
      title = {Quantum Attacks on PRFs Based on Public Random Permutations},
      howpublished = {Cryptology ePrint Archive, Paper 2022/442},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.