基于容错学习的GSW型全同态层次型IBE方案

戴晓明 张薇 郑志恒 李镇林

摘要：针对传统的基于身份的加密（IBE）方案不能够对密文直接进行计算这一功能上的缺陷，提出了一个新的IBE方案。该方案利用Gentry等提出的同态转化机制，结合Agrawal等构造的层次型IBE方案，构造了一个具有全同态性质的层次型IBE方案。与Gentry等提出的全同态加密（GSW）方案（GENTRY C， SAHAI A， WATERS B. Homomorphic encryption from learning with errors： conceptuallysimpler， asymptoticallyfaster， attributebased. CRYPTO 2013： Proceedings of the 33rd Annual Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2013： 75-92）和Clear等提出的全同态IBE（CM）方案（CLEAR M， MCGOLDRICK C. Bootstrappable identitybased fully homomorphic encryption. CANS 2014： Proceedings of 13th International Conference on Cryptology and Network Security. Berlin： Springer， 2014： 1-19）相比，该方案构造方法更加自然，空间复杂度由立方级降低到平方级，效率更高。在当前云计算背景下，有助于基于容错学习（LWE）的全同态加密方案从理论向实践转化。通过性能分析并在随机预言机模型下验证了所提方案具有完全安全下的选择明文攻击（INDIDCPA）安全性。

关键词：

全同态加密；基于身份的加密；近似特征向量；容错学习问题；密文校平

中图分类号： TP309.7 文献标志码：A

0引言

全同态加密能够在不解密的条件下实现对密文的任意计算，解密后可以达到相应明文计算的效果。全同态加密的这一优良特性使得它具有广阔的应用前景，如代理计算、电子投票、云存储中的密文搜索、安全多方计算等。“全同态加密”的概念是由Rivest等[1]于1978年首次提出。此后，学者们对构造同态加密方案进行了不断的探索，也提出了一些方案[2-4]，但这些方案在同态计算能力上非常有限，只能称为半同态或者类同态加密方案。2009年，Gentry[5]开创性地利用自举和压缩的构造方法，基于理想格提出了第一个全同态加密方案。这一突破性工作掀起了全同态加密的研究热潮，出现了许多按照Gentry所给框架进行设计的全同态加密方案[6-8]。这种框架具有以下的缺点：为了取得自举性，需要对类同态方案的解密电路进行“压缩”，这需要一个额外的安全假设（稀疏子集和问题），导致方案的安全性较弱；在同态计算一个电路时，需要对每个电路门通过同态解密来进行密文更新，由于同态解密计算复杂度较高，导致方案效率很低。

2013年，Gentry等[9]不再基于Gentry的初始框架，而是基于近似特征向量构造了一个全同态加密（GentrySahaiWaters， GSW）方案，不需要密钥交换技术和模交换技术就可以实现层次型全同态加密，方案效率更高，且该方案的安全性基于容错学习（Learning With Errors， LWE）问题，密文的计算就是矩阵的加法与乘法，因此是非常自然的一个全同态加密方案。

Shamir[10]提出了基于身份的公钥加密（IdentityBased Encryption， IBE）体制，其中用户公钥是与用户身份相关的可识别的一串字符，这就为数据提供了更灵活的访问控制，但在当前云计算的背景下，用户的隐私信息将会以密文形式上传到云端；但传统的IBE并不支持任何对密文的计算，所以传统的IBE已经不能满足多用户条件下对于隐私信息的保护和操作，构造具有全同态性质甚至类同态性质的IBE方案成为一个公开问题。

在探索构造具有同态性质的IBE方案的过程中，主要产生了以下成果：2010年，Gentry等[11]利用文献[4]中的类同态方案构造了一个具有类同态性质的IBE方案（IdentityBased Somewhat Homomorphic Encryption， IBSHE）。2013年，Clear等[12]基于Cocks[13]于2001年提出的IBE方案构造了一个具有加法同态性质的IBE方案，但该方案不能满足乘法同态的运算要求，同态计算能力十分有限。因而构造具有全同态性质的IBE方案依然是一个开放的难题。同年，Gentry等[9]首次提出具有全同态性质的层次型IBE方案，并提供了一种转化机制，可以将满足一定条件的IBE方案转化为全同态IBE方案（IdentityBased Fully Homomorphic Encryption， IBFHE），该转化机制同样适用于满足一定条件的基于属性的加密（Attribute Based Encryption， ABE， ABE）方案的转化。2014年，Clear等[14]又提出了一个自举的IBFHE方案，同样能扩展应用到基于属性的加密方案，但由于采用了自举的构造方法实现全同态，不可避免地造成计算复杂度太高。

针对以上问题，本文利用GSW方案提出的转化机制，结合2010年Agrawal等[15]提出的层次型IBE（Hierarchical IdentityBased Encryption， HIBE）方案，构造了一个新的层次型IBFHE（Hierarchical IdentityBased Fully Homomorphic Encryption， HIBFHE）方案，摒弃了以往基于LWE的同态加密方案利用重新线性化实现全同态的方式，而是使用了更为高效的近似特征向量的方式，对密文进行加、乘运算直接对应到矩阵的加、乘运算，构造方法上更加自然，空间复杂度也由立方级降低到平方级，这对于基于LWE的全同态加密方案从理论向实践转化是非常关键的。此外，本文方案在同态运算的过程中，不像以往的同态加密算法需要解密密钥的参与，因而支持只拥有公开参数的用户对同一目标身份下的密文进行同态运算，这也正是GSW方案能够与普通IBE方案相结合的根本原因。本文方案与原GSW方案相比，效率上有很大提高，文中进行了效率分析，并在随机预言机模型下证明该基于身份的层次型全同态加密方案对于完全安全下的选择明文攻击（Indistinguishability of the IdentityBased Encryption Scheme under ChosenPlaintext Attack， INDIDCPA）安全。

1相关基础理论

1.1LWE问题和GvpSAP

Regev[16]对LWE问题有详细描述，下面进行简要介绍。

定义1给定安全参数λ，令整数维n=n（λ），整数q=q（λ）≥2， χ=χ（λ）是Z上的一个分布。LWEn，q， χ问题就是区分以下两个分布：1）分布（ai，bi）随机取自Zn+1q；2）随机选择s ← Znq，ai ← Znq，ei ← χ，令bi=〈ai，s〉+ei，然后生成（ai，bi）∈Zn+1q，LWEn，q， χ假设就是LWEn，q， χ问题是困难的。

为了简化运算，将向量bi‖ai作为矩阵A的行，重新定义s ← （1，-s），这样无论矩阵A是否是随机矩阵或者s的第一个元素是否是1，都能保证生成的向量e=A·s的元素取自分布χ。

定义2对于格的维系数n和一个给定的数d，GapSVPγ问题是作出判定：n维格是拥有一个长度比d短的向量还是任何向量长度都比γ（n）·d大。

定理1[17]利用模n次多项式解决n维LWE问题意味着存在最坏情况的n维格上困难问题（如GapSVP）的高效解决方案。

1.2全同态加密本文的公式存在问题，即打开公式编辑器看到的公式，与word中看到的公式不一致，经过校对，现在已调整为word所显示的公式，请作者核对公式是否有误？若有，请单独指出来。

同态加密方案含有4个算法：密钥生成算法（KeyGen）、加密算法（Encrypt）、解密算法（Decrypt）和密文计算算法（Evaluate）。其中前3个算法提供加密和解密功能，密文计算算法是同态加密方案的核心所在，因为同态的目的就是要实现对密文的直接计算。将同态性质描述如下。

1）生成系统参数和公私钥，Gen（1λ） → （pk，sk），c∈C，m1，m2，…，mt∈M。

2）运用同态加密对明文进行加密运算，得到相应密文：

c1，c2，…，ct ← Enc（pk，m1），Enc（pk，m2），…，Enc（pk，mt）

3）密文计算算法对布尔电路Cir上输入的一组密文c=（c1，c2，…，ci）（其中ci ← encrypt（mi））进行计算输出一个新的密文c′。

4）解密算法对经过同态计算后的密文解密，得到与对明文作相应运算的结果相同的解密结果：

Cir（m1，m2，…，mt）=Dec（sk，Eval（pk，Cir，c1，c2，…，ct））

定义3同态加密的正确性。对于给定的电路Cir，任意由KeyGen生成的密钥对（pk，sk），任意t个明文m1，m2，…，mt以及经同态加密后每个明文对应的密文c1，c2，…，ct（其中ci ← encrypt（mi）），如果方案满足：

Dec（sk，Evaluate（pk，Cir，c））=C（m1，m2，…，mt）

则称该同态加密方案是正确的。

定义4全同态加密。如果对于所有的算术电路类，方案都具有同态性质，则称方案为全同态加密方案。

1.3HIBE方案及安全模型

IBE方案包括4个算法：Setup、KeyGen、Encrypt、Decrypt。其中：Setup算法生成系统主密钥（MSK，MPK），KeyGen（MSK，id）算法输出身份id的私钥skid，Enc（MPK，id， μ）算法输出在身份id下对明文μ的加密密文c，Dec（skid，c）算法对密文c进行解密（前提是私钥skid是在身份id下的）。通常KeyGen算法也被记作Extract算法，与Setup算法中出现的密钥生成加以区分，以免造成混淆。

HIBE方案可以解决单私钥生成器（Private Key Generator， PKG）负载过重的问题，并使其适合分布式环境下IBE方案的部署和应用。在HIBE方案中，身份信息不再是字符串而是向量，HIBE方案有第5个算法叫作Derive算法，它可以利用身份信息id′=（id1，id2，…，idl）和该身份对应的私钥skid′，生成身份id=（id1，id2，…，idl，…，idk）对应的私钥skid，该私钥与运行KeyGen算法对身份id输出的私钥相同。

在下面的描述中，设k为安全参数。以ODer表示模拟用户密钥产生算法的预言机。

定义5深度为d的HIBE方案在选择明文攻击下的安全性。如果任何概率多项式时间（Probabilistic Polynomial Time， PPT）敌手P在下面实验中的优势AdvP是可忽略的，则称方案具有INDIDCPA安全性：

1）模拟者O执行Setup，将输出值PK发送给P。

2）P进行多次用户私钥询问，分别由ODer给出相应回答。

3）P给出挑战身份向量id=（id1，id2，…，idl），l≤d和消息m0，m1，O随机选择γ∈{0，1}，计算c=Enc（id，mγ）并发送给P。

4）P继续进行多次用户私钥询问（但要求私钥询问向量id′不能是id本身也不能是id的前缀），由预言机给出回答。

5）P输出γ′∈{0，1}作为对γ的猜测，P的优势定义为：

AdvP=Pr[γ=γ′]-1/2

2HIBFHE方案

2.1方案描述

2.2解密正确性

在解密算法中，私钥skid=v是密文矩阵C的近似特征向量， μ是密文矩阵的特征值，根据特征向量与特征值的性质可得：xi ← 〈Ci，v〉=μ·vi+ei，这当中ei是噪声向量e中的一个元素，可以忽略不计，对xi/vi取最近整数将正确地恢复出消息μ。

2.3同态加与同态乘操作

设在同一身份id下对消息μ1， μ2∈{0，1}加密得到的密文分别为C1，C2∈ZNq，下面将分析如何根据C1和C2来计算消息μ1+μ2和μ1·μ2的加密。

1）同态加。

add（C1，C2）：输出Flatten（C1+C2），计算密文加法：

Add（C1，C2）·v=（C1+C2）·v=（μ1+μ2）·v+e1+e2

按照解密的计算形式，很容易看出其同态加之后的结果，只要满足噪声e1+e2

2）同态乘。

同样按照解密的计算形式，只有在满足噪声μ2·e1+Ci·e2

文献[9]中提出了一个密文校平技术，使得密文矩阵被严格控制在满足同态计算性质的界限内，2.4节将详细介绍这一技术。

2.4密文校平技术

3安全性及性能分析

3.1安全性分析

本文提出的HIBFHE方案的安全性基于LWE问题。下面给出定理2，将HIBFHE方案的语义安全性归约到LWE问题。

定理2在LWE困难问题下，本文方案具有INDIDCPA安全性。H是随机预言机，P是一个PPT敌手，定义QH为敌手P询问预言机的次数，d是最大层次深度。B为判定LWE问题的PPT算法，将敌手P的优势定义为ε，则：

ε≤LWE此处的符号是减号？连字符？还是下划线？请明确。adv[B]·（dQdH）+negl（n）

证明利用敌手P构造一个优势为ε/dQdH的LWE算法B。

SetupB按如下过程为P设置模拟攻击环境：

1）均匀地随机选择d个整数Q*1，Q*2，…，Q*d∈[QH]，其中QH是P能够进行查询最大次数。

2）通过运行R*i ← SampleR（1m），i=1，2，…，d生成d个m×m随机矩阵R*1，R*2，…，R*d。

3）在给定的LWE实例下，通过聚合得到随机矩阵A0∈Zn×mq。随机选择ω∈[d]，得到A ← A0R*ω…R*2R*1∈Zn×mq。

4）给出公开参数PP=（A， μ0）。

Secretkeyqueries敌手P可以适应性地选择任意身份id进行交互式私钥查询，B对满足长度id=k∈[d]的查询给出如下回答。

1）令j∈[k]作为满足H（id/j）≠R*j的最浅层级，若出现H（id/j）=R*j， j=1，2，…，k的情形则查询失败。

2）构造矩阵：

B=A·（R*1）-1…（R*j-1）-1·H（id/j）-1 mod q

TB是Λ⊥q（B）的一组短格基，得到skid/j=TB。

3）运行Derive（PP，TB，id）生成身份id对应的私钥skid，将这一结果发送给敌手P。

ChallengeP给出挑战身份id*和消息b∈{0，1}，令l=id*，i∈[l]，在H（id*/i）=R*i且ω=l的条件下生成加密矩阵C′id*，运行Encrypt算法得到消息b的密文矩阵C，将结果发送给敌手P。P得到结果后仍然能够继续进行私钥查询，但要求私钥询问向量不能是id*本身也不能是id*的前缀。

GuessP根据所掌握的信息给出猜测b′，B输出P的猜测并结束实验，如果b′=b，则敌手攻击成功。

由于公开参数的分配与实际系统中响应私钥查询的回应完全相同，而本实验中通过随机预言机H获取的回应也与实际系统中相同，所以在算法B不出现查询失败的情况下，挑战密文的分布或者与实际系统中相同，或者是完全独立且随机取自（Zq，Zmq）的。因而在不出现查询失败的情况下，算法B在判定LWE问题上的优势与敌手P攻击的优势相同。

将敌手P的优势定义为ε，则有：

LWEadv[B]≥[ε/（dQdH）]-negl（n）

可以得到AdvCPAP≤LWEadv[B]·（dQdH）+negl（n），解决LWE问题被公认为是困难的，所以认为敌手P攻击成功的优势可忽略。

3.2性能分析

本文构造了一个层次型全同态基于身份的加密方案，相较于文献[12]中的半同态加密方案和文献[11]中的类同态加密方案，明显扩展了IBE方案的同态功能，使其性能得到了很大提升。

在现有的IBFHE方案范围内作效率分析。与文献[14]中的方案—— CM（ClearMcgoldrick）方案进行比较，本文方案在构造方法上更加自然和直观，密文计算直接对应到矩阵的加乘运算。本文方案在计算过程中不需要先用加密过的私钥对密文进行同态解密，达到控制噪声的目的之后，得到新鲜密文参与到下一层电路的计算，即不需要进行同态解密的操作。CM方案的噪声在同态计算中将以两级指数的形式增长，而本文方案因为运用了密文校平技术，当运行深度为L的布尔电路时，噪声至多为（N+1）LB，可以更好地控制噪声增长，结果如表1。

与GSW方案[9]进行比较，虽然使用了相同的转化机制，但由于GSW方案中采用了CHKP10的IBE方案，而本文采用了ABB10b的IBE方案作为转化对象，后者相较于前者在效率上具有很大提升，所以本文方案效率更高。下面从密文长度、密钥长度以及格维数3个方面进行比较，结果如表2。

4结语

本文基于LWE问题，利用Gentry等[9]提出的全同态转化机制，结合Agrawal等[15]提出的HIBE方案，构造了一个新的HIBFHE方案，在随机预言机模型下证明是INDIDCPA安全的。与半同态和类同态IBE方案相比，提升了方案的同态运算能力；与现有的IBFHE方案相比，构造方法更加自然和直观，经过同态计算后密文维数不会增加，利用密文校平技术将噪声控制在解密正确的范围内，具有更高的效率。

基于属性的加密（ABE）作为IBE的扩展和延伸，把IBE中表示用户身份的唯一标识，扩展成为由多个属性组成的属性集合，还将访问结构融入到属性集合中，具备细粒度访问控制的能力，更能适应当前互联网的发展需求。下一步将对具备同态性质的ABE方案进行探索和研究。

参考文献：

[1]

RIVEST R L， ADLEMAN L， DERTOUZOS M L. On data banks and privacy homomorphisms [J]. Foundations of Secure Computation， 1978， 4（11）： 169-180.

[2]

BENALOH J. Dense probabilistic encryption [C]// Proceedings of the 1994 Workshop on Selected Areas of Cryptography. Berlin： Springer， 1994： 120-128.

[3]

PAILLIER P. Publickey cryptosystems based on composite degree residuosity classes [C]// EUROCRYPT99： Proceedings of the 17th International Conference on Theory and Application of Cryptographic Techniques. Berlin： Springer， 1999： 223-238.

[4]

BONEH D， GOH E J， NISSIM K. Evaluating 2DNF formulas on ciphertexts [C]// TCC05： Proceedings of the Second International Conference on Theory of Cryptography. Berlin： Springer， 2005： 325-341.

[5]

GENTRY C. Fully homomorphic encryption using ideal lattices [C]// Proceedings of the 41st ACM Symposium on Theory of Computing. New York： ACM， 2009： 169-178.

[6]

VAN DIJK M， GENTRY C， HALEVI S， et al. Fully homomorphic encryption over the integers [C]// EUROCRYPT10： Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2010： 24-43.

[7]

SMART N P， VERCAUTEREN F. Fully homomorphic encryption with relatively small key and ciphertext sizes [C]// PKC10： Proceedings of the 13th International Conference on Practice and Theory in Public Key Cryptography. Berlin： Springer， 2010： 420-443.

[8]

GENTRY C， HALEVI S， SMART N P. Fully homomorphic encryption with polylog overhead [C]// EUROCRYPT12： Proceedings of the 31st Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2012： 465-482.

[9]

GENTRY C， SAHAI A， WATERS B. Homomorphic encryption from learning with errors： conceptuallysimpler， asymptoticallyfaster， attributebased [C]// CRYPTO 2013： Proceedings of the 33rd Annual Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2013： 75-92.

[10]

SHAMIR A. Identitybased cryptosystems and signature schemes [C]// Proceedings of CRYPTO 84 on Advances in Cryptology. Berlin： Springer， 1984： 47-53.

[11]

GENTRY C， HALEVI S， VAIKUNTANATHAN V. A simple BGNtype cryptosystem from LWE [C]// EUROCRYPT10 Proceedings of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2010： 506-522.

[12]

CLEAR M， HUGHES A， TEWARI H. Homomorphic encryption with access policies： characterization and new constructions [C]// AFRICACRYPT 2013： Proceedings of the 6th International Conference on Cryptology in Africa. Berlin： Springer， 2013： 61-87.

[13]

COCKS C. An identity based encryption scheme based on quadratic residues [C]// Proceedings of the 8th IMA International Conference on Cryptography and Coding. Berlin： Springer， 2001： 360-363.

[14]

CLEAR M， MCGOLDRICK C. Bootstrappable identitybased fully homomorphic encryption [C]// CANS 2014： Proceedings of 13th International Conference on Cryptology and Network Security. Berlin： Springer， 2014： 1-19.

[15]

AGRAWAL S， BONEH D， BOYEN X. Lattice basis delegation in fixed dimension and shorterciphertext hierarchical IBE [C]// CRYPTO 2010： Proceedings of the 30th Annual Cryptology Conference on Advances in Cryptology. Berlin： Springer， 2010： 98-115.

[16]

REGEV O. On lattices， learning with errors， random linear codes， and cryptography [J]. Journal of the ACM， 2009， 56 （6）： Article No. 34.

[17]

BRAKERSKI Z， LANGLOIS A， PEIKERT C， et al. Classical hardness of learning with errors [C]// Proceedings of the 2013 Fortyfifth Annual ACM Symposium on Theory of Computing. New York： ACM， 2013： 575-584.