DAOrayaki |间谍游戏中的拜占庭将军

DAOrayaki |间谍游戏中的拜占庭将军

DAOrayaki DAO研究奖金池:

资助地址:  DAOrayaki.eth

投票进展:DAO Reviewer  1/0 通 过

赏金总量:45 USD

研究种类:Quantum Computing, Qubits, Bayes

原文作者:   Pierre Decoodt

创作者:Tan Zhi Xuan@DAOrayaki.org

审核者:SueT@DAOrayaki.org

原文:  Byzantine Generals in a Spy Game

本文我们从拜占庭将军,到量子,再谈论到贝叶斯。

你好!我是值班的怪人。你可以忽略我那些旨在深入探讨与量子计算和加密功能有关的评论。

我们需要记得的是,拜占庭一般协议的量子解决方案使我们有可能在将军们的圈子里发现比经典解决方案更多的叛徒。

在之前的文章里,追捕叛徒过程中,中尉们的对抗是在平等的基础上进行的。使用四名将军而不是两名将军的配置的优点之一就是出现了多数人的共识。在三名将军的配置中,如果两个中尉都在测试中被清除,那么指挥部的将军就是在欺骗,但我们无法知道其目标是谁。然而,在四名将军的配置中,经过了两次的对抗并没有发现叛徒,那么指挥部的将军就被认为是那名叛徒。指挥官进行欺骗的目标被确定,而该中尉可以顺理成章地执行发给其他两人的命令。那么这相当于一个错误的纠正。

叛徒的猎杀。假设鲍勃通知卡罗尔和戴夫,他被命令撤退,而他们回应鲍勃说他们被命令出击。鲍勃将面对卡罗尔,然后是戴夫,而在对峙中,对手依次向对方发送线索。图片由作者提供。

这个协议与Fitzi等人提出的原始协议是不一样的,他们的分发和测试协议不涉及分享保留部分副本的结果,以建立所有可能情况下的错误发生率表。在原始的版本中,一个中尉在广播会话中是会被另一个中尉测试的。

我们可以因此设想到不同类型的恶意攻击。所有与安全的经典通道有关的攻击在此不作考虑:假设在后量子密码学的领域里有着完美的保密性。那么我们感兴趣的就是对协议的量子方面所进行的攻击。

拜占庭将军协议的量子解决方案与量子密钥分配(QKD)有若干相似之处。正如这篇 2022 年初的评论所解释的:在光学 QKD 系统中,我们可以想象到一系列的攻击。这些攻击可以针对编码器、量子通道或解码器。Makarov 等人已经描述了通过激光破坏在量子通信中建立后门的情况。Lucamarini 和 Molotkov 等人描述了针对技术实现和信息侧漏渠道的其他类型的木马攻击。然而,如果满足了详细的要求清单,我们是可以假设 QKD 的无条件安全性。这些论文为拜占庭将军协议的量子解决方案中类似攻击的设计提供了灵感。

大多数对量子系统的攻击只是导致破坏而没有进一步的后果。事实上,就在量子比特测量之后,以及叛徒追捕之前,会进行一个纠缠检查的阶段:随机抽取的一部分结果并保留,用于进行一致性验证。如果这个条件没有得到满足,协议就会中止。

现在,假设一些中尉神奇地获得了躲避谎言检测的能力。在三名将军的配置中,这样的中尉可以随意中止进程:这就是破坏!

在四名将军的配置中,由于多数人的共识,这是不可能的。然而,两个具有神奇天赋的奸诈中尉可以说服一个忠诚的中尉执行与实际发出的命令相反的命令:这就是政变!

破坏和政变在理论上是可行的,我们将在量子硬件上进行演示。它还将表明,系统中经过良好校准的量子噪声可以成为一种有效的应对措施。

一个适合在硬件上模拟的特洛伊木马攻击的基本玩具模型已经被实现。这代码是用 Python 写的,并使用开源的量子计算包 Qiskit。该模型已在 IBM Q 的超导量子计算系统上进行了测试。政变的版本也在本文进行了说明。

这些代码可以在这个 GitHub Notebook 中以 Apache License 2.0 的形式浏览。

量子政变

请注意,从这里开始,共谋者及其参与者就像兰波特的拜占庭军队一样具有隐喻性。

玩具模型

灵感的一个重要来源是 Lucamarini 等人所描述的 QKD 中的特洛伊木马攻击。

针对光学QKD设置的特洛伊木马攻击的表现。图转载自: 《量子密钥分发中针对特洛伊木马攻击的实用安全界限》

作者:M. Lucamarini、I. Choi、M. B. Ward、J. F. Dynes、Z. L. Yuan、 和 A. J. Shields、Phys. Rev. X 5, 031030.

DOI 10.1103/PhysRevX.5.031030, URL, Creative Commons Attribution 3.0 Licence

与这种 QKD 木马攻击相反,我们的演示模型中修改了编码。通过泄漏渠道,窃听者可以了解“指挥部将军”的测量结果。

在目前ibm-q/open/main七个可用的量子比特超导量子器件上,如 ibm-nairobi 或 ibm-oslo,归功于高级转译,该布局允许两个辅助量子位提高电路保真度。然而,在这种情况下,一个卧底可以创造泄漏通道。我们就称他为埃文吧。他篡改了量子电路,在末端插入了两个 CNOT 门。CNOT门的控制量子比特是为总司令准备的,而目标量子比特则是辅助。

左上:ibm-nairobi的布局。右上:纠缠的原始电路。下:带有泄漏通道的电路。图片由作者提供。

当加入泄漏通道时,高度纠缠的状态被修改:

上:原始纠缠。下:特洛伊木马攻击中的纠缠。图片由作者提供。

共谋

让我们想象一下以下的例子。卡罗尔和戴夫是老鹰。他们知道爱丽丝不愿意进攻。他们同意如果爱丽丝发出撤退命令,并交给她的对手-也就是好斗的伊文负责,那就会把爱丽丝赶走。埃文测量了辅助量子比特,并将结果通过一个秘密和安全的经典通道传递给伊文。

共谋。量子状态从|φ₅>变为|φ₇>。潜入的特工埃文通过他创建的泄漏通道收到了两个额外的量子比特,对它们进行了测量,并将结果转发给了伊文。伊文、卡罗尔和戴夫在秘密通信中,准备好了他们的计划。图片由作者提供。

被操纵的叛徒猎杀

由于得到了埃文的帮助,伊文拥有一份爱丽丝的机密结果的相近副本。在分配和测量量子比特之后的阶段,卡罗尔和戴夫了解到哪一部分结果是用于狩猎而不是用于纠缠检查。然后,一旦爱丽丝发出撤退的命令,卡罗尔和戴夫就知道与这个命令相关的认证索引列表。在猎杀叛徒的过程中,他们应该避免在与鲍勃的交流中使用这些索引。共谋者们创建了一个相同长度,并且对相反的命令有效的索引列表。卡罗尔和戴夫将在追捕中使用这份伪造的列表,并冒充忠诚的中尉。

请注意,从检查数据中,密谋者可以事先模拟他们的计划,看看它是否有机会成功。他们故意用伊文的结果列表而不是爱丽丝的结果列表来构建一个错误发生率的备用列表。

让我们来看看输出结果:

左边为没有泄漏的渠道。叛徒卡罗尔和戴夫被抓。右边,泄漏的渠道被利用。卡罗尔和戴夫设法使鲍勃相信他们是忠诚的。因此,对鲍勃来说,爱丽丝是一个叛徒。图片由作者提供。

在程序的输出结果中,当测试戴夫时,鲍勃观察到原始电路的错误率为 33%,修改后的电路为 34%。当测试卡罗尔时,他观察到原始电路的错误率为 38%,修正后的电路为 34%。这里有一个解释:

贝叶斯推断(见上一篇文章)。通过泄漏的渠道观察到超几何分布的右移(下)。对于卡罗尔,当她成功地摆出忠诚的姿态时,由于该计划,鲍勃观察到的错误率较低。对于戴夫来说,几乎相同的错误率被解释为叛徒或忠诚,这取决于泄漏渠道是否存在。图片由作者提供。

政变

从现在开始,鲍勃确信爱丽丝是一个叛徒。共谋者们只剩下争取鲍勃加入他们阵线的选择了。爱丽丝在无法提供任何证据谴责该计划的情况下被罢免了。伊文负责指挥行动,并对被围困的城市发起了猛攻。

爱丽丝可以争辩说,卡罗尔和大卫使用的认证索引列表与她的结果不一致,因此不是来自于她那里的,但她的说法与他们的说法就产生矛盾了。

政变成功,并发动了最后的攻击。图片由作者提供。

对于旁观者来说,这无法与拜占庭形式的可靠广播区分开来,因为在拜占庭形式的广播中,没有接收者是存在问题的。为了解释这个比喻,这相当于一个广播的值在所有的接收者中被翻转,尽管服务器并没有故障。

在这里,这个寓言已被刻意地戏剧化了,并在一次全面的攻击中达到高潮阶段,以强调其灾难性的后果。在一个真正的分布式系统中,服务器广播的正确值是会被忽略的。

应对措施

现在是时候研究逃避这种共谋的可能方式了。不仅在我们的玩具模型中,也在其他情况之下,在不同类型的量子系统中,以及对于不同数量的当事人。

错误的方法是将量子纠缠委托给一个将军。这个人可以很容易地修改系统,并得到任何其他人的结果的相近副本。

禁止辅助量子比特也是一个解决方案。但在现实世界中,自发的或创建出来的泄漏通道无论如何都可以被利用来进行恶意攻击。

Gaertner 等人在他们的四名将军配置的协议中用光子系统进行了实验证明,表明通过进一步分析获得的数据,可以揭示改变纠缠的拦截-发送攻击。这一发现有助于理解以下的保护手段,甚至是不同的保护手段,以抵御我们在本文所关注的特洛伊木马攻击。

由于原始电路中存在足够水平的量子噪声,该协议可以得到保障。如果发生攻击,由于更深的电路、更多的双量子比特门和额外的量子比特测量,噪音会增加。对于每个将军的完整结果,以及为纠缠检查汇集的部分结果,其保真度将低于预期。这一变化也将增加用于贝叶斯推理的列表中的预期错误发生率。而之前描述的超几何分布的转变也将出现。

结果的柱状图(6144份)。在嘈杂的量子系统中,泄漏修改了柱状图,而经典的保真度从 54.4% 下降到 45.5%。我们需要注意的是,柱状图不包括伊文的测量结果:这是每个将军从共享数据中得出的观点。图片由作者提供。

在现实环境中,当噪声在以下两个条件下出现时,安全性便有了保证。首先,系统中的单个量子门和测量误差必须是已知的、恒定以及具备足够水平的。第二,必须对电路进行优化,允许在所有情况下,忠实vs叛徒的两个超几何分布之间有足够的距离。这样一来,被篡改的电路就不能与原始电路混淆了。

总结

也许你现在觉得离分布式计算系统中的量子辅助数据验证问题有点远。然而,如果你从服务器和接收者的角度思考,这种攻击具有干扰的特点。在三名将军的版本中,希望翻转一个比特的接收者可能会反复中断传输,直到服务器最终发送一个非故意翻转的比特。在四名将军的版本中,两个接收者必须密谋,但他们可以设法在一次尝试中成功。如果在区块链中使用量子解决方案,这样的特洛伊木马攻击可能会在某个时候被用来验证另一个分类账本。

尽管它具有玩具性质,而且在现实的通信世界中很难有这样的可行性,但这个模型表明了,改变纠缠的特洛伊木马攻击可以在相对嘈杂的系统中被检测到。

这一集总结了量子拜占庭将军系列。

我希望你喜欢这个混合了古希腊文化、当今的极客文化和未来的量子战争的系列。

我声明在硬件测试中使用了 IBM Quantum 服务。本文所表达的观点是作者的观点,并不反映 IBM 或 IBM Quantum 团队的官方政策或立场。

参考文献:

1.量子:

https://medium.com/geekculture/byzantine-generals-turn-to-quantum-ab81bd938cc2

2.贝叶斯:

https://medium.com/geekculture/byzantine-generals-turn-to-bayes-b76a695b124e

3.这篇 2022 年初的评论:

https://www.mdpi.com/1099-4300/24/2/260

4.Makarov 等人:

https://arxiv.org/pdf/1510.03148.pdf

5.Lucamarini:

https://journals.aps.org/prx/pdf/10.1103/PhysRevX.5.031030

6.Molotkov 等人:

https://link.springer.com/epdf/10.1134/S1063776120050064?sharing_token=cqD_hF7AFnHdohq7_-Fb_EckSORA_DxfnEvY7GoQybbekIkapuGTBiOLI8eARtYGjBZOZExBGZjgKnnK1-zqeUC536W1x2n5xa3wtJ-m9JOxwcbVSLOawBBD138WnDEusATus8akaJWkTL4knk13ANFAzcYJJHmKwACFaAgPlqk=

7.Qiskit:https://qiskit.org/

8.Notebook:

https://github.com/pdc-quantum/byzantine-generals-in-qiskit/blob/main/wip-trojan-horse.ipynb

9.兰波特的拜占庭军队:

https://lamport.azurewebsites.net/pubs/byz.pdf

10.Lucamarini 等人:

https://journals.aps.org/prx/pdf/10.1103/PhysRevX.5.031030

11.实验证明:

https://arxiv.org/pdf/0710.0290.pdf

12.表明:https://arxiv.org/pdf/0810.3832.pdf

13.拦截-发送攻击:

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.101.208901


通过 DAO,研究组织和媒体可以打破地域的限制,以社区的方式资助和生产内容。DAOrayaki将会通过DAO的形式,构建一个代表社区意志并由社区控制的功能齐全的去中心化媒体。欢迎通过文末方式提交与DAO、量子计算、星际移民、DA相关的内容,瓜分10000USDC赏金池!欢迎加入DAOrayaki社区,了解去中心化自治组织(DAO),探讨最新话题!

官方网站:https://daorayaki.org

Media:https://media.daorayaki.org

Discord server: https://discord.gg/wNUPmsGsa4

Medium: https://medium.com/@daorayaki

Email: daorayaki@dorafactory.org

Twitter: @daorayaki_

微信助手:DAOrayaki-Media

小宇宙:DAOrayaki

详情请参考:

Dora Factory支持去中心化DAO研究组织DAOrayaki

对DAOrayaki第一阶段的回顾--去中心化媒体的先驱

DAOrayaki |DAOrayaki 开启去中心化治理2.0时代

DAOrayaki |风险投资的范式转移:无限主义基金和无限游戏

DAOrayaki |DAOrayaki dGov 模型:基于Futarchy的正和游戏

更多关于DAO的文章,关注Dorafactory,查看往期文章。

Category:

DAOrayaki

DAOrayaki is a decentralized media and research organization that is autonomous by readers, researchers, and funders.

More posts from this author