MLWE-based Homomorphic Inner Product Scheme
Author:
Affiliation:

Clc Number:

TP309

Fund Project:

National Natural Science Foundation of China (11671377); Research Project of Chongqing Science and Technology Commission (cstc2017zdcy-yszxX0011, cstc2018jcyj-yszxX0002)

  • Article
  • | |
  • Metrics
  • |
  • Reference [19]
  • |
  • Related
  • | | |
  • Comments
    Abstract:

    The homomorphic inner product has a wide range of applications such as secure multi-geometry calculation, private data mining, outsourced computing, and sortable ciphertext retrieval. However, the existing schemes for calculating the homomorphism inner product are mostly based on FHE by RLWE with low efficiency. With MLWE, this study proposes a homomorphic inner product scheme by using a low expansion rate encryption algorithm proposed by Ke, et al. Firstly, the tensor product operation in the cipher space is given, which corresponds to the integer vector product operation in the plaintext space. Then, the correctness and security of the scheme are analyzed. At last, two sets of optimized encryption parameters are given, corresponding to the different application scenarios of homomorphic inner product. The scheme of this study is implemented by C++ and the large integer computation library NTL. Compared with other homomorphic encryption schemes, this scheme can efficiently calculate the homomorphism inner products of integer vectors.

    Reference
    [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]
    [15] Langlois A, Stehlé D. Worst-Case to average-case reductions for module lattices. Designs, Codes and Cryptography, 2015,75(3):565-599.
    [16] Golub GH, Van Loan CF. Matrix Computations. Baltimore:The Johns Hopkins University Press, 2012. 219-222.
    附中文参考文献:
    [12] 柯程松,吴文渊,冯勇.基于MLWE的低膨胀率加密算法.计算机科学,2019,46(4):144-151.
    [13] 柯程松.基于模容错学习问题的加密算法研究[硕士学位论文].重庆:重庆邮电大学,2019.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

柯程松,吴文渊,冯勇.一种基于MLWE的同态内积方案.软件学报,2021,32(11):3596-3605

Copy
Share
Article Metrics
  • Abstract:834
  • PDF: 2829
  • HTML: 2018
  • Cited by: 0
History
  • Received:July 02,2018
  • Revised:October 08,2019
  • Online: November 05,2021
  • Published: November 06,2021
You are the first2043735Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063