可编辑区块链与多项式方程
《Advances in Applied Mathematics》:Redactable blockchains and polynomial equations
【字体:
大
中
小
】
时间:2026年08月28日
来源:Advances in Applied Mathematics 1.2
编辑推荐:
摘要
我们开发了新的工具,用于构建具有后量子安全性的可擦除认证数据结构。在我们的构造中,逆推所提出的一次函数意味着求解具有多个变量的多项式方程(或多项式方程组)。这目前被认为具有量子安全性,即如果参数选择得当,目前没有任何已知的量子算法能够高效地解决此问题。
引言
大多数人
摘要
我们开发了新的工具,用于构建具有后量子安全性的可擦除认证数据结构。在我们的构造中,逆推所提出的一次函数意味着求解具有多个变量的多项式方程(或多项式方程组)。这目前被认为具有量子安全性,即如果参数选择得当,目前没有任何已知的量子算法能够高效地解决此问题。
引言
大多数人工智能系统的关键部分是一个自适应电子设备网络。此类网络中最流行且迅速普及的一类是物联网。
物联网代表了本世纪最重要的技术之一。它是互联网(计算机互联网)向嵌入式系统和网络物理系统的自然演变,“物”虽然不明显是计算机本身,但内部却装有计算机。
物联网在研究和产业方面正经历指数级增长,但仍存在隐私和安全漏洞。传统的安保和隐私方法往往不适用于物联网,这主要归因于其去中心化拓扑结构以及大多数设备的资源限制。最近,区块链被用于为点对点网络和人工智能系统提供安全和隐私,例如智能汽车、智能家庭、智能城市等。
区块链可以是公开的,也可以是私有的。公开区块链的典型例子是比特币。相比之下,私有区块链网络中的参与者是已知且受信任的:例如,一个行业集团、一个军事单位,或者事实上任何大型或小型的私有网络。
最初,区块链是为了支持公共的比特币网络而创建的。对于这样的网络来说,不可篡改性至关重要。最近,随着人工智能理念的发展,私有网络成为了焦点,这带来了新的挑战。特别是,希望在保留篡改检测属性的同时,允许拥有更高权限访问权的人员(如系统管理员或其他机构)能够更改数据或将其擦除(“忘记”)。能够像这样更改的区块链被称为可擦除区块链。即使是公共区块链也需要可擦除性的原因,由以下《纽约时报》[6] 的引用解释得很清楚:“这种持久性对于建立对数百万人使用的去中心化货币的信任至关重要。但它可能会严重限制区块链在其他金融服务业领域的实用性,这些领域依赖数十亿人。通过与新的隐私法(如‘被遗忘权’)发生冲突,并使高效解决人为错误和恶作剧几乎不可能,区块链的不可篡改性最终可能成为它自身最大的敌人。”消除冗余和删除过时记录对于计算能力有限的设备网络(例如物联网)尤其重要。
本文提出了一种基于多元多项式方程的新安全、私有且轻量级的可擦除区块链架构。
早期的可擦除区块链构造(例如 [1], [5], [11])要么不实用,要么不具备量子安全性,要么两者兼是。在保持 [11] 中构造的简单性和效率的同时,我们开发了新的工具,用于构建具有后量子安全性的可擦除认证数据结构。避免基于求解隐藏子群问题的量子攻击(包括 [15] 中的攻击)的一种可能方法是不要使用本质依赖于某种(半)群结构的一次函数。在我们的构造中,逆推所提出的一次函数意味着求解具有多个变量的多项式方程(或多项式方程组)。这目前被认为具有量子安全性,即如果参数选择得当,目前没有任何已知的量子算法能够高效地解决此问题。
章节摘要
背景
本提案中的方法专注于私有区块链。它与 [1], [5], [14] 及其他方法大不相同,且具有透明性和易于实现性。
在高层面上,我们的方法与 [11] 中的构造有一些相似之处,后者基于 RSA 问题的计算困难性,因此不具备量子安全性,而本文旨在构建具有量子安全性的构造。尽管如此,我们首先简要描述 [11] 中的构造以提供背景。
基本构造
现在,我们描述一种涉及带有陷门的量子安全单向函数的区块链完整性条件。在本节中,为了阐明这一想法,我们首先描述构造的基本版本。基本版本易受几种攻击。在文本的后半部分(第 5 节),我们提出了一种能够抵御这些攻击的构造。
回顾一下,$\mathcal{P}_i$ 表示区块 $B_i$ 的前缀。前缀是不可变的,即任何人都无法更改它们。我们不深入探讨。
对基本构造的可能攻击
现在让我们看看未经授权的方可能试图做什么以将 $\mathcal{C}_i$ 修改为某个 $\mathcal{C}'_i$。有几种可能性:
攻击 1. 求解多项式方程 $F(\mathcal{P}_i, \mathcal{C}'_i, X) = \mathcal{P}_{i+1} \pmod{(t-t_0)\cdots(t-t_d)}$ 中的 X,其中 X 是 t 的一个次数为 d 且系数来自 $\mathbb{Z}_n$ 的多项式。然后这个 X 可以作为区块 $B_i$ 的新后缀。这导致了 X 系数中的一个平方多项式系统。一般来说,求解这样的系统是一个困难的问题,但也许对于一些特殊多项式来说,它可能会变得。
高级量子安全构造
现在我们提出一种构造(完整性条件和陷门),它不会受到之前提到的攻击的影响。
设 $F(x,y,z)$ 为一个三变量多项式,其系数为模 n 整数。引入新的不定元 $\bar{A} = (A_0, \dots, A_d)$,同样地对于 $\bar{B}, \bar{C}, \bar{D}$。设 $\hat{\mathcal{P}}_i(t), \hat{\mathcal{C}}_i(t), \hat{\mathcal{S}}_i(t), \hat{\mathcal{P}}_{i+1}(t)$ 为定义如下的一元多项式,次数均为 d:
$\hat{\mathcal{P}}_i(t) = A_0 + \dots + t^d A_d$,
$\hat{\mathcal{C}}_i(t) = B_0 + \dots + t^d B_d$,
$\hat{\mathcal{S}}_i(t) = C_0 + \dots + t^d C_d$,
$\hat{\mathcal{P}}_{i+1}(t) = D_0 + \dots + t^d D_d$.
注意,如果将 $\bar{A}, \bar{B}, \bar{C}, \bar{D}$ 专门化为某些值。
建议参数和区块大小
设 $d_1, d_2, d_3, d_4 \in \mathbb{N}$。设
$G(x,y) = \sum_{i=0}^{d_1} \sum_{j=0}^{d_2} a_{i,j} x^i y^j$
和
$H(x,y) = \sum_{i=0}^{d_3} \sum_{j=0}^{d_4} b_{i,j} x^i y^j$,
其中 $a_{i,j}$ 为模 n 整数,$i = 0, \dots, d_1$ 且 $j = 0, \dots, d_2$,$b_{i,j}$ 为模 n 整数,$i = 0, \dots, d_3$ 且 $j = 0, \dots, d_4$。
建议的参数值为:n 是一个大小约为 20 位的素数,$d_1 = d_2 = d_3 = d_4 = 2$,$d = 20$。对于这些 $d_1, d_2, d_3, d_4, d$ 的值,执行所提出的攻击在实际中似乎是不可能的,我们将在第 7 节的实验中看到。
$a_{i,j}$ 的值可以选择为随机非零整数。
实验结果
在本节中,我们展示了针对基本构造的攻击可能成功,但用于针对高级量子安全构造时却失败了。
本项目的实验在 Intel? i9-13900 处理器上完成,配备 50 GB 内存,使用 24 核心。作为主要平台,我们使用了 Maple 2024 [2],以及两个 Julia 包:Groebner.jl 0.8.3 [4] 和 AlgebraicSolving.jl 0.8.2 [3]。我们使用 time 命令测量内存消耗。我们的实验代码是。
结论
我们提出了一种基于多元多项式方程的新量子安全且轻量级的可擦除区块链构造。
我们使用各种格罗伯基计算技术研究了我们的方案可能面临的几种攻击,并确定它们中的任何一种针对我们的构造都是不可行的。
致谢
我们感谢审稿人指出攻击 4。
Alexander Demin, Alexey Ovchinnikov, Vladimir Shpilrain
巴黎综合理工学校信息实验室,LIX, UMR 7161, 法国国家科学研究中心,91120 Palaiseau, 1 rue Honoré d'Estienne d'Orves, 法国