-
摘要:
随着数字化进程的加速推进,数据安全和隐私保护问题备受关注. 数据加密一直是解决该问题的重要手段,但加密存储和传输较为常见,一旦涉及计算往往需要先解密,以明文形式计算后再加密. 全同态加密(fully homomorphic encryption,FHE)将加密延展到计算层面,无需解密即可以完成密文的处理任务,有保护数据安全和用户隐私的天然特性. 首个FHE方案于2009年由Gentry提出,自此FHE方案一直备受业界和学界的关注. 从FHE方案的构造思想、不同研究阶段及面临的问题等方面梳理分析了FHE 10余年的研究进展,从算法库实践、标准化进展以及典型应用场景等方面介绍了FHE的应用进展,并提出未来研究的方向建议.
Abstract:With the acceleration of the digitization process, the problem of data security and privacy protection has attracted much attention. Data encryption has always been an important means to solve this problem. However, it is common to store and transfer data in encrypted form. Once calculation is involved, it is often necessary to decrypt the ciphertext, perform the calculation in plaintext, and then encrypt the calculation result. Full homomorphic encryption (FHE) extends encryption to the computing, which can perform meaningful calculations in ciphertext without decryption, and the calculation process and result are encrypted, so it has the natural characteristics of protecting data security and user privacy. The first FHE scheme was proposed by Gentry in 2009, and then FHE has always attracted the attention of the industry and academia. After more than ten years of research, FHE has developed to the fourth stage, and substantial progress has been made. We review and analyze the research progress of FHE from the aspects of the construction idea, different research stages and problems faced, introduce the application progress of FHE from the aspects of algorithm library, standardization progress and typical application scenarios, and put forward suggestions for future research direction.
-
随着车联网中车辆数量的不断增加,车辆之间数据共享交换的速度和频率越来越高,安全高效的智能车联网数据共享方案已成为研究热点. 其中,基于区块链的方案持续涌现,成为车联网数据共享的重要途径. 目前,基于区块链的车联网数据共享方案主要有:基于区块链的联邦学习数据共享方案[1-2],使用区块链代替联邦学习中的中心化服务器,提出了面向分布式终端的去中心化数据共享架构与系统; 基于新型共识协议的数据共享方案[3-4],针对不断变化的车联网环境,提出适用于不同场景的共识机制;基于区块链访问控制的数据共享方案[5-6],提出新的加密方式实现对区块的细粒度访问控制. 以上方法所使用的区块链系统吞吐量较为有限,难以应对未来智能车联网中海量数据共享需求.
区块链分片技术[7]旨在提高吞吐量以实现区块链系统的可扩展性. 该技术将区块链网络节点分成多个分片(shard),每个分片只需要处理一部分交易数据,多个分片并行执行. 主要的分片区块链技术,如Elastico[8],RapidChain[9],OmniLedger[10],ChainSpace[11],MVCom[12],在提升系统吞吐量的同时,为了保证分片的安全性,采用了多种密码技术将区块链节点随机分配到各个分片中,以抵御敌手对片内节点的贿赂,防止片内恶意节点数量超过单个分片安全阈值.
将区块链验证节点随机地分配到不同分片,在理论上能最大程度地保证分片区块链的安全性,然而难以适配实际的车联网应用环境,原因在于:1)地理位置上接近的车联网区块链节点可能被分配到不同的分片当中,使得车辆之间的数据共享协同效率降低;2)随机分片的方案对车联网区块链分片的负载问题考虑较少,可能导致不同分片之间的负载存在较大差异,造成车联网基础设施资源(带宽、算力等)分配不均匀和利用不充分. 因此,亟需适用于实际车联网应用的区块链分片方案,该方案面临3个挑战:
1)现有的分片算法缺乏实现片内节点距离相近与片间负载均衡的能力,仅能够取得这2个要素中单一目标的较优解,无法同时优化2个要素;
2)各个分片内恶意路侧单元的数量未知,当分片内的恶意路侧单元(road side unit,RSU)数量过多时,由恶意RSU主导的共识产生区块上链;
3)为保证分片系统的安全性,现有方案需要定期对各个分片实行轮换和置乱等节点重新配置,带来了节点额外数据下载开销,且需要维持较大的单个片内节点数量,降低了片内共识过程效率.
针对上述3个挑战,本文设计了一种基于分片区块链的车联网数据共享方案. 主要贡献包括3个方面:
1)提出了一种基于机器学习的分片算法,该算法基于聚类实现片内节点在地理位置上的紧凑分布,借助平衡损失实现分片间在负载上的均匀分布,实现高吞吐量的车联网区块链架构;
2)提出了基于声誉的片内共识协议,通过片内各个RSU参与共识的行为评估其声誉,高于设定的声誉阈值的RSU可参与片内共识,确保高声誉节点主导片内共识,抵御片内恶意RSU数量过多导致的安全问题;
3)提出了监督人机制,选取声誉度较高的节点作为监督人,可以随机、定期验证不同分片节点交易验证的合法性,降低了对片内节点数量较大的要求,对提升分片系统的安全和效率都有重要作用.
1. 相关工作
区块链是一种去中心化的分布式账本技术,通过将交易记录按照时间顺序连接成块,并使用密码学方法保证数据的安全性和完整性,实现了可信、不可篡改的数据存储. 将区块链技术应用于智能车联网,为车联网提供了去中心化的数据共享方式,减少了单点故障的风险. 在提升性能方面,文献[13]提出了一种车联网区块链资源管理方案,通过优化RSU和利用车辆的计算资源来提升吞吐量. 文献[14]设计了一种增强的委托权益证明(delegated proof of stake,DPoS)共识协议,加速了交易确认的同时缩短了数据共享时间,有效提升了车联网系统的吞吐量. 文献[15]提出了一种新型的区块验证方法,每个节点存储自身的交易验证记录,如果之前已验证过发送节点的区块,就简化验证过程,从而提升系统性能. 在增强安全性方面,文献[16]提出了一种基于区块链的车联网可信数据共享机制,利用基于Kademlia算法的流量数据转发方法来控制车联网中信道的拥塞状态,保证了重要数据在传输过程中的安全性. 文献[17]设计了一种双链并行的车联网信息共享方案,通过智能合约的自动执行实现数据的安全流通,并与区域内其他用户共享车联网数据. 文献[18]提出一种基于区块链和加权密文的车联网数据安全共享方法,基于特征对链上数据进行访问控制,确保只有授权的访问者才能访问数据内容,实现了车联网中安全的数据共享. 文献[19]设计了基于零知识证明的区块链数据共享方案,以匿名方式将数据和车辆信息相结合,并允许其他车辆和RSU匿名验证数据记录,实现安全的数据共享.
文献[13-19]方案主要是将区块链技术引入车联网数据共享与安全领域,对区块链系统的吞吐量性能考虑较少. 分片机制是提升吞吐量的主要手段之一,它将区块链节点划分为多个分片,各个分片可以并行地、独立地处理各自的交易和数据,这使得区块链的吞吐量能够线性扩展,即吞吐量可以随着节点数的增加而线性增长. 因此,分片技术可以用来解决区块链的可扩展性问题,且同时保持较高的安全性和去中心化程度. 现有的区块链分片方案,一般从分片节点的随机分配以保障安全性[8-12]、降低跨分片开销以提升吞吐量[20-22]、分片之间负载均衡以避免热点分片[12,23-25]、分片安全与效率平衡[26-27]、智能合约分片[28-29]等多个方面开展研究.
在分片区块链安全性方面,文献[9]利用有限布谷鸟原则以保证不同分片规模的平衡,并使用可验证秘密共享来生成无偏随机性,要求新加入节点解决工作量证明(proof of work,PoW)难题加入分片协议,从而抵御女巫攻击. 文献[10]中的每个共识周期,依赖可验证随机函数(verifiable random function,VRF)进行不可预测的领导者选举. 协议将领导者视为RandHound协议的客户来生成随机种子. 此外,还可以通过引入声誉机制来确保系统的安全与可信. 文献[30]提出一种基于区块链的隐私保护车辆数据共享框架,使用零知识证明技术以保护车辆的身份隐私,同时设计高效的分片协议降低系统的通信成本,增强系统的安全性. 针对分片内部共识安全问题,文献[31]基于车辆间历史交互信息和其他车辆的推荐信息评估该车辆的声誉,并赋予高声誉节点出块权力,从而确保数据共享的安全性和可追溯性. 然而,文献[9-10, 30-31]所述的方法要求对分片的高频率重构,且忽视了将参与共识的行为作为节点声誉的评估标准,难以适用于实际车联网动态变化环境,需要提出更简单高效的分片安全性保护方法和对节点的声誉评估方法.
2. 预备知识
2.1 区块链分片
将区块链分片协议进行形式化. 给定一个区块链网络,其中包含n个节点,每个节点维护全网的一部分交易历史,其中有f个拜占庭节点. 目标是将该区块链网络分割成k个分片,其中k≪n,以提高网络的可扩展性和性能. 每个分片i(1⩽包含1组节点,记作shar{d_i}, shard = \bigcap\limits_{i = 1}^m {shar{d_i}} ,且 shar{d_i} \cap shar{d_j} = \varnothing ,即所有节点被分片覆盖且分片间的节点互不相交. 区块链节点之间运行分片协议,输出一个集合X,其中包含 k 个不相交的分片或子集 {X_{{i}}} = \{ x_i^j\} (1 \leqslant j \leqslant \left| {{X_i}} \right|) . 区块 i 中的交易 j 被定义为 x_i^j . 节点可以通过使用函数C给定任何交易,输出1或0分别表示交易是否有效,以确定交易的合法性.
1)一致性. 对于 i \in \{ 1,2, … ,k\} ,所有诚实的节点对 {X_i} 达成一致.
2)有效性. 对于 i \;\in\; \{ 1,2, … ,k\} 和 j \;\in \;\{ 1,2,…,\left| {{X_i}} \right|\} , C({x_{i,j}})= 1 .
3)可扩展性. k 随着网络规模或 n 的增长而线性增长.
2.2 基于声誉的共识协议
共识协议的主要功能是存在拜占庭节点的情况下,确保诚实节点能够维护一个一致的账本. 声誉机制在现代社会中扮演着至关重要的角色. 在人们进行决策时,往往会依赖公开的且基于声誉的排名系统来做出选择. 将声誉机制与共识协议相结合可以实现3个重要目标:
1)对参与共识的节点的历史行为进行评估,从而实现对节点的良性行为进行褒奖和对不当行为进行追责[32-33];
2)基于节点的声誉,公平地选举诚实的节点参与共识并且提升协议的可扩展性[34-35];
3)将节点投票权重转换为声誉,当系统中的恶意节点超过容错上限时,能使共识协议在一定时间内保证安全性与活性[32,34].
3. 基于分片区块链的车联网数据共享方案
3.1 系统模型
本文设计了一个支持分片的车联网区块链架构,由车载单元(on board unit,OBU)、RSU和可信机构(trusted authority,TA)组成. 系统模型及组件之间的关系如图1所示.
1)OBU. OBU通常依附于智能汽车,具备计算、存储和无线通信能力,可以与其他OBU、RSU、TA进行通信,在通信之前需要向TA发起并完成注册.
2)RSU. RSU是分片内参与共识的节点. 其主要职责是接收来自OBU的数据,并与其他RSU达成共识后,最终将数据上传至本地分布式账本. 在此过程中,假设每个分片中各个RSU的公钥是相互知晓的.
3)TA. TA为合法OBU和RSU颁发证书,并通过安全通道分发车辆和RSU的公钥和私钥.
OBU之间的通信以及OBU与RSU之间的通信采用IEEE 802.11p[36]或DSRC[37]协议,以上协议在数据传输过程中具有低延迟、高稳定的性质.
3.2 基于机器学习的分片算法
区块链中,节点数据可以被转化基于属性的表示形式,以便机器学习算法进行分析和应用于分片任务. 首先需要对基于机器学习的车联网分片问题进行定义.
定义1. 基于机器学习的车联网分片. 给定一个由N个RSU组成的集合:
V = \{ {c_i}=({x_i},{y_i}),w_i|x_i,y_i \in {\mathbb{R}} ,w_i \in (0,+\infty),i=1,2,…,N\}. (1) 其中ci代表RSU的2维位置坐标,表示RSU所在的地理位置;wi代表RSU的负载,表示RSU一定时间内的平均负载. 基于机器学习的车联网分片需要通过机器学习模型,最小化以下目标函数:
\arg \min \displaystyle\sum\limits_{i = 1}^k {\displaystyle\sum\limits_{v \in {X_i}} w } + \displaystyle\sum\limits_{i = 1}^k {\displaystyle\sum\limits_{v \in {X_i}} {||c - {\mu _i}||} } \text{,} (2) 其中v代表RSU节点,k代表分片数,Xi代表第i个分片,μi代表归属于第i个分片的所有RSU的位置均值, ||{c_i} - {\mu _j}|| 代表两点之间的欧氏距离.
现有的聚类算法一般是通过将邻近节点聚合成簇实现分片,满足片内节点相近的需求. 在车联网区块链分片中,若分片间负载不均衡,会导致基础设施资源分配失衡,进而造成资源浪费. 例如,在下班高峰时段,某个分片的车流量激增,导致该分片的RSU负载显著增加,无法高效地处理车辆数据,而其他分片的计算资源却处于闲置状态. 因此,实现负载均衡的分片能避免资源浪费,并提高数据共享效率. 本文提出了一种面向车联网区块链分片的均衡聚类算法,该算法在K-Means++[38]算法上使用正则项约束簇间负载以尽可能保持均衡,其损失函数为
L({c_i},{w_i},{\mu _j}) = ||{c_i} - {\mu _j}|| + {w_i}{(1 + \lambda )^{T - M + {w_i}}} \text{,} (3) \lambda = \exp \left(\dfrac{{\ln \bar w - \ln M}}{{\bar w - M}} - 1\right) \text{,} (4) T = \displaystyle\sum\limits_{v \in {X_j}} w \text{,} (5) M = \dfrac{{\displaystyle\sum w }}{k} \text{,} (6) 其中T代表第j个簇内所有节点负载之和,M代表每个簇的最优负载值, \lambda 代表损失函数的惩罚系数.
由式(3)可知,该损失函数由2部分组成:第1部分是距离损失 ||{c_i} - {\mu _j}|| ,其代表某个点与最近聚类中心的欧拉距离,与K-Means算法中的距离损失相同;第2部分是正则项 {w_i}{(1 + \lambda )^{T - M + {w_i}}} ,其代表分片负载均衡的惩罚项. 采用贪心算法为节点分配聚类簇,若分配的簇加入该节点后权重超过簇的最优负载值,惩罚项则会呈现指数增大,进而实现负载均衡的目标;而 \lambda 作为自适应权重,能够根据节点的权值与质心数自动调整,使得惩罚处于合理的范围内.
基于该损失函数的优化过程如算法1所示.
算法1. 均衡聚类算法.
输入:节点集V,分片数k;
输出:聚类结果.
① 用式(4)~(6)初始化λ, T, M;
② for iter in max_iters
③ clear cost[k];
④ previous_assignment = assignment;
⑤ for each vi sampled from V
⑥ assign vi to kj by minimizing 式(3);
⑦ cost[kj] += wi;
⑧ end for
⑨ for each kj in k
⑩ centers[kj] = mean(ci where assignment == kj);
⑪ end for
⑫ if previous_assignment == assignment
⑬ break;
⑭ end if
⑮ end for
算法1采用贪心策略搜索最优的分片策略. 每次遍历将为当前节点分配损失最小的簇,并更新对应簇的负载值,直至算法收敛. 在搜索前期,惩罚项指数为负,该阶段的分配策略是距离优先;随着节点的不断分配,部分簇的负载已接近最优负载值,惩罚项会逐步增大,该阶段的分配策略是混合分配;在搜索末期,绝大多数簇已达到最优负载,分配策略是负载优先. 这种策略能够确保算法在前期形成簇状聚类结构,并在搜索过程中不断优化,进而在维持聚类结构的同时实现负载均衡. 值得注意的是,由于RSU的数据负载随着时间不断变化,因此每隔一定时间需重新运行均衡聚类算法以生成新的区块链分片.
3.3 基于声誉机制的片内共识
通过基于机器学习的分片算法将RSU分入若干个分片后,为了保证片内共识协议安全地运行,需要对片内RSU进行筛选,从而防止恶意的RSU主导共识过程. 本节对片内RSU选举的方式和参与共识的过程进行描述.
3.3.1 设计概览
单个分片内安全地运行共识协议存在2个挑战:1)基于机器学习的分片无法保证片内节点多数诚实,单个分片可能会被贿赂;2)当每个分片内RSU数量过多时,需要共识协议具备一定的可扩展性,从而保持系统性能的稳定.
为保证共识协议的最大容错能力,假设系统处于同步网络模型中,消息在2个RSU间的传播的延迟上限为\varDelta ,能容忍小于1/2的拜占庭节点. 为了保证分布式账本确定的一致性,需要在分片中设计一个同步拜占庭容错(Byzantine fault-tolerant,BFT)协议. 同时,由于各个分片中诚实的RSU数量未知,无法确保片内共识协议能安全运行. 对此,需要对每个RSU进行声誉的评估,通过声誉显式表达RSU的可信度. 此外,需要基于各个RSU的声誉选举高声誉的RSU参与片内共识. 基于声誉的状态机复制(reputation-based state machine replication,Reputation-based SMR)协议[32]是一个同步BFT协议,能对参与共识的节点行为进行评估,从而为每个节点评估所有节点公认的声誉. 当RSU作为参与共识的节点时,该协议能针对RSU的扣留区块(即RSU作为领导者拒绝提议区块)、提议冲突区块(即RSU作为领导者提议2个及2个以上的区块)、恶意投票(即RSU投票给非领导者区块)、恶意区块提议(即非领导者RSU提议区块)4个恶意行为对RSU的声誉进行削减. 同时,该协议能针对RSU的正常区块提议与投票增加RSU的声誉,因此该协议拥有普适性,能够很好地适用于车联网环境.
在Reputation-based SMR协议上设计片内共识节点选举函数,选择声誉高于阈值的RSU参与共识,避免声誉低的恶意节点主导共识. 同时,选举高声誉的节点参与共识而非分片内所有节点降低了协议的通信复杂度并提高了可扩展性,协议的性能不会随着片内节点的增多而明显下降.
3.3.2 协议描述
1)协议组件
基于声誉的片内共识协议将Reputation-based SMR协议与片内共识节点选举函数作为协议组成部分. Reputation-based SMR协议中的声誉机制能基于节点参与共识的行为,对产生不当行为的拜占庭节点声誉削减,并给予产生良性行为的节点声誉褒奖. 此外,Reputation-based SMR协议的证据广播阶段保证了声誉一致性.
定义2. Reputation-based SMR协议. 由领导者选举函数、拜占庭广播原语和声誉机制组成. Reputation-based SMR协议满足3个属性:
1)安全性. 任意2个诚实节点在同一高度上不会提交不同的区块.
2)声誉一致性. 在同一区块高度,任意2个诚实节点不会对某一节点产生不同的声誉视图.
3)活性. 如果1笔交易被1个诚实节点接受,那么这笔交易最终会被包含在所有诚实节点的账本上.
基于Reputation-based SMR协议构建片内共识节点选举函数,确保高声誉的节点参与共识. 具体过程如算法2所示.
算法2. 片内共识节点选举函数.
输入:分片内RSU的总数m,分片内RSU的公钥集合PK,分片内RSU的声誉集合U,当前轮次数q;
输出:高声誉RSU的公钥集合PK′.
① 初始化 PK' \leftarrow \varnothing ;
② x \leftarrow H(p{k_i},q) ;
③ if \tau {r_i} - \dfrac{x}{{{2^\eta }}} > 0 then
④ PK' \leftarrow PK' \cup {p_i} ;
⑤ else
⑥ PK' \leftarrow PK' ;
⑦ end if
算法2中, {r_i} 代表任意 {RSU_i} 的声誉; \tau 代表难度系数,控制各个节点被选举的难度;\eta 代表所选加密哈希函数的位长. 可以看出,RSU声誉越高,越容易超过给定阈值,从而担任共识节点. 反之亦然.
2)基于声誉的片内共识协议
通过片内共识节点选举函数与Reputation-based SMR协议构建基于声誉的片内共识协议. 协议流程如图2所示.
基于声誉的片内共识协议在由片内共识节点选举函数选举出的高声誉节点中执行提议、转发和投票步骤. 此外,基于声誉的片内共识协议通过分片内广播的共识结果与分片内所有RSU共享. 下面描述该协议的详尽过程.
1)节点更新声誉. 此步骤与Reputation-based SMR协议下的节点更新声誉步骤相同. RSU执行Reputation-based SMR协议中附带的声誉函数更新当前轮次的声誉并开启一个4\varDelta 的计时器.
2)区块生成. 分片内的RSU执行片内共识节点选举函数,选举高声誉RSU参与共识,并且被选举的高声誉RSU被公知. 在此基础上,通过Round-Robin选举领导者来进行区块提议. 如果某个RSU被片内共识节点选举函数选中,它将参与共识协议;否则,它将等待分片内广播传播的区块与各类证据.
3)片内广播. 这个阶段与Reputation-based SMR协议的证据广播阶段相似. 当计时器仅剩\varDelta 时,参与共识流程的RSU将在提议、转发和投票过程中产生的区块和各类证据(如扣留区块、良性区块提议等)广播给分片内所有节点. 分片内所有诚实RSU将会对这些内容达成共识.
4)区块提交. 此阶段与Reputation-based SMR协议的区块提交阶段相同. RSU根据在此轮共识中是否出现扣留区块证据或冲突区块证据来判定是否提交空块.
然而,当分片内恶意RSU数量过多时(如超过1/2时),无法以极大概率选举多个诚实的RSU参与共识. 此时,恶意RSU将有可能终止甚至主导片内的共识过程,并产生非法区块,从而影响分布式账本上区块的合法性. 在3.4节中将用监督人机制来解决这个问题.
3.4 监督人机制
分片机制将区块链节点划分为多个分片,每个分片内的分片规模远小于整个区块链网络的规模. 通常情况下,在相同的节点规模的基础上,分片数量的增加,即每个分片内节点数量的减少,有助于提高系统的吞吐量.
然而,片内节点数的减少会降低分片系统的安全性,例如:单个分片容易遭受贿赂攻击[39]. 节点规模为4 000个,未分片的区块链系统,敌手需要攻击区块链系统全网的1/3节点(1 667个节点);分片后,在16个分片情况下,敌手仅需攻击分片系统中单个分片内的1/3节点(84个节点).
同时,对片内共识协议能够支持的节点数量提出了新的要求. 例如:使用PBFT作为片内共识协议时,由于该算法的通信复杂度为 O({n^2}) ,当分片内节点数量增多时,其共识效率会大幅度降低,导致分片系统的总吞吐量快速下降. 因此,现有分片系统往往需要选择能够支持更多节点的片内共识协议[10].
采用超几何分布来计算每个分片在不同分片规模下,随机挑选出一个分片,其恶意节点数量大于1/2的概率(分片内恶意节点数量超过分片安全阈值).
Pr\left[X \geqslant \left\lfloor {\dfrac{m}{2}} \right\rfloor \right] = \displaystyle\sum_{x = \left\lfloor {\tfrac{m}{2}} \right\rfloor }^m \dfrac{{\left( {\begin{gathered} t \\ x \end{gathered}} \right)\left( {\begin{gathered} {n - t} \\ {m - x} \end{gathered}} \right)}}{{\left( {\begin{gathered} n \\ m \end{gathered}} \right)}} \text{,} (7) 其中m代表分片规模,n代表区块链网络中的总节点数,t代表区块链网络中恶意节点的数量,x则是被随机选中组成一个分片的恶意节点数量.
当t = n/3时,即系统容忍不超过1/3的恶意节点. 图3展示了使用超几何分布模拟在4 000个节点的场景下,随机选择一个分片,并计算该分片中恶意节点比例超过1/2的概率. 由图3可以看出,分片规模越大,选取分片失败的概率越低,区块链系统的安全性越高,当分片规模超过250个节点时,其失败概率是可以接受的. 例如:RapidChain[9]在网络规模为4 000个节点时,将每个分片的节点数量限制在250个节点以保障极高的安全性,平均每4 500年才会出现1次故障.
现有的保证系统安全性的分片方案通常是定期地将各个分片中的节点进行全部打乱或者部分打乱. 然而,这种做法会破坏分片内节点之间的地理位置关系,不利于3.2节分片算法的实施. 此外,还引入了节点更换分片时数据移动的额外开销. 当1个节点从分片 \alpha 转移到分片\beta 时,它需要重新下载分片\beta 节点所存储的所有历史数据,以便能够验证分片\beta 后续的数据.
重新组建整个分片需要耗费大量时间和额外成本,但仅进行部分重新配置无法确保足够的安全性. 例如,在RapidChain[9]中,系统周期性地对分片进行重新划分,以确保大多数成员仍属于活跃分片. 当有新节点加入时,参考分片会根据一定规则随机地将新节点分片到某个活跃分片中,并将一定数量的节点从该活跃分片随机分配到其他的消极分片中,实现了新节点加入系统,控制了活跃分片和消极分片数量,达到了一种活跃节点间的平衡. 这种方式旨在平衡活跃分片数量以及不活跃分片数量,从而提高了整个区块链分片系统的活跃性、增加了敌手共谋攻击的成本,间接提高了系统的安全性. 但由于仅是对各个分片的部分节点进行重新配置,因此系统安全性提高的程度非常有限.
为了解决以上这些问题,本文提出了监督人机制,以代替现有的分片重构方案.
根据3.3节得到每个节点的声誉度,选取每个分片中声誉度较高的节点作为系统监督人,它们可以监督和验证分片系统中的数据. 这意味着每个数据同时被1个分片的所有节点以及监督人所验证,管理者可以通过调控奖惩机制来控制监督人的数量,达到所期望的性能与安全性的平衡.
车辆在行驶过程中,会不断地与周围的RSU进行通信. 每个RSU需要接收和传播数据,如图1所示. RSU接收到了新的车辆数据时,它会将带有车辆签名的数据传输给地理位置接近的若干个RSU. 在车辆数据产生时,RSU首先将数据发送至TA,TA向所有RSU广播数据,通过车辆单元的移动和RSU之间的交互,促使各分片之间可以共享数据,监督人也进而具备监督并验证所有分片数据的能力. 如果发现其他分片对某次数据进行作恶,任何一个验证了该分片数据的监督人都可以将其验证结果通知给分片系统,从而协同决定原始分片是否存在恶意行为,并进一步做出处理.
当节点加入系统时,每个节点需要缴纳一部分的押金,该押金由TA进行管理,用于防止节点在后续处理车联网数据时出现恶意行为. 并且,有利于避免恶意监督人以增加系统运行负担为目的而提交无效监督,提高恶意行为门槛. 若监督人发现非法数据,表明该数据所属分片已经被损坏,即分片内的恶意节点数量已经超过安全阈值. 在这种情况下,监督人提交一笔特殊交易,特殊交易包含监督信息以及用于防止恶意举报行为的押金. 区块链节点将根据这一特殊交易验证举报信息是否有效,验证结果分2种情况:1)如果举报有效,则返回监督人的举报押金,扣除恶意数据中包含的所有参与签名的节点的押金,并报告至TA,TA根据一定规则对监督人以及作恶节点进行奖惩,并降低作恶节点声誉;2)若举报无效,说明监督人提交了恶意的举报,则扣除监督人的举报押金以及基础押金,降低监督人节点的声誉.
监督人可以在恶意分片中、正常分片中、数据发起用户或者区块链网络之外的第三方. 它们可以从共享数据中存储数据,从而拥有对分片系统中所有分片数据验证的能力. 显然,节点保存选择验证分片系统中的数据越多,监督成功并获得的奖励就越多. 这一机制会鼓励更多的节点提高声誉度以及担任监督人的角色,形成积极循环,从而进一步增强车联网系统的安全性.
4. 安全性分析
4.1 共识协议安全属性分析
本节将证明由片内共识节点选举函数选举的RSU满足诚实多数. 此外,证明基于声誉的片内共识协议满足安全性、活性.
引理1. 诚实多数. 如果单个分片内诚实RSU数量大于1/2,则片内共识节点选举函数选出的RSU中至少一半是诚实的.
证明. 在最坏的情况下,所有节点的声誉值均为1. 片内共识节点选举可以看作一个独立的随机抽样问题,节点被选中的概率为
Pr[{R_j}{\text{ is selected}}] = \dfrac{{s{r_j}}}{{\displaystyle\sum\limits_{i = 1}^m {{r_i}} }} = \dfrac{s}{m} \text{,} (8) 其中 s 是被选中RSU的数量, m 是分片内RSU的总数, {r_j} 是某个RSU的声誉值.
假设 \rho = \dfrac{{m - {f^*}}}{m} 表示选举的节点为诚实节点的概率, \sigma = \dfrac{{{f^*}}}{m} 表示选举的节点为拜占庭节点的概率,其中 {f^*} 代表分片内恶意节点的数量. 随机变量A表示被选中RSU中诚实节点的数量,随机变量B表示选中RSU中拜占庭节点的数量. 随机变量A和B满足以下二项式分布:
Pr[A = k] = \left( \begin{gathered} m \\[-5pt] k \\ \end{gathered} \right){\left(\rho \dfrac{s}{m}\right)^k}{\left({\text{1}} - \rho \dfrac{s}{m}\right)^{m - k}} \text{,} (9) Pr[B = k] = \left( \begin{gathered} m \\[-5pt] k \\ \end{gathered} \right){\left(\sigma \dfrac{s}{m}\right)^k}{\left({\text{1}} - \sigma \dfrac{s}{m}\right)^{m - k}} \text{,} (10) 设 X 和 Y 分别表示为
X = \left\{ {A:0 \leqslant A \leqslant \left\lfloor {\dfrac{s}{2}} \right\rfloor } \right\} \text{,} (11) Y{\text{ = }}\left\{ {B:\left\lceil {\dfrac{s}{2}} \right\rceil \leqslant B \leqslant m} \right\} \text{,} (12) 当 X 和 Y 都未成立,被选中的RSU诚实大多数的性质成立. Pr[X \cup Y] 代表 X 和 Y 至少有1个成立,其概率为
\begin{split} Pr[X\cup Y] = &Pr[X]+Pr[Y]-Pr[X\cap Y]=Pr\left[A\le \left\lfloor \dfrac{s}{2}\right\rfloor \right]+\\ & Pr\left[B\ge \left\lceil \dfrac{s}{2}\right\rceil \right]= F\left(\left\lfloor \dfrac{s}{2}\right\rfloor ,m,\dfrac{\rho s}{m}\right)+\\ &F\left(m-\left\lceil \dfrac{s}{2}\right\rceil ,m,\text{1}-\dfrac{\sigma s}{m}\right)\text{,}\\[-1pt]\end{split} (13) 其中 F(k,m,p) = Pr[X \leqslant k] 是随机变量 X \sim B(m,p) 的累积分布函数,根据二项式尾界定理可知
Pr[X\cup Y]\le 2\mathrm{exp}\left(-2m{\left(\dfrac{\lfloor s/2\rfloor -\sigma s}{m}\right)}^{2}\right)\text{=}\epsilon \left(s\right), (14) 被选举的RSU满足诚实多数. 证毕.
引理2. 安全性. 如果片内共识节点选举函数选举出的RSU满足诚实多数且Reputation-based SMR协议满足安全性,那么基于声誉的片内共识协议也满足安全性.
证明. 假设基于声誉的片内共识协议不满足安全性,即这里存在某个出块周期,在这个周期中2个诚实RSU提出了2个不同的区块b与b′. 通过引理1,被选举出的RSU符合诚实多数的性质,且Reputation-based SMR协议满足安全性性质,对于任意2个被选中的诚实RSU,它们在同一个周期会对相同区块达成共识并提交相同的区块到本地的区块链上. 这与假设相反,因此基于声誉的片内共识协议满足安全性. 证毕.
引理3. 活性. 如果片内共识节点选举函数选举出的RSU满足诚实多数且Reputation-based SMR满足活性,则基于声誉的片内共识协议满足活性.
证明. 假设基于声誉的片内共识协议不满足安全性,即这里存在一个交易被诚实的RSU接受,但最终没有被所有诚实的RSU提交到本地的账本上. 通过引理1,被选举出的RSU符合诚实多数的性质,在此基础上通过轮询调度算法选举的领导者要么是诚实RSU,要么是恶意RSU(拜占庭节点). 如果领导者是诚实RSU,那么领导者会提议一个区块到所有节点,并且在片内广播后,所有诚实节点将在本地提交这一区块. 如果领导者是恶意RSU,那么该RSU要么遵循协议,要么背离协议. 当RSU遵循协议时,结果与诚实RSU担任领导者时相同. 反之,当RSU背离协议时,因为Reputation-based SMR协议满足活性与片内广播,最终所有的交易都将提交到每个分片中节点的账本上. 这与假设相反,因此基于声誉的片内共识协议满足活性. 证毕.
引理4. 声誉一致性. 如果基于声誉的片内共识协议满足安全性,则基于声誉的片内共识协议满足声誉一致性.
证明. 假设某一共识轮次结束时,分片内存在2个诚实的RSU1和RSU2对RSU3的声誉视图不同. 通过引理2,基于声誉的片内共识协议满足安全性,这表明在任意一个周期,任意2个诚实的RSU提交由诚实的领导者RSU提议的区块或空块. 如果提交空块,这表明领导者RSU是恶意的并且扣留区块或提议冲突区块,在当前共识轮次的计时器还剩1个\varDelta 时,这2种行为都会被委员会内至少1个诚实的RSU所检测. 委员会内所有诚实的RSU会将检测到的行为与区块广播给片内所有RSU,片内所有诚实的RSU会根据收到的行为更新在其视图上各个节点的声誉,从而使所有诚实的RSU拥有相同的声誉视图,这与假设相反. 如果提交的区块是正常区块,那么存在2种情况:1)协议的执行中不存在不当行为;2)协议执行的过程中存在不影响共识安全性的不当行为,即恶意区块提议与恶意投票行为. 对于情况1,所有诚实的RSU通过声誉函数一致地更新其本地声誉视图,这与假设相反. 对于情况2,它与诚实节点提交空块的情况相同,在片内广播后,所有诚实的RSU将获得相同的节点声誉视图,这与假设相反. 证毕.
4.2 监督人机制安全性分析
假定分片系统中存在 n 个监督人,分片系统在运行时,每当产生 t 个由不同分片生成的区块时,监督人需要对这些区块进行验证以确认其数据合法性. 每个监督人至少需要验证1个区块,同时,为了增加系统的安全性,验证区块的选择必须具备一定的不可预测性,以确保潜在的敌手无法轻易获悉下一个需要验证的区块.
监督人从 t 个块中选取的规则为:首先,每个监督人以不可预测的方式选取1个区块. 接着,对于剩下的 t - 1 个区块,监督人对每个区块的选择验证的概率均为 x .
本文引入了以下区块选择规则选择必选区块,以增强监督人区块选择的不可预测性.
区块序号=H(最新区块哈希值||唯一标识符) {\rm mod} \;t, (15) 其中区块序号是监督人从 t 个区块中选取的, H() 是一个安全的、单向的哈希函数,其将最新的区块哈希值和监督人标识符转换为一个确定的值. 其次, || 表示字符串连接操作符, {\text{mod }}t 表示对结果取模运算. 最后,这个规则的应用范围是分片系统中需要验证的区块.
通过引入这个区块选择规则,可以增加系统的安全性,因为敌手无法轻易预测每一个监督人需要验证的区块,这使得潜在的敌手难以进行恶意行为,从而保护了整个分片系统的安全性和稳定性.
根据以上规则,在必选验证环节,某个区块不被所有监督人随机以不可预测选中验证的概率为
Pr(C) = {\left( {\dfrac{{t - 1}}{t}} \right)^n} \text{,} (16) 对于剩下的 t - 1 个区块,某个区块不被某个监督人随机选择的概率可以用 1 - x 表示. 此外,各个区块不被所有监督人选择是相互独立的,符合二项分布,可表示为
Pr(D) = {(1 - x)^n} \text{,} (17) 最终,某个区块不被监督人所验证的概率为
Pr(\text{block is not selected}) = Pr(C)\times Pr(D) = {\left( \dfrac{t-1}{t} \right)}^{n} (1 - x)^n\text{,} (18) 式(18)反映了监督人机制的安全性. 假设t = 10,系统共有n = 80个监督人,x = 0.3,一个区块不被监督人验证的概率为 3.86 \times {10^{ - 12}} . 可以得知,分片系统中每个区块都以高概率被监督人所验证. 随着监督人数量的增加,某个特定区块不被选中的概率逐渐减小,从而增大了分片系统的安全性. 一方面涉及监督人必选验证环节的不可预测性,另一方面涉及监督人随机验证区块的不可预测性. 敌手难以预测哪个监督人将验证哪个区块,保证了分片系统的安全性.
5. 实验评估
5.1 分片方案性能评估
本节对所提出基于机器学习的分片算法进行实验评估. 本实验基于Python语言实现均衡聚类、K-Means++[38]、层次聚类[40]和随机分配等算法,并评估它们的簇间负载方差与聚类距离成本. 结果显示均衡聚类算法得到的分片结果在距离成本几乎没有增加的情况下,簇间负载方差显著低于其他算法. 此外,在RSU节点负载不均衡、呈现指数分布的情况下,均衡聚类算法仍然能够维持较低的簇间负载方差与聚类距离成本.
通过实验,评估以下2个问题:
1)RSU节点负载呈现均匀分布下,随着RSU节点负载的增加,均衡聚类算法和其他3个算法的聚类距离成本与簇间负载方差的变化趋势;
2)RSU节点负载呈现指数分布下,随着RSU节点负载的增加,均衡聚类算法和其他3个算法的聚类距离成本与簇间负载方差的变化趋势.
5.1.1 实验设置与实现
实验基于Python3.10实现,采用numpy1.62.2实现均衡聚类算法和随机分配算法,采用scikit-learn1.3.2实现K-Means++与层次聚类算法,采用matplotlib3.8.2与seaborn0.13.0实现数据可视化. 随机分配算法是目前绝大多数区块链分片方案所采用的算法;层次聚类算法相较K-Means++算法具有更强的可解释性,被广泛应用于无监督聚类. 对于地理位置呈现随机分布的RSU节点,K-Means++算法与层次聚类算法能够将相近的RSU节点划分至同一分片,相较随机分配算法更加适用于车联网区块链.
实验模拟了200个RSU并将其划分为15个分片,其中每个RSU拥有位置信息与负载状态2种属性. 实验从标准均匀分布中采样200个2维数据作为RSU的位置信息,分别从均匀分布与指数分布中采样200个1维数据作为RSU的负载状态,且分布的期望值线性增大,进而模拟RSU的负载状态在不同分布、不同大小下分片算法的性能.
实验中涉及的性能指标为簇间负载方差和聚类距离成本,以每个RSU与其分片中心的平均欧拉距离为单位. 簇间负载方差能够直观反映各个分片间负载的差异性,方差越大则代表算法负载均衡的能力越差. 而每个RSU与其分片中心的平均欧拉距离(以下简称簇均值)能够反映簇内紧凑性. 采用以上2种指标对片内节点距离相近和片间负载均衡2个要素进行评估.
5.1.2 均衡K-Means性能评估
图4展示了4种算法簇间负载方差随RSU节点平均负载的变化. 相对于其他3种算法,均衡K-Means簇间方差更低. 随着RSU负载逐步提升,其余3种算法的簇间负载方差均指数级增长;而均衡K-Means线性增长,表明该算法具有更强的负载均衡能力.
图5与图6分别展示了4种和3种算法聚类距离成本随RSU节点平均负载的变化. 随机分配算法的簇均值显著高于其他算法,表明同一分片的节点在地理位置上分布稀疏,车辆之间的数据共享协同效率更低. 除随机分配算法以外的3种聚类算法均将地理位置相近的节点划分至同一分片,均衡K-Means与另外2种算法在簇均值上相近,均保持在较低水平,表明该算法满足车联网区块链分片的2个要素.
图7展示了负载呈指数分布与均匀分布的差异. 相对于均匀分布,指数分布下的RSU负载不均衡程度显著增加. 图8展示了除随机分配以外的3种算法在该实验设置下的聚类簇间方差. 在RSU负载不平衡的情况下,最高方差超过600 000,表明K-Means++与层次聚类算法的片间负载存在极大的差异. 均衡K-Means方差最高未超过100 000,显著优于其他算法. 由于RSU负载不平衡,维持分片间节点均衡将会付出更多的距离成本. 图9展示了除随机分配以外的3种算法在该实验设置下的聚类距离成本. 相对其他算法,均衡K-Means的簇均值略有上升,仅提升0.2左右,表明其仍然保持较为紧凑的聚类结构.
图10对比了4种算法的聚类可视化结果. 相较随机分配算法,其他3种算法生成的聚类结构边界清晰,表明它们能够将相邻的节点划分至同一分片,满足片内节点相近的需求. 而K-Means++与层次聚类算法仅考虑片内节点相近,难以满足车联网区块链分片中负载均衡的要求. 相较K-Means++与层次聚类算法,均衡聚类算法簇间负载方差更低,更加适用于车联网区块链分片. 聚类结构同样反映了均衡聚类算法特点,即部分分片间节点出现“交叉”. 由于节点分配时需要同时考虑负载与距离2个因素,部分节点为了实现负载均衡,未加入距离最近的簇,导致“交叉”的出现,表明均衡聚类算法更加符合车联网区块链分片的需求.
5.2 片内共识性能评估
本节对所提出片内共识协议进行实验评估. 该实验通过Go语言实现基于声誉的片内共识协议,并在云实例上评估它们的吞吐量与共识时延. 结果显示在多个分片中基于声誉的片内共识协议的共识时延与Reputation-based SMR基本相同. 且随着分片中RSU数量的增加,基于声誉的片内共识协议的吞吐量下降幅度低于Reputation-based SMR协议与Sync-HotStuff协议[41]. 此外,随着分片数量的增长,基于声誉的片内共识协议相较于Reputation-based SMR吞吐量更优,且相较于Sync-HotStuff协议没有显著的吞吐量差距.
通过实验,评估以下3个问题:
1)在单个分片内,随着区块中包含的交易的增加,基于声誉的片内共识协议的性能变化趋势;
2)在单个分片内,随着RSU数量的增加,基于声誉的片内共识协议与Reputation-based SMR共识时延和吞吐量的变化趋势;
3)随着分片数量的增长,基于声誉的片内共识协议共识时延和吞吐量的变化趋势.
5.2.1 实验设置与实现
本节的实验利用libp2p完成点对点网络的搭建,采用protobuf进行信息的序列化与反序列化以便在网络中传递数据,采用secp256k1椭圆曲线算法来执行数字签名,采用SHA256作为哈希函数. 使用Go语言成功实现了Sync-HotStuff、Reputation-based SMR以及基于声誉的片内共识协议. 在协议的实现中,每个区块包含由OBUs发送的多个交易. 将每个区块包含的最多的交易数量称为该区块的大小,设置同步网络上限时延\varDelta =0.25 s,即基于声誉的片内共识协议和Reputation-based SMR的时延计时器的设定均为1 s. 而对于Sync-HotStuff,相较于以上2个协议缺少证据广播阶段和片内广播阶段,因此其时延计时器设定为0.75 s.
基于声誉的片内共识协议部署在阿里云实例上,参数如表1所示.
表 1 云服务器配置参数Table 1. Elastic Compute Service Configuration Parameters参数 配置环境 实例规格 ecs.c7a.8xlarge 处理器核心数 32 内存/GB 256 本地存储/GB 100 处理器主频/GHz 3.5 内网带宽/GBps 25 内网收发包/PPS 1200 万处理器型号 AMD EPYC™ Milan 7T83 镜像操作系统 Ubuntu18.04 64位 实验中涉及的性能指标主要为共识时延与吞吐量.
5.2.2 基于区块大小的协议性能评估
将车辆产生的每条数据近似看成区块中的1笔交易,在区块大小分别为400,800,
1600 笔交易的条件下,固定每笔交易大小为64 B,测试了基于声誉的片内共识协议的性能. 通过控制OBU节点发送命令的时间间隔来模拟不同的负载,OBU节点发送每个命令的速度越快,客户端在给定时间拥有的未完成命令池就越大. 如图11所示,最开始增加OBU发送请求的速率不会对延迟产生影响,因为节点的带宽还没有达到饱和状态. 随着节点负载的增加,吞吐量会增加,但延迟仍然保持稳定,直到系统的带宽达到饱和. 一旦带宽饱和,随着负载的增加,吞吐量将保持不变或稍微下降,而延迟则会上升. 由图11可知,基于声誉的片内共识协议的吞吐量在720 tps左右达到带宽饱和,将以800区块大小与64 B交易大小作为后续实验的固定参数.5.2.3 基于RSUs节点数量的协议性能评估
图12与图13展示了在单个分片中,随着RSU数量的增加,Reputation-based SMR协议、Sync-HotStuff协议与基于声誉的片内共识协议在共识时延与吞吐量2个性能指标上的对比. 设置RSU个数分别为5,9,17,33,从图12与图13中可以观察到,随着RSU数量的增加,基于声誉的片内共识协议的共识时延增长速率与吞吐量的下降速率明显低于Reputation-based SMR协议. 且当网络中RSU数为33时,基于声誉的片内共识协议的时延和吞吐量分别约为1 600 ms,490 tps,相较于Reputation-based SMR协议的时延和吞吐量分别为2 100 ms和280 tps左右,基于声誉的片内共识协议有着更优的性能. 而对于Sync-HotStuff,该协议不具有对RSU不当行为追责的能力,但有更低的共识时延与更高的吞吐量. 随着RSU数量的增加,Sync-HotStuff协议的性能明显下降,当RSU数量为33时,Sync-HotStuff协议的时延和吞吐量分别为1 590 ms,492 tps左右,这表明随着RSU数量的增加,基于声誉的片内共识协议与Sync-HotStuff协议在性能上的差距会逐步减小. 其原因是基于声誉的片内共识协议通过小规模RSU替代分片内所有RSU参与共识,从而带来了更低的通信损耗,这意味着基于声誉的片内共识协议的性能不会随着片内RSU的增多而明显下降.
5.2.4 基于分片数量的协议性能评估
为了尽可能体现基于声誉的片内共识协议能对高声誉节点进行选举,从而保证片内共识协议的正常运行,本节设计了如下实验. 固定每个分片中RSU节点数为11,测试分片数量分别为1,3,5,7的情景下2个协议的吞吐量. 当分片数量为3时,设定其中一个分片的恶意RSU为6个(为了简化实验的进行,通过代码沉睡这6个节点,使其不参与片内共识协议). 同时,因为恶意节点不参与共识过程,它们的声誉远小于其他节点,将这样的分片称为恶意分片. 同理,当分片数量为5时,恶意分片数量为2;当分片数量为7时,恶意分片数量为3.
图14展示了Sync-HotStuff,Reputation-based SMR和基于声誉的片内共识协议在不同分片数量下的吞吐量变化趋势. 随着分片数量的增加,系统吞吐量明显上升. Reputation-based SMR协议的吞吐量低于基于声誉的片内共识协议. 而对于Sync-HotStuff,因为其在单个分片内拥有更高的吞吐量,当分片数量为1且不存在恶意分片时,该协议有着最优的性能. 随着恶意分片数量的增多,基于声誉的片内共识协议与Sync-HotStuff协议在吞吐量上并未体现出明显的差距. 其原因是,在恶意分片中Sync-HotStuff与Reputation-based SMR无法通过足够的签名来完成共识. 而对于基于声誉的片内共识协议,它通过片内共识节点选举,使片内诚实RSU提供签名并完成共识.
6. 结 论
本文提出了一种基于机器学习分片的车联网区块链数据共享方案,每个分片负责存储和管理特定类型的车联网数据,使得设备间的数据共享可以并发执行,提高了数据共享的效率. 为了保证分片方案的安全性,本文提出了基于声誉的共识协议和监督人机制,通过片内共识节点选举函数尽可能地保证高声誉的诚实RSU参与并完成共识. 监督人机制使节点从共享数据中存储数据并获得验证其他分片数据的能力,进一步有助于提高系统的安全性. 性能评估和安全分析证明,本文方案可以实现安全高效的车联网数据共享.
作者贡献声明:陈骁、黄牧鸿负责方案整体设计并撰写论文;田一凡、王岩负责部分算法思路和实验方法;曹晟、张小松提出指导意见并修改论文.
https://homomorphicencryption.org/https://github.com/ microsoft/electionguard -
表 1 不完全同态加密方案
Table 1 Imperfect Homomorphic Encryption Scheme
同态加密方案 支持的加、乘运算次数 支持的多项式运算 RSA[3] 不限次乘法 任意多元单项式 文献[8] 不限次乘法 任意多元单项式 文献[9] 不限次乘法 任意多元单项式 文献[2] 不限次加法 任意多元一次多项式 GM82[10] {\mathbb{Z}_2}上的不限次加法 任意多元一次多项式 文献[11] 不限次加法 任意多元一次多项式 文献[12] 不限次加法 任意多元一次多项式 文献[13] 不限次加法 任意多元一次多项式 文献[14] 不限次加法 任意多元一次多项式 GK05[15] 不限次加法 任意多元一次多项式 AKK07[16] 不限次加法 任意多元一次多项式 CGP08[17] 不限次加法 任意多元一次多项式 CB08[18] 不限次加法 任意多元一次多项式 AS08[19] 不限次加法 任意多元一次多项式 SYY99[20] 有限次加法和乘法 有限项多项式 IP07[21] 有限次加法和乘法 有限项多项式 BGN05[22] 不限次加法,至多1次乘法 任意多元二次多项式 MGH08[23] 不限次加法,有限次乘法 任意多元d次多项式 表 2 主流FHE方案对比分析
Table 2 Comparative Analysis of Main FHE Schemes
阶段 FHE方案 安全性 依赖困难问题 自举性能 单次自举耗时/s 均摊耗时/(ms/bit) 第1代 Gentry09[1] 不可证明 CVP问题和SSSP问题 1800 / 第2代 BGV12[6,119] CPA R-LWE问题 11 0.9 GIK23[53] CPA R-LWE问题 70 1.1 第3代 FHEW14[62] CPA R-LWE问题 <1 / TFHE16[67] CPA R-LWE问题 <0.1 / XZD23[72] CPA R-LWE问题 0.112 / YDA23[71] CPA R-LWE问题 0.08 / 第4代 CCS19 [77,120] CPA R-LWE问题 78.7 0.95 HK20[121] CPA R-LWE问题 52.8 0.46 JKA21 [122] CPA R-LWE问题 135.4 0.11(1-CPU) 0.527 423×10−6(1-GPU) 注:/表示不支持SIMD. 表 3 主流FHE算法库及其支持的FHE方案
Table 3 Main FHE Algorithm Libraries and Their Supported Schemes of FHE
表 4 各FHE算法库其他信息对照表
Table 4 Comparison Table of Other Information of Each FHE Algorithm Library
算法库 开发语言 OS环境 发布年份 开发者/组织 TFHE C++,C Linux,
MacOS2016 Nicolas,Gama FHEW C++ Linux,
MacOS,
Windows2017 Leo,Ducas等 HElib C++ Ubuntu,
MacOS2018 IBM SEAL C++ Linux,
MacOS,
Windows,
FreeBSD,
Android2018 微软 cuFHE Cuda,
C++,
pythonUbuntu,
MacOS,
Windows2018 Gizemscetin等 HEAAN C++ Ubuntu 2018 三星 Lattigo Go Linux,
FreeBSD,
MacOS,
Windows2019 EPFL实验室 PALISADE C++ Ubuntu,
CentOS,
Windows2019 Duality Concrete Rust Linux,
MacOS,
WSL2020 Zama Pyfhel Python,
CythonLinux,
WSL2021 Ibarrondo等 OpenFHE C++ Linux,
MacOS,
Windows2022 Duality主导 HEhub C++ Linux,
MacOS2022 原语科技 -
[1] Gentry C. Fully homomorphic encryption using ideal lattices[C]//Proc of the 41st Annual ACM Symp on Theory of Computing. New York: ACM, 2009: 169–178
[2] Paillier P. Public-key cryptosystems based on composite degree residuosity classes[G]//LNCS 1592: Advances in Cryptology (EUROCRYPT’99). Berlin: Springer, 1999: 223–238
[3] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120−126 doi: 10.1145/359340.359342
[4] Regev O. On lattices, learning with errors, random linear codes, and cryptography[C]//Proc of the 37th ACM Symp on Theory of Computing. New York: ACM, 2005: 84–93
[5] Rothblum R. Homomorphic encryption: From private-key to public-key[G]//LNCS 6597: Proc of the 8th Conf on Theory of Cryptography. Berlin: Springer, 2011: 219–234
[6] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) Fully homomorphic encryption without bootstrapping[C]//Proc of the 3rd Innovations in Theoretical Computer Science Conf. New York: ACM, 2012: 309–325
[7] Brakerski Z. Fully homomorphic encryption without modulus switching from classical GapSVP[G]//LNCS 7417: Advances in Cryptology (CRYPTO 2012). Berlin: Springer, 2012: 868–886
[8] Rabin M O. Digitalized signatures and public-key functions as intractable as factorization, MIT-LCS-TR-212[R]. Cambridge, MA: MIT, 1979
[9] Elgamal T. A public key cryptosystem and a signature scheme based on discrete logarithms[J]. IEEE Transactions on Information Theory, 1985, 31(4): 469−472 doi: 10.1109/TIT.1985.1057074
[10] Goldwasser S, Micali S. Probabilistic encryption and how to play mental poker keeping secret all partial information[C]//Proc of the 14th Annual ACM Symp on Theory of Computing. New York: ACM, 1982: 365–377
[11] Benaloh J. Verifiable secret-ballot elections[D]. New Haven, CT: Yale University, 1987
[12] Okamoto T, Uchiyama S. A new public-key cryptosystem as secure as factoring[G]//LNCS 1403: Advances in Cryptology (EUROCRYPT’98). Berlin: Springer, 1998: 308–318
[13] Naccache D, Stern J. A new public key cryptosystem based on higher residues[C]//Proc of the 5th ACM Conf on Computer and Communications Security. New York: ACM, 1998: 56−66
[14] Damgård I, Jurik M. A length-flexible threshold cryptosystem with applications[C]//Proc of the 8th Australasian Conf on Information Security and Privacy. Berlin: Springer, 2003: 350–364
[15] Goldwasser S, Kharchenko D. Proof of plaintext knowledge for the Ajtai-Dwork cryptosystem[C]//Proc of the 2nd Int Conf on Theory of Cryptography. Berlin: Springer, 2005: 529–555
[16] Kawachi A, Tanaka K, Xagawa K. Multi-bit cryptosystems based on lattice problems[C]//Proc of the 10th Int Conf on Practice and Theory in public-Key Cryptography. Berlin: Springer, 2007: 315–329
[17] Melchor C A, Castagnos G, Gaborit P. Lattice-based homomorphic encryption of vector spaces[C]//Proc of the 2008 IEEE Int Symp on Information Theory. Piscataway, NJ: IEEE, 2008: 1858–1862
[18] Peikert C, Waters B. Lossy trapdoor functions and their applications[J]. SIAM Journal on Computing, 2007, 40(6): 1803−1844
[19] Armknecht F, Sadeghi A R. A new approach for algebraically homomorphic encryption[EB/OL]. 2008[2022-07-21].https://eprint.iacr.org/2008/422
[20] Sander T, Young A, Yung M, et al. Non-interactive crypto computing for NC1[C]//Proc of the 40th Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 2001: 554−566
[21] Ishai Y, Paskin A. Evaluating branching programs on encrypted data[C]//Proc of the 4th Theory of Cryptography Conf. Berlin: Springer, 2007: 575–594
[22] Boneh D. Evaluating 2-DNF formulas on ciphertexts[G]//LNSC 3378: Proc of the 2nd Theory of Cryptography Conf. Berlin: Springer, 2005: 325–341
[23] Melchor C A, Gaborit P, Herranz J. Additively homomorphic encryption with t-operand multiplications[G]//LNSC 6223: Advances in Cryptology (CRYPTO 2010). Berlin: Springer, 2010: 138–154
[24] Fellows M, Koblitz N. Combinatorial cryptosystems galore[J]. Contemporary Mathematics, 1994, 168: 51−61
[25] Grigoriev D, Ponomarenko I. Homomorphic public-key cryptosystems and encrypting Boolean circuits[J]. Applicable Algebra in Engineering, Communication and Computing, 2006, 17(3): 239−255
[26] Steinwandt R, Geiselmann W. Cryptanalysis of polly cracker[J]. IEEE Transactions on Information Theory, 2002, 48(11): 2990−2991 doi: 10.1109/TIT.2002.804112
[27] Choi S J, Blackburn S R, Wild P R. Cryptanalysis of a homomorphic public-key cryptosystem[J]. Journal of Mathematical Cryptology, 2007, 1(4): 351−358
[28] Ferrer J. A new privacy homomorphism and applications[J]. Information Processing Letters, 1996, 60(5): 277−282 doi: 10.1016/S0020-0190(96)00170-6
[29] Domingoferrer J. A provably secure additive and multiplicative privacy homomorphism[G]//LNCS 2433: Proc of the 6th Int Conf on Information Security. Berlin: Springer, 2002: 471−483
[30] Wagner D. Cryptanalysis of an algebraic privacy homomorphism[G]//LNCS 2851: Proc of the 6th Int Conf on Information Security. Berlin: Springer, 2003: 234–239
[31] Cheon J H, Kim W H, Nam H S. Known-plaintext cryptanalysis of the Domingo-Ferrer algebraic privacy homomorphism scheme[J]. Information Processing Letters, 2006, 97(3): 118−123 doi: 10.1016/j.ipl.2005.09.016
[32] Gentry C. Toward basing fully homomorphic encryption on worst-case hardness[G]//LNCS 6223: Advances in Cryptology (CRYPTO 2010). Berlin: Springer, 2010: 116–137
[33] Stehlé D, Steinfeld R. Faster fully homomorphic encryption[G]//LNCS 6477: Advances in Cryptology (ASIACRYPT 2010). Berlin: Springer, 2010: 377–394
[34] Ogura N, Yamamoto G, Kobayashi T, et al. An improvement of key generation algorithm for Gentry’s homomorphic encryption scheme[G]//LNCS 6434: Proc of the 5th Int Workshop on Security. Berlin: Springer, 2010: 70−83
[35] Scholl P, Smart N P. Improved key generation for Gentry’s fully homomorphic encryption scheme[G]//LNCS 7089: Proc of the 13th IMA Int Conf on Cryptography and Coding. Berlin: Springer, 2011: 10−22
[36] Gentry C, Halevi S. Implementing Gentry’s fully-homomorphic encryption scheme[G]//LNCS 6632: Advances in Cryptology (EUROCRYPTO 2011), Berlin: Springer, 2011: 129–148
[37] Gentry C, Halevi S. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits[C]//Proc of the 52nd IEEE Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 2011: 107−109
[38] Gentry C, Halevi S, Smart N P. Better bootstrapping in fully homomorphic encryption[G/OL]//LNCS 7293: Proc of the 15th Int Conf on Practice and Theory in Public Key Cryptography. Berlin: Springer, 2012[2022-09-02].https://doi.org/10.1007/978-3-642-30057-8_1
[39] Smart N P, Vercauteren F. Fully homomorphic encryption with relatively small key and ciphertext sizes[G]//LNCS 6056: Proc of the 13th Int Conf on Practice and Theory in Public Key Cryptography. Berlin: Springer, 2010: 420−443
[40] Smart N P, Vercauteren F. Fully homomorphic SIMD operations[EB/OL]. 2011[2022-08-01].https://eprint.iacr.org/2011/133
[41] Mikuš M. Experiments with the plaintext space in Gentry’s somewhat homomorphic scheme[J]. Tatra Mountains Mathematical Publications, 2012, 53(1): 147−154 doi: 10.2478/v10127-012-0044-6
[42] Brakerski Z, Vaikuntanathan V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[G]//LNCS 6841: Advances in Cryptology(CRYPTO 2011). Berlin: Springer, 2011: 505–524
[43] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings[G/OL]//LNCS 6110: Advances in Cryptology (EUROCRYPT 2010). Berlin: Springer, 2010[2022-09-02].https://doi.org/10.1007/978-3-642-13190-5_1
[44] Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE[C]//Proc of the 52nd IEEE Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 2011: 97−106
[45] Brakerski Z, Langlois A, Peikert C, et al. Classical hardness of learning with errors[C]//Proc of the 45th ACM Symp on Theory of Computing. New York: ACM, 2013: 575−584
[46] 李增鹏,马春光,周红生. 全同态加密研究[J]. 密码学报,2017,4(6):561−578 Li Zengpeng, Ma Chunguang, Zhou Hongsheng. Overview on fully homomorphic encryption[J]. Journal of Cryptologic Research, 2017, 4(6): 561−578 (in Chinese)
[47] Fan J, Vercauteren F. Somewhat practical fully homomorphic encryption[EB/OL]. 2012[2022-08-01].https://eprint.iacr.org/2012/144
[48] Wu Ting, Wang Hui, Liu Youping. et al. Optimizations of Brakerski’s fully homomorphic encryption scheme[C]//Proc of the 2nd Int Conf on Computer Science and Network Technology. Piscataway, NJ: IEEE, 2012: 2000−2005
[49] Zhang Xiaojin, Xu Chunxiang, Jin Chunhua, et al. Efficient fully homomorphic encryption from RLWE with an extension to a threshold encryption scheme[J]. Future Generation Computer Systems, 2014, 36: 180−186 doi: 10.1016/j.future.2013.10.024
[50] Li Zengpeng, Ma Chunguang, Gang D U, et al. Dual LWE-based fully homomorphic encryption with errorless key switching[C]//Proc of the 22nd IEEE Int Conf on Parallel and Distributed Systems. Piscataway, NJ: IEEE, 2016: 1169−1174
[51] Bajard J C, Eynard J, Hasan M A, et al. A full RNS variant of FV like somewhat homomorphic encryption schemes[G]//LNCS 10532: Proc of the 23rd Int Conf on Selected Areas in Cryptography. Berlin: Springer, 2016: 423−446
[52] 赵秀凤,付雨,宋巍涛. 循环安全的同态加密方案[J]. 计算机研究与发展,2020,57(10):2117−2124 doi: 10.7544/issn1000-1239.2020.20200422 Zhao Xiufeng, Fu Yu, Song Weitao. Circular secure homomorphic encryption scheme[J]. Journal of Computer Research and Development, 2020, 57(10): 2117−2124 (in Chinese) doi: 10.7544/issn1000-1239.2020.20200422
[53] Geelen R, Iliashenko I, Kang J, et al. On polynomial functions modulo PE and faster bootstrapping for homomorphic encryption[G]//LNCS 14006: Advances in Cryptology (EUROCRYPT 2023). Berlin: Springer, 2023: 257−286
[54] Brakerski Z, Gentry C, Halevi S. Packed ciphertexts in LWE-based homomorphic encryption[G/OL]//LNCS 7778: Proc of the 16th Int Conf on Practice and Theory in Public-key Cryptography. Berlin: Springer, 2012[2022-09-02].https://doi.org/10.1007/978-3-642-36362-7_1
[55] Peikert C, Vaikuntanathan V, Waters B. A framework for efficient and composable oblivious transfer[G]//LNCS 5157: Advances in Cryptology (CRYPTO 2008). Berlin: Springer, 2008: 554–571
[56] 钟焰涛,蒋琳,方俊彬,等. 同态密码学原理及算法[M]. 北京:机械工业出版社,2022 Zhong Yantao, Jiang Lin, Fang Junbin, et al. The Principle and Algorithm of homomorphic Cryptography[M]. Beijing: China Machine Press, 2022 (in Chinese)
[57] Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[G]//LNCS 8042: Advances in Cryptology (CRYPTO 2013). Berlin: Springer, 2013: 75−92
[58] Brakerski Z, Vaikuntanathan V. Lattice-based FHE as secure as PKE[G/OL]//Proc of the 5th Conf on Innovations in Theoretical Computer Science. New York: ACM, 2014[2022-09-02].https://doi.org/10.1145/2554797.2554799
[59] Barrington D A. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1[J]. Journal of Computer and System Sciences, 1989, 38(1): 150−164 doi: 10.1016/0022-0000(89)90037-8
[60] Alperin-Sheriff J, Peikert C. Faster bootstrapping with polynomial error[G]//LNCS 8616: Advances in Cryptology (CRYPTO 2014). Berlin: Springer, 2014: 297−314
[61] Micciancio D, Peikert C. Trapdoors for lattices: Simpler, tighter, faster, smaller[G]//LNCS 7237: Advances in Cryptology (EUROCRYPT 2012). Berlin: Springer, 2012: 700−718
[62] Garg S, Gupta D. Efficient round optimal blind signatures[G]//LNCS 8441: Advances in Cryptology (EUROCRYPT 2014). Berlin: Springer, 2014: 477–495
[63] Ducas L, Micciancio D. FHEW: Bootstrapping homomorphic encryption in less than a second[G]//LNCS 9056: Advances in Cryptology (EUROCRYPT 2015). Berlin: Springer, 2015: 617−640
[64] Gama N, Izabachène M, Nguyen P Q, et al. Structural lattice reduction: Generalized worst-case to average-case reductions and homomorphic cryptosystems[G]//LNCS 9666: Advances in Cryptology (EUROCRYPT 2016). Berlin: Springer, 2016: 528−558
[65] Chillotti I, Gama N, Georgieva M, et al. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[G]//LNCS 10031: Advances in Cryptology (ASIACRYPT 2016). Berlin: Springer, 2016: 3−33
[66] Chillotti I, Gama N, Georgieva M, et al. Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[G]//LNCS 10624: Advances in Cryptology (ASIACRYPT 2017). Berlin: Springer, 2017: 377−408
[67] Chillotti I, Gama N, Georgieva M, et al. TFHE: Fast fully homomorphic encryption over the torus[J]. Journal of Cryptology, 2020, 33(1): 34−91 doi: 10.1007/s00145-019-09319-x
[68] Micciancio D, Polyakov Y. Bootstrapping in FHEW-like cryptosystems[C]//Proc of the 9th Workshop on Encrypted Computing & Applied homomorphic Cryptography, New York: ACM, 2021: 17−28
[69] Kim A, Deryabin M, Eom J, et al. General bootstrapping approach for RLWE-based homomorphic encryption[EB/OL]. 2021[2023-07-21].https://eprint.iacr.org/2021/691
[70] Bonte C, Iliashenko I, Park J, et al. FINAL: Faster FHE instantiated with NTRU and LWE[G]//LNCS 13792: Advances in Cryptology (ASIACRYPT 2022). Berlin: Springer, 2022: 188−215
[71] Joye M, Paillier P. Blind rotation in fully homomorphic encryption with extended keys[C/OL]//Proc of the 2022 Int Symp on Cyber Security, Cryptology, and Machine Learning. Berlin: Springer, 2022[2023-07-02].https://doi.org/10.1007/978-3-031-07689-3_1
[72] Xiang Binwu, Zhang Jiang, Deng Yi, et al. Fast blind rotation for bootstrapping FHEs[EB/OL]. 2023[2023-07-21].https://iacr.org/cryptodb//data/paper.php?pubkey=33119
[73] Lee Y, Micciancio D, Kim A, et al. Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption[G]//LNCS 14006: Advances in Cryptology (EUROCRYPT 2023). Berlin: Springer, 2023: 227−256
[74] Cheon J H, Kim A, Kim M, et al. Homomorphic encryption for arithmetic of approximate numbers[G]//LNCS 10624: Advances in Cryptology (ASIACRYPT 2017). Berlin: Springer, 2017: 409−437
[75] Cheon J H, Hao K, Kim A, et al. Bootstrapping for approximate homomorphic encryption[G]//LNCS 10820: Advances in Cryptology (EUROCRYPT 2018). Berlin: Springer, 2018: 360–384
[76] Cheon J H, Han K, Kim A, et al. A full RNS variant of approximate homomorphic encryption[G]//LNCS 11349: Proc of the 25th Int Conf Selected on areas in cryptography. Berlin: Springer, 2018: 347–368
[77] Chen Hao, Chillotti I, Song Yongzhu. Improved bootstrapping for approximate homomorphic encryption[G]//LNCS 11477: Advances in Cryptology (EUROCRYPT 2019). Berlin: Springer, 2019: 34−54
[78] Han K, Ki D. Better bootstrapping for approximate homomorphic encryption[G]//LNCS 12006: Topics in Cryptology (CT-RSA 2020). Berlin: Springer, 2020: 364–390
[79] Kim A, Papadimitriou A, Polyakov Y. Approximate homomorphic encryption with reduced approximation error[EB/OL]. 2020[2022-08-17].https://eprint.iacr.org/2020/1118
[80] Lee J W, Lee E, Lee Y, et al. High-precision bootstrapping of RNS-CKKS homomorphic encryption using optimal minimax polynomial approximation and inverse sine function[C]//LNCS 12696: Advances in Cryptology (EUROCRYPT 2021). Berlin: Springer, 2021: 618–647
[81] Bossuat J P, Mouchet C, Troncoso-Pastoriza J R, et al. Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys[G]//LNCS 12696: Advances in Cryptology (EUROCRYPT 2021). Berlin: Springer, 2021: 618–647
[82] Li Baiyu, Micciancio D. On the security of homomorphic encryption on approximate numbers[G]//LNCS 13696: Advances in Cryptology (EUROCRYPT 2021). Berlin: Springer, 2021: 648−677
[83] Cho J, Ha J, Kim S, et al. Transciphering framework for approximate homomorphic encryption[G]//LNCS 13092: Advances in Cryptology (ASIACRYPT 2021). Berlin: Springer, 2021: 640–669
[84] Ha J, Kim S, Lee B, et al. Rubato: Noisy ciphers for approximate homomorphic encryption[G]//LNCS 13275: Advances in Cryptology (EUROCRYPT 2022). Berlin: Springer, 2022: 581–610
[85] Jutla C S, Manohar N. Sine series approximation of the mod function for bootstrapping of approximate HE[G]//LNCS 13275: Advances in Cryptology (EUROCRYPT 2022). Berlin: Springer, 2022: 491–520
[86] Lee Y, Lee J W, Kim Y S, et al. High-precision bootstrapping for approximate homomorphic encryption by error variance minimization[G]//LNCS 13275: Advances in Cryptology (EUROCRYPT 2022). Berlin: Springer, 2022: 551–580
[87] Li Baiyu, Micciancio D, Schultz M, et al. Securing approximate homomorphic encryption using differential privacy[G]//LNCS 13507: Advances in Cryptology (CRYPTO 2022). Berlin: Springer, 2022: 560−589
[88] Dijk M V, Gentry C, Halevi S, et al. Fully homomorphic encryption over the integers[G]//LNCS 6110: Advances in Cryptology (EUROCRYPT 2010). Berlin: Springer, 2010: 24–43
[89] Coron J S, Mandal A, Naccache D, et al. Fully homomorphic encryption over the integers with shorter public keys[G]//LNCS 6841: Advances in Cryptology (CRYPTO 2011). Berlin: Springer, 2011: 487–504
[90] Coron J S, Naccache D, Tibouchi M. Public key compression and modulus switching for fully homomorphic encryption over the integers[G]//LNCS 7237: Advances in Cryptology (EUROCRYPT 2012). Berlin: Springer, 2012: 446–464
[91] Coron. Coron/fhe[EB/OL].(2012-04-10)[2022-04-10]. https//github.com/Coron/fhe
[92] Yang Haomiao, Xia Qi, Wang Xiaofen, et al. A new somewhat homomorphic encryption scheme over integers[C]//Proc of the 2012 Int Conf on Computer Distributed Control and Intelligent Environmental Monitoring. Piscataway, NJ: IEEE, 2012: 61−64
[93] Cheon J H, Coron J S, Kim J. Batch fully homomorphic encryption over the integers[G]//LNCS 7881: Advances in Cryptology (EUROCRYPT 2013). Berlin: Springer, 2013: 315–335
[94] Coron J S, Lepoint T, Tibouchi M. Scale-invariant fully homomorphic encryption over the integers[G]//LNCS 8383: Proc of the 17th Int Conf on Practice and Theory in Public-key Cryptography. Berlin: Springer, 2014: 311–328
[95] Cheon J H, Stehlé D. Fully homomorphic encryption over the integers revisited[G]//LNCS 9056: Advances in Cryptology (EUROCRYPT 2015). Berlin: Springer, 2015: 513–536
[96] Nuida K, Kurosawa K. (Batch) Fully homomorphic encryption over integers for non-binary message spaces[G]//LNCS 9056: Advances in Cryptology (EUROCRYPT 2015). Berlin: Springer, 2015: 537–555
[97] 熊婉君,韦永壮,王会勇. 一个基于整数的全同态加密改进方案[J]. 密码学报,2016,3(1):67−78 Xiong Wanjun, Wei Yongzhuang, Wang Huiyong. An improved fully homomorphic encryption scheme over the integers[J]. Journal of Cryptologic Research, 2016, 3(1): 67−78 (in Chinese)
[98] 王彩芬,成玉丹,刘超,等. 基于整数的多对一全同态加密方案[J]. 电子与信息学报,2018,40(9):2119−2126 Wang Caifen, Cheng Yudan, Liu Chao, et al. Multiple to one fully homomorphic encryption scheme over the integers[J]. Journal of Electronics & Information Technology, 2018, 40(9): 2119−2126 (in Chinese)
[99] Cheon J H, Han K, Kim D. Faster bootstrapping of FHE over the integers[G]//LNCS 11975: Proc of the 22nd Int Conf Information Security and Cryptology. Berlin: Springer, 2019: 242–259
[100] Pisa P S, Abdalla M, Duarte O. Somewhat homomorphic encryption scheme for arithmetic operations on large integers[C/OL]//Proc of the 2012 Global Information Infrastructure and Networking Symp. Piscataway, NJ: IEEE, 2012[2022-09-02].https://doi.org/10.1109/GIIS.2012.6466769
[101] Aggarwal N, Gupta C P, Sharma I. Fully homomorphic symmetric scheme without bootstrapping[C]//Proc of the Int Conf on Cloud Computing and Internet of Things. Piscataway, NJ: IEEE, 2014: 14−17
[102] Nuida K, Kurosawa K. (Batch) Fully homomorphic encryption over integers for non-binary message space[G]//LNCS 9056: Advances in Cryptology (EUROCRYPT 2015). Berlin: Springer, 2015: 537–555
[103] Cheon J H, Kim J, Lee M S, et al. CRT-based fully homomorphic encryption over the integers[J]. Information Sciences, 2015, 310(C): 149−162
[104] Benarroch D, Brakerski Z, Lepoint T. FHE over the integers: Decomposed and batched in the post-quantum regime[G]//LNCS 10175: Proc of the 20th IACR Int Conf on Practice and Theory in Public-key Cryptography. Berlin: Springer, 2017: 271–301
[105] López-Alt A, Tromer E, Vaikuntanathan V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C]//Proc of the 44th ACM Symp on Theory of Computing. New York: ACM, 2012: 1219–1234
[106] Stehlé1 D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices[G]//LNCS 6632: Advances in Cryptology (EUROCRYPT 2011). Berlin: Springer, 2011: 27–47
[107] Bos J W, Lauter K, Loftus J, et al. Improved security for a ring-based fully homomorphic encryption scheme[G]//LNCS 8308: Proc of the 14th IMA Int Conf on Cryptography and Coding. Berlin: Springer, 2013: 45–64
[108] Doröz Y, Hu Yin, Sunar B. Homomorphic AES evaluation using the modified LTV scheme[J]. Designs, Codes and Cryptography, 2016, 80(2): 333−358 doi: 10.1007/s10623-015-0095-1
[109] 李子臣,张卷美,杨亚涛,等. 基于NTRU的全同态加密方案[J]. 电子学报,2018,46(4):938−944 Li Zichen, Zhang Juanmei, Yang Yatao, et al. A fully homomorphic encryption scheme based on NTRU[J]. Acta Electronica Sinica, 2018, 46(4): 938−944 (in Chinese)
[110] Dahab R, Galbraith S, Morais E. Adaptive key recovery attacks on NTRU-based somewhat homomorphic encryption schemes[G]//LNCS 9063: Proc of the 8th Int Conf on Information Theoretic Security. Berlin: Springer, 2015: 283–296
[111] Chenal M, Tang Qiang. Key recovery attacks against NTRU-based somewhat homomorphic encryption schemes[C]//LNCS 9290: Proc of the 18th Int Conf on Information Security. Berlin: Springer, 2015: 397–418
[112] Albrecht M, Bai Shi, Ducas L. A subfield lattice attack on overstretched NTRU assumptions: Cryptanalysis of some FHE and graded encoding schemes[G]//LNCS 9814: Advances in Cryptology (CRYPTO 2016). Berlin: Springer, 2016: 153−178
[113] Kirchner P, Fouque P A. Revisiting lattice attacks on overstretched NTRU parameters[G]//LNCS 10210: Advances in Cryptology (EUROCRYPT 2017). Berlin: Springer, 2017: 3−26
[114] Genise N, Gentry C, Halevi S, Homomorphic encryption for finite automata[G]//LNCS 11922: Advances in Cryptology (ASIACRYPT 2019). Berlin: Springer, 2019: 473–502
[115] Lee C, Wallet A. Lattice analysis on MiNTRU problem[EB/OL]. 2020[2022-09-02].https://eprint.iacr.org/2020/230
[116] 车小亮,周潭平,李宁波,等. NTRU型多密钥全同态加密方案的优化[J]. 工程科学与技术,2020,52(5):186−193 Che Xiaoliang, Zhou Tanping, Li Ningbo, et al. Optimization of NTRU-type multi-key fully homomorphic encryption scheme[J]. Advanced Engineering Sciences, 2020, 52(5): 186−193 (in Chinese)
[117] Ducas L, Woerden W V. NTRU Fatigue: How stretched is overstretched?[G]//LNCS 13093: Advances in Cryptology (ASIACRYPT 2021). Berlin: Springer, 2021: 3−32
[118] Bonte C, Iliashenko I, Park J, et al. Revisiting lattice attacks on overstretched NTRU parameters[EB/OL]. 2022[2022-11-02].https://eprint.iacr.org/2022/074
[119] Halevi S, Shoup V. Bootstrapping for HElib[J]. Journal of Cryptology, 2021, 34(1): 1−44 doi: 10.1007/s00145-020-09366-9
[120] Kang H, Lee J, Lee Y, et al. Bootstrapping on SEAL[EB/OL]. 2020[2023-07-21].https://eprint.iacr.org/2020/1594
[121] Han K, Ki D. Better bootstrapping for approximate homomorphic encryption[C]//LNCS 12006: Topics in Cryptology (CT-RSA 2020). Berlin: Springer, 2020: 364–390
[122] Jung W, Kim W, Ahn J H, et al. Over 100x faster bootstrapping in fully homomorphic encryption through memory-centric optimization with GPUs[EB/OL]. 2021[2023-07-20].https://eprint.iacr.org/2021/508
[123] Gama N. TFHE v1.0. 1[EB/OL]. (2017-08-16)[2022-12-16]. https://github.com/tfhe/tfhe
[124] Ducas L. FHEW v 2.0-alpha[EB/OL]. (2017-05-30)[2022-11-06]. https://github.com/lducas/FHEW
[125] Bergamaschi F. HElib v2.2. 2[EB/OL]. (2022-12-06)[2022-12-16]. https://github.com/homenc/HElib
[126] Wei Dai. SEAL v4[EB/OL]. (2022-03-18)[2022-11-06]. https://github.com/microsoft/SEAL
[127] Wei Dai. cuFHE v1.0_beta[EB/OL]. (2018-03-14)[2022-11-06]. https://github.com/vernamlab/cuFHE
[128] Kim A. HEAAN V2.1[EB/OL]. (2018-09-05)[2022-11-06]. https://github.com/snucrypto/HEAAN
[129] Bossuat J P. Lattigo v4.1. 0[EB/OL]. (2022-12-01)[2022-12-16].https://github.com/tuneinsight/lattigo
[130] Polyakov Y. PALISADE v1.11. 9[EB/OL]. (2022-12-02)[2022-12-16]. https://gitlab.com/palisade/palisade-release
[131] Tmontaigu. Concrete v0.2. 0[EB/OL]. (2022-10-19)[2022-12-16]. https://github. com/zama-ai/concrete
[132] Ibarrond. Pyfhel v3.3. 2[EB/OL]. (2022-12-08)[2022-12-16]. https://github.com/ibarrond/Pyfhel
[133] Yspolyakov. OPenFFHE v1.0. 1[EB/OL]. (2022-12-01)[2022-12-06]. https://github. com/openfheorg/openfhe-development
[134] Ppppbamzy. HEhub v0.1. 0-alpha[EB/OL]. (2022-10-24)[2022-11-06]. https://github.com/primihub/HEhub
[135] Albrech M, Chase M, Chen Hao, et al. Homomorphic encryption Standard[S/OL]. (2018-11-21)[2022-10-06]. http://homomorphicencryption.org/wp-content/uplo-ads/2018/11/HomomorphicEncryptionStandardv1.1.pdf
-
期刊类型引用(5)
1. 宋朋,赵伯鸾. 农业机械车路协同辅助驾驶路线规划系统的设计与实现. 农机化研究. 2025(06): 232-238 . 百度学术
2. 尹璐,周俊龙,孙晋,吴泽彬. 不确定性感知的边缘计算任务调度算法. 控制与决策. 2024(07): 2405-2413 . 百度学术
3. 侯祥鹏,兰兰,陶长乐,寇小勇,丛佩金,邓庆绪,周俊龙. 边缘智能与协同计算:前沿与进展. 控制与决策. 2024(07): 2385-2404 . 百度学术
4. 李超,李文斌,高阳. 图多智能体任务建模视角下的协作子任务行为发现. 计算机研究与发展. 2024(08): 1904-1916 . 本站查看
5. 夏思洋,朱学芳. 5G环境下基于边缘计算的图书馆智慧服务响应能力研究. 情报理论与实践. 2023(12): 21-27+51 . 百度学术
其他类型引用(0)