Redactable blockchains and polynomial equations
本文通过利用通过求解多元多项式方程组来反转单向函数的计算难度，提出了一种用于可编辑认证数据结构的后量子安全构建方案。
原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。 阅读完整免责声明
在数字时代，我们的世界正日益通过智能设备的网络紧密交织在一起，从我们驾驶的汽车到家中的恒温器。这些系统通常被称为物联网，它们依赖于一个共享的事件记录来确保功能的安全性。多年来，保持此类记录安全的黄金标准是一种被称为区块链的技术。可以将区块链想象成一个复制在数千台计算机上的数字账本，其中每一个新条目的生成都由前一个条目锁定到位。一旦记录被写入，该系统的设计使得篡改或删除几乎变得不可能，从而确保没有人可以更改历史。这种永久性是一项优势，但在隐私法要求人们拥有“被遗忘权”，或者简单的由于人为错误需要进行修正而不破坏整个链条的世界里，它也变成了一个弱点。
科学家面临的挑战是创造一种既能保持不可篡改记录的安全性，又允许受信任的权威在必要时编辑或删除特定条目的系统。以往解决这一问题的尝试依赖于数学谜题，这些谜题在当今的计算机面前易于破解，但可能会被预计在十年内到来的未来量子计算机瞬间攻破。现在，一组研究人员提出了一种全新的解决方案，完全避开了这些脆弱的谜题。相反，他们将系统建立在另一种类型的数学难度之上：求解包含许多变量的复杂方程，这是一项目前已知的量子计算机无法高效完成的任务。
研究人员亚历山大·德明（Alexander Demin）、阿列克谢·奥夫钦尼科夫（Alexey Ovchinnikov）和弗拉基米尔·什皮尔赖因（Vladimir Shpilrain）开发了一种方法，其区块链的安全性取决于求解特定类型多项式方程的难度。在他们的系统中，每个区块中的数据被视为涉及一个变量的数学表达式，就像一个带有未知数的公式一样。链条的完整性由一个将一个区块链接到下一个区块的公共规则来维持。然而，中央权威机构持有一个密钥，这本质上是这些公式的一种特定的排列方式。凭借这个密钥，权威机构可以更改一个区块的内容，并计算出一个新的结尾部分，使其仍然满足公共规则，从而有效地在不破坏链条的情况下编辑记录。对于没有密钥的人来说，试图伪造这样的更改等同于求解一个拥有数十个未知数的庞大方程组，这在计算上是难以承受的。
为了确保他们的新系统真正安全，团队首先构建了一个基础版本，然后对其进行了系列模拟攻击，以观察其可能失效的地方。他们测试了攻击者可能尝试破解代码的四种不同方式。一种方法是尝试直接求解方程以找到新的结尾部分；另一种是尝试从公开数据中逆向工程出秘密公式；第三种方法是寻找公式构建过程中的模式；第四种方法则是通过观察系统随时间的变化来推导秘密。在最初的简化版本中，研究人员发现该系统对这四种攻击都存在漏洞。拥有足够计算能力的攻击者最终可以解出方程或推导出秘密公式，尤其是在他们能够观察到系统被多次编辑的情况下。
意识到这些弱点后，团队将他们的设计改进为高级版本，以堵塞这些漏洞。在改进后的构造中，链接区块的公共规则不再是一个已知的单一公式。相反，该规则是一个仅部分公开的隐藏方程组。现在的密钥包含了这些方程求值的特定点，而这些点是保密的。这意味着攻击者不能简单地通过查看公开数据来尝试求解秘密，因为他们所需的完整方程从未展示出来。当研究人员使用相同的四种攻击对这个高级版本进行测试时，结果截然不同。尝试求解方程的尝试失败了，因为系统过于复杂且缺少必要信息；试图推导秘密公式的尝试也失败了，因为攻击者无法看到数据被转换的全貌。
团队使用专门用于求解复杂数学问题的强大计算机和专业软件运行了这些测试。他们模拟了不同难度的攻击，通过增加方程的大小来观察破解系统需要多少计算能力。实验表明，随着他们增加方程的复杂度，求解所需的内存呈指数级增长。对于他们推荐的参数（涉及度数为20且系数基于约20位素数的方程），破解该系统所需的内存将超过任何现有计算机的容量，达到拍字节（PB）级别。这表明，虽然他们最初的想法存在缺陷，但高级版本为应对当前及未来的量子威胁提供了坚实的防御。
这项工作的意义在于它在灵活性与安全性之间取得了平衡。它提供了一种既能维护数字记录的可信度，又能尊重隐私和纠错需求的方法。通过从量子计算机预期会利用的数学结构转向多变量多项式方程的复杂性，研究人员为一种可以进化的区块链提供了蓝图。他们的研究结果表明，只要选择合适的参数，这种系统即使在计算技术进步的情况下也能保持安全，为在日益互联且受监管的世界中实现数据的安全管理提供了一条潜在的路径。
您所在领域的论文太多了？
获取与您研究关键词匹配的最新论文每日摘要——附技术摘要，使用您的语言。