基于NTRU的签名算法学习1

AI Studio

1020人浏览 · 2022-06-03 00:05:26

AI Studio · 2022-06-03 00:05:26 发布

NTRUSign
本文基于Modular Lattice Signatures, revisited学习了NTRUSign的基本思想，以及其改进。本文主要对该文章进行了转译，并利用python实现了底层的加解密、同态、签名等运算。

摘要在本文中，我们重访了模格签名方案和它的有效实例化称为pqNTRUSign。首先，我们证明了模格签名方案可以基于标准格问题。由于伪造者或潜在伪造者需要解决的基本问题是用受限范数恢复格向量，给定最小有效位，我们将这类一般问题称为“截短\学习”问题。我们证明了用双峰高斯采样代替pqNTRUSign中的均匀采样，可以进一步减小签名的大小。作为一个例子，我们展示了签名的大小可以低至4608位，而安全级别为128位。pqNTRUSign最重要的新贡献是，我们现在可以执行批处理验证，允许验证者在一次验证过程中检查大约2000个签名。

📖 介绍
由于量子计算机的威胁，组织和研究小组正在寻找候选算法来替代RSA和ECC基于方案。在所有候选方案中，基于点阵的解决方案似乎是最有前途的解决方案。对于加密方案，NTRUEncrypt是已知的最快的基于格的加密算法之一。在签名方案方面，目前有几种基于格点的签名方案依赖于NTRU格点的安全性，如BLISS、DLP和pqNTRUSign 。

本文重述了模格签名方案。给定具有陷门函数T的格L\mathcal {L}L，它是行向量的短基;和向量m形式的信息摘要，其系数为[0,p）模签名方案的签名是格向量v，使

1.v≡mmod pv\equiv m \mod pv≡mmodp

2.v∈Lv \in \mathcal{L}v∈L

可以通过以下步骤获得此向量：

1.从L\mathcal{L}L采样一个向量v0v_0v
0

;

2.用TTT对v0v_0v
0

进行微调，使v:=v0+aTv := v_0 + aTv:=v
0

+aT满足某aaa的同余条件;

3.使用拒收抽样从vvv中隐藏TTT

在本文中，我们将从以下角度重新审视上述方案。

安全证明。在原模格签名方案中，公钥安全问题与唯一最短非零向量问题(uSVP)有关。从L(一个坏的基础)中恢复T;而不可伪造性是基于一个晶格与一个晶格平移的交点上的近似最接近向量问题(approx-CVP)，即L∩(pZn+mp)\mathcal{L}\cap (pZ^n+m_p)L∩(pZ
n
+m
p

)。虽然第二个问题对于这个特殊的晶格来说是困难的，但是第一个问题和第二个问题之间的联系是缺失的。因此，该方案需要两个(看似独立的)硬度假设。例如，当方案通过一个NTRU晶格实例化时，他们需要对NTRU晶格进行uSVP假设，对两个晶格的交集进行上述approx- cvp假设。

在本文中，我们去掉了第二个假设。从本质上说,攻击者是给定一个晶格(任何晶格,不一定NTRU晶格),他被要求找到一个等晶格向量,这个向量相等的已知值mod p。换句话说,攻击者需要找到一个向量与预先确定的在这篇文章中,我们删除第二个假设。从本质上说,攻击者是给定一个晶格(任何晶格,不一定NTRU晶格),他被要求找到一个等晶格向量,这个向量相等的已知值mod p。换句话说,攻击者需要找到一个向量与预先设定的最低有效位。我们命名这个问题与截断(LWT)学习问题,可以被视为学习的逆着(LWR)问题,给出了在这种情况下,一个矩阵A和b = ⌊sAmod q⌋p\left \lfloor sA \mod q\right \rfloor_p⌊sAmodq⌋
p

,并要求找到s。也就是说,找到一个向量与晶格预先确定的最重要的部分.

这允许我们将伪造攻击与approx-SVP连接起来。因此，我们只需要一个简单的假设。特别地，当方案通过一个短整数解决方案(SIS)问题实例化时，在我们的方案中伪造签名与解决随机格的approx-svp一样困难。另一方面，当方案通过一个NTRU格实例化时，我们要求NTRU格的approx- svp是困难的，这等价于unique- svp假设(直到一个多项式因子)，即， NTRU算法。

抽样方法。早期基于点阵的签名方案，如GGHSign和NTRUSign，在消息/签名对的转录本中泄漏私钥信息。攻击者可以使用学习平行六面体的方法从足够长的文本中生成签名密钥"。

其中，Lyubashevsky提出了一种拒绝采样的方法来阻止转录泄漏攻击。使用他的技术，签名是根据一个固定的公共分布产生的(通常是一个高斯分布，如均匀分布)。记录只显示这种公开分发，不包含关于用于生成签名的特定签名密钥的信息。因此，采样方法成为设计签名方案的核心问题。例如，用双模高斯采样器代替高斯采样器可以显著提高算法的性能.

原先方案中的签名是格向量。由于验证者已经知道用于验证目的的格的一个(坏的)基，只要验证者在验证阶段能够完成整个向量，那么传输部分向量v就足够了。

流行的基于格的方案，如BLISS和TESLA，没有这个性质。这些方案中的签名是接近晶格的向量。因此，当向量被压缩时，需要为验证者生成一个额外的帮助器来推导原始向量(尽管这个帮助器只有几百位)。具体地说，如果我们用原先方案中相同的参数来参数化本文提出的方案，签名大小的差异就是这个参数的大小。

由于采样方法的原因，这种设计上的优势并没有给出更小的签名尺寸。对于系数为[−q/2,q/2)[-q/2,q/2)[−q/2,q/2)的n维向量，需要n⌈logq⌉n\left \lceil logq\right \rceiln⌈logq⌉位进行存储。相比之下,一个离散高斯向量相同的尺寸的偏差σ∼q\sigma \sim \sqrt{q}σ∼
q

可以存储∼n(logq/2+2)\sim n(logq/{2}+2)∼n(logq/2+2)位。一个自然的问题是，是否可以使用(双峰)高斯采样[10]对模格签名。在本文中，我们对这个问题给出了肯定的回答.

备注1。虽然使用高斯采样的方案允许更小的签名大小，但基于格点的签名方案最近的发展显示出一种向均匀拒绝采样的趋势，因为均匀采样更容易实现和确保恒定的时间。然而，使用pqNTRUSign，高斯采样使我们获得了一个额外的属性:签名聚合。

签名聚合。签名聚合，也称为批处理验证，允许验证一组签名(在同一键下签名)，其操作顺序为单个验证。在许多用例中，它是一个有用的属性。例如，对于签名软件映像的安全引导机制，签名聚合允许在一次验证整个软件映像集的同时，分别对各个软件映像进行签名(并且按照组件的方式而不是单块更新)。这允许快速启动.

我们的方案允许批处理验证(参数经过微调)。一般来说，对于消息摘要m的签名v只要≡m mod p和v∈Lv\in \mathcal{L}v∈L就有效。因此，对于一组签名vi{v_i}v
i

，对应于我们所拥有的一组消息mi{m_i}m
i

.

1.∑vi≡∑mimod p\sum v_i \equiv \sum m_i \mod p∑v
i

≡∑m
i

modp

2.∑vi∈L\sum v_i\in \mathcal{L}∑v
i

∈L

因此，我们可以简单地检查∑vi\sum v_i∑v
i

而不是检查每个v。在为我们提出的方案实现这种技术时，我们可以使用单环乘法(这通常是验证中代价最高的操作)来验证一批签名。不过我们注意到，仍然需要执行多个散列函数来获得这些消息摘要。此外，由于累积的签名在格子中是一个更大的向量(与单个签名相比)，我们将要求这个累积的签名对应的格子问题也很困难。

我们还注意到，其他基于格的方案，如BLISS和TESLA，不能轻易地提供这个属性，因为它们需要在哈希函数之前执行环操作。

📖 背景知识
向量用小写粗体字，矩阵用大写粗体字。对于一个多项式f(x)=f0+f1x+…+fn−1xn−1f(x)=f_0+f_1 x+…+f_{n-1}x^{n-1}f(x)=f
0

+f
1

x+…+f
n−1

x
n−1
，我们用fff表示其向量形式<f0,f1,…,fn−1><f_0,f_1,…,f_{n-1}><f
0

,f
1

,…,f
n−1

。当没有歧义时，我们有时会滥用向量和多项式的表示法。对于一个多项式向量f，f范式是∥f∥:=∑i=0n+1fi2\left | f\right |:=\sqrt{\sum^{n+1}_{i=0}f2 _i}∥f∥:=
∑
i=0
n+1

f
i
2

和∥f∥∞:=max(∣fi∣)\left | f\right |_{\infty} :=max(|f_i|)∥f∥
∞

:=max(∣f
i

∣)

我们经常使用多项式环Rq:=Z[x]/F(x)R_q := Z[x]/F (x)R
q

:=Z[x]/F(x)和F(x)=xn±1F (x) = x^n±1F(x)=x
n
±1。环Rq上多项式f(x)的循环旋转矩阵为矩阵M=(f1,f2,…,fn)T;M = (f_1,f_2,…,f_n)^T;M=(f
1

,f
2

,…,f
n

)
T
;如果f(x)=xn−1f(x) = x^n - 1f(x)=x
n
−1，它是完全循环的，并且接近于循环，直到符号，如果f(x)=xn+1f(x) = x^n + 1f(x)=x
n
+1。

对于一个真实的a，我们让bae表示到a的壁橱整数。对于一个整数a，我们使用[a]q[a]_q[a]
q

来表示a mod q,⌊a⌋p:=(a−[a]p)p/\left \lfloor a\right \rfloor _p := (a−[a]_p)p/⌊a⌋
p

:=(a−[a]
p

)p/用于将a四舍五入到p的最接近倍数的运算。模运算的中心被提升，例如模q在−q/2−q/2−q/2和q/2q/2q/2范围内返回一个整数。这些符号也扩展到向量和矩阵中。

NTRU,SIS,LWR与格

格L\mathcal {L}L是RnR^nR
n
的离散子群，也就是d≤n个线性无关向量在RRR上的所有积分组合的集合:

L:=Zb1+Zb2+…+Zbd,bi∈R\mathcal{L}:=Zb_1+Zb_2+…+Zb_d,b_i\in RL:=Zb
1

+Zb
2

+…+Zb
d

,b
i

∈R

B：=(b1…bd)TB ：= (b_1…b_d)^TB：=(b
1

…b
d

)
T
称为L\mathcal{L}L的一组基，给定一个格L，找到一个不超过γ⋅λ1（L）\gamma ·\lambda _1{\mathcal{（L）}}γ⋅λ
1

（L）的向量称为近似最短向量问题(γ−SVP\gamma-SVPγ−SVP)，其中λ1\lambda_1λ
1

是晶格中最短向量的长度。高斯函数的启发式说在一个随机格中,这第一个最小值λ1≈dim2πedet(L)1dim\lambda _1 \approx \sqrt{\frac{dim}{2\pi e}}det(\mathcal{L})^{\frac{1}{dim}}λ
1

≈
2πe
dim

det(L)
dim
1

在det(L)表示的行列式L\mathcal{L}L .给定一个特定的晶格L,存在一个唯一最短非零向量,发现这个向量称为独特的最短向量问题(u-SVP)

我们把一个NTRU格看成是一个2阶的RqR_qR
q

模。让f,g的系数为小于q的实数。令h=g/fh = g/fh=g/f在 RqR_qR
q

。与h相关的NTRU晶格定义为

L:={(s,t)∈Rq2:t≡shmod q}.\mathcal{L}:={(s,t)\in R^2 _q :t\equiv sh \mod q}.L:={(s,t)∈R
q
2

:t≡shmodq}.

已知h，认为很难找到f和g，这就是NTRU假设，可以简化为NTRU格点唯一的最短向量问题。

我们把NTRU晶格中的向量写成v = <s，t>,其中s和t都是RqR_qR
q

的元素;此外，我们将构成该向量第一部分的子向量称为s边的向量，将构成该向量第二部分的子向量称为t边的向量。

我们将此概念扩展到适用的短整数解决问题(SIS)。回想一下SIS问题的定义如下:

SISq,n,m,βSIS_{q,n,m,\beta}SIS
q,n,m,β

问题：在一个n×mn\times mn×m的随机矩阵中，其中元素皆为小于q的正整数，寻找一个最小非0向量v使得vA≡0mod q,∣∣v∣∣2<βvA\equiv 0 \mod q,||v||_2<\betavA≡0modq,∣∣v∣∣
2

<β.

如果将A 矩阵看出两个矩阵的上下串联，例如A=∣A1A2∣A=\begin {vmatrix}A_1\ A_2\end{vmatrix}A=
∣
∣
∣
∣
∣

A
1

A
2

∣
∣
∣
∣
∣

,则原问题变为： L:={(s,t):sA1+tA2≡0mod q}\mathcal{L}:={(s,t):sA_1+tA_2 \equiv 0 \mod q}L:={(s,t):sA
1

+tA
2

≡0modq}

找到短的(s,t)在此点阵中提供了SIS问题的解决方案。对于n = poly(m)， q⩾βmδq \geqslant \beta m^\deltaq⩾βm
δ
的一些正数δ\deltaδ，平均求解SIS问题与具有最近似因子的 max{1,ββ∞/q}⋅0(βm)max{1,\beta \beta_\infty /q}·0(\beta \sqrt{m})max{1,ββ
∞

/q}⋅0(β
m

) 最短独立向量问题一样困难;其中β∞\beta_\inftyβ
∞

是v的无穷范数的上界。

SIS问题有一个“双”版本，称为LWE问题。通俗地说，让m，n，q为某个正整数，设格数为由σ\sigmaσ参数化的χσ\chi _\sigmaχ
σ

分布，例如:具有标准差为σ\sigmaσ的离散高斯分布，均匀随机抽样A∈Zqn×m,s,b1∈ZpnA \in Z^{n\times m} _q,s,b_1\in Z^n _pA∈Z
q
n×m

,s,b
1

∈Z
p
n

;样品e∈χσme \in \chi ^m _\sigmae∈χ
σ
m

计算b0=sA+emodqb_0=sA + e mod qb
0

=sA+emodq;决策LWE假设表明，给定两对(A,b0)，生成b0,(A,b1),b1选自均匀分布，无法区分这两对.

我们还利用了舍入学习(LWR)问题。这可以被看作是SIVP问题的一个变体，它具有四舍五入带来的确定性误差。我们正式记录LWR问题如下:

LWRq,r,n,mLWR_{q,r,n,m}LWR
q,r,n,m

:均匀从随机抽样矩阵和A∈Zqn×mA \in Z^{n\times m} _qA∈Z
q
n×m

和向量s∈Zqns\in Z^n _qs∈Z
q
n

,计算b=⌊sAmod q⌋rb=\left \lfloor sA \mod q\right \rfloor_rb=⌊sAmodq⌋
r

;决策的LWR问题是:给定u在ZqnZ^n _qZ
q
n

中均匀随机采样的两对(A,b)和(A,⌊u⌋r)(A,\left \lfloor u \right \rfloor_r)(A,⌊u⌋
r

)，区分这两对。计算问题为:给定(A,b),发现s。

假设带参数的LWRq,r,n,mLWR_{q,r,n,m}LWR
q,r,n,m

是困难的，决策LWEq,r,n,m‘LWE_{q,r,n,m^`}LWE
q,r,n,m
‘

问题也是困难的。

m≥log(q)log(2γ)⋅m‘m\geq \frac{log(q)}{log(2\gamma )}·m^`m≥
log(2γ)
log(q)

⋅m
‘
and q≥γ(nmβp)q\geq \gamma (nm\beta p)q≥γ(nmβp)

对于一些γ\gammaγ≥1的。就我们所知，我们不知道计算的LWR和其他假设之间的规约。

双峰高斯分布和拒绝抽样：

定义了均值v和标准差为σ\sigmaσ的n维高斯分布ρv,σ(x):=exp(−∥x−v∥22σ2)\rho _{v,\sigma}(x):=exp(\frac{-\left | x-v\right |^2}{2\sigma2})ρ
v,σ

(x):=exp(
2σ
2

−∥x−v∥
2

);当没有歧义时，我们把它简称为ρσ\rho_\sigmaρ
σ

。定义了一个n维的离散高斯分布在Z上:χσ:=ρσ(x)ρσ(Zn)\chi _\sigma :=\frac{\rho _\sigma (x)}{\rho _\sigma (Z^n)}χ
σ

:=
ρ
σ

(Z
n
)
ρ
σ

(x)

，其中ρσ(Zn):=∑z∈Znρσ(z)\rho _\sigma (Z^n):=\sum _{z\in Z^n}\rho _\sigma (z)ρ
σ

(Z
n
):=∑
z∈Z
n

ρ
σ

(z)是使函数变成概率分布[23]所需要的标度量.

截断:对于一个离散高斯分布χσm\chi _\sigma^mχ
σ
m

和τ>1\tau>1τ>1

ρσ(Zm/στmB)≤2ρσ(Zm)(τexp(1−τ22))m\rho _\sigma (Z^m / \sigma \tau \sqrt{m}\mathcal{B} )\leq 2 \rho _\sigma (Z^m)(\tau exp(\frac{1-\tau^2}{2}))mρ
σ

(Z
m
/στ
m

B)≤2ρ
σ

(Z
m
)(τexp(
2
1−τ
2

))
m

其中B是中心单位球。令τ=λ2ln2\tau = \sqrt{\lambda 2 ln2}τ=
λ2ln2

为一维高斯将确保所有样品都以τσ\tau \sigmaτσ为边界的概率大于1−2−τ1-2^{-\tau}1−2
−τ
。通常情况下，对于λ=128\lambda = 128λ=128，可以使用 $\tau= 13.3;对于3;对于3;对于\lambda = 256，可以使用，可以使用，可以使用\tau= 18.8$

拒绝抽样:设S为秘密矩阵，c为从均匀分布中抽样得到的向量，y为从离散矩阵中抽样得到的向量。考虑x = y + cS的分布，即，一个经过cS平移的高斯分布。在[28,13]中已经表明，每个样本x都泄漏了关于S的部分信息。用来密封泄漏的方法是拒绝采样,通过根据一定的标准概率接受输出，使输出分布独立于S.

如果我们希望使输出分布与y相同，则有:

χσ(x)χcS,σ(x)≤M,\frac{\chi _\sigma(x)}{\chi _{cS,\sigma}(x)} \leq M,
χ
cS,σ

(x)
χ
σ

(x)

≤M,

这个不等式成立

M=exp(2τσmaxc∣∣cS∣∣+maxc∣∣cS∣∣22σ2)M=exp(\frac{2\tau \sigma max_c||cS||+max_c||cS||^2}{2\sigma2})
M=exp(
2σ
2

2τσmax
c

∣∣cS∣∣+max
c

∣∣cS∣∣
2

)

其中M为重复率。常数M决定了拒绝率，M越小，签名生成过程越高效。一种常见的选择是设置出一个常数σ=τmaxc∣∣cS∣∣\sigma =\tau max_c||cS||σ=τmax
c

∣∣cS∣∣(虽然仍然较大).:

双峰高斯分布:非正式地说，双峰高斯分布是两个具有相同的σ\sigmaσ和相同的绝对值，符号相反的高斯分布的和。由上例可知，x = y±cS的分布非常接近于双峰高斯分布。如果存在一个常数M，则可以使用拒收抽样从双峰高斯分布12χcS,σ(x)+12χ−cS,σ(x)\frac{1}{2}\chi {cS,\sigma}(x)+\frac{1}{2}\chi{-cS,\sigma}(x)
2
1

χ
cS,σ

(x)+
2
1

χ
−cS,σ

(x)得到一个新的高斯分布χσ\chi_\sigmaχ
σ

,并且

χσ(x)12χcS,σ(x)+12χ−cS,σ(x)≤M\frac{\chi _\sigma (x)}{\frac{1}{2}\chi {cS,\sigma}(x)+\frac{1}{2}\chi{-cS,\sigma}(x)}\leq M
2
1

χ
cS,σ

(x)+
2
1

χ
−cS,σ

(x)
χ
σ

(x)

≤M

这个不等式是成立的:

M=exp(maxc(∣∣cS∣∣2)2σ2)M = exp(\frac{max_c (||cS||^2)}{2\sigma2})
M=exp(
2σ
2

max
c

(∣∣cS∣∣
2
)

)

同时，对于一个个体x = y±cS，接受它的概率为

ρ=1/(Mexp(−∣∣cS∣∣2σ2)cosh(<x,cS>σ2))\rho=1/(M exp(-\frac{||cS||}{2 \sigma ^2}) cosh(\frac{<x,cS>}{\sigma^2}))
ρ=1/(Mexp(−
2σ
2

∣∣cS∣∣

)cosh(
σ
2

<x,cS>

))

备注2。通常，在效率和存储大小之间存在权衡。对于离散高斯分布χσ\chi _\sigmaχ
σ

的列线图，其输出x的熵有上界

H(x)≤≈klog(4.1σ)\mathcal {H}(x)\leq \approx klog(4.1\sigma)
H(x)≤≈klog(4.1σ)

因此，使用霍夫曼编码，这样的向量可以有效地存储为大约k(log(σ)+2)k(log(\sigma)+2)k(log(σ)+2)位。因此，一个更小的报文会产生更小的签名σ\sigmaσ，但同时也会降低拒收采样的效率。

📖 具有高斯抽样的模格签名
3.1 方案
构造:设m、n、k为3个正整数，n = k + m，设S1∈Zm×kqS_1 \in Z^m×k qS
1

∈Z
m
×k
q

为系数小且稀疏的矩阵。为简单起见,我们假设S1S_1S
1

是抽样从某个边界为β的分布中采集的,这样∣∣S1∣∣∞≤β≪q||S_1||\infty \leq \beta \ll q∣∣S
1

∣∣
∞

≤β≪q。在实践中可以使用一个方差小的离散高斯采样器,或均匀取样器在小的范围内。

我们的密钥是一个矩阵S:=[pS1∣Im]∈Zq(m×n)S := [pS_1|I_m]\in Z^{(m \times n)} _qS:=[pS
1

∣I
m

]∈Z
q
(m×n)

，它具有小的项。公钥是由一个矩阵A=[A1A2]A = \begin{bmatrix} A_1\A_2 \end{bmatrix}A=[
A
1

A
2

]同时SA = 0 mod q和A2是A的逆的mod q。同样,我们可以从Zqk×mZ^{k\times m}_qZ
q
k×m

均匀得采样到样本A1,然后设置A2=−pS1A1A_2 = -pS_1A_1A
2

=−pS
1

A
1

mod q。A1如果A2不是可逆的mod q,我们重取。SIS点阵定义为:

$\mathcal {L}:={(u,v):u A_1+v A_2 =0 \mod q},$

其中S是该栅格的短活板门基础。注意，上面的过程是SIS问题的标准构造，除了S1上有一个因子p。在下一小节中，我们将说明我们的构造与标准SIS问题之间的等价性.

看一个k×m矩阵B:=A1(−A2)−1mod qB:=A_1(-A_2)^{-1} \mod qB:=A
1

(−A
2

)
−1
modq可能更方便。与B,晶格L可以解释为

$\mathcal {L}:={(u,v):uB=v \mod q},$

对于错误学习的基

P=[0qImIkB]P=\begin{bmatrix} 0 & qI_m \ I_k & B \end{bmatrix}
P=[
0
I
k

qI
m

B

]

这样就可以进行有效的抽样。

签名:我们将哈希函数H作为一个随机的oracle,在ZpnZ^n _pZ
p
n

上均匀输出,这允许我们从消息文摘中生成随机元素mp∈Zpnm_p \in Z^n _pm
p

∈Z
p
n

。我们写mp:=(up,vp)m_p:=(u_p,v_p)m
p

:=(u
p

,v
p

),同时up∈Zpku_p \in Z^k _pu
p

∈Z
p
k

和vp∈Zpmv_p \in Z^m _pv
p

∈Z
p
m

。

下一步是从P:u1≡upmod pP :u_1 \equiv u_p \mod pP:u
1

≡u
p

modp中采样一个向量(u1,v1)(u_1,v_1)(u
1

,v
1

)要做到这一点，我们可以简单地从一个离散高斯分布的χσk\chi ^k _\sigmaχ
σ
k

函数中采样一个向量r。然后计算u0=pr,u1=u0+upu_0 = pr, u_1 = u_0 + u_pu
0

=pr,u
1

=u
0

+u
p

，u1u_1u
1

满足v1=u1Bmod qv_1 = u_1 B \mod qv
1

=u
1

Bmodq， $u_1,v_1) 是晶格中的一个向量，是晶格中的一个向量，是晶格中的一个向量，u_1≡u_p \mod p$ .

另一种查看上述过程的方法是生成一个随机向量(r,rBmod q)(r,rB \mod q)(r,rBmodq)在晶格中。根据定义，矩阵[Ik∣B][I_k|B][I
k

∣B]是L§\mathcal {L}§L§的子格的一组基。此外，由于r是从一个离散的高斯分布采样，这个随机向量可以看作是一个GPV采样器L([Ik∣B])\mathcal{L}([I_k|B])L([I
k

∣B])的输出r([Ik∣B])r([I_k|B])r([I
k

∣B])。如果参数σ\sigmaσ大于平滑参数L([Ik∣B])\mathcal{L}([I_k|B])L([I
k

∣B])，则向量r([Ik∣B])r([I_k|B])r([I
k

∣B])在L([Ik∣B])\mathcal{L}([I_k|B])L([I
k

∣B])是均匀的，在ZnZ^nZ
n
上是离散的高斯分布。然后我们取这个向量对q的模来得到精确的输出向量.

由于v1v_1v
1

在ZnZ^nZ
n
上是离散高斯分布的，它将具有以p为模的随机系数，因此不满足全等条件。为了完成这个过程，我们需要对v1v_1v
1

进行微调，使t侧也满足一致性条件：同时，我们不想破坏s边的同余条件。我们使用秘密基S=[pS1∣Im]S=[pS_1 | I_m]S=[pS
1

∣I
m

]来实现这个目标。令a=vp−v1mod pa = v_p - v_1 \mod pa=v
p

−v
1

modp，计算(u2,v2)=aS=(paS1,a(u_2,v_2) = aS = (paS_1,a(u
2

,v
2

)=aS=(paS
1

,a).注意(u2,v2)≡(0,a)(u_2,v_2)≡(0,a)(u
2

,v
2

)≡(0,a)构造对mod p\mod pmodp，$ (u_2,v_2)$是晶格中的向量。

最终的签名为(u,v)=(u1,v1)+(u2,v2)(u,v)=(u_1,v_1)+(u_2,v_2)(u,v)=(u
1

,v
1

)+(u
2

,v
2

),很容易看出(u,v)(u,v)(u,v)在∣∣v∣∣∞<q/2||v||_\infty< q/2∣∣v∣∣
∞

<q/2时仍在晶格中。同时我们有

u=u1+u2=u1≡upmod pu=u_1+u_2=u_1\equiv u_p \mod p
u=u
1

+u
2

=u
1

≡u
p

modp

以及

v=v1+v2≡v1+vp−v1≡vpmod pv=v_1+v_2\equiv v_1+v_p -v_1 \equiv v_p \mod p
v=v
1

+v
2

≡v
1

+v
p

−v
1

≡v
p

modp

因此,(u,v)(u,v)(u,v)是我们方案的有效签名

3.2 拒绝抽样
如前所述，候选签名(u，v)泄漏关于密钥S的信息。要密封此泄漏，需要使用拒收采样技术。上述方案的效率很大程度上取决于拒绝签名的频率。作为一个概念的证明，我们将展示拒收抽样可以用来密封信息泄漏在这里。我们将在第4节中给出一个更有效的实例，它使用双峰高斯分布。

对u的拒收抽样。先文提到u=p(r+aS1)+upu = p(r + aS_1) + u_pu=p(r+aS
1

)+u
p

。由于p和upu_pu
p

都是公开的，我们需要封住来自b:=r+aS1b := r + aS_1b:=r+aS
1

对S1S_1S
1

的泄漏。还请回忆一下，所有r的分布方式为χσk\chi ^k _\sigmaχ
σ
k

。

在v上的拒收抽样，在t边，我们不需要拒收抽样。我们有v=v1+v2v = v_1 + v_2v=v
1

+v
2

。首先v1=(pr+up)Bv_1 = (pr + u_p)Bv
1

=(pr+u
p

)B，它没有链接到秘钥S1S_1S
1

。其次，S2=(v1−vp)mod pS_2 = (v_1−v_p) \mod pS
2

=(v
1

−v
p

)modp也没有链接到任何密钥.

另一种说法是，拒绝抽样对t边来说是不需要的，因为事实上，与t边相对应的\密钥实际上是ImI_mI
m

。事实上，我们可以把v=v1+aS2v = v_1 + aS_2v=v
1

+aS
2

写成S2=ImS_2 = I_mS
2

=I
m

。在下一节中我们将看到，当一个秘密矩阵替代ImI_mI
m

时，我们仍然需要使用拒收抽样来密封S2S_2S
2

的泄漏。

尽管如此，如果∣∣v∣∣∞||v||_\infty∣∣v∣∣
∞

变得太大，导致了一个wrap-around mod q，我们确实需要重新启动。当这种情况发生时，mod q降低后，全等条件被打破.

替代方案。在我们的构建中，我们选择做拒收抽样，这样∣∣v∣∣∞||v||_\infty∣∣v∣∣
∞

不会导致任何wrap-aroud。尽管有以下两种选择，我们还是选择了这种方法。首先，签署人可以发送一个助手来指示校验人发生wrap-around的系数。这可以看作是2012中基于Ding ® LWE的密钥交换的一种和解方法。我们不采用这种解决方案，因为它会增加签名的大小。

其次，由于wrap-around发生的概率较低，我们可以基于模糊匹配让验证者接受签名:当t侧的大部分系数满足同余条件时接受签名。这种有前途的方法可能会削弱我们的安全，因为它使伪造更容易。出于保守目的，我们不考虑这种方法.

3.3 签名压缩
有三个压缩源。首先，只要向量是l，验证者可以有效地只存储向量的\、s边，而不是整个向量，即给定u，验证者可以重构v=uBmod qv = uB \mod qv=uBmodq

其次，验证者可以从b中重构u=pb+upu = pb + u_pu=pb+u
p

，因为p和upu_pu
p

都是已知的。所以只需要b来验证.

最后，由于b在拒绝采样后遵循离散高斯分布，可以使用基于代码的压缩技术来减少b的空间需求。

最后的签名是一个k维离散高斯向量，允许霍夫曼编码。最终签名的大小为k(log(σ)+2)k(log(\sigma)+ 2)k(log(σ)+2)。

3.4 模拟记录
上述签名算法必须在统计上与三(up,vp,b)(u_p,v_p,b)(u
p

,v
p

,b)，分布为Upk×Upm×χσkU^k_p\times U^m _p \times \chi ^k _\sigmaU
p
k

×U
p
m

×χ
σ
k

的高斯分布，其中UpU_pU
p

为均匀模p，高斯分布为χσk\chi ^k _\sigmaχ
σ
k

高斯分布。在不知道密码匙的情况下，可以通过以下方式模拟这样一份文本:

1. 从χσk\chi ^k \sigmaχ
σ
k

中随机选择b 2. 设u=pb+upu = pb + u_pu=pb+u
p

，随机取upmod pup \mod pupmodp，使∣∣u∣∣∞<q/2||u||\infty < q/2∣∣u∣∣
∞

<q/2 3. 集合v≡uBmod qv≡uB \mod qv≡uBmodq，并将v提升到区间(−q/2,q/2)(−q/2,q / 2)(−q/2,q/2) 4. 设vp≡vmod pv_p≡v \mod pv
p

≡vmodp

备注3。我们正在做一个假设，经过实验验证，即step4生成一个vp≡uBmod qmod pv_p≡uB \mod q \mod pv
p

≡uBmodqmodp，它的项都是均匀mod p

3.5 安全性
对于公钥的安全性，很容易看出从公钥找到秘钥(或者仅仅是允许伪造的足够短的向量)的能力可以降低为解决SIS问题的能力。在本节中，我们主要关注伪造签名的困难。

为了量化伪造的难度，我们首先引入带截断的学习问题。

定义3 (LWTq,p,n,mLWT_{q, p,n,m}LWT
q,p,n,m

)。让q,p,m,nq,p,m,nq,p,m,n是p共一撇到q的正整数，均匀随机抽样一个矩阵A∈Zqn×mA\in Z^{n\times m} _qA∈Z
q
n×m

q乘以m和一个向量s∈zqns\in z^{n}_qs∈z
q
n

,计算b = sA mod q mod p;决策LWT问题为:给定两对(A,b)和(A,[u]p)(A,[u]_p)(A,[u]
p

)其中u在ZqnZ^n _qZ
q
n

中均匀随机采样，区分这两对。计算问题为:给定(A,b)，找到s。

如前所述，这个LWT问题可以看作是LWR问题的逆。这里我们展示了问题之间的简化。

引理1。选择一对(p,q)使得p和r≡p−1mod qr≡p^{−1} \mod qr≡p
−1
modq都在q\sqrt{q}
q

的数量级上。那么，如果存在求解参数q的计算LWT的算法A\mathcal {A}A ,对于给定参数为q,p,n,m的任意输入(A,b)∈Zqq×m×Zpm(A,b) \in Z^{q×m} _q \times Z^m _p(A,b)∈Z
q
q×m

×Z
p
m

，存在另一种算法B\mathcal {B}B，求解参数q,r, n, m, 的LWR，在参数为$ (A’,B’)，对，对，对A’从从从Z^n _q$中均匀随机取样。

我们在这里简述一下证明

证明。假设算法A\mathcal {A}A 能够解决LWT问题，即给定(A，b)它找到一个晶格向量

- v = b mod p，并且

- v = tA mod q 对某些t。

然后，我们可以建立一个oracle，在输入(A，b)它找到u和t，这样

v+pu=tAmod qv + pu = tA \mod q
v+pu=tAmodq

对一些∣∣u∣∣∞≤⌊q2p⌋<r||u||_\infty \leq \left \lfloor \frac{q}{2p}\right \rfloor < r∣∣u∣∣
∞

≤⌊
2p
q

⌋<r

给定LWR实例(A′,B′)(A’,B’)(A
′
,B
′
)算法B\mathcal {B}B设A=pA′A = pA’A=pA
′
, b=b′,b = b’,b=b
′
, r=p−1r = p^{−1}r=p
−1
mod q;然后B\mathcal {B}B通过调用A\mathcal {A}A 输入(A,b).由于A′A’A
′
是均匀的，p与q是共素的，所以A在Zqn×mZ^{n\times m} qZ
q
n×m

上也是均匀的。同时，由于∣∣b∣∣∞≤p||b||\infty ≤p∣∣b∣∣
∞

≤p， (A,b)将是A\mathcal {A}A 的一个合法输入，因此，A\mathcal {A}A 将找到u和t，使得b + pu = tA mod q，即

rb′+u=tA′mod q和b′=⌊tA′mod q⌋rrb’+u=tA’ \mod q 和 b’=\left \lfloor tA’ \mod q\right \rfloor _r
rb
′
+u=tA
′
modq和b
′
=⌊tA
′
modq⌋
r

因此，t是计算LWR问题的解。

现在我们准备对伪造的难度进行量化定理1 (Unforgeability)。让B是一个公共密钥生成按我们的方案参数q, p, n, m。对于任何新的输入消息µ,如果敌人能够打造一个签名,不可忽视ρ概率,然后有一个算法B\mathcal {B}B有相同的概率解决LWTq,p,k,mLWT_{q,p,k,m}LWT
q,p,k,m

证明。首先，我们将哈希函数H建模为均匀输出在ZpnZ^n_pZ
p
n

上的随机预言符。此外，伪造者被要求在一个他以前没有见过的消息上签名。因此，如果算法B\mathcal {B}B能够以不可忽略的概率μ\muμ为每一个合法的输入对象伪造签名，那么一定是A\mathcal {A}A能够伪造任何合法的mp=H(μ∣B)m_p = H(\mu |B)m
p

=H(μ∣B)同时，从伪造者的角度来看，任何新的向mod p\mod pmodp向量看起来都像是一个合法的散列输出。

其次，我们声明B与随机一致地从Zpk×mZ^{k×m} _pZ
p
k×m

中选择的矩阵不可区分。这是由于A与随机均匀地从Zpn×mZ^{n×m} _pZ
p
n×m

中选取的矩阵不可区分。回忆B=A1(−A2)−1mod qB = A_1(−A_2)^{−1} \mod qB=A
1

(−A
2

)
−1
modq和A=[A1A2]A = \begin{bmatrix}A _1\ A_2\end{bmatrix}A=[
A
1

A
2

]。

因此，给定LWT实例(A’,b’)，伪造者无法区分A’与合法生成的公钥;它也不能区分b’和合法生成的公共消息摘要。结果，它将返回一个签名向量v，该向量将以概率ρ\rhoρ递进的方式通过验证测试。从v中很容易提取出LWT问题的解。

我们注意到，从伪造到LWR/LWT的降低如此之小，我们将需要一个相当大的p，按q\sqrt{q}
q

的顺序，这使得该方案的效率较低。在下一节中，我们将看到，高效的实例化使用来自著名攻击的实际参数(这也是大多数实用的基于格的签名的设计原则)。为此，我们将选择一个小的p，允许有效的拒绝抽样。

strong unforgeability。(标准的)不可伪造性概念的一个微妙之处是，伪造者被要求签署以前从未签署过的消息。然而，强不可伪造性的概念要求攻击者不能在消息上伪造签名，即使给出了同一消息的一组签名。上述定理没有说明这一点。实际上，这里我们展示了一个修改，允许实现强大的不可伪造性。

对于给定的消息摘要mpm_pm
p

，与该消息摘要相关的所有候选签名都是原始格与pZn+mppZ^n +m_ppZ
n
+m
p

相交的短向量。因此，伪造的任务变成了在原始格中寻找一个满足长度要求和同余模p要求的短向量。这在[18]大致是还原到approx-cvp.

现在，假设向攻击者提供了同一消息摘要上的一组签名，那么，攻击者在这个格子中找到另一个短向量(与没有这个列表相比)就变得更容易了，也就是说，在同一消息上生成一个新的签名。然而，我们注意到这些签名的任何线性组合都不太可能同时满足正确的模p同余条件。

通常，我们实现强不可伪造性的解决方案是在生成消息摘要时在散列中包含一个随机的“盐”;此盐将作为签名的一部分，并在验证期间使用。这确保了相同的消息摘要出现不止一次的可能性非常小(每个消息的概率(1=p)2n(1=p)^{2n}(1=p)
2n
)。注意，这也是为基于GPV的签名[15]提供类似功能的相同技术。

然而，由于强不可铸造性模型有时对于实际应用(即，攻击者不需要伪造新的签名，因为它已经在同一消息上获得了它们的列表)，我们在有效的实例化中忽略了这个salt，以最小化签名的大小。

📖 一个使用NTRU格的实际实例化
在上一节中，我们提出了一个基于SIS/LWT的低效模格签名方案，该方案要求n≈m log(m)。即使我们使用环的版本，这个方案仍然有些低效，因为它需要n≈log(m) - m的减少直接来自环的使用。提高效率的一种自然方法是放宽对n≈log(m)的要求(这将使底层(ring) SIS问题更容易，因此我们将从最著名的攻击中获得参数)。

例如，我们可以把n简化为2m(在环化的情况下是2)。这使得A1A_1A
1

是一个方阵，这就导致了另一个问题:

pS1A1+ImA2=0mod ppS_1A_1+I_mA_2=0\mod p
pS
1

A
1

+I
m

A
2

=0modp

当A1A_1A
1

是方阵且可逆时，我们可以很容易地从A1A_1A
1

和A2A_2A
2

恢复S1S_1S
1

一个天真的补救方法是设置A2A_2A
2

是私有的,因此我们将有一个秘密矩阵和[pS1∣A2][pS_1|A_2][pS
1

∣A
2

]一个公共矩阵[A1Im]\begin{bmatrix}A_1\ I_m\end{bmatrix}[
A
1

I
m

]也满足上述方程没有暴露S1S_1S
1

。这个看似合理的解决方案带来了另一个挑战:我们无法再对向量的t边进行微调，因为现在A2A_2A
2

已经不再小了。如果我们做同样的微调，u2u_2u
2

的系数会非常大，总是会导致q的wrap-around。

因此，上述问题的最终解决方案是拥有一个小型的私有A2A_2A
2

。最终的关键生成是找到这样的A2A_2A
2

和可逆S1S_1S
1

，并设置A1=A2(pS1)−1mod qA_1 = A_2(pS_1)^{−1} \mod qA
1

=A
2

(pS
1

)
−1
modq。下面，我们将稍微改变符号:H:=A1,G:=A2H := A_1, G := A_2H:=A
1

,G:=A
2

和F:=S1F:=S_1F:=S
1

4.1 方案实施
在下面，我们将对多项式环Rq=Zq[x]/(xN+1)\mathcal {R}_q = Z_q[x]/(x^N + 1)R
q

=Z
q

[x]/(x
N
+1)进行处理。我们的方案也适用于其他环，例如Zq[x]/(xN−1)Z_q[x]/(x^N−1)Z
q

[x]/(x
N
−1)，只是做了一些小小的修改。设f(x)，g(x)f(x)， g(x)f(x)，g(x)和h(x)h(x)h(x)是RqR_qR
q

中的3个多项式，其中f(x)f(x)f(x)和g(x)g(x)g(x)系数很小;h(x)=p−1g(x)f−1(x)h (x) = p^{−1} g(x) f^{-1} (x)h(x)=p
−1
g(x)f
−1
(x)。我们用fghf g hfgh表示多项式的向量形式。设F、G、HF、G、HF、G、H为由负循环旋转得到的矩阵。关于hhh的NTRU晶格被定义

Lh={(u,v)∈Rq2:uh=v}\mathcal{L}_h ={(u,v)\in \mathcal{R}^2_q :uh=v}
L
h

={(u,v)∈R
q
2

:uh=v}

或者更确切地说，向量/矩阵形式:

Lh={(u,v):uH=vmod q}\mathcal {L}_h = {(u,v):uH=v \mod q}
L
h

={(u,v):uH=vmodq}

那里存在一个公共基础P=[0qININH]P=\begin{bmatrix} 0 & qI_N \ I_N & H \end{bmatrix}P=[
0
I
N

qI
N

H

]和秘密发生器[pF∣G][pF|G][pF∣G]。我们还要求g(x)g(x)g(x)对RpR_pR
p

可逆，也就是ggg对ppp可逆。

该方案的其余部分几乎与上一节中介绍的方案相同，除了两个不同之处。

首先，我们使用双峰高斯分布来提高接受率。为了解决这个问题，我们设p = 2，使b=r±afb = r±afb=r±af的符号变化在对ppp作模后消失。

其次，我们使用[pF∣G][pF|G][pF∣G]而不是[pS1∣Im][pS_1|I_m][pS
1

∣I
m

]来执行微观调整。这一修改确实提出了另一个问题:在签字过程中t边的向量将包含关于G的信息。更精确地说，t边的向量将是v:=v1±agv := v_1±agv:=v
1

±ag，其中v1v_1v
1

与Rq\mathcal{R}_qR
q

上的一致不可区分，a与ZpNZ^N_pZ
p
N

上的一致不可区分。我们需要进行拒收采样来封闭g信息的泄漏。如[18]所示，拒收采样后，v的分布在计算上与均匀分布在(−q2+Bt;q2−Bt)(−\frac{q}{2} + B_t;\frac{q}{2} −B_t)(−
2
q

+B
t

;
2
q

−B
t

)表示一个公共参数BtB_tB
t

，该参数依赖于q、a的(均匀)分布以及g中的+1和- 1的数量。

为了避免混淆，我们将用MsM_sM
s

表示s边的拒收率，MtM_tM
t

表示t边，M表示总比率。

设计NTRU加密内容：

class NtruCipher:
N = None
p = None
q = None
f_poly = None
g_poly = None
h_poly = None
f_p_poly = None
f_q_poly = None
R_poly = None

def __init__(self, N, p, q):
    self.N = N
    self.p = p
    self.q = q
    self.R_poly = Poly(x ** N + 1, x).set_domain(ZZ)
    log.info("NTRU(N={},p={},q={}) initiated".format(N, p, q))

def generate_random_keys(self):
    g_poly = random_poly(self.N)
    log.info("g: {}".format(g_poly))
    log.info("g coeffs: {}".format(Counter(g_poly.coeffs())))


    tries = 10
    while tries > 0 and (self.h_poly is None):
        f_poly = random_poly(self.N)
        log.info("f: {}".format(f_poly))
        log.info("f coeffs: {}".format(Counter(f_poly.coeffs())))
        try:
            self.generate_public_key(f_poly, g_poly)
        except NotInvertible as ex:
            log.info("Failed to invert f (tries left: {})".format(tries))
            log.debug(ex)
            tries -= 1
    if self.h_poly is None:
        raise Exception("Couldn't generate invertible f")

def generate_public_key(self, f_poly, g_poly):
    self.f_poly = 2 * f_poly + 1
    self.g_poly = g_poly
    log.debug("Trying to invert: {}".format(self.f_poly))
    self.f_p_poly = invert_poly(self.f_poly, self.R_poly, self.p)
    log.debug("f_p ok!")
    self.f_q_poly = invert_poly(self.f_poly, self.R_poly, self.q)
    log.debug("f_q ok!")
    log.info("f_p: {}".format(self.f_p_poly))
    log.info("f_q: {}".format(self.f_q_poly))
    log.debug("f*f_p mod (x^n - 1): {}".format(((self.f_poly * self.f_p_poly) % self.R_poly).trunc(self.p)))
    log.debug("f*f_q mod (x^n - 1): {}".format(((self.f_poly * self.f_q_poly) % self.R_poly).trunc(self.q)))
    p_f_q_poly = (self.p * self.f_q_poly).trunc(self.q)
    log.debug("p_f_q: {}".format(p_f_q_poly))
    h_before_mod = (p_f_q_poly * self.g_poly).trunc(self.q)
    log.debug("h_before_mod: {}".format(h_before_mod))
    self.h_poly = (2 * h_before_mod % self.R_poly).trunc(self.q)
    log.info("h: {}".format(self.h_poly))

def encrypt(self, msg_poly, rand_poly):
    log.info("r: {}".format(rand_poly))
    log.info("r coeffs: {}".format(Counter(rand_poly.coeffs())))
    log.info("msg: {}".format(msg_poly))
    log.info("h: {}".format(self.h_poly))
    return (((rand_poly * self.h_poly).trunc(self.q) + msg_poly) % self.R_poly).trunc(self.q)

def decrypt(self, msg_poly):
    log.info("f: {}".format(self.f_poly))
    log.info("f_p: {}".format(self.f_p_poly))
    a_poly = ((self.f_poly * msg_poly) % self.R_poly).trunc(self.q)
    log.info("a: {}".format(a_poly))
    b_poly = a_poly.trunc(self.p)
    return b_poly

4.2 秘钥生成
def Key_generation(N,p,q):
f_raw=mathutils.random_poly(N).trunc(2)
f_updated = p * f_raw + 1
modlist=np.zeros(N+1,int)
modlist[0]=1
modlist[-1]=1
#print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
inv_f_updated = mathutils.invert_poly(f_updated, mod, q)
#print(“f:{0}”.format(f_updated))
s=mathutils.random_poly(N).trunc(2)
h = ((p * inv_f_updated * s)%mod).trunc(q)
#print(s)
#print(h)
return (f_updated,(h,s))
4.3 加解密
def encryption(N,p,q,pk,m):
modlist = np.zeros(N + 1, int)
modlist[0] = 1
modlist[-1] = 1
# print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
c = ((pk[0] * pk[1] + m) % mod).trunc(q)
return c

def decryption(N,p,q,sk,c):
modlist = np.zeros(N + 1, int)
modlist[0] = 1
modlist[-1] = 1
# print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
m = ((sk * c) % mod).trunc(q).trunc§
return m
4.4 同态运算
def homo_add(N,p,q,c1,c2):
modlist = np.zeros(N + 1, int)
modlist[0] = 1
modlist[-1] = 1
# print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
return ((c1+c2)%mod).trunc(q)

def homo_mult(N,p,q,c1,c2):
modlist = np.zeros(N + 1, int)
modlist[0] = 1
modlist[-1] = 1
# print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
return ((c1*c2)%mod).trunc(q)

def evaluate(N,p,q,sk1,sk2,c):
modlist = np.zeros(N + 1, int)
modlist[0] = 1
modlist[-1] = 1
# print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
m=((sk1sk2c)%mod).trunc(q).trunc§
return m
5. 最终代码及结果
In [4]
import sys
sys.path.append(‘/home/aistudio/wy’)

import numpy as np

from ntru import mathutils

from sympy.abc import x

from sympy import ZZ, Poly

def Key_generation(N,p,q):
f_raw=mathutils.random_poly(N).trunc(2)
f_updated = p * f_raw + 1
modlist=np.zeros(N+1,int)
modlist[0]=1
modlist[-1]=1
#print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
inv_f_updated = mathutils.invert_poly(f_updated, mod, q)
#print(“f:{0}”.format(f_updated))
s=mathutils.random_poly(N).trunc(2)
h = ((p * inv_f_updated * s)%mod).trunc(q)
#print(s)
#print(h)
return (f_updated,(h,s))

def encryption(N,p,q,pk,m):
modlist = np.zeros(N + 1, int)
modlist[0] = 1
modlist[-1] = 1
# print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
c = ((pk[0] * pk[1] + m) % mod).trunc(q)
return c

def decryption(N,p,q,sk,c):
modlist = np.zeros(N + 1, int)
modlist[0] = 1
modlist[-1] = 1
# print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
m = ((sk * c) % mod).trunc(q).trunc§
return m

def homo_add(N,p,q,c1,c2):
modlist = np.zeros(N + 1, int)
modlist[0] = 1
modlist[-1] = 1
# print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
return ((c1+c2)%mod).trunc(q)

def homo_mult(N,p,q,c1,c2):
modlist = np.zeros(N + 1, int)
modlist[0] = 1
modlist[-1] = 1
# print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
return ((c1*c2)%mod).trunc(q)

def evaluate(N,p,q,sk1,sk2,c):
modlist = np.zeros(N + 1, int)
modlist[0] = 1
modlist[-1] = 1
# print(modlist)
mod = Poly(modlist, x).set_domain(ZZ)
m=((sk1sk2c)%mod).trunc(q).trunc§
return m

if name==“main”:
N=32
p=32
q=10000723
‘’‘因私有函数库，无法公开进行展示，此处仅对部分技术思路和实验结果进行讲解和展示。
(sk1,pk1)=Key_generation(N, p, q)
#print(sk)
#print(pk)
m1 = Poly([0,1,0,1,1], x).set_domain(ZZ)
c1=encryption(N,p,q,pk1,m1)
print(“m1=”,m1)
print(“m1加密结果：”,c1)
m1_decrypted=decryption(N,p,q,sk1,c1)
print(“c1解密结果：”,m1_decrypted)
(sk2, pk2) = Key_generation(N, p, q)
m2 = Poly([1,0,1,0,0], x).set_domain(ZZ)
c2=encryption(N,p,q,pk2,m2)
print(“m2=”,m2)
print(“m2加密结果：”,c2)
m2_decrypted=decryption(N,p,q,sk2,c2)
print(“c2解密结果：”,m2_decrypted)
#print(homo_add(5,2,97,c,c))
homo_c=homo_mult(N, p, q, c1, c2)
print(“m1m2同态乘结果：",homo_c)
homo_m=evaluate(N,p,q,sk1,sk2,homo_c)
print("m1m2同态解密结果：”,homo_m)
‘’’
运行结果如下：

m1= Poly(x3 + x + 1, x, domain=‘ZZ’)
m1加密结果： Poly(3284343*x31 + 2108998x**30 + 3382527x29 - 2022312*x28 + 1445430x**27 - 4103553x26 + 2186932*x25 - 2887823x**24 + 1707515x23 - 1961609*x22 - 4490402x**21 - 488503x20 - 4820228*x19 - 1419062x**18 + 4663653x17 - 616473*x16 - 308613x**15 + 2530948x14 - 3788285*x13 - 2906419x**12 + 540120x11 + 4645349*x10 - 869216x**9 + 4873778x8 + 2887821*x7 + 3266827x**6 - 4884532x5 - 533436*x4 - 2831953x**3 + 2971347x2 + 4985141*x + 118432, x, domain=‘ZZ’)
c1解密结果： Poly(x3 + x + 1, x, domain=‘ZZ’)
m2= Poly(x4 + x2, x, domain=‘ZZ’)
m2加密结果： Poly(633893x**31 + 3141282x30 + 1806755*x29 + 1074787x**28 - 4339348x27 - 2038976*x26 + 110016x**25 - 2084644x24 + 941907*x23 + 764676x**22 - 1392117x21 + 4489722*x20 + 4260836x**19 - 4720594x18 - 4560990*x17 + 4477931x**16 + 91218x15 - 971510*x14 - 2090340x**13 + 2928978x12 - 2315957*x11 + 2963446x**10 - 4442306x9 + 358189*x8 - 393412x**7 - 4145723x6 + 4063545*x5 + 2604736x**4 + 2841033x3 - 2552980*x2 + 2633358x + 2589579, x, domain=‘ZZ’)
c2解密结果： Poly(x4 + x2, x, domain=‘ZZ’)
m1m2同态乘结果： Poly(28479x**31 - 1950186x30 + 4662772*x29 + 2378350x**28 + 3222463x27 - 3270780*x26 - 3911557x**25 + 2268506x24 - 4929247*x23 - 4053986x**22 + 2746968x21 + 2696063*x20 + 2839513x**19 - 2438726x18 + 1562762*x17 - 1295123x**16 + 345153x15 - 728221*x14 - 1510487x**13 - 1473839x12 + 2215256*x11 + 350121x**10 - 648692x9 - 2116576*x8 + 1054796x**7 - 3767592x6 + 1611484*x5 + 474441x**4 + 961208x3 - 953814*x2 + 2593332x - 1408044, x, domain=‘ZZ’)
m1m2同态解密结果： Poly(x7 + 2*x5 + x4 + x3 + x**2, x, domain=‘ZZ’)
6. 📖 小结与展望
本文实现了对NTRUSign的基本知识了解，并通过python实现了该起那么的签名、验证的过程。