﻿ 某信息系统二次规划同态加密梯度下降算法研究
 舰船科学技术  2024, Vol. 46 Issue (5): 159-162    DOI: 10.3404/j.issn.1672-7649.2024.05.029 PDF

1. 中国人民解放军 92578部队，北京 100161;
2. 海装驻郑州某军事代表室，河南 郑州 450000

Research on quadratic programming homomorphic encrypted gradient descent algorithm for an information system
SHEN Jun1, DING Bei2, WANG Kai1, LV Zhong1
1. No. 92578 Unit of PLA, Beijing 100161, China;
2. A Military Representative Office in Zhengzhou , Zhengzhou 450000, China
Abstract: The homomorphic encryption method can realize the function of analyzing or operating encrypted data without leaking the content. However, this method has a heavy computational overhead and has been very hard to achieve in practice within the control domain.. In order to solve this problem, we first calculated and analyzed the applicability of the gradient descent algorithm in solving quadratic programming in the homomorphic encryption method, reduced the limitation of the multiplication depth of the homomorphic encryption circuit on the iteration of the gradient descent algorithm, and quantified the prototype example. Lay the foundation for further research. Secondly, the choice of gradient descent and accelerated gradient descent methods was weighed and evaluated, which opened up a path for the engineering application of homomorphic encryption technology. The adopted CKKS scheme allows the program to achieve convergence by selecting an appropriate step size, directly demonstrating the feasibility of the homomorphic encryption gradient descent algorithm.
0 引　言

1）在CKKS方法框架下，选取适当的步长以确保底层算法的收敛性；

2）通过改进同态加密矩阵乘法，在乘法深度方面提升效率；

3）通过计算分析，权衡梯度下降和加速梯度下降算法的适用范围。

1 无约束二次规划的下降算法

 $\mathop {\min }\limits_{_{x \in {{R}^n}}} f(x)。$ (1)

 ${x_{t + 1}} = {x_t} - \eta \nabla f({x_t}) 。$ (2)

2 同态加密算法

CKKS方案[8]通常被认为是对实数和复数执行近似同态加密计算的最有效方法[9]。它可以被认为是一个噪声通道[10]，一个简单的加密/解密过程会给原始消息添加噪声。该方案中，明文和密文空间$R[{Z_q}]$$R[C]利用整数多项式环的结构来完成。该多项式环与规范嵌入变换相结合，对{C^N}中的向量进行编码-解码的往返交替复多项式R[C]的环。要对消息x \in R[C]进行编码，可应用逆嵌入变换来得到\mu = {\sigma ^{ - 1}}(x) \in R[C]，然后将\mu 按因子 \Delta = {2^p} 缩放并四舍五入以获得纯文本m = [\Delta \cdot \mu ] \in R[{Z_q}] 综上可认为CKKS方案是最适合应用梯度下降或加速梯度下降的同态加密方案。因其步长η可以足够小，使得梯度下降算法能够收敛[11-12] 3 同态加密梯度下降算法 同态加密下降算法与普通下降算法相比，仍以迭代的方式运行，其区别在于将迭代密文而不是纯文本。针对加速梯度下降和梯度下降算法在同态加密过程中的应用，与通常的加速梯度下降和梯度下降算法非常相似，区别仅在于使用了同态加密算数运算和特殊的MMULT矩阵乘法。 在迭代密文时有2个步骤需格外注意，分别是停止条件和矩阵乘法过程。矩阵乘法过程与噪声水平相关，而噪声水平随乘法深度呈指数增长。当前已有学者提出了一种全同态矩阵乘法算法（Halevi-Shoup 方法）来以更有效的方式执行这些运算[13]。这种方法提出了一种新矩阵乘法方案（JKLS），该方案允许进行加密矩阵乘法，每个矩阵仅适用一个密文，遵循行排序编码 A \to a 。虽然应用方便，但JKLS算法仍需2次明文与密文的乘法运算。本文对此做了部分改进，将明文与密文的乘法运算减少了一次。在该算法的基础上，本文将矩阵 {{\boldsymbol{V}}_k}$$ {{\boldsymbol{W}}_k}$分别对行编码矩阵AB进行排列，使得所知的矩阵乘法算法可通过逐元素乘法和加法来实现，具体如下式：

 ${V_k}(d \cdot i + j,l) = \left\{ {\begin{split} 1，{l = d \cdot i + {{[i + j + k]}_d}}，\\ 0，{l \ne d \cdot i + {{[i + j + k]}_d}}。\end{split}} \right.$ (3)
 ${W_k}(d \cdot i + j,l) = \left\{ {\begin{split} 1，{l = d \cdot {{[i + j + k]}_d} + j}，\\ 0，{l \ne d \cdot {{[i + j + k]}_d} + j}。\end{split}} \right.$ (4)

 图 1 矩阵乘法${V_k}$和${W_k}$举例，其中$d = 4$ Fig. 1 Example of matrix multiplication Vk and Wk, where d=4

1）不指定容差ε，而是固定迭代次数N。通过给定的迭代次数N和算法的收敛速度推断出可达到的容差ε

2）引入初始估计x0

4 数值分析

 图 2 同态加密加速梯度下降解密算法验证结果 Fig. 2 Verification results of homomorphic encnyption accelerated gradient descent decryption algorithme

 图 3 $f(x) - f({x^*})$的公差箱型图 Fig. 3 The tolerance box diagram of $f(x) - f({x^*})$

5 结　语

 [1] BRAKERSKI Z . Fully homomorphic encryption without modulus switching from classical GapSVP[C]//International Cryptology Conference, Springer, Berlin, Heidelberg, 2012. [2] FAN J, VERCAUTEREN F. Somewhat practical fully homomorphic encryption[J]. Cryptology ePrint Archive, 2007, 216676. [3] JUNG H C, ANDREY K, MIRAN K, et al. Homomorphic encryption for arithmetic of approximate numbers. InTsuyoshi Takagi and Thomas Peyrin, editors, Springer International Publishing, 2017, 409−437. [4] CRAIG, GENTRY, ZVIKA, et al. (Leveled) Fully homomorphic encryption without bootstrapping[J]. Acm Transactions on Computation Theory, 2014, 11: 20−25. [5] GENTRY C, SAHAI A, WATERS B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[C]//Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, Springer Berlin Heidelberg, 2013: 75-92. [6] BUBECK S. Convex optimization: algorithms and complexity[J]. Foundations and Trends® in Machine Learning, 2015, 8(3): 231−358. [7] LYUBASHEVSKY V, PEIKERT C, REGEV O. On ideal lattices and learning with errors over rings[C]//Advances in Cryptology–EUROCRYPT 2010: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, Springer Berlin Heidelberg, 2010: 1−23. [8] JUNG H C, ANDREY K, MIRAN K, et al. Homomorphic encryption for arithmetic of approximate numbers. InTsuyoshi Takagi and Thomas Peyrin, editors, Advances in CryptologyASIACRYPT, Springer International Publishing, 2017, 409−437. [9] KIM A, PAPADIMITRIOU A, POLYAKOV Y. Approximate homomorphic encryption with reduced approximation error[C]//Cryptographers’ Track at the RSA Conference. Cham: Springer International Publishing, 2022: 120-144. [10] LEE Y, LEE J, KIM Y S, et al. High-precision and low-complexity approximate homomorphic encryption by error variance minimization[J]. IACR Cryptol ePrint Arch, 2020, 1549. [11] KIM J, KIM D, SONG Y, et al. Comparison of encrypted control approaches and tutorial on dynamic systems using Learning With Errors-based homomorphic encryption[J]. Annual Reviews in Control, 2022, 54: 200−218. [12] JUNSOO K, HYUNGBO S, KTOOHYUNG H. Dynamic controllerthat operates over homomorphicallyen-crypted data for infinite time horizon[J]. IEEE Transactions on Automatic Control, 2023, 68(2): 660−672. [13] JIANG X, KIM M, LAUTER K, et al. Secure outsourced matrix computation and application to neural networks[C]//Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, 2018: 1209−1222.