本技术公开了一种改进的格上基于身份的全同态加密方法。该方法按照以下步骤实施：首先
利用一种新型陷门函数与对偶LWE
算法相结合，构造一个改进的标准模型下格上基于身份
的加密方案，然后利用特征向量的思想将该方案转化为一个改进的标准模型下格上基于身份
的全同态加密方案。本技术所公开的方法消除了基于身份全同态加密运算密钥的问题，且所
生成的格的维数更低，具有更高的实际应用可行性。
权利要求书
1.
一种改进的格上基于身份的全同态加密方法，其特征在于采用两层结构设计：首先将新型
陷门函数与对偶LWE
算法相结合，构造一个改进的标准模型下格上基于身份的加密方案
iIBE
，然后利用特征向量方法将iIBE
转化为标准模型下格上基于身份的全同态加密方案
IBFHE
；IBFHE
方案包括私钥生成中心，云服务方，消息发送方和消息接收方，它们之间采
用双向通信；
所述改进的格上基于身份的全同态加密方法具体实施步骤是：
首先构造标准模型下的格上基于身份的加密方案iIBE
：
iIBE方案需要以下基本参数：均匀随机矩阵和其陷门其中n
是安全参数，m
＝O(n log q)，w
＝nk，模数q
＝q(n)；构造一个公开矩阵其中In
是n×n单位矩阵，FRD
编码函数H1:
系统建立算法iIBE-Setup(1n)：选取均匀随机矩阵选取n维均匀随机向量运行陷门生成算法
TrapGen(1n,1m,q,H)，其中为随机的可逆矩阵；输出矩阵和格Λ
⊥(A)的陷门矩阵输出MPK
＝
(A,u)
，MSK
＝R
；
用户密钥提取算法iIBE-Extract(MPK,MSK,id)
：利用FRD
编码函数H1:
将用户身份id
映射为一个可逆矩阵运行原像采样算法SampleL(A,Hid·G,R,u,σ)
，输出用户密钥e
，满足Aide
＝u
，其中加密算法iIBE-Enc(MPK,id,b)
：为加密明文消息b
∈{0,1}，选取均匀随机向量选取均匀随机矩阵计算其中容错量容错向量输出密文
解密算法iIBE-Dec(MPK,e,CT)：计算如果输出1
，否则输出0
；
在此基础之上，将iIBE
方案转化为IBFHE
方案：
IBFHE
需要以下基本参数：L
为同态运算的最大电路深度，模数q
＝q(n,L)，令N
＝(m+1)·l，对任意维向量a
，b
，BitDecomp(a)
表示N维向量其中ai,j
表示ai
分量的第j个二进制位，表示
BitDecomp
的逆运算，Flatten(a)
＝BitDecomp(BitDecomp-1(a))，且有以下等式成立：
＝
，
＝
＝
；
系统建立算法IBFHE-Setup(1n,1L):
调用iIBE-Setup算法，输出MPK
＝(A,u)
，MSK
＝R
；
用户密钥生成算法IBFHE-KeyGen(R,id):
调用iIBE-Extract
算法生成用户密钥，重新定义用户密
钥e为并令
同态加密算法IBFHE-Enc(MPK,id,μ
∈{0,1}):
为加密μ
∈{0,1}，构造矩阵矩阵的行为调用iIBE-
Enc
算法生成0
的N
个密文，每行的密文形式为：C′i
＝(c0,c1T)；输出其中ΙN
为N
维单位矩
阵；
同态解密算法IBFHE-Dec(C,v):计算已知v
的前l
个系数为1,2,...,2l-1
，令v[i]
＝2i
∈(q/4,q/2]
，Ci
为C
的第i
行；计算xi←
〈Ci,v
〉，输出μ
＝xi/v[i]
；
同态运算算法IBFHE-Eval(f,C1,C2,...,Ct):
算法的输入为运算函数f:{0,1}t→{0,1}
和属于同一身
份id
的一组密文(C1,C2,...,Ct)
，输出为一个新的密文Cf
；
同态加法：同态乘法：
技术说明书
一种改进的格上基于身份的全同态加密方法
技术领域
本技术涉及信息安全技术领域，具体涉及一种改进的格上基于身份的全同态加密方法，该方
法支持云环境下的隐私信息检索和密文计算，可用于保护云端数据和用户隐私。
背景技术
近几年，云计算受到广泛关注，而它在实现中遇到的问题之一就是如何保证数据的私密性，
全同态加密可以很好地解决这个技术难题。利用同态加密来保护数据的私密性，这个概念最
早由R.Rivest
等人于1978
年提出。直到2009
年，IBM
研究员C.Gentry
基于理想格提出第一个全
同态加密方案，此后，具备类似功能的密码方案的设计成为密码学研究领域的热点。
全同态加密作为公钥加密的一种，需要考虑在云环境和安全多方计算中身份认证的问题，一
般方法是引入公钥证书，但同时，证书中心的存在也为整个密码系统带来存储、计算、通信
与管理等方面的额外开销，而且已有的全同态加密体制普遍存在公钥尺寸过大的问题，因此
与证书相关的开销将严重影响全同态加密体制在实际应用中的效率。虽然近几年该体制的计
算效率得到更进一步的优化，但对于公钥尺寸过大的问题，目前仍无根本的解决方案。基于身份加密体制(IBE,Identity-based Encryption)
使用用户的唯一身份标识(
如手机号码，邮箱
地址等)
作为公钥，用户的私钥由可信第三方私钥生成中心(KGC,KeyGeneration Center)
利用
系统主私钥生成，因此无需公钥证书，所以IBE
体制消除了与证书有关的计算和存储，可以
更有效的管理密钥，减小密钥尺寸。因此，研究者们开始研究如何将基于身份加密的思想与
全同态加密相结合。然而，以往的基于身份的全同态加密(IBFHE,Identity-based Fully
Homomorphic Encryption)
方案都需要借助运算密钥来实现，并非真正意义上的IBFHE
方案。
2013
年C.Gentry
等人利用特征向量的方法构造出一个新型的全同态加密方案，并提出一个转
化机制，满足相应转化条件的格上IBE
方案可转化为格上IBFHE
方案，转化后的方案成功的
消除了运算密钥，实现了真正意义上的IBFHE
方案。因此，在构造格上IBFHE
方案之前需要
先构造一个能够满足转化条件的格上IBE
方案。
然而，现有的大多格上IBE
方案在原像采样过程方面，原像采样算法复杂度过高，需要执行
高精度实数的正交化迭代运算；在陷门生成方面，陷门生成算法复杂度过高、运行时间过
长，输出“
质量”(
指陷门的Gram-Schimt
正交范数的最大值)
不理想，不能够满足实际应用。为
使格上IBFHE
更具有实际应用可行性，必须解决陷门生成过程低效和原像采样过程复杂的问
题。
技术内容
本技术的目的是克服现有技术的不足，提供一种改进的格上基于身份的全同态加密方法，首
先将新型陷门函数与对偶LWE
算法相结合，构造出格上IBE
方案，然后利用特征向量的思想
将格上IBE
方案转化为格上IBFHE
方案。
为达到上述目的，本技术采用如下加密方案：
系统建立算法Setup(1n)→(MPK,MSK)
：输入安全参数n
，运行陷门生成算法
TrapGen(1n,1m,q,H)
，输出均匀随机矩阵A
和格Λ
⊥(A)
的陷门矩阵R
，输出MPK
＝(A,u)
，MSK
＝R
。
用户密钥提取算法Extract(MPK,MSK,id)→e
：输入系统主公钥和主私钥(MPK,MSK)
，密钥生成中心调用原像采样算法SampleL(A,Hid·G,R,u,σ)
，输出e
，输出用户密钥v
＝(1,-e)
。
同态加密算法Enc(MPK,id,μ
∈{0,1})→C
：输入系统主公钥MPK
＝(A,u)
，用户身份id
，明文消
息μ
，为加密μ
∈{0,1}
，构造矩阵C′
，矩阵的行为调用基于身份加密方案中的加密算法IBE-
Enc
算法生成0
的N
个密文，每行的密文形式为：C′i
＝(c0,c1T)
。将构造后密文矩阵进行噪音
校平操作(Flatten)
后输出。
同态解密算法Dec(C,v)→μ
：输入用户密钥v
和需要解密的密文C
，输出明文μ
。
同态运算算法Eval(f,C1,C2,...,Ct)→Cf
：输入运算函数f:{0,1}t→{0,1}
和属于同一身份id
的一组
密文(C1,C2,...,Ct)
，输出为一个新的密文Cf
。
本技术具有以下优点和积极效果：
1)
本技术是一种基于高效安全的陷门函数所构造的加密方法，在陷门生成和原像采样的阶段
具有较低的复杂度，且所生成的格的维数更低，从而使与格的维数相关的其它参数依次被优
化。
2)
本技术是一种具有更高安全性的加密方法，所基于的难题可归约至格上最短无关向量问题
(SIVP)
，且SIVP近似因子缩小倍，因此本方法所基于的难题具有更高的难解性。
3)
本技术是一种利用特征向量思想转化的格上基于身份的全同态加密方法，消除了以往格上
基于身份的全同态加密方法中运算密钥的问题，从而本技术的公私钥尺寸更加短小。
附图说明
图1
是一种改进的格上基于身份的全同态加密模型图。
具体实施方式
以下结合实施例和附图对本技术作进一步描述。