量子保密查询：实用量子密码协议的一缕曙光

量子计算可以更快速地解决大数分解、密钥搜索等问题，对现代密码系统的安全性形成了严峻挑战。寻找可抵抗量子计算攻击的新型密码体制已经成为密码学研究的重要任务。量子密码就是这样一种新型密码体制。它利用量子力学特性来发现潜在的窃听行为，为设计信息论安全的密码协议提供了一种新思路。

相关概念

量子密码是量子力学与密码学相结合的产物。

相关概念以及它们之间的关系

►量子密钥分配（Quantum Key Distribution，QKD）：利用量子特性在通信双方之间建立密钥的过程。该过程通常以量子态为信息载体，并将量子态在信道中传输，而密钥是一串只有通信双方才知道的随机经典比特。建立密钥之后，用户可将之应用于保护数据的机密性、完整性、来源真实性、不可伪造性以及安全多方计算等各种密码学任务。

►量子保密通信：利用量子特性在通信双方之间实现保密通信（密码学主要任务之一，保障通信内容不被第三方获得）的过程。大多数情况下，量子保密通信可以看作是QKD与加密算法的结合，本质上是将QKD建立的密钥应用于保密通信。此外，还有一种不需预先建立密钥、直接利用量子特性实现保密通信的特殊形式，称为量子安全直接通信（Quantum Secure Direct Communication，QSDC）。就目前而言，量子保密通信的通信内容一般是经典消息，加密算法一般是经典算法。如果选用一次一密（One-Time Pad）算法，则整个保密通信过程在理论上可达到信息论安全。

►量子密码：利用量子特性实现各类密码学任务的新型密码体制，包括量子保密通信和其他借助量子态传输来实现的密码协议和算法。

►量子通信：以量子态为载体或传输内容的通信的统称，主要包括利用量子特性来实现的通信（如量子保密通信）和用以传输量子消息的通信（如量子隐形传态）。

研究现状与现存问题

自从1984年C. Bennett和G. Brassard提出第一个QKD协议以来，量子密码逐渐引起了人们广泛的研究兴趣。量子秘密共享、量子安全直接通信、量子签名、量子比特承诺、量子掷币、量子拍卖、量子拜占庭等协议相继被提出。人们希望量子力学能够全面提升信息系统的安全性。然而，由于种种原因（如信道噪声难处理、实现难度大、缺乏易用的公钥算法、安全两方计算面临no-go定理限制等）当前技术条件下真正实用的协议凤毛麟角。目前，各国量子通信网络中运行的密码协议几乎仅限于QKD。

我们知道，一个信息系统的安全性取决于多种因素（木桶原理）。

信息系统的安全性与各种密码算法和信息安全技术的安全性息息相关，系统的整体安全性强度往往取决于上述因素中最弱的一个。

量子密码“仅提高密钥分配安全性”的现状与“全面提升信息系统安全性”的预期还有很大的距离。人们开始质疑，如果量子力学不能武装更多密码算法和协议使之免受量子计算的威胁，那我们投入巨大人力物力来建设量子保密通信网络是否物有所值？因此，能否发掘出新的实用量子密码协议，已经成为关系到未来量子密码兴衰成败的关键理论问题。

量子保密查询协议

可喜的是，近年来人们找到了一种极具实用潜力的新型量子密码协议，即量子保密查询。从密码学角度来说，量子保密查询解决的是N传1的不经意传输问题。下面的例子可以形象地描述该问题：Bob有一个数据库，里面有N条秘密消息，而Alice想购买其中1条并得到它。由于这些消息很敏感，Alice不想让Bob知道她拿走了哪1条消息。与此同时，Bob也希望Alice只能拿走1条消息（而不能多得到额外的秘密消息，因为Alice只付了购买1条消息的钱）。不经意传输是安全两方计算中的代表性问题之一。

由于量子安全两方计算受到no-go定理的限制（即量子密码中尚无法实现理想的安全两方计算协议），量子保密查询将不经意传输的安全目标进行了适当放松。具体来说，要求用户Alice可以获得受限的条目数（即稍大于1，而不是严格等于1），且数据库拥有者Bob的欺骗（通过攻击去获知用户查询的是哪一条内容）总有非零的概率会被用户发现。在这种放松的安全模型下，量子保密查询可以实现信息论安全。量子保密查询协议的最大特点是实用，其量子部分与BB84 QKD协议类似，而经典后处理理论也已相对完善。换句话说，将现有QKD系统的后处理程序进行适当的修改，就可以运行量子保密查询协议了。

通过移位叠加技术可以巧妙地消除引入纠错码对数据库安全性带来的不良影响。对于不诚实的Alice，她可以从纠错码的冗余中额外获得一些密钥比特。但通过移位叠加之后，这些额外获得的密钥比特会被压缩掉，而诚实Alice所获得的密钥比特会被保留下来。

Science China-Physics, Mechanics & Astronomy 2019年第7期发表了北京邮电大学高飞教授等的综述文章“Quantum private query: a new kind of practical quantum cryptographic protocol”。

该文详细介绍了近年来人们围绕实用量子保密查询协议所取得的研究进展，包括：

• 基本协议：如何通过量子不经意密钥传输、密钥蒸馏、加密查询等步骤来完成保密查询的任务，以及在协议灵活性和蒸馏效率方面的两个改进方案；

• 可用性：如何在保护双方隐私的前提下实现密钥纠错（见上图），以及如何解决数据库安全性和失败概率之间的固有矛盾；

• 理论安全性：如何定量刻画高效蒸馏方案中的信息泄露对协议安全性的影响（见下图），以及如何抵抗联合测量攻击；

• 实际安全性：设备无关和测量设备无关的量子保密查询协议。

用获得全部数据库所需的查询次数来定量刻画高效蒸馏方案的不安全性。图中的方格代表条目总数为10000的数据库，方格被平均分成100×100的点阵，每个点代表一个数据库条目。灰色的点代表Alice完全不知道的条目，深褐色的点代表Alice已经完全获得的条目，其他颜色的点代表Alice知道了部分信息的条目。仿真实验中，不同查询次数后的信息泄露情形如图中9个方格所示。结果表明，Alice仅需53次查询就能获得全部10000条数据。因此，为了达到安全性，最初的蒸馏方案才是目前最好的选择。

论文也指出两个新观点：一是在实用的两方安全计算协议中，需要增加检测外部攻击的步骤；二是结合移位叠加或窄步长移位叠加技术，在使用弱相干光源代替理想单光子源时量子保密查询仍然可以达到同样的安全性。

曾经，极具吸引力的“物理安全性”使人们对量子密码赋予了极高的期望。现在，设计实用量子密码协议却面临着重重困难。量子保密查询的出现让人们看到了一缕曙光。希望今后能有更多密码学家投入到相关研究中来，为推动量子密码理论的进步而做出贡献。

---

点击下方“阅读原文”免费读全文：

F. Gao, S. J. Qin, W. Huang, and Q. Y. Wen, Quantum private query: A new kind of practical quantum cryptographic protocol, Sci.China-Phys. Mech. Astron. 62, 070301 (2019)

https://doi.org/10.1007/s11433-018-9324-6

《中国科学》杂志社

Science China Press 

公众微信号：scichina1950

长按识别二维码关注