基于多身份的全同态加密方案，利用基于身份加密(IBE, identity-based encryption)方案无需公钥证书的特性来解决FHE(fully homomorphic encryption)方案公钥尺寸过大的问题，从而更有效地管理密钥，降低密钥和密文的尺寸，为加快全同态加密方案的应用具有重要意义. Gentry等^[1]利用特征向量思想提出首个基于身份的全同态加密(IBFHE, identity-based fully homomorphic encryption)方案. Clear等^[2]提出一种可自举的IBFHE方案，该方案的同态运算具有可任意次计算的优点.康元基等^[3-4]分别利用任意次分圆环和NTRU格的特性提出高效的IBFHE方案，但二者均基于随机预言模型. Clear等^[5]于Crypto'15上对Gentry等^[1]的工作进行了改进，提出一种基于多身份的全同态加密(mIBFHE, multi-identity based fully homomorphic encryption)方案，但该方案是随机预言模型下可证明是安全的.以上方案的陷门函数过于低效，主要采用的是陷门生成算法^[6-8]，因其含有计算复杂的HNF和矩阵求逆操作而过于复杂，且所基于的Gentry等^[8]的原像采样算法需执行高精度实数的正交化迭代运算，导致原像采样的复杂度过高，不具有实际应用性.

为使格上mIBFHE方案更具有实际应用性，必须解决陷门函数低效的问题.作者针对文献[5]所述的mIBFHE方案，提出一种改进方案.主要包括：1)利用Micciancio和Peikert^[9]于Eurocrypt'12上提出的MP12陷门函数，结合文献[10]中的对偶Regev算法，构造出一种可转化的基于身份的加密方案；2)对文献[5]中转化机制中的Mask系统进行重构，提出一种支持标准模型下IBE转化的Mask系统；3)结合该系统和特征向量的思想将1)中提出的IBE方案成功转化为mIBFHE方案.

1 预备知识 1.1 格的相关定义

定义1(格的定义)  设b₁, b₂, …, b_m是$ {\mathbb{R}^n} $上m个线性无关向量，格Λ定义为所有这些向量的整系数线性组合，即$ \mathit{\Lambda } = \left\{ {\sum\limits_{i = 1}^m {{x_i}{\mathit{\boldsymbol{b}}_i}:{x_i} \in \mathbb{Z}, i = 1, 2, \cdots, m} } \right\} $，其中向量组b₁, b₂, …, b_m称为格的一组基.

定义2(q元格)  设$ q, n, m \in \mathbb{Z}, A \in \mathbb{Z}_q^{n \times m} $，且$ \mathit{\boldsymbol{u}} \in \mathbb{Z}_q^n $，定义

$ \begin{array}{l} {\mathit{\Lambda }^ \bot }\left( \mathit{\boldsymbol{A}} \right) = \left\{ {\mathit{\boldsymbol{x}} \in {\mathbb{Z}^m}:\mathit{\boldsymbol{Ax}} = \mathit{\boldsymbol{0}}\bmod \;q} \right\}\\ \mathit{\Lambda }_\mathit{\boldsymbol{u}}^ \bot \left( \mathit{\boldsymbol{A}} \right) = \left\{ {\mathit{\boldsymbol{x}} \in {\mathbb{Z}^m}:\mathit{\boldsymbol{Ax}} = \mathit{\boldsymbol{u}}\bmod \;q} \right\} \end{array} $

(1)

即所有与矩阵A行向量模q内积为0的m维列向量构成格Λ^⊥(A)；格Λ_u^⊥(A)是格Λ^⊥(A)的陪集，满足Λ_u^⊥(A)=Λ^⊥(A)+t，其中t∈Λ_u^⊥(A).

定义3(离散高斯分布)  对任意σ > 0，定义以向量c为中心，σ为参数的格Λ上的离散高斯分布为

$ {D_{\mathit{\Lambda }, \sigma, \mathit{\boldsymbol{c}}}}\left( \mathit{\boldsymbol{y}} \right) = \frac{{{\rho _{\sigma, \mathit{\boldsymbol{c}}}}\left( \mathit{\boldsymbol{y}} \right)}}{{{\rho _{\sigma, \mathit{\boldsymbol{c}}}}\left( \mathit{\Lambda } \right)}} = \frac{{{\rho _{\sigma, \mathit{\boldsymbol{c}}}}\left( \mathit{\boldsymbol{y}} \right)}}{{\sum\limits_{y \in \mathit{\Lambda }} {{\rho _{\sigma, \mathit{\boldsymbol{c}}}}\left( \mathit{\boldsymbol{y}} \right)} }} $

其中：y∈Λ，ρ_{σ, c}(y)=exp(-π‖y-c‖/σ²).

1.2 相关算法和困难问题

本文方案构造所基于的MP12陷门生成算法和与之对应的MP12原像采样算法分别由引理1和引理2给出；对偶Regev算法的具体描述请参阅文献[10]；方案的正确性证明基于引理1、引理2、定义4和定义5；方案的安全性证明基于引理1，引理3、引理4和定义4.

引理1^[10]  设整数n≥1，q≥2和充分大的m=O(nlog q)，m=m-nk，w=nk，k=$ \left\lceil {\log \;q} \right\rceil $，可逆矩阵$ \mathit{\boldsymbol{H}} \in \mathbb{Z}_q^{n \times n} $，构造公开的矩阵$ \mathit{\boldsymbol{G}} \in \mathbb{Z}_q^{n \times w} $.选取一个均匀随机矩阵$ \mathit{\boldsymbol{\bar A}} \in \mathbb{Z}_q^{n \times \bar m} $，存在概率多项式时间(PPT, probabilistic polynomial time)算法TrapGen(1ⁿ, q)，输出矩阵$ \mathit{\boldsymbol{A}} = \left[{\mathit{\boldsymbol{\bar A|HG}}-\mathit{\boldsymbol{\bar AR}}} \right] \in \mathbb{Z}_q^{n \times m} $和陷门矩阵$ \mathit{\boldsymbol{R}} \in \mathbb{Z}_q^{\bar m \times w} $，陷门尺寸$ {s_1}\left( \mathit{\boldsymbol{R}} \right) \le \sqrt m \omega \left( {\sqrt {\log \;n} } \right) $，其中A在$ \mathbb{Z}_q^{n \times m} $上是统计均匀的，R是矩阵A的陷门.

引理2^[9]  与引理1参数相同，设$ \sigma = {s_1}\left( \mathit{\boldsymbol{R}} \right) \times \omega \left( {\sqrt {\log \;n} } \right) $是充分大的高斯参数，存在概率多项式时间算法SampleL(A_id, M, R, 0, σ)，其中$ \mathit{\boldsymbol{M}} \in \mathbb{Z}_q^{n \times w}, {\mathit{\boldsymbol{A}}_{\boldsymbol{\rm{id}}}} = \left[{\mathit{\boldsymbol{\bar A}}|{\mathit{\boldsymbol{H}}_{\boldsymbol{\rm{id}}}}\mathit{\boldsymbol{G}}-\mathit{\boldsymbol{\bar AR}}} \right] \in \mathbb{Z}_q^{n \times w} $，输出向量$ \mathit{\boldsymbol{e}} \in {\mathbb{Z}^m} $，且e的分布与$ {\mathscr{D}_{\mathit{\Lambda }_\mathit{\boldsymbol{u}}^ \bot \left( {{A_{\boldsymbol{\rm{id}}}}} \right), \sigma \omega \left( {\sqrt {\log \;n} } \right)}} $统计不可区分，

$ \Pr \left[{\mathit{\boldsymbol{e}} \leftarrow {\mathscr{D}_{\mathit{\Lambda }_u^ \bot \left( {{\mathit{\boldsymbol{A}}_{\boldsymbol{\rm{id}}}}} \right), \sigma \omega \left( {\sqrt {\log \;n} } \right)}}:\left\| \mathit{\boldsymbol{e}} \right\| > \sigma \sqrt m } \right] \le {\rm{negl}}\left( n \right) $

引理3^[11]  与引理1参数相同，设$ \sigma = {s_1}\left( \mathit{\boldsymbol{R}} \right)\left\| {\mathit{\boldsymbol{\bar R}}} \right\|\omega \left( {\sqrt {\log \;n} } \right) $是充分大的高斯参数，存在PPT算法SampleR(A, G, T_G, 0, σ)，输出向量$ \mathit{\boldsymbol{e}} \in {\mathbb{Z}^{m + \ell w}} $，且e的分布与$ {\mathscr{D}_{\mathit{\Lambda }_\mathit{\boldsymbol{u}}^ \bot \left( {{\mathit{\boldsymbol{A}}_{\boldsymbol{\rm{id}}}}} \right), \sigma \omega \left( {\sqrt {\log \;n} } \right)}} $统计不可区分.

引理4^[10]  与引理1参数相同，对于除了至多2q^-n部分的$ \mathit{\boldsymbol{A}} \in \mathbb{Z}_q^{n \times m} $和任意高斯参数$ \sigma \ge \omega \left( {\sqrt {\log \;m} } \right) $，有$ \mathit{\boldsymbol{e}} \in {D_{{\mathbb{Z}^m}, \sigma }} $，其中$ {D_{{\mathbb{Z}^m}, \sigma }} $为离散高斯分布，所得u=Aemod q的分布和$ \mathbb{Z}_q^n $上的均匀分布是统计不可区分的.

定义4^[12]  容错学习问题.设n为正整数，q为素数，对任意$ 0 < \alpha \le 1/\omega \left( {\sqrt {\log \;n} } \right) $，定义Ψ_α为中心是0，标准差是$ \alpha /\sqrt {2{\rm{ \mathsf{ π} }}} $的[0, 1)上的正态分布，对应的$ {\mathbb{Z}_q} $上的离散分布为Ψ_α.设χ为$ {\mathbb{Z}_q} $上的容错分布，($ {\mathbb{Z}_q} $, n, χ)-LWE问题实例由未指明的挑战预言机$ \mathscr{O} $构成：预言机$ \mathscr{O} $是带噪音的伪随机预言机$ \mathscr{O}$_s或者是真随机的预言机$ \mathscr{O} $_＄，2种预言机的输出如下.

$ {\mathscr{O}_s} $：输出的采样值形式为(u_i, v_i)=(u_i, u_i^Ts+x_i)∈$ \mathbb{Z}_q^n \times {\mathbb{Z}_q} $，其中$ \mathit{\boldsymbol{s}} \in \mathbb{Z}_q^n $是随机均匀且不变的秘密向量；

$ \mathscr{O} $_＄：输出$ \mathbb{Z}_q^n \times {\mathbb{Z}_q} $上的真随机且均匀的采样值.

($ {\mathbb{Z}_q} $, n, χ)-LWE问题允许对挑战预言机$ \mathscr{O} $重复查询.笔者称一个攻击算法$ \mathscr{A} $可以解决($ {\mathbb{Z}_q} $, n, χ)-LWE问题，如果LWE-adv[$ \mathscr{A} $]=|Pr[$ \mathscr{A}^{{{\mathscr{O}_s}}} $=1]-Pr[$ \mathscr{A}^{{{\mathscr{O}_＄}}} $=1]|是不可忽略的，其中LWE-adv[$ \mathscr{A} $]表示$ \mathscr{A} $解决($ {\mathbb{Z}_q} $, n, χ)-LWE问题的优势.

定义5^[1]  设整数B < q，对于分布集合{χ_n}_{n∈$ \mathbb{N} $}，如果对所有的整数有$ \mathop {\Pr }\limits_{\mathit{\boldsymbol{e}} \leftarrow {\chi _n}} \left[{\left\| \mathit{\boldsymbol{e}} \right\| > B} \right] = {\rm{negl}}\left( n \right) $，则称分布χ_n是B-界分布.

2 方案构造 2.1 符号说明

对文中符号进行说明，如表 1所示.

2.2 高效的基于身份的加密方案

基于MP12陷门函数，结合对偶Regev算法完成格上高效IBE方案构造，其结合的理论依据是：Gentry等^[10]于STOC'08上提出基于对偶Regev算法的格上IBE方案，并指出基于常规LWE加密算法构造格上IBE方案存在用户公钥指数稀疏的问题；Micciancio等^[9]于Eurocrypt'12上提出MP12陷门函数，并指出其可提高以往格上IBE方案，但未给出具体方案及思路.

为方便mIBFHE方案的构造，对对偶Regev算法进行改造，结合MP12高效陷门函数完成方案构造.所构造的方案与同类方案相比，在不降低方案安全性的前提下，使格的维数、主私钥尺寸、身份公钥尺寸和密文尺寸均有效缩短(见4.1节效率分析).方案的基本参数包括：均匀随机矩阵$ \mathit{\boldsymbol{A}} \in \mathbb{Z}_q^{n \times m} $和其陷门矩阵$ \mathit{\boldsymbol{R}} \in {\mathbb{Z}^{\bar m \times w}} $，其中n是安全参数，充分大的m=O(nlog q)，m'=m+1，m=m-nk，w=nk，$ k = \left\lceil {\log \;q} \right\rceil $，模数q=q(n)；构造公开的矩阵$ \mathit{\boldsymbol{G}} = {\mathit{\boldsymbol{I}}_n} \otimes {\mathit{\boldsymbol{g}}^{\rm{T}}} \in \mathbb{Z}_q^{n \times nk} $，其中g^T=[1, 2, 2², …, 2^k-1]∈$ \mathbb{Z}_q^k $，I_n为n×n单位矩阵；FRD函数^[11]$ H:\mathbb{Z}_q^n \to \mathbb{Z}_q^{n \times n} $.

IBE-Setup(1ⁿ)：输入安全参数n，选取一个均匀随机矩阵$ \mathit{\boldsymbol{\bar A}} \in \mathbb{Z}_q^{n \times \bar m} $，选取一个n维均匀随机向量$ \mathit{\boldsymbol{u}} \in \mathbb{Z}_q^n $，运行引理1的MP12陷门生成算法TrapGen(1ⁿ, 1^m, q, I_n)，输出矩阵$ \mathit{\boldsymbol{A}} = \left[{\mathit{\boldsymbol{\bar A}}|-\mathit{\boldsymbol{\bar AR}}} \right] \in \mathbb{Z}_q^{n \times m} $和A的陷门矩阵$ \mathit{\boldsymbol{R}} \in \mathbb{Z}_q^{\bar m \times w} $，输出系统主公钥MPK=(A, u)，主私钥MSK=R.

IBE-Extract(MPK, MSK, id)：输入主公钥MPK、主私钥MSK和用户身份向量id∈$ \mathbb{Z}_q^n $.利用FRD函数$ H:\mathbb{Z}_q^n \to \mathbb{Z}_q^{n \times n} $将用户身份向量id映射为一个可逆矩阵H_id∈$ \mathbb{Z}_q^{n \times n} $，构造用户身份公钥矩阵为A_id=[A|H_idG-AR]∈$ \mathbb{Z}_q^{n \times m} $，设A_id'=[u|A_id] $ \mathbb{Z}_q^{n \times m'} $，运行引理2中的MP12原像采样算法SampleL(A_id, R, I_n, u, σ)，输出用户密钥e_id∈$ {\mathbb{Z}^m} $，重新定义用户密钥为s_id=(1, -e_id)∈$ {\mathbb{Z}^{m'}} $，满足A_id's_id=0.

IBE-Encrypt(MPK, id, μ)：输入主公钥MPK、用户身份向量id∈$ \mathbb{Z}_q^n $和待加密的明文消息μ∈{0, 1}.设μ∈$ \mathbb{Z}_q^{m'} $是除第一分量是$ \mu \left\lfloor {q/2} \right\rfloor $的m'维零向量.选取均匀随机向量$ \mathit{\boldsymbol{s}} \leftarrow \mathbb{Z}_q^n $，选取均匀随机矩阵R←{-1, 1}^m×w，计算$ \mathit{\boldsymbol{c}} = {\mathit{\boldsymbol{s}}^{\rm{T}}}{\mathit{\boldsymbol{A'}}_{\boldsymbol{\rm{id}}}} + \mathit{\boldsymbol{\mu }} + \left[\begin{array}{l} \;\;x\\ \;\;\mathit{\boldsymbol{y}}\\ {{\mathit{\boldsymbol{\bar R}}}^{\rm{T}}}\mathit{\boldsymbol{y}} \end{array} \right] \in \mathbb{Z}_q^{m'} $，其中容错值$ x\mathop \leftarrow \limits^{{{\mathit{\bar \Psi }}_\alpha }} {\mathbb{Z}_q} $，容错向量$ \mathit{\boldsymbol{y}}\mathop \leftarrow \limits^{\mathit{\bar \Psi }_\alpha ^{\bar m}} \mathbb{Z}_q^{\bar m} $，输出密文$ \mathit{\boldsymbol{c}} \in \mathbb{Z}_q^{m'} $.

IBE-Decrypt(MPK, s_id, c)：输入主公钥MPK、用户密钥s_id和待解密密文c.设δ←〈s_id, c〉，如果$ \delta < \left\lfloor {q/4} \right\rfloor $，输出1，否则输出0.

2.3 支持标准模型下IBE转化的Mask系统

Clear等^[5]提出的转化机制能将满足相应转化条件的IBE方案转化为mIBFHE，其转化机制要求IBE方案满足以下条件：

1) 密文和用户密钥均为向量形式，且用户密钥向量的第一个分量是1；

2) 若密文c是对消息比特"0"的加密，则c与用户密钥的点积〈s_id, c〉相对模数q是可忽略不计的；

3) 在LWE难题的假设下，对消息比特"0"的加密密文与$ {\mathbb{Z}_q} $上的均匀向量不可区分；

4) 存在一个正确且安全的Mask系统.

不难看出，2.2节构造的IBE方案满足前3个条件.事实上，满足前3个条件可利用Gentry等^[1]构造的转化机制将IBE方案成功转化为IBFHE方案.如果再满足条件4)，则可以利用Clear等的转化机制将IBE转化为mIBFHE方案.

步骤4)中的Mask系统是构造mIBFHE方案的关键机制，下面对该机制的作用和功能进行举例解释：假设C₁和C₂分别是明文μ₁和μ₂利用身份id₁和id₂加密得到的密文，令v_id1和v_id2分别是身份id₁和id₂对应的同态解密密钥.则有解密算式C₁v_id1=μ₁v_id1+z₁，C₂v_id2=μ₂v_id2+z₂成立，其中z₁, z₂∈$ \mathbb{Z}_q^N $为容错向量.如果想对密文C₁和C₂进行同态运算，即将它们输入到同一运算电路C中.紧凑性条件要求输出的密文尺寸与参与者数量D多项式相关.假设运算密文涉及的参与方为D=2，则输出的运算结果为$ \mathit{\boldsymbol{C'}} \in \mathbb{Z}_q^{2N \times 2N} $，那么C'的解密结果应为μ'=C(μ₁, μ₂)，即

$ \mathit{\boldsymbol{C'}}\begin{array}{*{20}{c}} {\left[\begin{array}{l} {\mathit{\boldsymbol{v}}_{{\boldsymbol{\rm{id}}_{\rm{1}}}}}\\ {\mathit{\boldsymbol{v}}_{{\boldsymbol{\rm{id}}_{\rm{1}}}}} \end{array} \right]} \end{array} = \mu '\left[\begin{array}{l} {\mathit{\boldsymbol{v}}_{{\boldsymbol{\rm{id}}_{\rm{1}}}}}\\ {\mathit{\boldsymbol{v}}_{{\boldsymbol{\rm{id}}_{\rm{1}}}}} \end{array} \right] + \mathit{\boldsymbol{z'}} $

(2)

其中$ \mathit{\boldsymbol{z'}} \in \mathbb{Z}_q^{2N} $为容错向量.可以看出，输出密文的尺寸与参与者数量D呈二次增长关系，则满足紧凑性条件.这个例子的难题是如何生成C'，Mask系统可解决该难题.

令$ {\mathit{\boldsymbol{C'}}_1} \in \mathbb{Z}_q^{2N \times 2N} $为密文C₁的膨胀密文，则

$ {\mathit{\boldsymbol{C'}}_1}\left[\begin{array}{l} {\mathit{\boldsymbol{v}}_{{\boldsymbol{\rm{id}}_1}}}\\ {\mathit{\boldsymbol{v}}_{{\boldsymbol{\rm{id}}_2}}} \end{array} \right]\mathit{\boldsymbol{ = }}{\mu _1}\left[\begin{array}{l} {\mathit{\boldsymbol{v}}_{{\boldsymbol{\rm{id}}_1}}}\\ {\mathit{\boldsymbol{v}}_{{\boldsymbol{\rm{id}}_2}}} \end{array} \right] + \left[\begin{array}{l} {\mathit{\boldsymbol{z}}_1}\\ {\mathit{\boldsymbol{z}}_2} \end{array} \right] $

(3)

其中$ \mathit{\boldsymbol{z'}} \in \mathbb{Z}_q^{2N} $为容错向量.将C'视为由2×2个$ \mathbb{Z}_q^{N \times N} $子矩阵构成，令i, j分别表示C'行和列，为满足式(3)的上半部分，可将C₁'(1, 1)←C₁，C₁'(1, 2)←0；为满足式(3)的下半部分，需利用Mask系统计算矩阵X, Y∈{0, 1}^N×N以满足

$ \mathit{\boldsymbol{X}}{\mathit{\boldsymbol{v}}_{{\boldsymbol{\rm{id}}}_1}} + \mathit{\boldsymbol{Y}}{\mathit{\boldsymbol{v}}_{{\boldsymbol{\rm{id}}_2}}} = {\mu _1}{\mathit{\boldsymbol{v}}_{{\boldsymbol{\rm{id}}_2}}} + {\mathit{\boldsymbol{z}}_2} $

(4)

因此，在参与同态运算时，利用Mask系统可完成各个参与者的膨胀密文的构造，进而完成mIBFHE方案的构造.

而Clear等^[5]提出的转化机制所依赖的Mask系统只针对随机预言模型下的IBE方案.该转换机制利用文献[2]的IBE构造方法，需依赖随机预言机将用户身份信息哈希成用户公钥，然后利用数字签名的原理由用户公钥生成用户私钥.针对2.2节构造的标准模型下的IBE方案，下面给出一种支持标准模型下IBE转化的Mask系统.利用文献[13]中盆景树模型的方法消除方案对随机预言机的依赖，在系统主公钥矩阵中拼接均匀随机向量，然后结合文献[9]或文献[13]中的陷门派生算法和文献[10]或文献[9]中的原像采样算法生成用户私钥.

首先给出以下基础操作：

已知m'=m+1，令$ {\ell_q} = \left\lfloor {\log \;q + 1} \right\rfloor, N = m'{\ell_q}, \eta = n{\ell_q} $，对任意的m'维向量a，b，BitDecomp(a)表示N维向量$ \left( {{a_{1, 0}}, \cdots, {a_{1, {\ell_q} - 1}}, \cdots, {a_{m', 0}}, \cdots, {a_{m', {\ell_q} - 1}}} \right) $，其中a_{i, j}表示a_i分量的第j个二进制位，BitDecomp^-1(a)=$ \left( {\sum {{2^j}{a_{1, j}}}, \cdots, \sum {{2^j}{a_{m', j}}} } \right) $是BitDecomp的逆运算，Flatten(a)=BitDecomp(BitDecomp^-1(a))，Powersof2(b)=$ \left( {{b_1}, 2{b_1}, \cdots, {2^{{\ell_q} - 1}}{b_1}, \cdots {b_{m'}}, 2{b_{m'}}, \cdots, {2^{{\ell_q} - 1}}{b_{m'}}} \right) $，且有以下等式成立：

$ \begin{array}{l} \;\;\;\left\langle {{\rm{BitDecomp}}\left( \mathit{\boldsymbol{a}} \right), {\rm{Powersof}}2\left( \mathit{\boldsymbol{b}} \right)} \right\rangle = \left\langle {\mathit{\boldsymbol{a}}, \mathit{\boldsymbol{b}}} \right\rangle \\ \left\langle {\mathit{\boldsymbol{a}}, {\rm{Powersof}}2\left( \mathit{\boldsymbol{b}} \right)} \right\rangle = \left\langle {{\rm{BitDecom}}{{\rm{p}}^{ - 1}}\left( \mathit{\boldsymbol{a}} \right), \mathit{\boldsymbol{b}}} \right\rangle = \\ \;\;\;\;\;\;\;\;\;\;\;\left\langle {{\rm{Flatten}}\left( \mathit{\boldsymbol{a}} \right), {\rm{Powersof}}2\left( \mathit{\boldsymbol{b}} \right)} \right\rangle \end{array} $

基于以上基础操作，所提出的支持标准模型下IBE转化的Mask系统由以下2个算法构成.

1) GenUnivMask(MPK, id, μ)：输入系统主公钥MPK，用户身份信息id和明文μ.选取一个n维均匀随机向量$ \mathit{\boldsymbol{u}} \in \mathbb{Z}_q^n $，利用引理1中的TrapGen算法生成均匀随机矩阵A，设用户公钥A^id←u‖$ \mathit{\boldsymbol{A}} \in \mathbb{Z}_q^{n \times m'} $，对于i∈[N]，有

如果$ i \le {\ell_q} $：对于j∈[η-1]：调用2.2节中的IBE加密算法对明文信息μ·2ⁱ进行加密输出$ {\mathit{\boldsymbol{b}}_\eta } \in \mathbb{Z}_q^{m'} $，最后将b₁^T, …, b_η^T拼接成矩阵B_i.

如果$ i > {\ell_q} $：选取均匀随机向量$ \mathit{\boldsymbol{r}} \leftarrow \mathbb{Z}_q^n $，容错向量$ \mathit{\boldsymbol{z'}}\mathop \leftarrow \limits^{\mathit{\bar \Psi }_\alpha ^{m'}} \mathbb{Z}_q^{m'} $，计算c←(A^id)^Tr+z'∈$ \mathbb{Z}_q^{m'} $，r2←Powersof2(r)∈$ \mathbb{Z}_q^{m'} $.对于j∈[η]：选取均匀随机向量$ \mathit{\boldsymbol{s}} \leftarrow \mathbb{Z}_q^n $，容错向量$ \mathit{\boldsymbol{f}} \leftarrow {\mathbb{Z}^{m'}} $，设$ {\mathit{\boldsymbol{\omega }}_j} \leftarrow \left( {\mathit{\boldsymbol{r}}{2_j}, 0, \cdots, 0} \right) \in \mathbb{Z}_q^{m'} $，调用2.2节中的IBE加密算法对ω_j进行加密输出$ {\mathit{\boldsymbol{b}}_\eta } \in \mathbb{Z}_q^{m'}, \mathit{\boldsymbol{b}}_1^{\rm{T}}, \cdots, \mathit{\boldsymbol{b}}_\eta ^{\rm{T}} $拼接成矩阵B_i.令d←0∈{0, 1}^N，d_i←μ，计算u_i←BitDecomp^-1(d)+Flatten(c).

最后，B₁, …, B_N垂直拼接成矩阵$ \mathit{\boldsymbol{B}} \in \mathbb{Z}_q^{\left( {N + \eta } \right) \times m'}, \mathit{\boldsymbol{u}}_1^{\rm{T}}, \cdots, \mathit{\boldsymbol{u}}_N^{\rm{T}} $组成矩阵$ \mathit{\boldsymbol{U}} \in \mathbb{Z}_q^{N \times m'} $，输出U=(B, U).

2) DeriveMask(MPK, U, id')：输入系统主公钥MPK，U=(B, U)和任意的用户身份id'.令$ \mathscr{H} = \left\{ {H:{{\left\{ {0, 1} \right\}}^ * } \to \mathbb{Z}_q^n} \right\} $为一类一般的单向(或抗碰撞)哈希函数，设id"=BitDecomp(id')∈$ {\mathbb{Z}^\eta } $，1←(0, …, 0, 1)∈$ \mathbb{Z}_q^n $.在j∈[N]区间内：如果j≤[$ {\ell_q} $]，计算x_j←Powersof2(1)B_j，若$ {\ell_q} $≤j≤[N]，计算x_j←Powersof2(H(id"))B_j，x₁^T, …, x_N^T垂直拼接成$ {\mathit{\boldsymbol{X'}}_i} \in \mathbb{Z}_q^{N \times m'} $，最后计算X←BitDecomp(X')∈{0, 1}^N×N，Y←BitDecomp(U)∈{0, 1}^N×N，输出(X, Y).

2.4 基于多身份的全同态加密方案

在2.2节高效的基于身份的加密方案和2.3节支持标准模型下IBE转化的Mask系统的基础上，构造多身份的全同态加密方案相对容易.基本参数与2.3节相同，方案的具体构造如下.

mIBFHE-Setup(n, L, D)：输入安全参数n，系统支持的最大同态运算电路深度L和一次同态运算中可支持的不同身份的数量D.调用2.2节IBE方案中的IBE-Setup(1ⁿ)算法，输出系统主公钥MPK=(A, u)，主私钥MSK=R.

mIBFHE-KeyGen(MSK, id)：输入主公钥MPK=(A, u)和用户身份向量id∈$ \mathbb{Z}_q^n $，调用2.2节IBE方案中的IBE-Extract(MPK, MSK, id)算法，输出用户密钥s_id=(1, -e_id)∈$ {\mathbb{Z}^m}^\prime $.

mIBFHE-Encrypt(MPK, id, μ)：输入主公钥MPK=(A, u)，用户身份向量id∈$ \mathbb{Z}_q^n $和待加密明文消息μ∈{0, 1}，将μ转化为第一分量是$ \mu \left\lfloor {q/2} \right\rfloor $的m'维零向量$ \mathit{\boldsymbol{\mu }} \in {\mathbb{Z}_q} $.调用2.3节的GenUnivMask(MPK, id, μ)算法，输出U∈{0, 1}^*.输出密文C=(id, type=0, enc=U)，其中type=0表示该密文是"新鲜"密文(未经同态运算的密文).

mIBFHE-Eval(MPK, C, C₁, …, $ {\mathit{\boldsymbol{C}}_\ell} $)：输入主公钥MPK，密文运算电路C和一系列密文C₁=(id₁, type=0, enc=U₁), …, $ {\mathit{\boldsymbol{C}}_\ell} $=(id${_\ell} $, type=0, enc=$ U_\ell $).令I={id₁, id₂, …, id${_\ell} $}表示不同身份的集合，|I|=τ≤$ \ell $表示不同身份的个数.若τ > D即超出系统一次同态运算可支持的身份数量，算法终止. 设id₁, id₂, …, id_τ是输入的一系列用户身份中不相同的用户身份.在对密文进行同态运算前，需要将每个与用户身份id₁, id₂, …, id_τ对应的密文C₁, C₂, …, C${_\ell} $转换为τN×τN的膨胀密文.令(id_r, type=0, enc=U${_\ell} $)是相关身份id_r的密文，其中r∈[τ]，膨胀密文$ \mathit{\boldsymbol{\hat C}} $的具体计算过程如下.

先将$ \mathit{\boldsymbol{\hat C}} \in \mathbb{Z}_q^{\tau N \times \tau N} $设置为零矩阵，可将$ \mathit{\boldsymbol{\hat C}} $视为由τ×τ个子矩阵组成，将第i行j列的子矩阵表示为$ {\mathit{\boldsymbol{\hat C}}_{ij}} \in \mathbb{Z}_q^{N \times N} $.在i∈[τ]中，调用2.3节的DeriveMask(MPK, U, id')算法，返回(X_i, Y_i)，令$ {\mathit{\boldsymbol{\hat C}}_{i, i}} \leftarrow {\mathit{\boldsymbol{Y}}_i}, {\mathit{\boldsymbol{\hat C}}_{i, r}} \leftarrow {\mathit{\boldsymbol{C'}}_{i, r}} + {\mathit{\boldsymbol{X}}_i} $.

将输出的τ个膨胀密文输入运算电路C进行同态运算，若每个$ {\mathit{\boldsymbol{\hat C}}^{\left( i \right)}} $加密的明文消息是μ_i∈{0, 1}，则输出运算结果$ \mathit{\boldsymbol{\hat C'}} $加密的明文消息是C(μ₁, …, μ${_\ell} $).最后，输出三元组C=(id₁, …, id_d, type=1, enc=$ \mathit{\boldsymbol{\hat C'}} $)，其中type=1表示该密文已同态运算一次.

mIBFHE-Decrypt(MPK, v_id1, …, v_idτ, CT):输入主公钥MPK，待解密密文C=(id₁, …, id_τ, type, enc)和与用户身份id₁, …, id_τ相对应的用户密钥v_id1, …, v_idτ∈$ \mathbb{Z}_q^N $.令v=(v_id1^T‖…‖v_idτ^T)^T∈$ \mathbb{Z}_q^{dN} $为v_id1, …, v_idτ垂直拼接而成的向量.如果type=0，将enc解析为U并计算(X, Y)←(MPK, U, id₁)，设C←X+Y；如果type=1，将enc解析为$ \mathit{\boldsymbol{\hat C'}} $并设C←$ \mathit{\boldsymbol{\hat C'}} $.已知向量v的前$ {\ell_q} $个系数为1, …, 2^{$ {\ell_q} $-1}，设索引i满足v_i=2ⁱ∈(q/4, q/2]，令c_i为密文C的第i行，计算x_i←〈c_i, v〉，输出解密结果$ \mu \leftarrow \left\lfloor {{x_i}/{v_i}} \right\rfloor $.

3 安全性证明

通常，一个格上IBFHE方案的安全性应满足选择身份攻击和选择明文攻击下的密文不可区分性(IND-ID-CPA).格上mIBFHE方案的安全性因Mask系统存在而稍有不同，仅是在安全游戏中敌手被给予的挑战密文被2.3节中的U^*←GenUnivMask(MPK, id^*, μ_b)所代替(具体见以下安全性证明部分).根据安全强度不同，分为适应性选择身份选择明文攻击(IND-aID-CPA)和选择性选择身份选择明文攻击(IND-sID-CPA)，区别在于后者敌手需在攻击的初始化阶段向挑战者宣布欲攻击的目标身份，而前者可等到挑战阶段才宣布，且后者可在挑战阶段前的用户密钥查询阶段对任意的用户身份进行适应性的查询，后者的唯一限制是挑战阶段不能宣布之前查询过密钥的用户身份作为攻击目标.笔者的方案是IND-sID-CPA安全的，且挑战密文与密文空间的随机元素不可区分(INDr-sID-CPA)，因此保证了方案的语义安全和接收方的匿名性，且主公钥的私密性可被其创建的密文保护.

本方案采用Agrawal等^[11]在Eurocrypt'10上提出的标准模型下的INDr-sID-CPA安全模型进行安全性证明.基于该安全模型进行安全证明的还有Clear等^[2]提出的可自举IBFHE方案和康元基等^[3]提出的环LWE上IBFHE方案.

正确性：本文方案的解密正确性由定理1刻画.

定理1  mIBFHE方案的解密是正确的，对任意的(MPK, MSK)←Setup(λ, L, D)，用户身份id₁, …, id_τ∈$ \mathscr{I}, \mathscr{I} $为合法的用户身份空间，私钥向量v_idi←Powersof2(KeyGen(MSK, id_i))∈$ \mathbb{Z}_q^N $，U←GenUnivMask(MPK, id_i, μ)，(X_i, Y_i)←DeriveMask(MPK, U, id_i')，密文空间中的任意密文C，有Pr[Decrypt(MPK, v_id1, …, v_idτ, C)=μ]=1-negl(n)成立.

证明  方案解密算法的输出为

$ \begin{array}{l} \;\;\;\;\;\;\;\;\;{x_i}/{v_i} = \left\langle {{\mathit{\boldsymbol{c}}_i}, \mathit{\boldsymbol{v}}} \right\rangle /{v_i} = \\ \left\langle {\left( {\mu {{\left( {{\mathit{\boldsymbol{I}}_N}} \right)}_i} + {\rm{BitDecomp}}\left( {{\mathit{\boldsymbol{c}}_i}} \right)} \right), \mathit{\boldsymbol{v}}} \right\rangle /{v_i} = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {\mu {v_i}} \right)/{v_i} = \mu \end{array} $

为保证密文中的噪声小于q/4且q/B与安全参数n亚指数相关，对参数设定如下：由引理1可知，其TrapGen算法要求m≥2nlog q，参数B的取值取决于B_preimage和B_χ，由引理2可知B_preimage≤$\sigma \sqrt m $，由定义4和定义5可知B_χ≥${B_\chi } \ge \sqrt m \log \;n $，则B=R_quality×mlog²n，其中R_quality为陷门质量，即陷门矩阵R的最大奇异值s₁(R)，因此B=m^1.5log²n.设α是方案密文中容错项的膨胀因子，2.2节IBE方案的$ \alpha = \left\| {\mathit{\boldsymbol{\tilde R}}} \right\|\omega \left( {\sqrt {\log \;n} } \right) $，则q=B·2^{O(Llog nD)}.方案的参数设定如表 2所示.

安全性：本文方案的安全性由定理2刻画.

定理2  若($ {\mathbb{Z}_q}, n, {\mathit{\bar \Psi }_\alpha } $)-LWE的难解性成立，则在标准模型下mIBFHE方案是INDr-sID-CPA安全的.

证明  定理证明采用基于游戏序列的证明方法，证明敌手无法区分定义4中预言机$ \mathscr{O} $的输出是来自伪随机预言机$ {\mathscr{O}_s} $还是真随机预言机$ \mathscr{O}$_＄，从而证明敌手无法以不可忽略的优势在INDr-sID-CPA的Game中获胜.

Game 0  Game 0是一个标准的攻击本方案的敌手$ \mathscr{A} $与挑战者$ \mathscr{C} $之间进行的INDr-sID-CPA游戏.

Game 1  令id^*∈$\mathscr{I} $为敌手的目标用户身份.挑战者对预言机$ \mathscr{O} $进行询问并获取一组实例(u_i, v_i)∈$ \mathbb{Z}_q^n \times {\mathbb{Z}_q} $，其中i=1, …, m，利用实例(u_i, v_i)∈$ \mathbb{Z}_q^n \times {\mathbb{Z}_q} $生成随机均匀矩阵$ \mathit{\boldsymbol{A}} \in \mathbb{Z}_q^{n \times m} $，矩阵A的第i列是向量u_i，i=1, …, m，并将向量u作为公共随机向量u∈$ \mathbb{Z}_q^n $.将主公钥MPK=(A, u)发送给敌手$ \mathscr{A} $.

Game 0  与Game 1是统计不可区分的，原因在于：利用实例(u_i, v_i)生成的随机均匀矩阵A与引理1中的TrapGen算法输出的矩阵A是统计不可区分的，且公共随机向量u均为随机均匀选取，由引理4可知随机均匀选取的向量u与Game 0中的u=A_id·e_id是统计接近的，因此Game 0与Game 1是统计不可区分的.

Game 2  与Game 1不同的是，利用引理1中的TrapGen算法来生成G∈$ \mathbb{Z}_q^{n \times w} $和格Λ_q^⊥(G)的公开陷门矩阵T_G，A仍保留为Game1中的形式，则A_id=A+[0‖H_idG]=[A‖[H_id-H_id^*]G-AR]，由FRD函数的性质^[10]可知，[H_id-H_id^*]为可逆矩阵，则挑战者$ \mathscr{C} $可使用陷门矩阵T_G进行原像采样来回应敌手$ \mathscr{A} $的私钥查询：若id≠id^*，调用引理3中e_id←SampleR(A, (H_id-H_id^*)G, T_G, u, σ)算法，输出e_id并回应给攻击者；若id=id^*，则[H_id-H_id^*]为零矩阵不可逆，游戏终止.

Game 1与Game 2是统计不可区分的，原因在于：由引理3可知，当σ > s₁(R)‖R‖$ \omega \left( {\sqrt {\log \;n} } \right) $时，e_id的分布与Game 1中的分布$ {\mathscr{D}_{\mathit{\Lambda }_u^ \bot \left( {{\mathit{\boldsymbol{A}}_{\boldsymbol{\rm{id}}}}} \right), {\sigma _\ell}}} $是统计不可区分的.因此Game2中的私钥查询回应方法和矩阵G的构造与Game1是统计不可区分的.

For i∈[$ {\ell_q} $]：

Game i+1与之前的Game不同的是：将如2.3节所示的GenUnivMask算法中的b_η替换为随机选取的b_η← $ \mathbb{Z}_q^{m'} $.假设存在攻击者$ \mathscr{P} $能以不可忽略的优势来区分Game i与Game i+1，那么可以利用$ \mathscr{P} $来构造一个算法. $ \mathscr{B} $求解格上LWE实例.采用与Game 1中相同的方式构造公共参数(A, u)，且对攻击者的用户密钥查询方式与Game 2相同.

$ \mathscr{B} $运行与之前Game相同的GenUnivMask算法，但不同的是：将GenUnivMask算法中的b_η替换为b_η←x^*+(μ2ⁱ, 0, …, 0)∈$ \mathbb{Z}_q^{m'} $，其中x^*∈$ \mathbb{Z}_q^{m'} $是一个LWE挑战向量，该向量有2种可能：输出伪随机预言机$ {\mathscr{O}_s} $或真随机预言机$ {\mathscr{O}_＄} $，$ {\mathscr{O}_s} $和$ {\mathscr{O}_＄} $的输出分别与Game i和Game i+1是统计不可区分的.因此，算法$ \mathscr{B} $能够输出攻击者$ \mathscr{P} $的猜测来对LWE问题求解.

For $ {\ell_q} $ < i≤N：

  For j∈[η]：

Game(i, j)：与之前Game不同的是：将如3.3节所示的GenUnivMask算法中的B_i替换为随机选取的b_j←$\mathbb{Z}_q^{m'} $.与上述对Game i和Game i+1是统计不可区分的分析相同，Game(i, j)与Game(i, j+1)同样是统计不可区分的.

Game(i, η+1)：与之前Game不同的是：将如3.3节所示的GenUnivMask算法中的u_i替换为随机选取的u_i←$\mathbb{Z}_q^{m'} $.同样可利用上述对Game i和Gamei+1是统计不可区分的分析，来证明Game(i, η)与Game(i, η+1)是统计不可区分的.

可知，直到Game(N, η+1)结束，可以得出结论：明文比特信息μ被完全地安全隐藏在GenUnivMask算法所输出的U中，敌手从信息U中能获取到的优势为零.因此，敌手无法猜测出与之交互的是伪随机预言机$ {\mathscr{O}_s} $还是真随机预言机O_＄.

4 效率分析 4.1 基于身份加密方案效率分析

由于所构造的基于多身份的全同态加密方案是利用特征向量的思想由基于身份的加密方案转化而来，所以前者的效率很大程度上取决于后者.另外，为更好地理解基于多身份的全同态加密方案的效率分析，首先对基于身份加密方案的效率进行分析.

这里选择2个经典的与本文方案安全性相同的格上IBE方案进行效率对比：Agrawal等^[11]于Eurocrypt'10上提出的标准模型下选择性安全的高效格上IBE方案(简称CHKP方案)和Cash等^[13]于Eurocrypt'10上提出的首个标准模型下选择性安全的格上IBE方案(简称ABB方案).效率对比见表 3.

由表 3可看出，本文方案的主要效率参数和LWE容错率都有优化，表明与其他方案相比本方案的效率较好，且所基于的LWE问题更具有较高难解性.

首先是格的维数，由于CHKP方案和ABB方案基于文献[8]的陷门生成算法，为满足所基于困难问题同程度的安全性和支持方案主公钥参数与均匀分布的统计不可区分性需要较高的格维数.本方案的主私钥尺寸是在合理高斯分布上选取的一组短向量，而不是CHKP方案和ABB方案的某个格矩阵的一组基，且这组基可在无质量变差的情况下由主私钥生成. CHKP方案将用户身份看成一系列比特串，并为每一比特生成一个均匀随机的矩阵，然后拼接成用户的身份公钥矩阵，导致该矩阵的维数过大.而ABB方案和本文方案均采用FRD函数^[11]，将用户身份映射成一个n×n满秩矩阵，身份公钥矩阵的维数明显降低.因为本方案的用户私钥不再利用陷门派生算法和原像采样算法相结合的方式来生成，所以仅须生成一个均匀随机矩阵即可生成身份公钥.密文的尺寸与身份公钥尺寸直接相关.由于公开且构造特殊矩阵G参数的引入，本方案具有较低的LWE容错率，由G矩阵的构造容易计算‖G‖=$\sqrt 5 $，则$ 1/\alpha \ge 2\sqrt 5 \sigma \omega \left( {\sqrt {\log \;n} } \right) $.

4.2 基于多身份全同态加密方案效率分析

为充分展示本方案的效率，除与2015年Clear和McGoldrick于Crypto'15上提出的格上基于多身份的全同态加密方案^[5](简称CM方案)相比外，还选择了Wang等^[14]利用混淆器构造的一种高效的格上基于身份的全同态加密方案(简称WH方案).相比之下，本文方案基于标准模型，在陷门生成和原像采样上的计算效率明显提升，在格的维数、陷门、密文、运算密文尺寸明显缩短.设安全参数n为284，方案支持的最大运算电路深度为L=50，为满足解密正确性需设$ \log \;q = \left\lceil {cL\log \;L = 4 \times 50 \times \log \;50} \right\rceil = 1129 $，c=4为常数，设方案在一次同态运算中所支持的不同的用户身份的最大数量是D=20.对比结果如表 4所示，其中RO表示随机预言模型，SM表示标准模型.效率对比见表 4.

由表 4看出，相比CM和WH方案，本文方案基于标准模型，且在效率参数和计算效率等方面均有优化.

效率参数方面，首先在格的维数上，本方案较最优的WH方案有2.5倍的降低，原因在于：所基于的MP12陷门生成算法输出的矩阵$ \mathit{\boldsymbol{A}} \in \mathbb{Z}_q^{n \times m} $的维数仅为2nlog q时，矩阵A的分布与均匀分布的统计距离即可满足为安全参数n的可忽略函数.另外，陷门生成算法所输出陷门的生成质量较好，即陷门的最大奇异值较低，陷门不再是格Λ^⊥(A)的格基，而是从特定概率分布随机抽取的短向量组成的陷门矩阵.因此陷门矩阵的尺寸相比CM方案较小.此外，低维数和小的陷门尺寸也是密文、运算密文尺寸较短和明文-密文扩展率较低的主要原因.应当注意的是，在相同的安全性下，WH方案的格维数虽然比CM方案低，但密文、运算密文和明文-密文扩展率劣于CM方案的原因在于：WH方案基于的混淆器原理需要方案中的参数N=(2m+1)log q即密文矩阵的维数，因而导致上述原因.运算密文即2.4节mIBFHE方案中所述的膨胀密文，其尺寸取决于参与运算用户身份的数量D和密文尺寸，这里对运算密文尺寸的计算忽略了膨胀密文矩阵里填充的零矩阵，因此尺寸近似等于19倍的密文尺寸.

计算效率方面，格上mIFBHE陷门函数的高效与否主要与其构成算法(陷门生成和原像采样)有关.在陷门生成上，笔者提出的陷门生成算法运行过程中不存在计算代价高的HNF和矩阵求逆操作，陷门生成的复杂度仅相当于2个随机矩阵的一次乘运算.因此，相比其他方案本方案，在陷门生成的计算效率上明显降低.在原像采样上，较其他方案显著降低，原因在于本方案的原像采样算法使用小整数作为输入项且支持并行化运算，而CM和WH方案所基于的文献[9]的原像采样算法是输入项为高精度实数的正交化迭代运算；另一个原因是，方案的原像采样算法存在的部分高代价计算可线下进行，从而节省了线上资源消耗和用户时间.

综上，本文方案陷门函数的效率和密文尺寸以及其他效率参数均得到不等程度的优化.

5 结束语

针对格上基于多身份的全同态加密方案中陷门函数低效的问题，提出一种改进的方案.首先基于MP12陷门函数构造出一种高效的且可转化的IBE方案，并构造出一种支持标准模型下IBE方案转化的Mask系统，然后结合该系统并利用特征向量的思想将构造出的IBE方案转化为mIBFHE方案.对比同类方案，本方案的陷门函数有明显的效率优势，且重要的效率参数均有所缩短.在标准模型下，方案的安全性满足INDr-sID-CPA安全.

所提方案的不足在于标准模型下方案安全性仅满足IND-sID-CPA安全，在某些安全需求更高的应用场景中会有使用限制.如何构造标准模型下IND-aID-CPA安全的格上HIBE方案是值得进一步研究的问题.