第42卷第3期通信学报V ol.42No.3 2021年3月Journal on Communications March 2021 基于NTRU的多密钥同态代理重加密方案及其应用
李瑞琪1,2，贾春福1,2，王雅飞1,2
（1. 南开大学网络空间安全学院，天津 300350；2. 天津市网络与数据安全技术重点实验室，天津 300350）
摘 要：为了提高同态加密算法在多用户云计算场景下的实用性，构造了一个基于NTRU的多密钥同态代理重加密方案。首先利用密文扩张思想提出了一种新的NTRU型多密钥同态密文形式，并基于此设计了相应的同态运算和重线性化过程，从而形成一个支持分布式解密的NTRU型多密钥同态加密方案；然后借助于密钥交换思想设计了重加密密钥和重加密过程，将代理重加密功能集成到该NTRU型多密钥同态加密方案中。所提方案保留了多密钥同态加密和代理重加密的特性，而且在用户端的计算开销较低。将所提方案应用于联邦学习中的隐私保护问题并进行了实验，结果表明，所提方案基本不影响联邦训练的准确率，加解密、同态运算和重加密等过程的计算开销也可接受。
关键词：同态加密；代理重加密；多密钥；云计算；联邦学习
中图分类号：TP309.7
文献标识码：A
DOI: 10.11959/j.issn.1000−436x.2021023
Multi-key homomorphic proxy re-encryption
scheme bad on NTRU and its application
LI Ruiqi1,2, JIA Chunfu1,2, WANG Yafei1,2
1. College of Cyber Science, Nankai University, Tianjin 300350, China
2. Tianjin Key Laboratory of Network and Data Security Technology, Tianjin 300350, China
Abstract: To improve the practicability of homomorphic encryption in the application of multi-ur cloud computing, a NTRU-bad multi-key homomorphic proxy re-encryption (MKH-PRE) scheme was constructed. Firstly, a new form of NTRU-bad multi-key ciphertext was propod bad on the idea of ciphertext extension, and the corresponding homo-morphic operations and relinearization procedure were designed on the basis of this new ciphertext form, so that a NTRU-bad multi-key homomorphic encryption (MKHE) scheme which supported distributed decryption was con-structed.
Then, resorting to the idea of key switching, the re-encryption key and re-encryption procedure were put forward such that the functionality of proxy re-encryption (PRE) was integrated to this new NTRU-bad MKHE scheme. The MKH-PRE scheme prerved the properties of MKHE and PRE, and had a better performance on the client side. The scheme was applied to the privacy-prerving problems in federated learning and an experiment of the application was carried out. The results demonstrate that the accuracy of learning is scarcely affected by the encryption procedure and the computational overhead of this MKH-PRE scheme is acceptable.
Keywords: homomorphic encryption, proxy re-encryption, multi-key, cloud computing, federated learning
收稿日期：2020−10−14；修回日期：2020−12−16
通信作者：贾春福，****************
基金项目：国家重点研发计划基金资助项目（No.2018YFA0704703）；国家自然科学基金资助项目（No.61972215, No.61702399, No.61972073）；天津市自然科学基金资助项目（No.20JCZDJC00640）
Foundation Items: The National Key Rearch and Development Program of China (No.2018YFA0704703), The National Natural Science Foundation of China (No.61972215, No.61702399, No.61972073), The Natural Science Foundation of Tianjin (No.20JCZDJC00640）
·12·通信学报第42卷
1 引言
全同态加密（FHE, fully homomorphic encryp-tion）是一种新型密码学原语，其支持在加密信息上进行任意函数运算，并且解密后得到的结果与在明文上执行相应运算的结果一致。同态加密的思想最初由Rivest等[1]在1978年提出（最初的概念被称作privacy homomorphism）。2009年，Gentry[2-3]构造出了第一个全同态加密方案。在Gentry的开创性工作之后，一系列关于同态加密的研究成果相继出现[4-10]。同态加密的特性使其能够广泛应用于多种云计算场景，如外包计算。
考虑如下的外包计算场景。多个数据拥有者想要联合进行某种计算（例如机器学习或数据挖掘等），于是各自将数据加密后发送到云端。云服务器在密文上进行指定的计算，然后将结果发送给接收者。接收者既可以是数据提供者，也可以是数据提供者之外的第三方。大多数情况下，数据提供者希望自己的数据对其他提供者和接收者是保密的，显然单密钥同态加密方案无法满足此要求。因此，需要一个具有如下性质的同态加密方案。1) 每个数据提供者能够用自己的公钥进行加密，并且这些密文能同
时参加同态计算；2) 计算结果的接收者即使获得了（其他）数据提供者的原始密文也无法对其进行解密。
多密钥同态加密（MKHE, multi-key homo-morphic encryption）支持多方用户以各自的密钥对消息进行加密，得到的密文可以一起参与同态运算。López-Alt等[8]首次提出了MKHE的概念并构造了第一个MKHE方案，此后一系列MKHE方案被提出[11-18]。MKHE方案能够满足性质1)，并且当接收者是数据提供者时，借助于分布式解密，MKHE方案也能够满足性质2)。然而当接收者是数据提供者之外的第三方时，只有2种解密方式：一是把所有数据提供者的私钥收集给接收者；二是数据提供者和接收者之间进行交互。前一种情况在现实中不太可能发生，后一种情况则需要数据提供者在线才能进行解密，因此在这种场景下MKHE的使用仍存在问题。
扎啤桶为了解决上述问题，Yasuda等[19]提出了一个新概念——多密钥同态代理重加密（MKH-PRE, multi-key homomorphic proxy re-encryption）。MKH-PRE方案既有MKHE的特性，也具有PRE 的性质。此类方案允许数据提供者用自己的公钥加密数据来进行多密钥同态计算，同时也允许对同态计算得到的密文进行代理重加密，将结果密文转换为只能由接收者解密的新密文。重加密功能的加入使当接收者是数据提供者之外的第三方时能够满足性质2)。由于数据提供者预先生成了重加密密钥并发送到云端，因此接收者在解密时不需要与提供者进行交互，即提供者不需要实时在线。Yasuda等[19]也给出了一个基于PS16方案[16]的MKH-PRE实例（简称YKHK18方案），但该实例不适用于实际的外包计
算场景，这是因为在PS16多密钥同态加密方案中，明文空间只有1 bit，大大降低了实用性；同时，PS16方案需要在加密时生成冗余密文，给用户带来了额外的开销，并且整个方案难以实现。
NTRU（number theory rearch unit）是由Hoffstein、Pipher和Silverman[20]于1998年提出的一种基于格的公钥加密体制，此后的研究工作[21-23]构造了可证明安全的NTRU加密方案，这些方案的安全性能够规约于标准的密码学假设RLWE（ring learning with error）。相较于传统公钥密码，NTRU 具有显著的计算性能优势，而且被认为能够抵抗量子计算攻击。除此之外，NTRU加密体制自提出后一直备受关注的原因还包括其能够用于构造具有功能性的密码学原语。近年来，一些研究关注于利用NTRU算法构造多密钥同态加密方案[8,24-25]，但现有的NTRU型MKHE方案在实际应用时仍存在一定的问题。此类MKHE方案需要将所有数据提供者的私钥收集给接收者才能解密，这意味着当接收者是数据提供者时，需要多轮协议才能完成解密；当接收者是第三方时，需要将所有私钥提供给第三方。NTRU算法也能够用于构造代理重加密方案[26-27]，这些方案可以将密文转换成接收者能够解密的密文，因而适用于接收者为提供者之外的第三方的情况，但PRE并不支持密文计算。综上所述，鉴于NTRU能构造多种功能性密码学原语以及上述方案在应用中存在局限性，可以利用NTRU算法构造适合多种外包计算场景的多密钥同态代理重加密方案。
本文构造了一个基于NTRU的多密钥同态代理重加密方案，并给出了该方案的一个实际应用。本文主要的研究工作如下。
1) 利用密文扩张的思想设计了一种新的
第3期 李瑞琪等：基于NTRU 的多密钥同态代理重加密方案及其应用 ·13·
NTRU 型多密钥同态密文形式，并以此为基础设计了相应的同态运算和重线性化过程，从而得到了一个支持分布式解密的NTRU 型MKHE 方案。
2) 利用密钥交换的思想，在此NTRU 型MKHE 方案中加入了代理重加密的功能，得到了一种新的基于NTRU 的MKH-PRE 方案。新方案同时保留了MKHE 和PRE 的特性，可根据使用场景选取功能。
风铃花的花语3) 本文方案在用户端的开销相对较低，并且支持加密多项式而不是1 bit ，从而支持并行化操作，因此相较此前的MKH-PRE 方案更具实用性。
4) 将本文方案进行了实现，并应用于一个实际场景——联邦学习。实验结果表明，本文方案的使用基本不会影响联邦学习的准确性，加解密、同态运算、重加密等过程的计算开销也是可接受的。
2 基础知识
本文使用加粗大写字母表示矩阵，例如M ；使
用加粗小写字母表示（行）向量，例如v ；[]i v 表示向量v 的第i 个分量。对于一个实数r ，r ⎣⎤表示四舍五入取整。x D ←表示从分布D 中随机抽取样本x 。对于有限集S ，()U S 表示S 上的均匀分布。若一簇分布{}n n χ∈ 满足[|||Pr ne )]l |g (n
e B n e χ∞←>≤，
则称其为B 界分布。
本文方案中涉及的所有运算均在环[]/()m R X x Φ= 中进行，其中()m x Φ是分圆多项式，次数为()n m ϕ=。令/q R R qR =，其中元素的
系数都在,,22q q ⎧⎫⎢⎥⎢⎥−⎨⎬⎢⎥⎢⎥⎣⎦
⎣⎦⎩⎭
内
（2R 中元素的系数都在{0,1}中）。定义环R 中元素
121210n n n n a a x a x a x a −−−−=++++ 的无穷范数为
||||max||i a a ∞=。对于任意的,a b R ∈，有+a b a
b ∞∞
∞+≤，ab
a
b δ∞
∞
∞≤，其中δ被
称作环常数。
2.1 RLWE 问题与DSPR 假设
环带错学习问题（RLWE, ring learning with error ）是由Lyubashevsky 等[28]提出的。参数为,,,n q χς的RLWE 分布定义为：随机选取q R 中的多项式s ς←，()q a U R ←，e χ←，输出
(,)a b as e =+。判别版本的RLWE 假设（记作,,,DRLWE n q χς）定义为：从,,,RLWE n q χς分布中抽取
的多项式个样本(,)i i a b 与从)(q U R 中抽取的相同个数的样本之间是统计上不可区分的。
López-Alt 等[8]介绍了判别小多项式比（DSPR,
decisional small polynomial ratio ）
问题，其定义如下。令q 为素数，φ是环R 上的分布。DSPR 问题（记作,DSPR q φ）是区分如下2个分布：1)1h gf −=的分布，其中f 和g 是从分布φ中随机选取的（要求f 在q R 上可逆）；2)q R 上的均匀分布。
此前有关NTRU 的研究[21-23]已经证明，当分布
φ为离散高斯分布,n
r
D
且)r n >时，
秘书英文,DSPR q φ问题是困难的（即分布1)和2)统计上不可区分），然而为了能进行多密钥同态计算，需假设当φ的标准差较小时，,DSPR q φ问题仍是困难的。 2.2 工具向量
文献[29]中介绍了工具矩阵（Gadget ）G 及其对应
的逆函数1
()−⋅G 。本文中，令:()d i g =∈g 为工具向量，对应的分解函数为1:d q R R −→g 。该函数将q R 中的一个元素a 分解为一个向量01(,,)d u u −=u d R ∈，满足()1
mod d i i i a g u q −==∑，并且每个i u 都是小多项
式。对于向量d q R ∈v ，1()−g v 表示将1−g 应用到v 的
每一个分量[]i v 上，从而得到矩阵d d R ×∈V ，满足
=(mod )q gV v 。
3 多密钥同态代理重加密
年饭
本节给出多密钥同态代理重加密的形式化定义及其IND-CPA 安全性的定义。 3.1 MKH-PRE 的定义
令M 为明文空间，设每个参与同态运算的用户都有一个id ，每个同态密文都伴随着一个用户id 集合，用来记录计算过程中涉及的所有用户。“新鲜的”密文所对应的集合T 中只包含一个元素，即{id}T =，而经过多密钥同态运算后的密文对应的集合会变为12{id ,id ,,id }k T = 。一个多密钥同态代理重加密方案包括如下算法。
pp Setup(1)λ←：输入安全参数λ，输出公共参数pp 。
(pk,sk)KeyGen(pp)←：输入公共参数pp ，输出公钥pk 和私钥sk 。
Enc(pk,)c m ←：输入消息明文m ∈M 和公钥pk ，输出密文c 。
·14· 通 信 学 报 第42卷
id id D }ec({sk ,)T m c ∈←：输入密文c 及其对应的运算参与方的私钥id id {sk }T ∈，输出明文m 。
Eval 1id id Eval(,{,,,{p }k })k T c c c ∈← C ：输入电路
C 、密文1,,k c c （对应的用户id 集合分别为1,,k
T T ）和公钥
id id {pk }T
∈（其中
12k T T T T =∪∪ ∪），输出密文Eval c （对应的用户id 集合为T ）。
rk RKGen(sk ,pk )i j i j →←：输入私钥sk i 和公钥pk j ，输出重加密密钥rk i j →。
ReEnc Re Enc({}rk ,)k T c c →∈← ：输入密文c 和重加密密钥{rk }k T →∈ （其中T 是密文c 对应的用户id 集合），输出密文ReEnc c （对应的用户id 为k ）。
一个MKH-PRE 方案应当满足以下性质。 正确性。令1,,s c c 为密文，i m 为i c 对应的明文，id id {sk }i T ∈为i c 对应的私钥。令:s →C M M 为作用于1,,s m m 的电路，Eval c 为同态计算电路C 后得到的密文。令rk 为重加密密钥，ReEnc c 为对Eval c 重加密后得到的密文，其对应的私钥为sk j 。若 1Ev i al 1i d d Pr[Dec({sk }
,)(,,)]negl()i
i s
s T c m m λ=∈
≠= ∪C
ReEnc 1Pr[Dec(sk ,)(,,)]negl()s j c m m λ≠= C (1)
成立，则称该MKH-PRE 方案是正确的。
紧致性。若存在一个多项式poly(,)⋅⋅使一个对应N 个用户的密文Eval c 及其重加密后得到的密文
ReEnc c 的尺寸满足Eval ReEnc ||||poly(,)c c N λ和都小于，
则称该MKH-PRE 方案是满足紧致性的。
3.2 安全性定义
本文采用的是文献[21]中关于MKH-PRE 方案的安全性定义。该定义中设计了一个敌手A 与挑战者之间的IND-CPA 安全游戏，使用一个有向非循环图来记录重加密过程，图中的顶点表示诚实用户，边表示可能的重加密方向。在此游戏中，敌手能够根据重加密图的情况来发起重加密密钥生成的询问。敌手和挑战者之间的IND-CPA 安全游戏的形式化定义如下。
阶段1
准备 挑战者将pp Setup(1)λ←发送给A 。令E =∅为重加密图的边的集合。
诚实密钥生成 A 将诚实密钥的数量U N 发送
给挑战者，挑战者生成(pk ,sk ), 1,,i i U i N = 并将pk i 发送给A 。令H Γ为诚实公钥集合。
非诚实密钥生成 A 将非诚实密钥的数量C
N 发送给挑战者，挑战者生成(pk ,sk ),1,,i i C i N = 并将其发送给A 。令C Γ为非诚实公钥集合。
阶段2
A 可以以任意顺序发起多项式个询问。
重加密密钥生成 A 将(,)i j 发送给挑战者。
若,H i j Γ∈且(,(,))H G E i j Γ=∪是有向非循环图，挑
战者将(,)i j 添加到E 中并将rk RKGen(sk ,pk )i j i j →←发给A ；否则返回⊥。
葆宫止血颗粒禁忌
重加密 A 将1(,,,,)s i i j c 发送给挑战者。若
C j Γ∈且=*c c ，挑战者返回⊥；否则挑战者将1Re Enc(rk ,,rk ,)s j i j i j c c →→← 发送给A ，其中rk RKGen(sk ,pk ), 1,,k k i j i j k s →←= 。
挑战 令01,, *H m m i Γ∈∈M 。A 将01(*,)
,i m m 发送给挑战者，挑战者随机选取一个比特{0,1}
b ∈并将**Enc(pk ,)i b
c m ←返回给A 。A 只能发起一次挑战询问。
阶段3
A 输出一个比特'{0,1}b ∈。
在此游戏中，敌手A 的优势定义为
[]ind-cpa MKH-PRE,1
Adv ()Pr '2
b b λ==−
A (2)
若对于任意概率多项式时间的敌手A 有
ind-cpa MKH-PRE,Adv ()=negl()λλA
(3)
成立，则称该MKH-PRE 方案是IND-CPA 安全的。
4 方案构造
本节介绍基于NTRU 的多密钥同态代理重加密方案的构造。首先介绍Setup 和KeyGen 这2个算法，这是整个方案的基础。
Setup(1)λ。输入安全参数λ，生成RLWE 的维数n 、密文模数q 、明文模数t 和R 上的分布,ψχ；
随机抽取向量()d q
U R ←a 和矩阵2()m q U R ×←A ；输出公共参数pp (,,,,,,)n q t ψχ=a A 。
KeyGen(pp)。随机抽取',f g ψ←，计算'1(mod )f tf q =+，若f 在q R 中不可逆，则重新抽
取'f 。计算1q f R −∈并设()1mod h tgf q −=。随机抽取误差向量d χ←e ，计算()mod f q =−+b a e 。令
12
(,1)q
f R ×=∈f ，随机抽取误差向量''n χ←e ，计算()'
'mod n q q R =−+∈d fA e 。输出公钥pk (,,)h =b d 和
第3期 李瑞琪等：基于NTRU 的多密钥同态代理重加密方案及其应用 ·15·
私钥sk f =。
4.1 多密钥同态加密的构造高中生物必修2
本节介绍多密钥同态加密部分的算法。类似于
文献[30-31]，本文使用的是Regev 型的NTRU 算法。本节除了给出前文所介绍的Enc 、Dec 和Eval
算法之外，还将介绍EvkGen 、CtxtExtend 和Relin 算法，这些算法是多密钥同态加密的重要组成部分。
EvkGen(pp,pk,sk)。随机抽取r χ←和001,,d χ←s e e ，计算()
1000mod h f r q −=++s e g evk 和()11mod r f q =++a e g evk ，输出计算密钥01[|]=Evk evk evk 。
Enc(,pk)m 。随机抽取,s e χ←，设=q t Δ⎢⎥⎣⎦，计算并输出密文 (mod )c hs e m q =++Δ。
1MKDec(,sk ,,sk )k ct ：设1(,,)k f f =f ，输
出明文/,(mod )m t q t =⎣()〈〉⎤ f ct 。
12CtxtExtend(,,),s ct ct ct 。设此时有s 个密文
参与运算，并设12(,,,)i
i k i k q
c c c R =∈ ct ，其对应的用户i
d 集合为12{id ,id ,,id }i k ，1,2,,i s = 。令12max{,,,}s k k k k = ，输出
k 维密文
*
***12(,,,)k i k q
c c c R =∈ ct ，其中
关于圆的知识*id , 10j j i
i c i j k c =⎧⎪=⎨
⎪⎩≤≤，，其他
(4)
12Eval(,,)ct ct Evk 。首先调用21CtxtExtend(),ct ct ，
得到**12,k q R ∈ct ct ；然后进行同态加法或乘法运算，
过程如下。
①*
*12HomAdd(,)ct ct 。计算并输出密文
*
*12mod )(q =+ct ct ct 。
②*
*12
HomMult(,,evk)ct ct 。计算*1t q
′=⎣⊗ct ct 2
*2mod k q q R ⎤ ()∈ct ，输出密文Relin(,evk)k
q
R ′=∈ct ct （下文介绍Relin 算法的细节）。
重线性化。在同态乘法运算的过程中，需要对密文进行重线性化。算法过程如下。
算法1 重线性化算法Relin 1) 输入密文2
,1,'()k i j i j k q c R ′=∈≤≤ct ，计算密钥和
公钥1{,}i i i k b ≤≤Evk 。
2) for i=1:1:k 3) for j =1:1:k
4) 1
,,(),i j i j j c c −′′′←〈〉g b
5) ()1,,0(),mod i i i j i c c c q −′′←+〈〉g evk 6) ()1,,1(),mod j j i j i c c c q −′←+〈〉g evk 7) end for 8) end for
9) 输出密文1()k
i i k q c R =∈≤≤ct
下面，说明重线性化算法的正确性。已知用户i 生成的计算密钥i Evk 为
()()
1,0,0,1,1mod mod i i i i i i i i i i h f r q r f q −=++=++s e g a e g evk evk
(5)
根据式(5)可得
1,,0,1
,,1,,(), (mod )(), (mod )i i j i i i j j i j i i i j i j i j f c rc
q f c rc f f c q −−′′′′〈〉≈′′′′〈〉≈−+g g evk evk
(6)
所以有
,,1,01,1
1,1,,1
,
(),(),(mod ),(mod )
k
k
i i i
i i i j j i k
i j i j i i
j i j j c c f f
f q f
f c c q −==−=′′′′==
+阿胶功效与作用
≈
=′⊗∑∑∑f g g f f ct ct evk evk (7)
因此，重线性化过程是正确的。注意到，重线
性化过程中需要用公钥加密其对应的私钥，因此需假设本文方案具有循环安全性。 4.2 分布式解密
在4.1节介绍的多密钥同态加密方案中，解密多密钥密文需要所有参与运算的用户的私钥作为解密算法的输入。然而在实际应用中，某一方（运算参与方或第三方接收者）拥有所有私钥是不合理的。因此，可以设计一个协议进行分布式解密。本文方案利用一个简单且直接的方式——噪声泛洪[32-33]，来实现分布式解密。
分布式解密由2个算法组成：PartDec 和FinDec 。在PartDec 算法中，用户id 为i 的运算参与方接收到多密钥密文ct 的第i 个分量i c 后，用自己的私钥i f 将其解密并加上随机抽取的噪声flood i e φ←（噪声分布φ的标准差远大于噪声分布χ的标准差）。在FinDec 算法中，所有用户将自己的部分解密结果广播给其他用户，每个用户接收到所有其他用户的部分解密结果后，将其合并起来以恢复明文。
PartDec(,)i i c f 。输入分量i c 和密钥i f ，随机抽
