量子科技中心_量科网

Khurana和Tomer [STOC 2024] 引入的单向谜题（OWPuzzs）是单向函数（OWFs）的自然量子类比，也是“微密码学”中最基本的原语之一，其中单向函数不存在但量子密码学是可能的。OWPuzzs被几乎所有量子密码原语所蕴含，并暗示了若干重要应用，如非交互式承诺和多方计算。量子密码学领域的一个重要目标是将OWPuzzs建立在不会蕴含单向函数的合理假设上。在本文中，该研究团队基于非坍缩测量的困难性来构建OWPuzzs。为此，该团队引入了一个新的复杂度类𝐒𝐚𝐦𝐩𝐏𝐃𝐐𝐏，这是[Aaronson, Bouland, Fitzsimons, and Lee, ITCS 2016]中引入的决策类𝐏𝐃𝐐𝐏的采样版本。该研究团队证明，如果𝐒𝐚𝐦𝐩𝐏𝐃𝐐𝐏在平均情况下对量子多项式时间是困难的，那么OWPuzzs存在。该团队还证明，如果𝐒𝐚𝐦𝐩𝐏𝐃𝐐𝐏⊈𝐒𝐚𝐦𝐩𝐁𝐐𝐏，那么辅助输入的OWPuzzs存在。𝐒𝐚𝐦𝐩𝐏𝐃𝐐𝐏是可以由经典多项式时间确定性算法解决的采样问题类，该算法可以向非坍缩测量预言机进行单次查询，这是一种“神奇”的预言机，可以在量子态上采样测量结果而不使态坍缩。这种非坍缩测量是高度非物理的操作，在量子多项式时间内应该难以实现，因此该研究团队建立OWPuzzs的假设似乎极其合理。此外，这些假设似乎不会蕴含单向函数，因为反转经典函数的可能性对于实现量子非坍缩测量没有帮助。该研究团队还研究了𝐒𝐚𝐦𝐩𝐏𝐃𝐐𝐏困难性的上界。该团队引入了一个新的原语，分布抗碰撞谜题（dCRPuzzs），这是分布抗碰撞哈希[Dubrov and Ishai, STOC 2006]的自然量子类比。该研究团队证明dCRPuzzs蕴含𝐒𝐚𝐦𝐩𝐏𝐃𝐐𝐏（因此也包括OWPuzzs）的平均情况困难性。该团队还证明，具有经典通信的双消息诚实统计隐藏承诺和一次性消息认证码（MACs），这是[Amos, Georgiou, Kiayias, Zhandry, STOC 2020]中一次性签名的私有可验证版本，蕴含dCRPuzzs。