#pseudorandom

共收录 1 条相关安全情报。

← 返回所有主题
推荐 3.5
Conf: 50%
👥 作者: Ben Foxman, Alex Lombardi, Fermi Ma, Barak Nehoran, John Wright

本文研究量子算法和密码学中的一个核心挑战:如何推理以随机群元素(如随机函数、置换或酉算子)为 oracle 的算法。经典方法采用惰性采样,即 oracle 不预先承诺整个群元素,而是动态采样部分信息。本文提出了一种量子惰性采样的模拟方法:压缩 oracle(或记录 oracle),这是一种允许实时模拟量子查询的量子数据结构。该结构最初由 Zhandry (CRYPTO '19) 针对随机函数提出,随后由 Ma-Huang (STOC '25) 推广至酉算子,Carolan (STOC '26) 推广至置换,并在安全证明和下界中因可解释性而得到广泛应用。本文从第一性原理出发,定义并分析了一种通用且可解释的路径记录 oracle,它能够完美模拟 $U(N)$ 的任何闭子群中的随机元素。该 oracle 以叠加态存储 t 个输入-输出对,其更新用群张量幂表示的交换子来描述,从而透明地记录算法所学到的信息。本文扩展了 Grinko-Yoshida (QIP '26) 的工作,他们给出了另一种通用压缩 oracle,但缺乏清晰的可解释性。路径记录的一个有趣应用是允许直接比较不同群的压缩 oracle,从而为证明伪随机性提供了一种新技术。例如,比较 $S_N$ 和 $U(N)$ 可以得出迄今为止最简单的伪随机酉构造:伪随机置换与随机 Clifford 的乘积 PC,改进了之前的 PFC 构造 (Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25)。本文的主要贡献在于提出了一种通用、可解释的量子路径记录 oracle,并展示了其在伪随机构造中的应用,对量子算法和密码学理论具有重要价值。

💡 推荐理由: 本文提出的路径记录 oracle 为量子密码学安全证明提供了新工具,尤其是伪随机酉的简单构造对量子加密、认证和隐私保护有潜在影响。安全从业者需关注量子安全算法的理论基础。

🎯 建议动作: 学术研究跟进

排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.5)