由于存在广泛的密码学应用^[1]，损耗陷门函数自提出以来就受到密码学研究者的广泛关注.目前，关于损耗陷门函数构造的研究已有诸多进展^[1-5].通过对已有损耗陷门函数进行分析得知，在特定的应用环境中，损耗陷门函数的陷门相关信息可能会提前泄露给攻击者，即攻击者可能会得到陷门sk的一个多项式时间内可计算但难以求逆的函数h(sk).因此，需要考虑在函数h是亚指数困难求逆的情况下，如何保证损耗陷门函数仍然是可证明安全的.

为此，引入辅助输入安全的概念和技术^[6-8]作为解决问题的工具.具体而言，利用传统的d线性假设和抗量子计算攻击的错误学习问题(LWE, learning with errors)假设，分别构造了一个新的损耗陷门函数，并证明其是辅助输入安全的.最后从效率和安全性角度出发，对2个损耗陷门函数进行分析.

对于损耗陷门函数的定义，可以参考文献[1, 3]，在此不再详述.

对于指数困难求逆的定义，可以参考文献[6, 9]，在此不再详述.

引理1^[8-9]  q元数域F_q上的Goldreich-Levin定理.令q是一个素数，f:{0, 1}ⁿ→{0, 1}^*是任意函数.如果存在一个运行时间为z的区分算法D，使得

则存在一个运行时间为z′=z×poly(n, 2ⁿ, 1/ε)的求逆算法A，使得

由此可知，若函数f:{0, 1}ⁿ→{0, 1}^*是亚指数困难求逆的，则

对于矩阵形式的d线性假设的定义，可以参考文献[3, 9]，在此不再详述.

对于矩阵形式的LWE假设的定义，可以参考文献[10]，在此不再详述.进一步，可以将该判定型LWE问题表示为DLWE_{n, q, β}.

令q是一个素数，F_q表示q元域，G表示包含有q个元素的乘法群.对于任意一个g∈G，行向量x^T=(x₁, …, x_n)∈F_qⁿ，用g^xT表示行向量(g^x₁, …, g^x_n)∈Gⁿ.对于矩阵M=(a_ij)∈F_q^n×m，用g^M表示矩阵(g^a_ij)∈G^n×m.给定矩阵M=(a_ij)∈F_q^n×m和行向量g^T=(g₁, …, g_n)∈Gⁿ，定义运算(g^T)^M为

类似地，给定矩阵S=(g_ij)∈G^n×m和行向量x^T=(x₁, …, x_n)∈F_qⁿ，定义运算(S)^xT为

由以上定义和运算可得

对于任意实数ε∈(0, 1)，利用d线性假设的辅助输入安全损耗陷门函数族H₁由算法(C_inj, C_lossy, V_ltdf, V_ltdf^－1)描述如下.

1) 选取一个单射函数：在输入安全参数d的情况下，算法C_inj随机选取一个比特的素数q，正整数n=poly(d)，生成一个以元素g为生成元的q阶循环群G.选取矩阵A←F_q^n×d，S←F_q^d×n，且矩阵E是F_q上的n×n阶单位矩阵.计算S₁=g^A，S₂=g^AS+E.单射函数的索引是σ=(S₁, S₂)，相对应的陷门是τ=(g, S).

2) 选取一个损耗函数：在输入安全参数d的情况下，算法C_lossy随机选取一个比特的素数q，正整数n=poly(d)，生成一个以元素g为生成元的q阶循环群G.选取矩阵A←F_q^n×d，S←F_q^d×n，且矩阵E是F_q上n×n阶的单位矩阵.计算S₁=g^A，S₂=g^AS.损耗函数的索引是σ=(S₁, S₂).

3) 正向计算：给定函数索引σ=(S₁, S₂)和行向量x^T=(x₁, …, x_n)∈{0, 1}ⁿ，算法V_ltdf计算函数V_ltdf(S₁, S₂, x)=((S₁)^xT, (S₂)^xT)=(t₁^T, t₂^T)∈G^d+n.

4) 对于单射函数求逆：给定陷门τ=(g, S)和向量(t₁^T, t₂^T)，定义V_ltdf^－1(τ, t₁^T, t₂^T)如下.

① (t₁^T)^S=(a₁, …, a_n)∈Gⁿ，t₂^T=(b₁, …, b_n)∈Gⁿ；

② h^T=(h₁, …, h_n)=(b₁/a₁, …, b_n/a_n)∈Gⁿ；

③ 输出x^T=(x₁, …, x_n)=(log_g(h₁), …, log_g(h_n)).

引理2   若多项式时间内可计算的函数f:{0, 1}^d×w→{0, 1}^*是亚指数困难求逆的，则对于任意素数q元数域F_q, 正整数n, w>d，A←F_q^n×d，S=(s₁, …, s_w)←{0, 1}^d×w，从数域F_q中选取n×w维的秩为d的随机矩阵，即U←Rk_d(F_q^n×d)，满足

其中对于i∈{1, …, w}，由f(S)求出任意一个s_i都是亚指数困难的.

利用混合论证的方法和引理1，可以完成对引理2的证明，在此不再详述.

在引理2中，由于矩阵A和S都是秩为d的满秩矩阵，所以矩阵AS的秩也是d，从而矩阵U的秩也是d.若将AS替换为AS+E，其中E是满秩矩阵，则与之相对应的均匀矩阵U的秩应该是n.事实上，可以将引理2看成引理1的进一步扩展.

定理1   在ε(n－1)>d的情况下，如果q阶循环群G上的d线性假设成立，则函数族H₁是一个(n, (n－1)(1－ε))的辅助输入安全的损耗陷门函数族.

证明   首先证明在单射函数情况下，求逆算法的正确性.

此时，单射函数的索引为σ=(S₁, S₂)=(g^A, g^AS+E)，函数输出为

而(t₁^T)^S=(g^xTA)^S=g^xTAS.若(t₁^T)^S=(a₁, …, a_n)，t₂^T=(b₁, …, b_n)，则对于任意i∈{1, …, n}，b_i/a_i=g^x_i.因此，利用陷门S，可以对单射函数正确求逆.

其次证明在损耗函数的情况下，函数是损耗的.

此时，损耗函数的索引为σ=(S₁, S₂)=(g^A, g^AS)，函数的输出为

按照前面给出的运算规则，g^xTA∈G^d是一个d维向量，且AS∈Rk_d(G^n×n).因此，单射函数的值域中至多包含2q^d个元素.进一步，ε(n－1)>d，因此2ⁿ>2q^d.所以损耗分支是损耗的，且损耗量是(n－1)(1－ε).

最后证明即使攻击者在得到陷门的亚指数困难求逆的相关信息的情况下，以上损耗函数族和单射函数族仍然是计算不可区分的.需要证明对于任意亚指数困难求逆的函数f，满足

(1)

由引理2可知，(A, AS, f(S))≈_c(A, U, f(S))成立，其中U∈Rk_d(F^n×n).所以

(2)

由于矩阵E是n×n的单位矩阵，可以得到

(3)

其中U′←Rk_n(F_q^n×n).事实上，式(2) 和式(3) 的计算不可区分困难性是等价的.即如果存在一个能以不可忽略的优势成功区分式(2)(或式(3))的算法，则可以很容易地构造一个能成功区分式(3)(或式(2))的新算法.由此可知，在式(2) 成立的情况下，式(3) 的成立是合理的.进一步，由于U、U′与f(S)是相互独立的，且循环群G上的d线性假设成立，可知

(4)

显然成立.所以，由式(2)~式(4) 可知，式(1) 显然成立.

综上所述，函数族H₁是一个(n, (n－1)(1－ε))的辅助输入安全的损耗陷门函数族.

由Peikert^[1]所构造的利用LWE假设的损耗陷门函数的一个简单变形也是辅助输入安全的.与原始的Peikert损耗陷门函数相比，该变形构造的主要区别在于模数q是关于安全参数的一个拟多项式，单射函数所对应的陷门是一个分量从{0, 1}中选取的矩阵，差错参数是安全参数的多项式分之一等.下面给出该变形构造的详细描述.

对于任意2的幂次方形式的模数p，正整数n和w，满足n=wlbp，令I是整数上w×w的单位矩阵，行向量p^T=(2⁰, 2¹, …, 2^(lbp)－1)∈ ^lbp，则定义矩阵G=Iⓧp.其中ⓧ表示克罗内克乘积，即将矩阵I中的每个分量e_{i, j}替换成列向量e_{i, j}p∈ ^lbp×1.

定义从₂到_q的编码函数c:_p→_q为

其中∈(0, 1).同样，可以将函数c逐分量扩展到分量取自于_p的矩阵上.同时可以定义解码函数c^－1:_q→_p为

其中∈(0, 1).同样，可以将函数c^－1逐分量扩展到分量取自于_q的矩阵上.在适当选择p和q的情况下，可以使得c^－1(c(m))=m.

利用LWE假设的辅助输入安全的损耗陷门函数族H₂由算法(C_inj, C_lossy, V_ltdf, V_ltdf^－1)描述如下.

1) 选取一个单射函数：在输入安全参数d的情况下，选取正整数n和w，差错因子，模数q=2^O((lbd)t)，其中常数t>1，2的幂次方形式的模数p满足n=wlbp.选取矩阵A←_q^n×d，S←{0, 1}^w×d，且从_q上的离散高斯分布Ψ_α中选取n×w维矩阵E，生成矩阵G=Iⓧp.计算矩阵B′=AS^T+E∈_q^n×w，M=c(G).输出单射函数的索引σ=(A, B=B′+M)，相对应的陷门是τ=S.

2) 选取一个损耗函数：在输入安全参数d的情况下，选取正整数n和w，差错因子，模数q=2^O((lbd)t)，其中常数t>1，2的幂次方形式的模数p满足n=wlbp.选取矩阵A←_q^n×d，S←{0, 1}^w×d，且从_q上的离散高斯分布Ψ_α中选取n×w维矩阵E，计算矩阵B=AS^T+E∈_q^n×w.输出损耗函数的索引是σ=(A, B).

3) 正向计算：给定函数索引σ=(A, B)和行向量x^T=(x₁, …, x_n)∈{0, 1}ⁿ，算法V_ltdf计算函数V_ltdf(A, B, x^T)=(x^TA, x^TB)=(t₁^T, t₂^T)∈_q^d+w.

4) 对于单射函数求逆：给定陷门τ=S和向量(t₁^T, t₂^T)，定义V_ltdf^－1(τ, t₁^T, t₂^T)如下.

① 计算v^T=t₂^T－t₁^TS^T，m^T=c^－1(v^T)∈_p^w；

② 求解x^TG=m^T，其中m^T为分量在{0, …, p－1}中与m^Tmodp相等的唯一整数向量；

③ 输出x^T=(x₁, …, x_n)∈{0, 1}ⁿ.

引理3^[7-8]   令β>0，q∈，从离散高斯分布Ψ_β中选取整数y∈，则以压倒性的概率满足|y|≤ .

引理4^[7-8]   令β>0，q∈，y∈，则离散高斯分布Ψ_β和离散高斯分布Ψ_β+y之间的统计距离至多为|y|/(βq).

定理2   对于安全参数d∈，模数q=2^O((lbd)t)，t>1，p=poly(d)，α=1/poly(d)，β=poly(d)/q，正整数n、w=poly(d)满足n=wlbp，若假设DLWE_{d, q, β}成立，则损耗陷门函数族H₂是一个的辅助输入安全的损耗陷门函数族.

与定理1相类似，利用引理3和引理4可以完成定理2的证明，在此不再详述.

本节从效率、损耗量情况和安全性假设等方面出发，对损耗陷门函数族H₁和H₂进行分析.

对于利用d线性假设的损耗陷门函数族H₁，选取模数q=2^O((lbd)t).相应的函数索引需要占用n(d+n)lbq比特的存储空间，单射函数的求逆陷门需要占用ndlbq比特的存储空间.对该函数族进行正向计算需要n(d+n)个模指数运算，利用陷门进行求逆则需要dn个模指数运算，且当输入长度为n的情况下，损耗量为(n－1)(1－ε).

对于利用LWE假设的损耗陷门函数族H₂，选取模数q=2^O((lbd)t).相应的函数索引需要占用n(d+w)lbq比特的存储空间，单射函数的求逆陷门需要占用dwlbq比特的存储空间.对该函数族进行正向计算需要n(d+w)个模乘运算，利用陷门进行求逆则需要dw个模乘运算，且当输入长度为n的情况下，损耗量为.损耗陷门函数族H₁和H₂的具体分析如表 1所示.

表 1

表 1

表 1 2个新型损耗陷门函数族与已有相关结论的参数对比和分析

表 1 2个新型损耗陷门函数族与已有相关结论的参数对比和分析

由以上分析可知，2个损耗陷门函数族的存储代价相当，函数族H₁的计算代价较高，且损耗量相对较大；函数族H₂的计算代价较低，且损耗量相对较小.另外，虽然所构造的2个损耗陷门函数族的效率相对略低，但与已有的损耗陷门函数族相比的优势是能证明是辅助输入安全的.

首先，分析在攻击者得到与单射函数的陷门相关的辅助输入信息的情况下，现有损耗陷门函数的可证明安全性会受到较大影响；然后，利用d线性假设和LWE假设，分别构造了一个损耗陷门函数族，并利用扩展版的Goldreich-Levin定理，证明这2个损耗陷门函数是辅助输入安全的；最后，详细地分析这2个损耗陷门函数的效率和安全性，表明这2个损耗陷门函数族相对的优势和不足.此外，文中所用到的概念和技术，可以进一步扩展到all-but-one或all-but-many损耗陷门函数的构造上.

笔者构造的2个损耗陷门函数存在的缺点是存储和计算效率相对略低.如何构造高效的辅助输入安全的损耗陷门函数是进一步的研究方向.