XiaoMi-AI文件搜索系统
World File Search SystemColadangelo
论量子密码学所需的计算难度
[Crépeau，Kilian'88； ， Bartusek、Coladangelo、Khurana、Ma'21； Grilo, Lin, Song, Vaikuntanathan'21] • 没有 OWF 的 MPC [Kretschmer'21； Ananth，Q，Yuen'22； [森前，山川 '22]
量子证明复杂性的下限
此外，我还要感谢伯克利的博士后，他们同样公开地为我提供了时间、想法和友谊：Rotem Arnon-Friedman、Anurag Anshu、Adam Bouland、Andrea Coladangelo 和 Henry Yuen。我特别要感谢 Anurag，首先他是我的朋友，其次在 COVID-19 大流行期间非常支持我的想法，并与我一起写出了一些很棒的结果，这些结果构成了本论文的核心。此外，Anand Natarajan 一直很高兴与我合作进行研究，我很高兴他是我的朋友和搭档厨师。我也很幸运能与许多其他优秀科学家合作：Srinivasan Arunachalam、Thom Bohdanowicz、Sergey Bravyi、Nikolas Breuckmann、Elizabeth Crosson、Bill Fefferman、Sandy Irani、Bryan O'Gorman 和 Sujit Rao；研究并不是在真空中进行的。
来自经典预言机的量子状态混淆
量子密码学中一个尚未解决的主要问题是是否有可能混淆任意量子计算。事实上，即使在经典的 Oracle 模型中，人们也可以自由地混淆任何经典电路，但关于量子混淆的可行性仍有许多需要了解的地方。在这项工作中，我们开发了一系列新技术，用于构建量子态混淆器，这是 Coladangelo 和 Gunn (arXiv:2311.07794) 最近在追求更好的软件版权保护方案时形式化的一个强大概念。量子态混淆是指将量子程序（由具有经典描述的量子电路 𝐶 和辅助量子态 | 𝜓 ⟩ 组成）编译成功能等价的混淆量子程序，该程序尽可能隐藏有关 𝐶 和 | 𝜓 ⟩ 的信息。我们证明了我们的混淆器在应用于任何伪确定性量子程序（即计算（几乎）确定性的经典输入/经典输出功能的程序）时是安全的。我们的安全性证明是关于一个高效的经典预言机的，可以使用量子安全不可区分混淆来启发式地实例化经典电路。我们的结果改进了 Bartusek、Kitagawa、Nishimaki 和 Yamakawa (STOC 2023) 的最新工作，他们还展示了如何在经典预言机模型中混淆伪确定性量子电路，但仅限于具有完全经典描述的电路。此外，我们的结果回答了 Coladangelo 和 Gunn 的一个问题，他们提供了一种关于量子预言机的量子态不可区分混淆的构造，但留下了一个具体的现实世界候选者的存在作为一个悬而未决的问题。事实上，我们的量子状态混淆器与 Coladangelo-Gunn 一起为所有多项式时间函数提供了“最佳”复制保护方案的第一个候选实现。我们的技术与之前关于量子混淆的研究有很大不同。我们开发了几种新颖的技术工具，我们期望它们在量子密码学中得到广泛应用。这些工具包括一个可公开验证的线性同态量子认证方案，该方案具有经典可解码的 ZX 测量（我们从陪集状态构建），以及一种将任何量子电路编译成“线性 + 测量”（LM）量子程序的方法：CNOT 操作和部分 ZX 测量的交替序列。
来自经典预言机的量子状态混淆
量子密码学中一个尚未解决的主要问题是是否有可能混淆任意量子计算。事实上，即使在经典的 Oracle 模型中，人们仍然很难理解量子混淆的可行性，在经典的 Oracle 模型中，人们可以免费混淆任何经典电路。在这项工作中，我们开发了一系列新技术，用它们来构建量子态混淆器，这是 Coladangelo 和 Gunn (arXiv:2311.07794) 最近在追求更好的软件版权保护方案时形式化的一个强大概念。量子态混淆是指将一个量子程序（由一个具有经典描述的量子电路 C 和一个辅助量子态 | ψ ⟩ 组成）编译成一个功能等价的混淆量子程序，该程序尽可能隐藏有关 C 和 | ψ ⟩ 的信息。我们证明了我们的混淆器在应用于任何伪确定性量子程序（即计算（几乎）确定性的经典输入/经典输出功能的程序）时是安全的。我们的安全性证明是关于一个高效的经典预言机的，可以使用经典电路的量子安全不可区分混淆来启发式地实例化它。我们的结果改进了 Bartusek、Kitagawa、Nishimaki 和 Yamakawa (STOC 2023) 的最新工作，他们也展示了如何在经典预言机模型中混淆伪确定性量子电路，但仅限于具有完全经典描述的电路。此外，我们的结果回答了 Coladangelo 和 Gunn 的一个问题，他们提供了一种关于量子预言机的量子态不可区分混淆的构造，但留下了一个具体的现实世界候选者的存在作为一个悬而未决的问题。事实上，我们的量子状态混淆器与 Coladangelo-Gunn 一起为所有多项式时间函数提供了“最佳”复制保护方案的第一个候选实现。我们的技术与之前关于量子混淆的研究有很大不同。我们开发了几种新颖的技术工具，我们期望它们在量子密码学中得到广泛应用。这些工具包括一个可公开验证的线性同态量子认证方案，该方案具有经典可解码的 ZX 测量（我们从陪集状态构建），以及一种将任何量子电路编译成“线性 + 测量”（LM）量子程序的方法：CNOT 操作和部分 ZX 测量的交替序列。
纳米级Terahertz电导率和
我们从单向函数构建量子键入加密。在我们的建筑中，公共钥匙是量子，但密文是经典的。在最近的一些作品中也提出了来自单向函数（或较弱的原始函数（例如伪和函数）状态）的量子公钥加密[Morimae-Yamakawa，Eprint：2022/1336; Coladangelo，Eprint：2023/282； Barooti-Grilo-Malavolta- Sattath-Vu-Walter，TCC 2023]。但是，它们有一个巨大的缺点：只有在量子公共钥匙可以传输到发件人（运行加密算法的人）而不会被对手篡改时，它们才是安全的，这似乎需要不令人满意的物理设置假设，例如安全量子通道。我们的构造摆脱了这样的缺点：即使我们仅假设未经身份验证的量子通道，它也保证了加密消息的保密。因此，加密是用对抗篡改的量子钥匙来完成的。我们的构建是第一个量子公共密钥加密，它实现了经典的公开加密的目标，即仅基于单向功能，建立对不安全渠道的安全沟通。此外，我们展示了一个通用编译器，以将对选择的明文攻击（CPA安全）升级到仅使用单向函数的选择Ciphertext攻击（CCA Security）的安全性。因此，我们仅基于单向功能获得CCA安全的量子公钥加密。
关于常见 Haar 状态模型的注释
在经典密码学中，引入了公共随机串和公共参考串模型来解决在普通模型中无法实现的密码任务。在公共参考串模型中，有一个可信设置，它会生成一个各方都可以访问的字符串。在公共随机串模型中，所有参与方可用的公共字符串是均匀随机采样的，从而避免了对可信设置的需要。因此，公共随机串模型是两者中更理想的模型。多年来，人们针对这两个模型提出了许多构造，包括非交互式零知识 [ BFM19 ]、通用组合下的安全计算 [ CF01 ；CLOS02 ] 和两轮安全计算 [ GS22 ；BL18 ]。研究量子密码协议的类似模型是值得的。在这种情况下，可以选择定义本质上是量子的模型。例如，我们可以定义一个模型，其中一个可信设置产生一个量子态，并且参与密码系统的每一方都会收到一个或多个该量子态的副本。事实上，Morimae、Nehoran 和 Yamakawa [ MNY23 ] 和 Qian [ Qia23 ] 的两篇作品都考虑了这种模型，称为通用量子参考弦模型 (CQRS)。他们提出了在这个模型中的无条件安全承诺。量子承诺是量子密码学的一个基础概念。近年来，量子承诺因其对安全计算的意义 [ BCKM21；GLSV21 ] 而得到了广泛的研究 [ AQY22；MY21；AGQY22；MY23；BCQ22；Bra23 ]。在普通模型中不可能实现信息理论上安全的承诺 [ LC97；May97；CLM23 ]，这一事实使得 [ MNY23；Qia23 ] 的贡献相当有趣。虽然 CQRS 是公共参考弦模型的量子类似物，但我们可以问是否存在公共随机弦模型的量子类似物。Chen、Coladangelo 和 Sattath [ CCS24 ]（以下简称 CCS）最近独立并同时进行的一项工作引入了一个模型，称为公共 Haar 随机状态模型 (CHRS)。在这个模型中，系统中的每个参与方都会收到许多 iid Haar 状态的多个副本。他们在这个模型中提出了伪随机性和承诺的构造。我们工作的目标是进一步研究这个模型。