引用本文

赵中原, 高旺, 蒋璐瑶, 葛泉波. 基于椭圆曲线ELGamal的隐私保护分布式优化算法. 自动化学报, 2025, 51(1): 210−220 doi: 10.16383/j.aas.c240404

Zhao Zhong-Yuan, Gao Wang, Jiang Lu-Yao, Ge Quan-Bo. Privacy-preserving distributed optimization algorithm based on elliptic curve ELGamal. Acta Automatica Sinica, 2025, 51(1): 210−220 doi: 10.16383/j.aas.c240404

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c240404

关键词

分布式优化，隐私保护，同态加密，椭圆曲线 

摘要

研究一类考虑节点隐私保护的分布式优化问题, 目标为保护各智能体的隐私信息不被泄露, 并最小化所有智能体局部成本函数之和. 首先, 针对无向连通图, 提出一种基于椭圆曲线密码机制的分布式凸优化算法. 通过设计底层权重矩阵, 将基于椭圆曲线的ELGamal同态加密和数字签名与分布式次梯度算法相结合, 克服了椭圆曲线密码机制与分布式一致性策略无法结合的难点. 在无第三方或聚合器的场景下, 该算法实现了系统的隐私保护. 理论分析表明, 该算法能够渐近收敛至全局最优解, 并适用于时变通信拓扑的动态环境. 此外, 算法能有效保护智能体的状态和成本函数不受来自诚实但好奇攻击者、外部窃听者和篡改攻击者的威胁. 最后, 通过数值仿真验证了算法的有效性.

文章导读

近年来, 随着数据处理技术和信息通信技术不断发展, 分布式优化方法在能源管理[1−3]、机器学习[4−6]、智能交通[7−9]等众多新兴和热门领域得到广泛应用. 在这些应用场景中, 各智能节点拥有自身的局部成本函数和局部约束集, 通过局部计算和通信以协同方式最小化成本函数之和[10]. 相较于集中式方法, 分布式方法具有更高的鲁棒性和灵活性, 有效避免集中式算法中单点故障和带宽限制问题, 在实际应用中具有重要意义[11−12].

针对分布式优化问题, 分布式次梯度算法作为一种经典的解决方案, 用于处理大规模分布式系统优化任务. 算法通过各智能体迭代地与邻居节点进行信息交换以确保一致性, 沿其本地凸成本函数的局部次梯度方向执行下降步骤, 逐步收敛到全局最小值[13]. 此外, 其他解决方案例如分布式交替方向乘子法 (Alternating direction method of multipliers, ADMM), 通过设计拉格朗日函数并引入拉格朗日对偶变量, 将原始优化问题分解为更小的子问题并行求解, 在提高收敛速度和解决复杂约束优化问题方面表现出色[14−15]. 上述研究主要关注于算法的收敛性, 忽略了算法的隐私问题. 算法要求智能体遵守规则, 显式地将自身状态信息发送给邻居节点. 从隐私角度来看, 每个智能体通常并不愿意向邻居节点透露私有信息 (例如家庭用电量、医疗信息、工资等)[16−17]. 此外, 文献[18−20]揭示了分布式优化算法中的隐私泄露问题. 例如, 在分布式训练和机器学习中, 智能体可以通过模型参数或者梯度信息准确地恢复出邻居节点的本地训练数据[21]. 因此, 有必要考虑数据隐私问题设计新型分布式优化算法, 以实现最小化全局成本函数同时保护智能体的隐私.

针对分布式优化中隐私保护问题, 文献[16−18]提出基于差分隐私机制的隐私保护分布式优化算法, 在智能体局部成本函数或传输的信息中注入随机噪声, 以实现隐私保护. 然而, 差分隐私存在隐私性和准确度的折衷, 噪声的持续注入会损害结果的最优性[22]. 同时, 随着隐私级别的提高, 所注入噪声的方差会增大, 进而影响算法的收敛速度和结果的准确性[23]. 为了避免算法准确性损失, 文献[24−25]通过添加衰减噪声或者相关噪声来混淆交换信息, 以保证准确性. 但隐私保护的水平取决于噪声的大小, 且注入的噪声具有相关性[26].

数据加密是实现隐私保护的另一类方法. 基于密码学的隐私保护机制可以同时保证隐私性和准确性. 常用密码学方案包括安全多方计算、秘密共享和同态加密等[27−28]. 其中, 同态加密允许在密文执行计算操作, 即在密文上进行运算后解密的结果等同于对明文数据直接进行运算的结果. 这种特性使同态加密能够同时实现数据计算和隐私保护[29]. 文献[28]提出一种基于Shamir秘密共享的分布式优化算法, 能够有效防御诚实但好奇攻击者的攻击. 然而, 算法存在一些限制, 包括智能体的成本函数被限制为线性函数, 且系统通信拓扑必须为树型拓扑. 文献[30]引入CKKS全同态加密, 提出了一种基于原对偶次梯度算法的分布式解决方案用于解决具有隐私泄露风险的电力系统中的最优潮流问题. 尽管成本函数的限制得到了放宽, 但为了保护隐私, 该算法仍需依赖树型拓扑. 为提高适用性, 文献[23, 27]分别提出基于同态加密的原对偶次梯度算法和分布式投影梯度算法. 然而, 这些方案需要借助第三方系统操作者完成聚合操作. 文献[31−32]设计了一种基于Paillier同态加密的分布式算法. 然而, Paillier同态加密方案存在密文长度和系统参数较大的问题, 这导致了计算和通信开销的增加, 影响了实际应用的可行性[33]. 此外, 现有的算法通常仅采用单一或几种独立加密方法来保护隐私, 存在隐私保护不足和系统复杂性增加的问题.

基于上述分析, 设计安全且高效的完全去中心化的同态加密分布式优化算法仍然是一个亟待解决的问题. 针对多智能体系统中存在的隐私风险, 本文充分利用椭圆曲线密码学的优势, 使用基于椭圆曲线的ELGamal加密和椭圆曲线数字签名, 通过设计底层权重矩阵, 提出了一种完全去中心化的基于椭圆曲线密码机制的隐私保护分布式优化算法. 本文的主要贡献如下:

1) 提出一种基于椭圆曲线密码机制的隐私保护分布式优化算法. 该算法通过构造底层权重矩阵, 将权重分解为两个随机正数的乘积, 从而将椭圆曲线同态加密集成至分布式投影次梯度算法. 与文献[23, 27]提出的同态加密分布式优化算法相比, 本文的算法无需第三方或者聚合器, 实现了完全去中心化的优化过程.

2) 设计了一种双层加密保护架构. 将基于椭圆曲线密码机制的加密算法和数字签名嵌入分布式优化算法, 不仅能够抵御系统内部的诚实但好奇攻击者, 且能防御外部窃听者和篡改者的攻击, 增强了分布式系统的安全性.

3) 提高了算法计算效率. 本文提出的分布式优化算法安全性建立于椭圆曲线离散对数问题基础之上, 在保持相同的安全等级下, 具有更短的密钥长度及更小的系统参数. 与文献[27, 31−32]所提的隐私保护分布式优化算法相比, 所提算法在确保安全性的同时, 降低了计算需求和带宽消耗.

本文其余部分安排如下. 第1节给出预备知识并对所研究问题进行形式化描述; 第2节提出基于椭圆曲线ELGamal的隐私保护分布式优化算法; 第3节分析算法收敛性和安全性; 第4节利用数值仿真验证理论结果; 最后, 总结本文的主要结果并介绍未来的研究方向.

图 1  10个智能体的通信拓扑图

图 2  10个智能体的状态演化

图 3  节点2接收到的加密信息$ c_1$的演化

本文研究了在无向连通图下具有隐私泄露风险的多智能体系统分布式优化问题. 为了解决这一问题, 本文提出一种基于椭圆曲线密码机制的隐私保护分布式优化算法. 该算法通过将权重分解为两个随机正数, 将椭圆曲线的ELGamal同态加密和基于椭圆曲线的数字签名与分布式次梯度算法结合, 在算法收敛的同时, 有效防御了来自诚实但好奇攻击者、外部窃听者和篡改攻击者的威胁. 此外, 所提算法在存储空间、带宽和功耗受限的多智能体系统中具有可行性. 未来的研究方向集中在将基于椭圆曲线的分布式优化算法拓展到时变有向图场景, 并考虑多智能体系统存在拜占庭节点时算法收敛的问题.

作者简介

赵中原

南京信息工程大学自动化学院副教授. 主要研究方向为协同控制, 机器学习和分布式优化. E-mail: zhaozhongyuan@nuist.edu.cn

高旺

南京信息工程大学自动化学院硕士研究生. 主要研究方向为去中心化联邦学习, 隐私保护和分布式优化. E-mail: gaowang@nuist.edu.cn

蒋璐瑶

上海交通大学机械与动力工程学院博士研究生. 主要研究方向为数据隐私保护, 分布式优化和复杂人机系统. E-mail: luyaojiang@sjtu.edu.cn

葛泉波

南京信息工程大学自动化学院教授. 主要研究方向为信息融合, 非线性滤波, 无人系统和分布式优化. 本文通信作者. E-mail: quanboge@163.com