Page 278 - 《软件学报》2021年第11期

3604 Journal of Software 软件学报 Vol.32, No.11, November 2021

[8]
从表 3 中可以看出,计算同态内积最快的方案是 Dijk 等人 的 DGHV 方案.但该方案的安全性是基于近似
[9]
[7]
GCD 问题,已被证明有办法破解 .而 Yasuda 等人的方案 基于理想格构造,引入了打包技术提升效率,但只能够
计算 bit 向量的内积,是不实用的.Zhou 的计算整数内积的方案 [10] 在计算大于 40 维的同态内积时,公钥会非常大,
[6]
计算内积的效率也十分低.Xu 等人 基于 HElib 优化的全同态加密方案,安全性基于 RLWE 问题,是目前最接近
实用的方案,使用 SIMD 技术优化后计算 256 维 8bits 同态内积需要进行 1 次乘法与 8 次加法共 20s 左右.本文
基于 Ke 等人 [12] 的基于 MLWE 的公钥加密方案构造了一种基于 MLWE 的同态内积方案,计算 256 维 7bits 向量
内积需要 10ms,计算 256 维 10bits 向量内积需要 20ms,在效率与实用性上比其他方案有一定的提升.
5 结束语

本文基于格困难问题 MLWE 构造了一种安全计算整数向量内积的同态内积方案,由于基于的格问题是
MLWE,在保证了安全性的前提下能够取更小的加密参数,并通过计算多项式乘法的方式来计算整数向量内积,
代替了传统同态加密方案中通过电路计算的方式,将时间复杂度降低到 O(nlogn).通过 C++与 NTL 库实现了该
[6]
方案,计算 256 维 7bit 同态内积需要 10ms 左右,比起 Xu 等人 的全同态加密方案有很大的提升,有望应用于某
些实际场景.下一步工作将研究把本文的同态内积方案应用于安全多方几何计算、隐私数据挖掘等实际场景.

References:
[1] Yao AC. Protocols for secure computations. In: Proc. of the 23rd Annual Symp. on Foundations of Computer Science. 1982.
160−164.
[2] Gentry C. A fully homomorphic encryption scheme [Ph.D. Thesis]. Stanford University, 2009.
[3] Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans. on
Computation Theory (TOCT), 2014,6(3):1−36.
[4] Lyubashevsky V, Peikert C, Regev O. On ideal lattices and learning with errors over rings. In: Proc. of the Annual Int’l Conf. on
the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer-Verlag, 2010. 1−23.
[5] Halevi S, Shoup V. Algorithms in HElib. In: Proc. of the Int’l Cryptology Conf. Berlin, Heidelberg: Springer-Verlag, 2014.
554−571.
[6] Xu C, Chen J, Wu W, et al. Homomorphically encrypted arithmetic operations over the integer ring. In: Proc. of the Int’l Conf. on
Information Security Practice and Experience. Cham: Springer-Verlag, 2016. 167−181.
[7] Yasuda M, Shimoyama T, Kogure J, Yokoyama K, Koshiba T. Packed homomorphic encryption based on ideal lattices and its
application to biometrics. In: Proc. of the Int’l Conf. on Availability, Reliability, and Security. Berlin, Heidelberg: Springer-Verlag,
2013. 55−74.
[8] Van Dijk M, Gentry C, Halevi S, Vaikuntanathan V. Fully homomorphic encryption over the integers. In: Proc. of the Annual Int’l
Conf. on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer-Verlag, 2010. 24−43.
[9] Ding J, Tao C. A new algorithm for solving the general approximate common divisors problem and cryptanalysis of the FHE based
on the gacd problem. 2014. http://eprint.iacr.org/2014/042
[10] Zhou H, Wornell G. Efficient homomorphic encryption on integer vectors and its applications. In: Proc. of the Information Theory
and Applications Workshop (ITA 2014). IEEE, 2014. 1−9.
[11] Bogos S, Gaspoz J, Vaudenay S. Cryptanalysis of a homomorphic encryption scheme. Cryptography and Communications, 2016,
10(1):27−39.
[12] Ke CS, Wu WY, Feng Y. Low expansion rate encryption algorithm based on MLWE. Computer Science, 2019,46(4):144−151 (in
Chinese with English abstract).
[13] Ke CS. Encryption algorithm based on module-LWE [MS. Thesis]. Chongqing: Chongqing University of Posts and
Telecommunications, 2019 (in Chinese with English abstract).
[14] Bos J, Ducas L, Kiltz E, Lepoint T, Lyubashevsky V, Schanck J, Schwabe P, Stehlé D. CRYSTALS-Kyber: A CCA-secure module-
lattice-based KEM. In: Proc. of the 2018 IEEE European Symp. on Security and Privacy (EuroS&P). 2018. 353−367. [doi: 10.1109/
EuroSP.2018.00032]