密码学报（中英文）2025，Vol.12Issue(2)：297-309,13.DOI:10.13868/j.cnki.jcr.000762
可调随机置换与随机函数的量子不可区分性紧界
Tight Bounds for Quantum Indistinguishability of Tweakable Random Permutations from Random Functions
摘要
Abstract
The development of quantum computers has forced the community to reevaluate the concrete security of various cryptographic problems against quantum attacks.This study focuses on the problem of distinguishing a tweakable random permutation from a random function on {0,1}t ×{0,1}n → {0,1}n.The hardness of this problem has been a central tool in security proofs of several cryptographic constructions.It is well-known that classical adversaries need Ω(2n/2)queries to achieve a constant success probability.In the quantum regime,Hosoyamada and Iwata(Asiacrypt 2019)proved that Q(2n/6)superposition queries are necessary to achieve a constant success probability,but left tightening the bound as an open problem.We revisit this problem using the"polynomial"proof method of Zhandry(FOCS 2012)and improve the lower bound to Q(2n/3).Using this conclusion,we also improve the quantum chosen-plaintext attack(qCPA)security bounds of the tweakable block cipher constructions LRWQ,TNT,and LRQ based on block ciphers from O(2n/6)to O(2n/4),O(2n/3),and O(2n/4),respectively.关键词
后量子密码/Q2模型/可调随机置换/量子伪随机函数Key words
post-quantum cryptography/Q2 model/tweakable random permutation/quantum pseudorandom function分类
计算机与自动化引用本文复制引用
郭晓宁,郭淳..可调随机置换与随机函数的量子不可区分性紧界[J].密码学报（中英文）,2025,12(2):297-309,13.基金项目
国家自然科学基金(62002202,62372274)National Natural Science Foundation of China(62002202,62372274) （62002202,62372274）
