一种基于MLWE的同态内积方案-柯程松，吴文渊，冯勇.pdf

上善若水

338

10页

0次

2022-05-26

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2021,32(11):3596−3605 [doi: 10.13 328/j.cnki.jos.006032] http://www.jos.org.cn

一种基于 MLWE 的同态内积方案

∗

柯程松

1,2

吴文渊

冯

勇

(自动推理与认知重庆市重点实验室(中国科学院重庆绿色智能技术研究院),重庆 400714)

(重庆邮电大学计算机科学与技术学院,重庆 400065)

通讯作者: 吴文渊, E-mail: wuwenyuan@cigit.ac.cn

摘要: 同态内积在安全多方几何计算、隐私数据挖掘、外包计算、可排序的密文检索等场景有广泛的应用.但

现有的同态内积计算方案大多是基于 RLWE 的全同态加密方案,普遍存在效率不高的问题.在柯程松等人提出的基

于 MLWE 的低膨胀率加密算法基础上,提出了一种同态内积方案.首先给出了密文空间上的张量积运算⊗,该密文空

间上的运算对应明文空间上的整数向量内积运算;然后分析了方案的正确性与安全性;最后给出了两种优化的加密

参数,对应计算两种不同大小的整数向量同态内积的应用场景.通过 C++与大整数计算库 NTL 实现了该方案.对比

其他同态加密方案,该方案能够比较高效地计算整数向量的同态内积.

关键词: MLWE;同态内积;安全多方计算

中图法分类号: TP309

中文引用格式: 柯程松,吴文渊,冯勇.一种基于 MLWE 的同态内积方案.软件学报,2 021,32(11):3596−3605. http://www.jos.org.

cn/1000-9825/6032.ht m

英文引用格式: Ke CS, Wu WY, Feng Y. MLWE-based homomorphic inner product scheme. Ruan Jian Xue Bao/Journal of

Software, 2021,32(11):3596−3605 (in Chinese). http://www.jos.org.cn/1000-9825 /6032.ht m

MLWE-based Homomor phic Inner Product Scheme

KE Cheng-Song

1,2

, WU Wen-Yuan

, FENG Yong

(Chongqing Key Laboratory of Automated Reasoning and Cogni tion (Chongqing Institute of Green and Intelligent Technology, Chinese

Academy of Sciences), Chongqing 400714, Chin a)

(College of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

Abstra ct : 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 stud y proposes a homomorphic inner product scheme

by using a low expansion rate encryption algorithm proposed by Ke, et al. Firstly, the tensor p roduct operation in the cipher space is giv en,

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 stud y is implemented by C++ and the large integer computation library NTL. Compared

with other homomorphic encryption schemes , this s cheme can efficiently calculat e the homo morphism inner prod ucts of int eger v ectors.

Key words: MLWE; homomorphic inner produ ct; secure multi-pa rty computation

安全多方计算最早由 Yao

[1]

提出,指的是解决一组互不信任的参与方之间保护隐私的协同计算问题.随着云

计算与大数据技术的广泛应用,越来越多的场景需要安全高效的计算两方所输入向量的内积,如安全多方几何

∗ 基金项目: 国家自然科学基金(11671377); 重庆市院士专项(cstc2017zdcy-yszxX0011 , cstc2018jcyj-yszxX0002)

Foundation item: National Natural Science Foundation of China (11671377); Research Project of Chongqing Science and

Technology Commission (cstc2017zdcy-yszxX0011, cstc2018jcyj-yszxX0002)

收稿时间: 2018-0 7-02; 修改时间: 2019-01-06, 2019-1 0-08; 采用时间: 2 020-02-28

柯程松等:一种基于 MLWE 的同态内积方案

3597

计算、隐私数据挖掘、外包计算、可排序的密文检索等场景.安全计算两个整数向量的内积,是安全多方计算

的重要技术之一.

全同态加密允许对密文进行任意复杂的运算,而不需要解密密文,自然可以应用于安全计算两个整数向量

的内积.设计全同态加密方案,一直是密码学界的研究热点.2009 年,Gentry

[2]

基于理想格构造了第一个全同态加

密方案,由于需要使用压缩电路、自举等技术,该方案的效率很低,难以应用于实际.2012 年,Brakerski 等人

[3]

提出

了一种基于 RLWE(ring learning with errors)问题

[4]

的层级全同态加密方案 BGV,即分成一层层的电路进行同态

计算,计算效率有所提高. 2014 年,Halevi 等人根据 BGV 方案构造了第一个全同态计算库 HElib

[5]

,该计算库是目

前公认效率最高能够进行全同态加密的计算库.2016 年,Xu 等人

[6]

对 HElib 进行了优化,可完成两个整数的密文

四则运算,使用 SIMD 技术将一个明文向量的所有坐标打包到一个密文中,尽管进行了优化,要计算两个 256 维

8bits 整数向量的同态内积,使用 SIMD 技术仍然需要计算一次乘法和 8 次加法共约 20s 左右的时间.这是由于

基于 RLWE 构造同态加密方案,安全性要取较大的安全参数.文献[7]利用基于理想格的全同态加密来安全计算

内积,并应用于身份认证.但是该方案的计算效率并不高,如对两个 2 048 维的 bi t 向量,为了安全计算内积,其预

计计算的时间需要 38s;并且该方案只能计算 0-1 向量,使用场景有局限性.除了使用全同态加密,也有学者通过

其他方法计算整数向量的同态内积.2010 年,Dijk 等人

[8]

提出了基于整数的同态加密算法,虽然效率较高,但安全

性是基于近似 GC D 问题,已被证明是不安全的

[9]

.2014 年,Zhou 等人

[10]

提出了一种计算整数同态内积的方法,

效率较高,但也存在安全性问题

[11]

.总之,目前已有的方法都难以安全高效地计算两个整数向量的同态内积.

柯程松等人

[12,13]

于 2018 年对 Bos 等人的 Kyber 密钥封装算法

[14]

进行改进,提出了一种基于 MLWE(module

learning with errors)问题

[15]

的低膨胀率加密算法,加密效率高于基于 RLWE 问题构造的加密算法.这是由于

RLWE 问题只能规约到理想格上的困难问题,加密参数会取得很大,所以加密效率较低.但 MLWE 问题能归约到

模格上的困难问题,模格是一般格与理想格的推广,使能够在保证同等安全性的前提下选取更小的加密参数,所

以柯程松等人提出的加密算法效率很高,并且该方案本身保证了具有能够加密多位的整数.在此基础上,本文构

造一种基于 MLWE 的安全高效的同态内积方案.

1 本文贡献与文章结构

1.1 本文贡献

本文构造了一种基于 MLWE 的安全高效的同态内积方案,贡献如下:

(1) 基于 BGV 方案的思想,给出了基于 MLWE 问题构造的同态内积方案的密文空间上运算⊗,该密文空

间上的运算对应明文空间上的整数向量内积运算.

(2) 分析了本文基于 MLWE 问题构造同态内积算法的正确性与安全性.

(3) 针对计算两种不同大小的整数向量同态内积的应用场景,给出了两种优化的加密参数.

(4) 通过 C++与大整数计算库 NTL 实现了本文方案.对比其他同态加密方案,该方案能够高效地计算整数

向量的同态内积.

1.2 文章结构

本文第 2 节将介绍本文中出现的一些符号以及预备知识.第 3 节首先给出本文的同态内积方案,其中定义

了密文空间上的张量运算⊗;接着描述如何通过多项式乘法计算向量内积.其次给出了通过密文空间上的张量

运算⊗计算同态内积的过程;然后分析了方案的正确性.针对两种不同大小的整数向量同态内积的应用场景,给

出了两种优化的加密参数.最后证明了本文方案的 IND-CPA 安全性.第 4 节分析本文同态内积方案的计算复杂

度,并与其他几个方案做同态内积的效率进行对比.第 5 节总结全文,并对下一步值得关注的研究方向和应用场

景进行简单讨论.

of 10

免费下载

软件学报计算机技术

关注

评论