Paper 2022/442
Quantum Attacks on PRFs Based on Public Random Permutations
Tingting Guo, Peng Wang, 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.
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- PRFPermutationQuantum Attack
- Contact author(s)
-
w rocking @ gmail com
guotingting @ iie ac cn - History
- 2022-04-12: received
- Short URL
- https://ia.cr/2022/442
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/442,
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{https://eprint.iacr.org/2022/442}},
url = {https://eprint.iacr.org/2022/442}
}
