ACM通信
研究突出了
技术角度:埃德加·爱伦·坡到底错了吗?
数千年来，编码制定者和密码破解者之间的战争一直在激烈进行。纵观历史，命运曾发生过戏剧性的逆转，有时会带来改变文明进程的壮观后果。例如，如果盟军没有在第二次世界大战期间破解德国的Enigma密码，今天的世界将是一个非常不同的地方。关于密码战争的畅销书不胜枚举，比如西蒙·辛格的畅销书《密码书:从古埃及到量子密码学的保密科学。今天，我们的整个经济，以及网络空间的存在，都至关重要地依赖于我们的保密沟通能力。但我们真的可以吗?
最重要的问题是:最终无可争议的胜利者是编码者还是密码破解者?又或者，这场猫捉老鼠的游戏将永远持续下去，编码人员发明出越来越聪明的加密方案，却被更聪明的解码人员打败。1841年，诗人兼小说家埃德加·爱伦·坡以其不可思议的名字而著名格雷厄姆女士和绅士杂志“可以全面地断言，人类的智慧无法制造出人类的智慧无法解决的密码。”这是一个相当大胆的声明，因为Blaise de Vigenère在1585年发表了一个计划，当时被称为le数字indechiffrable当时还没有人能打破这个规则。坡怎么能预见到它会在几年后被查尔斯·巴贝奇打破呢?所以，也许他终究是对的。
然后电脑进入游戏，设计出了相当复杂的密码。某种程度上与P NP猜想有关，计算机日益强大的出现似乎对编码人员有利。20世纪70年代公钥密码学的发明似乎坚定地扭转了对码创作者有利的趋势。特别是RSA密码系统的发表(ccacm 1978年2月)是一个转折点。坡似乎错了。
直到彼得·肖尔在1994年发现，量子计算机不仅可以有效地破解RSA，还可以有效地破解早期的Diffie-Hellman密钥建立方案(即使是基于椭圆曲线)，本质上使目前互联网所依赖的整个加密基础设施瘫痪。不用担心:在1994年，量子计算机似乎对遥远的未来是一个威胁……但现在不是了。看来坡会笑到最后。
但早在1983年，查尔斯·贝内特和我就发明了量子密钥分发(QKD)，从而利用量子的力量为编码人员服务，比肖尔利用它为相反的一方服务早了十年。就像Asher Peres曾经说过的，“量子带走，量子还回来。”此外，QKD的实现似乎比运行Shor算法所需的全尺寸量子计算机的构建要容易得多。1996年，多米尼克·梅耶斯(Dominic Mayers)证明了量子密钥的无条件安全性(甚至是针对量子计算机)，越来越复杂的原型正在建造中。因此，这个问题最终得到了解决:坡错了。
直到量子黑客他们中的许多人都在瓦迪姆·马卡罗夫的领导下他们意识到量子密钥分配的安全性是无条件的，除非该装置能够完全按照理论论文中定义的那样建造，而这似乎是一项不可能完成的任务。2009年，他们演示了对运行中的QKD连接进行全域攻击的实现。马卡罗夫发现的特定弱点很快就被修补好了，但另一个弱点也同样迅速地出现了。坡的说法可以被解释为“可以全面地断言，工程师的独创性不能在不留下工程师独创性可以利用的漏洞的情况下实现量子密钥分配装置。”因此，猫捉老鼠的游戏将永远继续下去，尽管从数学领域提升到工程领域。
Umesh Vazirani和Thomas Vidick的论文就是在这里登场的。早在1991年，Artur Ekert就意识到，利用量子密码技术是可能的纠缠这可以说是量子理论最非经典的表现形式。尽管埃克特最初的协议除了我和贝内特的早期发明之外，并没有提供任何安全保障，但他已经为一场革命埋下了种子。一些人认为，在2000年代中期，一些研究人员意识到，基于纠缠的协议可以导致无条件的安全，即使它们的实施不完美，即使量子密钥分配设备是由窃听者建造的。十年来，这些纯理论的想法仍然难以捉摸，似乎需要不合理的硬件，比如一个星系大小的设备!Vazirani和Vidick的论文提供了一个意想不到的简单而优雅的解决方案，事实上，这是一个几乎可以用目前的技术实现的解决方案。一旦它成为现实，代码开发者将赢得最终的战斗，尽管坡有这样的预言。
数字图书馆是由计算机协会出版的。版权所有©2019 ACM股份有限公司
没有发现记录