[论文解析] TEVC 2023 基于同态加密的增强多任务粒子群算法
| 标题 | Privacy-Enhanced Multitasking Particle Swarm Optimization based on Homomorphic Encryption |
|---|---|
| 作者 | Hao Li, Fanggao Wan, Maoguo Gong, A. K. Qin, Yue Wu, Lining Xing |
| 机构 | School of Electronic Engineering, Key Laboratory of Collaborative Intelligence Systems, Ministry of Education, Xidian University, Xi’an, China |
| 邮箱 | gong@ieee.org |
| 论文 | https://ieeexplore.ieee.org/document/10263995 |
摘要
进化多任务优化（EMTO）是近年来在进化计算领域提出的一种新的优化范式。EMTO可以同时解决几个不同的优化任务，并通过在任务之间传递有效的知识来促进上级的收敛特性。然而，现有的EMTO通常只注重促进收敛特性，而忽略了潜在的隐私泄漏问题，在不同的任务之间的知识转移。隐私泄露可能会导致相当大的经济损失或严重的声誉受损，这可能会阻碍EMTO在现实世界中的应用的发展。针对EMTO中的隐私泄露问题，提出一种隐私增强的多任务粒子群优化算法。结合多任务粒子群优化算法，设计了一种基于同态加密的具有隐私保护的知识传递策略。此外，在一个低维子空间中实现的任务间的知识转移机制，以减少隐私保护所造成的额外的计算负担。综合和NAS问题进行了全面的实验，以验证所提出的方法的有效性。实验结果表明，与现有的EMTO算法相比，该算法在隐私保护方面具有明显的优势。
概述
研究背景
根据目前的研究，实现多任务优化的方法可以大致分为两种。一种方法是使用单一种群，类似于最初提出的MFEA方法，而另一种方法则是维护多个子种群。在第一种方法中，所有任务都依赖于单一种群进行求解，这可能导致任务之间的优化信息相互泄露的问题。而在多种群的多任务优化中，每个任务都由独立的种群来解决。在进化过程中，每个种群可以经历两种类型的演化操作：自我进化和跨任务进化。尽管基于种群的隔离机制为每个任务提供了一定程度的隐私保护，但在跨任务演化过程中仍然存在一定程度的隐私信息泄露风险。然而，值得注意的是，迄今为止提出的EMTO方法没有充分考虑到这些问题。在需要强制实施与隐私保护相关的法规的情况下，这些方法可能受到限制甚至禁止。具体而言，随着深度神经网络模型在自动驾驶和人脸识别等领域的广泛应用，神经架构搜索(NAS)引起了越来越多的关注。由于优秀的网络结构通常共享一些共同的知识和面临相似的挑战，EMTO预计将成为NAS问题的有效解决方案。然而，一旦搜索到的架构泄露，相应部署的深度模型可能会受到对抗性攻击的威胁，如快速梯度符号方法、基于雅可比的显着图攻击等。这对于人脸识别和自动驾驶模型来说可能具有重大的经济和安全风险。总之，如何保护每个任务的隐私性是EMTO领域面临的一项重大挑战。
文章贡献
本文的主要目标是提出一种隐私保护增强的EMTO方法，以解决潜在的隐私泄露风险，并充分利用EMTO的优势。此外，由于密码操作通常具有较高的计算成本，因此引入隐私保护可能会对算法的计算效率产生影响。因此，本研究探讨了一种降低密码操作计算资源需求的策略，即在低维子空间中进行知识转移。
隐私增强的EMTO旨在实现知识转移，在达到促进优化的目的的同时保留每个任务的私人信息。传统的加密技术有效地保护了数据，但无法支持在加密数据上进行计算。全同态加密虽然使得能够在加密数据上进行计算成为可能，但却存在高计算成本的问题。差分隐私在计算上是有效的，但引入了噪声，从而降低了解决方案的精度。安全多方计算通常需要多轮通信，这增加了任务之间的通信负担。因此，本文采用一种计算效率高且具有加性同态性质的部分同态加密系统来实现具有隐私保护的EMTO。粒子群算法中的速度和位置更新公式计算简单，可以很好地支持部分同态加密技术。此外，粒子群算法易于实现且能够快速收敛，因此在解决实际问题时得到广泛应用。近年来，粒子群算法在EMTO中也越来越受到关注。
鉴于可行性、可扩展性和实际价值的综合考虑，本文结合同态加密和粒子群算法来实现隐私保护的EMTO。在本文中，提出了一种名为隐私增强的多任务粒子群优化（PEMTPSO）方法，以保护与EMTO相关的任务的隐私。首先，不同计算节点上的任务被分布在各自独立的进化群中。这一基于群体的隔离机制有效地防止了信息的无意泄露，提高了隐私安全性。为了应对EMTO中的隐私泄露问题，设计了一种基于同态加密的知识传递策略。然而，加密、解密和对密文的计算是耗时的。因此，子空间知识转移策略的目标是减少额外的计算负担，并同时保护隐私。而在实际案例研究中，本文首先分析了在NAS中实现隐私保护的重要性，然后在三组双任务NAS问题上验证了PEMTPSO的实用性。
本文提出了一种基于同态加密的隐私增强EMTO方法，并深入研究了其在现实世界中的应用问题。所提出的方法具有两个主要的创新点，与以前的EMTO方法相比。首先，该方法能够在多任务环境中保护任务信息的隐私，而大多数以前的方法忽略了任务间的隐私泄露风险。其次，该方法考虑到了隐私保护引入的计算负担，因此研究了子空间中的知识传递机制，以实现高效的EMTO方法并确保隐私保护。
我们的主要贡献包括以下方面：
首次解决了EMTO中的隐私泄露问题。具体来说，我们提出了一种基于同态加密的知识传递策略，并提供了浮点数和负数的加密方法。 为了减少隐私保护带来的额外计算负担，设计了低维子空间的构造和子空间中的知识转移策略。
同态加密和paillier加密
同态加密（Homomorphic encryption）是一种加密形式，它允许人们对密文进行特定形式的代数运算得到仍然是加密的结果，将其解密所得到的结果与对明文进行同样的运算结果一样。换言之，这项技术令人们可以在加密的数据中进行诸如检索、比较等操作，得出正确的结果，而在整个处理过程中无需对数据进行解密。其意义在于，真正从根本上解决将数据及其操作委托给第三方时的保密问题，例如对于各种云计算的应用。
加法同态加密是一种特殊类型的加密技术，它具有一个特殊的属性，即在加密状态下执行加法操作会产生与在明文状态下执行相同的结果。换句话说，如果你有两个加密的值，比如A和B，那么当你对它们进行加法操作时，得到的结果也会是它们的明文之和的加密。这个属性在一些隐私保护和安全应用中非常有用，因为它允许在不暴露明文数据的情况下进行一些计算。例如，假设有一个加法同态加密系统，允许两个参与者分别加密他们的工资，然后将这些加密值相加，而不需要在计算过程中暴露他们的实际工资数值。这可以用于实现隐私保护的工资计算。
paillier加密
paillier加密算法的流程图如图所示：
paillier加密算法可以主要分为三个步骤：生成密钥，加密过程以及解密过程。
首先，在密钥生成的过程中，要随机选择两个长度相近或相等的质数p和q； 计算 以及 ,其中lcm表示计算最小公倍数的过程； 随机选择一个整数，这个数字满足，（后面会发现g=n+1满足条件，因此一般可以直接取g=n+1），mod为取模运算，gcd为计算最大公约数的过程。其中 Z 表示整数，下标表示该整数集合里有多少个元素；。 生成的公钥为： 私钥为:
加密过程则简单地多：
对于任意明文消息,任意选择一个随机数,通过计算得到密文c：
对应地，解密过程如下：
对于密文，计算得到明文 m ：
paillier加密是一种加法同态加密算法，对于任意明文 和任意 ， 对应密文满足：
将这个密文相乘后的结果经过解密则能够得到：
隐私增强的多任务粒子群算法
这一部分将主要介绍文章中提出隐私增强的多任务粒子群算法。如下图所示，传统EMTO的成功归因于任务间的知识转移。这一类EMTO方法在设计知识迁移方案时，侧重于提高算法在各类问题上的收敛性能。然而，任务间的知识转移是一个信息共享的过程，可能会暴露每个参与者的隐私信息。因此，使用这些EMTO方法可能会给参与者带来巨大的损失，尤其是对于金融业，医疗健康产业以及一些设计公民身份信息的业务中，隐私安全是尤为重要的。
这篇文章基于上文中提到的加法同态加密算法设计了无隐私泄露的知识转移策略。此外，由于paillier加密算法的同态性质与PSO中的速度更新公式高度一致，本文还基于PSO设计了隐私增强的多任务优化方法。最后，引入子空间知识迁移策略，以减轻隐私保护相关的计算负担。
算法2中示出了PEMTPSO的框架。首先，在分布在不同计算节点的任务之间建立通信。然后，每个任务执行进化搜索，如第3行到第28行所示。不同任务间的知识转移强度受随机配对参数rmp的调节。当rmp的值接近0时，只允许同一任务中的粒子交换知识。这时解决方案总是倾向于陷入局部最优，而一个合适的rmp值可以平衡搜索空间的开发和探索，以促进任务优化的收敛性能。在速度更新的过程中，设计了三种方法来安全有效地传递知识。
粒子只利用其所属任务的信息来更新其速度，这与单任务PSO中的方式相同。 如11行所示，从当前多任务环境中随机选择一个在线任务，然后利用从所选任务传递的知识来更新粒子的速度。与传统的EMTO不同，本文提出的知识转移方法不会导致任务私有信息的泄露。 在前一种方法的基础上，首先将传递的知识映射到一个低维子空间，然后粒子利用该子空间中的知识完成速度更新。
提出算法的一些细节问题：1)处理不同节点断开连接时各任务的进化方法：由于通信线路不稳定等因素，某些任务可能会被动地与其他任务断开连接。这些断开连接的任务无法继续与其他任务通信以执行知识传递。在这种情况下，这些任务仅通过上述第一速度更新方法来完成后续的搜索过程。换句话说，当任务检测到其断开时，它将执行单任务优化方法。
2)与联邦学习的区别：所提出的方法属于进化优化领域，而联邦学习是机器学习领域的一部分。进化优化的目的是通过利用自然选择或适者生存等原则来寻找给定问题的最佳解决方案。相反，机器学习的主要目标是创建能够很好地泛化的模型，并对看不见的数据做出准确的预测或决策，这强调发现数据中的模式和关系。当表征与联邦学习的相似性时，PEMTPSO可以被视为联邦范例优化方法而不是学习方法。
基于同态加密的多任务PSO知识迁移
为了解决EMTO中的隐私泄露问题，进一步提升多任务范式的现实价值，这一部分设计了一种基于同态加密的隐私保护知识迁移策略。首先给出了PEMTPSO中速度更新的基本公式。粒子的速度可以根据下述公式进行更新。
此外，在参数rmp的调节下，每个粒子还可以结合其他任务的知识来更新其速度，可以表示为
上式中， 表示任务h的全局最优解的第d维, 和 表示分别表示任务k的粒子i的自我经验和社会经验。TE被定义为迁移经验，它代表任务之间的信息共享和合作。PEMTPSO中每个任务只占用一个种群，不同种群之间的知识交换只体现在T E中，因此，只要TE的计算过程不涉及信息泄露，任务的隐私就可以得到保护。
假设待优化任务为任务k和任务h,将任务k和任务h分别定义为主动方和被动方。主动方是知识迁移的发起者，被动方作为推动者帮助主动方更新速度。PEMTPSO中具有隐私保护的知识转移如算法3所示。首先，Tk通过执行密钥生成算法KeyGen 生成密钥对。接下来，加密，并将得到的密文标记为，可以表示为
式中：d = 1，2，..，D。D表示统一搜索空间的维数。由于的随机性，可以将相同的明文加密成不同的密文，提高了密文的语义安全性。接下来，向发送公钥和密文。
收到的请求后，首先对其全局最优粒子进行加密，并将的密文标记为。然后，生成一个随机向量。根据Paillier加密算法的同态性质，可以将TE对应的密文写为
到这里其实就很清楚了，所谓隐私增强，就是利用加法同态加密中密文乘等于明文加的这样一个性质，实现了具有隐私保护性质的知识迁移，由于被传输的只有公钥以及被加密后的单个解，所以对方只能得到加密的方法，而收到信息的一方得到的是使用对方最优解，我方需要优化的解以及一个随机向量三者计算处理后才能得到的密文，因此也不能得到对方最优解的原始信息。
此外，Paillier加密算法只能加密0⋅n之间的正整数，其中n是两个大素数的乘积。这显然不能满足对粒子的加密要求。针对浮点数无法加密的问题，在加密前将每个明文放大倍，然后丢弃小数部分，其中pcs表示加密精度。为解决负数无法加密的问题，在对明文进行加密之前，首先对其进行mod n操作进行映射，可表示为
式中：m和分别表示原始明文和映射明文。Z表示整数空间。对明文进行预处理后，正数映射到之间，负数映射到之间，如图2所示。由于负数的映射满足:
$m\bmod n=m+n,(-\frac{n}{2}<m<0,m\in\mathbb{z})$< p=""></m<0,m\in\mathbb{z})$<>
还需要通过减去n将之间的解密结果映射回负数。
子空间知识迁移
同态加密的出现为保密计算提供了一种解决方案。然而，在解决实际问题时，与加密相关的额外计算负担仍然是一个不可忽视的问题。为了在更大程度上减少这种负担，首先将待加密的数据投影到低维子空间中。然后，在低维子空间中进行加密、解密等操作。在这里，主成分分析（PCA）方法被用于子空间的构造。主成分分析可以保证尽可能少的信息损失，并且可以很好地保留数据的主要成分，同时消除次要成分。一般来说，负面因素，如噪音干扰，隐含在次要组成部分。因此，在某些情况下，剔除次要成分也可以增强算法对噪声的鲁棒性，并揭示问题的主要搜索方向。总之，在不降低原算法的性能，PCA为基础的子空间知识转移，可以实现大规模减少与隐私保护相关的计算负担。
为了在低维子空间中实现计算，首先为每个任务构造投影矩阵。我们使用两个任务的情况用于说明，并且两个所选择的任务被表示为Tk和Th。它们分别对应于大小为N的粒子群Pk和Ph，RD是它们的统一搜索空间。为了获得协方差矩阵，两个任务的所有粒子被处理为具有零均值的D维向量。接下来，为每个任务求解协方差矩阵，并计算每个协方差矩阵的特征值和特征向量。最后，选择对应于Tk的协方差矩阵的第一DL特征值的特征向量用于构造投影矩阵Wk。类似地，执行Wh的构造。其中DL表示子空间的维数，Wk和Wh分别表示Tk和Th的正交投影矩阵。
实验结果
加密精度分析：如前文所述，由于在计算传输经验时密码操作的限制，粒子的精度降低。浮点加密精度记为pcs，表示保留的小数位数。然而，在实际问题中，EMTO中的数据经常使用双精度计算。为了验证知识传递过程中降低粒子准确度对所提方法性能的影响，本实验对PCS的灵敏度进行了测试和分析。在本实验中，pcs依次设置为2、3、4、5和6。此外，一个双精度PEMTPSO作为控制组。值得注意的是，加密操作只是一种隐私保护措施，并不会改变算法的结果。这样，在知识传递过程中，就不需要对PEMTPSO进行双精度的密码运算，从而方便了实验的实现。上述算法，然后运行50次独立的两个任务的基准问题，其中包括Griewank的和Rastrigin的功能。该实验的结果如图所示。3.可以观察到，当该参数大于2时，PEMTPSO对pcs的灵敏度非常低。特别地，当pcs的值等于6时，具有该参数值的PEMTPSO的优化曲线与具有双精度的PEMTPSO的优化曲线高度重叠。在随后的实验中，将参数pcs统一设置为6。
子空间维数DL的分析：为了减少与隐私保护相关的额外计算开销，PEMTPSO还允许在低维子空间中进行任务间的知识传输。其中，子空间的维数DL作为一个关键参数，对PEMTPSO的收敛性能有着重要的影响。因此，本文测试了一组问题的参数DL的敏感性。在该实验中，子空间维度DL被依次设置为统一空间的维度的0.2、0.4、0.5、0.6和0.7倍。实验结果如图所示。4.补充材料中有更多的实验结果。可以观察到，对于低相似性问题，小DL可以以高概率表现良好。然而，对于高相似性问题，大DL往往表现得更稳定。值得注意的是，DL = 0.5作为折衷设置可以在大多数问题上始终如一地表现良好，例如CI+HS，PI+LS和NI+HS。因此，在本文的后续实验中，将参数DL统一设置为0.5。
子空间知识迁移组件的效果检验：子空间中的知识转移可以减少用于隐私保护的额外资源，但其对性能的影响需要进一步验证。首先去除PEMTPSO中的子空间知识传递成分，形成变体算法PEMTPSO-N。可以观察到，PEMTPSO的整体性能优于PEMTPSO-N。具体而言，PEMTPSO获得了显着的上级解决方案的质量方面的平均目标值的18个任务中的7个，其性能并不比PEMTPSO对任何剩余的任务。此外，当在低维子空间中执行知识转移时，要保护的隐私向量的维数从D降低到DL。由于隐私向量上的密码操作是针对每个维度单独执行的，因此隐私保护所需的计算资源与隐私向量的维度近似线性且正相关。与原始空间中的知识转移相比，DL = 0.5的子空间中的知识转移可以减少用于隐私保护的计算资源约50%。因此，当以相等的概率随机执行两种类型的知识转移时，与仅在原始空间中执行的知识转移相比，用于隐私保护的计算资源可以减少约25%。综上所述，在子空间中传递知识的策略不仅达到了减少隐私保护所消耗资源的目的，而且在一定程度上提高了算法的性能。
为了深入分析所提出的方法的性能，PEMTPSO相比，五个单任务优化算法和六个多任务优化算法，分别。为了清楚起见，首先给出对比较算法的简要描述。粒子群算法是该方法的基本对应物，并被用作baseline来确认PEMTPSO的优势。GA和DE是两种经典的SOO进化算法。受PSO的启发，竞争性群体优化器（CSO）利用竞争机制在探索和开发之间取得良好的平衡，并在大规模问题上获得改进的结果。MFEA是第一个基于遗传算法的多任务搜索算法。MFEA-II 是一种改进的具有自适应任务间转移概率的MFEA。LDA-MFEA 通过与线性化领域适应策略相结合，阐明了MFEA中负知识转移的影响。MFPSO和MFDE分别是基于PSO和DE的EMTO方法。在SREMTO中，跨任务知识转移的强度可以随着进化搜索的进行而自动调整。MFEA-AKT 是一种新的MFEA方法，它能够自适应地配置交叉算子以进行知识转移。
与SOO算法的比较结果如表V所示。由于任务间的知识转移，可以观察到，PEMTPSO的整体性能是显着优于四个SOO算法上级。具体而言，该算法获得显着上级的解决方案的质量相比，遗传算法，AO，和CSO的平均目标值方面的14 18个任务，PEMTPSO的这种优势是更显着的PSO和DE相比。此外，PEMTPSO在PI+LS和NI+ MS优化问题上的性能优于基线PSO。它表明，对于由不同维度的任务组成的优化问题，在所提出的方法中提供知识转移有助于两个任务的收敛。通常，具有较小搜索空间的低维任务往往收敛得更快，并且所提供的信息可以加速高维任务的收敛。在高维任务的搜索过程中获得的经验通常有助于低维任务逃离局部最优。从CI+HS和PI+HS等问题的优化结果可以看出，PEMTPSO也可以很好地处理具有不同上限和下限的优化任务。PEMTPSO将不同的任务编码到一个由0和1限定的统一搜索空间中，保证了任务之间的知识转移能够顺利实现。与SOO相比，PEMTPSO没有达到最佳结果的三种情况{CI+LS，PI+LS，NI+LS}的特征在于组成任务之间的非常低的相似性，这突出了任务间协同对多任务成功的重要性。
从表VI中可以看出，PEMTPSO的综合性能与当前大多数EMTO算法相当。然而，PEMTPSO并没有实现超越MFEA-II和MFEA-ATK的收敛性能。这个问题可能是由于PEMTPSO缺乏自适应调整任务间知识转移程度的能力造成的。MFEAII在这方面具有显著优势。由于本文的主要目的是克服EMTO中的隐私泄漏问题，因此不太强调提高收敛性能。虽然PEMTPSO算法的性能与其他EMTO算法相比不是最好的，但它可以保护任务的隐私信息不被泄露。在具有信息安全和隐私保护要求的场景中，该方法的综合优势更加显著。
总结
针对EMTO中的隐私泄露问题，本文提出了一种隐私增强的多任务粒子群优化算法。这是EMTO在隐私安全方向的首次尝试。具体而言，通过对参与者进行协议约束，并利用同态加密技术，实现了对EMTO中每个任务的隐私信息的保护。此外，在低维子空间的知识转移已被设计，以减少密码操作的性能PEMTPSO的负面影响。为了有效地解决具有不同相似性的任务，该方法集成了低维子空间和原始空间的搜索。实验结果表明，所提出的方法的整体性能显着优于相应的单任务求解器，是最近提出的EMTO算法相媲美。值得注意的是，与这些EMTO算法相比，所提出的方法可以保护参与者的隐私信息不被泄露。
公众号联系邮箱evoIgroup@163.com
欢迎投稿、交流！