基于NTRU可验证的秘密分享方案

A Verifiable Secret Sharing Scheme Based on NTRU

摘要: 随着信息技术的快速发展，数据安全问题日益受到重视。本文提出了一种可验证的秘密分享方案，该方案基于Shamir秘密分享方案，并结合NTRU数字签名算法，增强方案的安全性。NTRU数字签名算法作为一种能够抵抗量子攻击的数字签名算法，有效防御了伪造和篡改攻击，确保了秘密恢复过程的可信度。本文详细分析了方案的正确性和安全性。

Abstract: With the rapid development of information technology, data security issues are increasingly being taken seriously. This paper proposes a verifiable secret sharing scheme based on the Shamir secret sharing scheme and combined with the NTRU digital signature algorithm to enhance the security of the scheme. The NTRU digital signature algorithm, as a type of digital signature algorithm capable of resisting quantum attacks, effectively defends against forgery and tampering attacks, ensuring the credibility of the secret recovery process. This paper provides a detailed analysis of the correctness and security of the scheme.

1. 引言

随着计算机和通信技术的迅速发展，秘密分享作为一种关键的密码技术逐渐被广泛应用。其基本思想是将一条秘密信息拆分成多个部分，将各部分分发给不同的成员，只有当足够多的成员合作时，才能重构出原始秘密。

1979年，Shamir [1]基于拉格朗日多项式提出了经典的$\left(t,n\right)$ 阈值秘密分享方案。Shamir的方案将秘密分割为n个部分，需要至少t个秘密才能恢复原始秘密。该方案因其简单而高效，成为密码学中的经典方法。秘密分享技术是一种用于划分秘密信息(如口令、密钥等)的加密技术。将秘密分成多个份额，只有在满足一定的门限条件时，才能重构出原始的秘密信息[2]-[4]。秘密分享为信息安全提供了强有力的保障，但也面临着一些挑战。目前，大多数秘密分享方案都是基于传统数学困难问题假设，如因子分解、离散对数等[5]-[7]。然而，随着Shor [8]在1994年提出了一种量子算法来解决多项式内的因子分解问题，越来越多的学者提出了针对传统数学困难问题量子破解算法的研究，证明了基于传统数学困难问题方案的脆弱性。因此，迫切需要研究新的后量子方案。从实用的角度来看，基于格的秘密分享具有重要的研究意义和应用前景，特别是它的一些特殊性质，如可验证性、多秘密性等，从而拓宽了秘密分享在不同场景中的应用[9] [10]。1996年，Hoffstein等人提出了NTRU公钥加密方案[11]，并首次提出了NTRU假设。2000年，NTRU公钥加密方案的三位作者利用NTRU提出了NSS数字签名体制[12]，其安全性与在某个格中寻找短的向量有关。2003年，Hoffstein等人基于NTRU提出了签名方案[13]，作为GGH签名方案的高效实现。2014年，Hoffstein等人基于NTRU提出了Hash And Sign类型的签名方案[14]。国内学者也对NTRU签名算法进行了深入研究，并取得了显著成果。2006年，杨真真等人结合格中的最近向量问题(CVP)和单向哈希函数的不可逆性，提出了一种基于NTRU的数字签名方案[15]。2008年，胡予濮提出了一种新型的NTRU类数字签名方案[16]，该方案通过将公钥恢复私钥与格上的最小向量问题(SVP)等价，伪造签名与格上的最近向量问题(CVP)等价，但可能泄露私钥信息。2015年，曹杰等人提出了一种新型基于NTRU的签名方案[17]，并对其安全性进行了全面分析，探讨了副本分析等攻击方法，同时优化了签名验证的速度。

本文提出了一种基于NTRU数字签名算法的$\left(t,n\right)$ 秘密分享方案，从理论上对方案的安全性和正确性进行了证明。利用NTRU数字签名算法，有效防止了恶意解码和篡改。

本文第2节介绍了秘密分享的基本概念，格理论的相关知识，以及NTRU公钥加密算法的核心原理，为理解本文提出的方案打下基础。第3节详细描述了该方案的设计和实现过程，包括参数设置、方案初始化、秘密分享过程和秘密重建过程。此部分重点阐述了如何结合NTRU算法和Shamir的阈值方案，以实现高效且安全的秘密分享。第4节对提出的方案进行了详细的正确性和安全性分析。通过定理的证明，验证了方案的理论可行性和安全性保障。第5节总结了本文的主要贡献，并提出了未来的研究方向和改进建议。

2. 基础知识

2.1. 秘密分享

Shamir秘密分享是一种将秘密分割成多个份额的方法[18]，使得只有当一定数量的份额组合在一起时，原始秘密才能被恢复。这个过程可以用以下步骤描述：

1) 秘密分发：设有n个参与者进行秘密分享，存在可信方为管理者，秘密为S，管理者选择一个足够大的素数q，构造多项式$s\left(x\right)=a_0+a_{1}x+a_2{x}^2+\cdots +a_{t-1}{x}^{t-1}\left(\mathrm{mod}q\right)$ 其中$a_0=S$ ，$a_1,\cdots ,a_{t-1}$ 是随机生成的系数，t是恢复秘密所需的最小份额数。

2) 生成份额：对于$i=1,2,\cdots ,n$ ，管理者计算$s\left(x_i\right)$ ，其中$x_i$ 是为每个参与者生成的随机值；每个$\left(x_i,s\left(x_i\right)\right)$ 称为一个份额，其中i是份额的索引，$s\left(x_i\right)$ 是份额的值。

3) 秘密恢复：t个参与者通过拉格朗日插值法恢复多项式$s\left(x\right)$ ，恢复多项式后，可以通过计算$s\left(0\right)$ 来恢复秘密S。

2.2. 偏差

定义1 (偏差) 给定两个多项式$a\left(X\right)$ 和$b\left(X\right)$ ，首先将它们的系数模q约简到区间$\left[-\frac{q}{2},\frac{q}{2}\right]$ ，再将它们的系数模p约简到区间$\left[-\frac{p}{2},\frac{p}{2}\right]$ ，化简后的多项式分别为：

$\overline{a}\left(X\right)={\overline{a}}_0+\cdots +{\overline{a}}_{N-1}{X}^{N-1}$

$\overline{b}\left(X\right)={\overline{b}}_0+\cdots +{\overline{b}}_{N-1}{X}^{N-1}$

偏差是两个多项式在模p情况下的不同系数的位置的数量：

$Dev\left(a,b\right)=\#\left\{i:{\overline{a}}_i\ne {\overline{b}}_i\mathrm{mod}p\right\}$

其中$\#$ 表示集合的元素个数。偏差是验证签名的核心指标，用于确保签名s和秘密m的关联性，其中$D_{\min }$ 和$D_{\max }$ 控制允许的偏差范围。通过偏差验证，可以在签名和消息之间引入一定的“容忍度”，既保证签名有效性，又增强安全性。实际计算中，多项式的卷积和模运算可能引入小的系数偏差。偏差允许一定程度的误差，而不影响签名的真实性。

偏差范围的设置避免了直接解码攻击：如果没有偏差$D_{\min }=D_{\max }=0$ ，攻击者可以通过多次观察完全恢复私钥。偏差的存在迫使攻击者处理更高维度的格问题，显著增加破解难度。

偏差范围的选择直接影响安全性和签名验证速度：较大的$D_{\max }$ 提高了效率，但降低安全性。较小的$D_{\max }$ 增强了安全性，但增加了计算开销。

2.3. NTRU格

定义2 (NTRU格)给定环$R_q={\mathbb{Z}}_q\left[x\right]/\left(X^N-1\right)$ ，q是素数，N是2的幂，设$f,g\in R_q$ (f存在逆元$f^{-1}\in R_q$ )，$h=f^{-1}\cdot g\mathrm{mod}q$ 。则NTRU格由q和h定义为：

${\Lambda }_{h,q}=\left\{\left(u,v\right)\in R^2|u+vh=0\mathrm{mod}q\right\}$

2.4. NTRU数字签名

NTRU数字签名的核心思想是利用公共和私有密钥对，这些密钥的形式与NTRU公钥密码体系中使用的密钥相同。公钥是一个多项式h，私钥是一个多项式f。签名过程涉及选择一个多项式w，它与消息m和私钥f相乘，生成签名s。验证过程需要检查s与m的偏差是否在允许的范围内，以及使用公钥h计算出的多项式c与另一个多项式$g_0\cdot m$ 的偏差是否也在允许的范围内。NTRU数字签名方案介绍见表1：

Table 1. NTRU lattice-based signature scheme

表1. NTRU数字签名方案

步骤1：密钥生成	NTRU数字签名方案涉及五个参数$\left(N,p,q,D_{\min },D_{\max }\right)$ 。选择两个多项式f和g，计算f在模q情况下的逆元$f^{-1}$ ，然后计算公钥$h\equiv f^{-1}\cdot g\left(\mathrm{mod}q\right)$
步骤2：签名过程	构造一个掩码多项式w，然后对消息m计算签名$s\equiv f\cdot w\left(\mathrm{mod}q\right)$ ，则签名是$\left(m,s\right)$
步骤3：验证过程	检查$s\ne 0$ 并验证两个条件：s和$f_0\cdot m$ 的偏差是否在$D_{\min }$ 和$D_{\max }$ 之间，以及$c\equiv h\cdot s\mathrm{mod}q$ 和$g_0\cdot m$ 的偏差是否在$D_{\min }$ 和$D_{\max }$ 之间

3. 基于NTRU可验证的秘密分享方案设计

文献[19]-[21]介绍了格理论在秘密共享技术中的应用，在本节将详细介绍基于NTRU数字签名算法的可验证秘密分享方案的设计，包括参数设置、方案初始化、秘密分享过程和秘密重建过程，首先，参数设置部分见表2。

3.1. 参数设置

Table 2. Parameter settings

表2. 参数设置

N	NTRU中使用的多项式的最高次数，通常作为素数
q	NTRU中的最大模数，通常为正整数
p	NTRU中的最小模数，通常为小的正整数或低次幂的多项式
$f,g$	NTRU中生成密钥的多项式
$f^{-1}$	f模p下的逆元
w	NTRU中用于加密的随机多项式

3.2. 秘密分享过程

管理员生成参数$\left(N,p,q\right)$ ，选择可逆私有多项式f和多项式g，形如：

$f=f_0+p{f}_1$

$g=g_0+p{g}_1$

其中$f_0,g_0$ 是固定的多项式，$f_1,g_1$ 是具有小系数的随机多项式，从多项式集合$F_f$ 和$F_g$ 中选取，p是一个小整数。计算多项式$f^{-1}$ ，通过扩展欧几里得算法满足下式：

$f^{-1}\cdot f\equiv 1\left(\mathrm{mod}q\right)$

计算公钥如下式所示：

$h\equiv f^{-1}\cdot g\left(\mathrm{mod}q\right)$

私钥为$\left(f,g\right)$ ，公钥为h，管理员将秘密转换为对应的十进制数，作为多项式$sk\left(x\right)$ 中的常数项m进行计算，如下式所示：

$sk\left(x\right)=m+{\displaystyle \sum _{i=1}^{t-1}{a}_i{x}^i}$

3.3. 签名过程

计算$s{k}_i=sk\left(x_i\right)$ ，$\left(i=1,2,\cdots ,n\right)$ 。构造随机掩码$w_i$ ，如下式：

$w_i=s{k}_i+w^{\prime }+p{w}^{″}$

其中$s{k}_i$ 为每位参与者所持有的份额，i为每位参与者的ID，$w^{\prime },w^{″}$ 是具有小系数的随机多项式。使用私钥多项式f，计算签名：

$s_i\equiv f\cdot w_i\left(\mathrm{mod}q\right)$

则签名结果为$\left(s{k}_i,s_i\right)$ ，将$\left(x_i,s{k}_i,s_i\right)$ 作为份额通过安全信道传送给子份额持有者

3.4. 验证过程

文献[22]-[25]介绍了多种秘密共享份额验证方法，本文采用偏差(Deviation)概念[12]，用于衡量两个多项式在模p的情况下的不同程度。为了排除伪造的零签名，首先确保$s_i\ne 0$ ，然后验证以下两个条件：

验证条件(A)：比较$s_i$ 和$f_0\cdot m$ 的偏差：

$D_{\min }\le Dev\left(s_i,f_0\cdot m\right)\le D_{\max }$

验证条件(B)：使用公钥h，计算$c_i\equiv h\cdot s_i\left(\mathrm{mod}q\right)$ ，比较$c_i$ 和$g_0\cdot s{k}_i$ 的偏差

$D_{\min }\le Dev\left(c_i,g_0\cdot s{k}_i\right)\le D_{\max }$

如果验证条件(A)和(B)均满足，则签名有效，可进行秘密重建过程，否则，可通过对应未通过验证份额的索引i获得欺骗者的ID。

3.5. 秘密重构过程

验证签名通过，可进行秘密重构，通过拉格朗日插值法对原始多项式进行重建，如下式所示：

$sk\left(x\right)={\displaystyle \sum _{i=1}^t\left(s{k}_i{\displaystyle \sum _{j\ne i}^{1\le j\le t}\frac{x-x_i}{x_j-x_i}}\right)}$

当$x=0$ 时，可得到$sk\left(0\right)=m$ 。

4. 方案分析

4.1. 正确性分析

定理1本方案满足至少t个参与者可恢复秘密信息。

证明：本方案中秘密分发以及重建过程应用Shamir多项式和拉格朗日插值法，与文献[1]类似，并在此基础上增加了安全验证过程，保证可成功重建秘密的条件并且增加了更多的安全性。

定理2在NTRU签名方案中，如果私钥f和掩码多项式$w_i=s{k}_i+w^{\prime }+p{w}^{″}$ 被正确选择，那么由f生成的签名$\left(s{k}_i,s_i\right)$ 必定能够通过验证条件A和B。

证明：根据NTRU签名方案，签名s的生成公式为：

$\begin{array}{c}{s}_i\equiv f\cdot w_i\mathrm{mod}q\\ \equiv f_0\cdot s{k}_i+f_0\cdot w^{\prime }+p{f}_0\cdot w^{″}+p{f}_1\cdot w_i\mathrm{mod}q\end{array}$

上式可以分为主项$f_0\cdot m$ 、修正项$f_0\cdot w\text{'}$ 和随机项$p{f}_0\cdot w^{″}+p{f}_1\cdot w_i$ 。

目标1：证明$s_i$ 和$f_0\cdot m$ 的偏差满足$Dev\left(s_i,f_0\cdot s{k}_i\right)\le D_{\max }$ 。$w^{\prime }$ 的设计是为了减少$s_i$ 和$f_0\cdot s{k}_i$ 的偏差；通过遍历每个系数位置，调整$w^{\prime }$ 使偏差最小化。p的选择限制了随机项的幅度；随机掩码$w^{″}$ 的稀疏性(例如，非零系数有限)确保随机项引入的噪声有限。

多项式$f\cdot w_i$ 的系数在模q下可能出现截断。根据小系数多项式的性质，卷积的无穷范数满足：

${\Vert f\cdot w_i\Vert }_{\infty }\approx \gamma \cdot \Vert f\Vert \cdot \Vert w_i\Vert$

其中$\gamma <0.15$ 是经验值，只要$\gamma \cdot \Vert f\Vert \cdot \Vert w\Vert <q/2$ ，模q化简不会显著增加偏差。因此通过合理参数选择和$w^{\prime },w^{″}$ 的设计，可以保证偏差$Dev\left(s_i,f_0\cdot s{k}_i\right)$ 满足条件。

目标2：证明$c_i$ 和$g_0\cdot s{k}_i$ 的偏差满足$Dev\left(c_i,g_0\cdot s{k}_i\right)\le D_{\max }$ 。根据验证公式，$c_i$ 的计算为：

$\begin{array}{c}{c}_i\equiv h\cdot s_i\mathrm{mod}q=g\cdot w_i\mathrm{mod}q\\ \equiv g_0\cdot s{k}_i+g_0\cdot w^{\prime }+p{g}_0\cdot w^{″}+p{g}_1\cdot w_i\mathrm{mod}q\end{array}$

主项$g_0\cdot s{k}_i$ 在模p下，理论上应与$c_i$ 的主要部分一致。修正项$g_0\cdot w^{\prime }$ 和随机项$p{g}_0\cdot w^{″}+p{g}_1\cdot w_i$ 的分析与目标1类似。模q化简得影响由$g\cdot w_i$ 得无穷范数控制，通过参数设置可以确保截断误差不会引入额外偏差。

通过以上分析和推导，已证明本方案中签名方案的正确性。只要参数选择合理(如$q,p,N,D_{\min },D_{\max }$ )，并正确生成签名$\left(s{k}_i,s_i\right)$ ，签名将通过验证条件(A)和(B)。

4.2. 安全性分析

定理3本方案安全性基于格上最短向量困难问题。

证明：给定公钥$h=f^{-1}\cdot g\mathrm{mod}q$ ，攻击者希望通过NTRU格恢复私钥$\left(f,g\right)$ 。令NTRU格为$L_{NTRU}$ 是一个2N-维格，生成矩阵为：

$B=\left[\begin{array}{cc}I& H\\ 0& qI\end{array}\right]$

其中I是$N\times N$ 单位矩阵，H是公钥h的循环矩阵。攻击者需要在格$L_{NTRU}$ 中找到短向量$\left(f,g\right)$ ，使得：

$f\cdot h\equiv g\mathrm{mod}q$

假设攻击者使用格约简算法(如LLL或BKZ)，其复杂度与格的维度和最短向量长度密切相关。根据高斯启发式，$L_{NTRU}$ 中最短向量长度为：

$\lambda \approx \sqrt{\frac{q}{2\pi e}}\cdot N^{1/4}$

如果私钥向量的欧几里得范数$\left(\Vert f,g\Vert \right)$ 远小于$\lambda$ ，则格约简攻击可能恢复私钥。因此本方案中推荐参数选取$N=251,q=128$ 确保$\Vert f,g\Vert \gg \lambda$ 。

定理4本方案随机搜索给定消息上的有效签名的概率是可忽略的。

证明：设想一名攻击者企图随机挑选出一条消息的有效签名[26]。他首先随机挑选一个符合条件(A)的s值，这一步相对容易，接着尝试找到一个符合条件(B)的$c_i$ 值。一旦找到，攻击者便伪造了签名；如果没找到，攻击者就更换s值重试。我们需要评估一个随机选择的、符合条件(A)的s值生成一个符合条件(B)的$c_i$ 值的几率。s值的条件(A)对最终的$c_i$ 值没有实质影响，因为$c_i$ 值是通过s值乘以h并对q取模数得到的，而h的值在模q下接近于均匀分布。简而言之，我们是在计算一个随机选择的系数在$-q/2$ 到$q/2$ 区间内的多项式$c_i$ 满足条件(B)的概率。这个概率可以通过基础概率论来估算。

随机挑选的$c_i$ 的系数可以看作是N个独立的随机变量，它们的值在模q下均匀分布。$s{k}_i$ 的系数是固定的目标值在模p下。我们需要计算随机挑选的N个整数元组在模q下的坐标至少为$D_{\min }$ 且不超过$D_{\max }$ 等于在模p下到固定目标值的概率。如果q远大于p，那么这个概率可以近似为：

$P\left(D_{\min }\le Dev\left(c_i,g_0\cdot s{k}_i\right)\le D_{\max }\right)\approx \frac{1}{p^N}{\displaystyle \sum _{d=D_{\min }}^{D_{\max }}\left(\begin{array}{l}N\\ d\end{array}\right){\left(p-1\right)}^d}$

注意，对于条件(B)，概率是$p^{-N}$ ，因为$c_i\left(\mathrm{mod}p\right)$ 的所有N个“随机”系数必须匹配$g_0\cdot s{k}_i$ 。所以使用随机选择的s成功伪造的概率可忽略。

定理5本方案可抵抗NTRU格结构及其针对公钥的格攻击。

证明：攻击者可以尝试从公钥h中提取私钥f，无论是否有一长串真实签名。或者，他可以尝试在不知道f的情况下伪造签名，只使用h。攻击者希望通过格约简算法从公钥中获得私钥。与NTRU密码系统的情况一样，通过这种方式恢复私钥相当于解决某类最短或最接近向量问题。

设L是一个行列式为d，维数为n的格。设$v_0$ 表示给定的固定向量，可能是原点。设r表示一个给定的半径，并考虑定位一个向量$v\in L$ 的问题，使得$\Vert v-v_0\Vert <r$ 。对于大的n，解决这个问题的难度与数量有关，$\kappa$ 值是衡量格中最短向量与目标向量之间距离的一个指标：

$\kappa =\kappa \left(L,r\right)=\frac{r}{d^{1/n}\sqrt{n/\left(2\pi e\right)}}$

这里的分母是高斯启发式算法预测L中最短预期向量的长度。如果$\kappa <1$ ，那么高斯启发式表明，如果存在解决方案，那么解决方案可能是唯一的。$\kappa$ 越接近0，使用格约简方法找到唯一解决方案就越容易。当$\kappa$ 接近1时，格约简方法变得越无效。例如，设$\left(L_n,r_n,v_{0,n}\right)$ 是一系列格、半径和目标向量，其维度n不断增加，包含目标向量(即，满足$\left|v_n-v_{0,n}\right|<r_n$ )，且其$\kappa$ 值满足：

${\kappa }_n=\kappa \left(L_n,r_n\right)=b/\sqrt{n}$

对于常数b，格点归约方法找到目标向量$v_n$ 所需的时间像${\text{e}}^{\alpha n}$ 一样增长，$\alpha$ 的值大致与b成正比。类似地，如果$\kappa \ge 1$ ，那么方程的解可能不是唯一的，但当$\kappa$ 接近1时，找到解会变得越来越困难。

由于本方案中的公钥与NTRU公钥的形式非常相似，因此可以使用基于最短向量的2N维格攻击来尝试从h导出f和g。2N维NTRU格$L^{NT}$ 由集合中的2N个向量的线性组合组成：

$\left\{\left(X^i,X^i\cdot h\right):0\le i\le N\right\}\cup \left\{\left(0,q{X}^i\right):0\le i\le N\right\}$

更有效的攻击是利用对$f_0,g_0$ 的了解，在同一个2N维格上对$f_1,g_1$ 进行最近向量攻击。目标是在$L^{NT}$ 中找到最接近向量$\left(0,\left(g_0-f_0\cdot h\right)p^{\prime }\right)$ 的向量，其中$p{p}^{\prime }\equiv 1\left(\mathrm{mod}q\right)$ 。如果成功，这次攻击会产生一个小型F，使得$G\equiv F\cdot h-\left(g_0-f_0\cdot h\right)p^{\prime }\left(\mathrm{mod}q\right)$ 也很小。然后$\left(f_0+pF,g_0+pG\right)$ 要么是原始密钥，要么是一个有用的替代品。采用这种方法，在平衡格后，我们得到方程中的常数c的以下估计：

$b>\frac{2\pi e\Vert f_1\Vert \cdot \Vert g_1\Vert }{q}$

由于更大的b值会产生更长的求解运行时间，所以$N,F_f,F_g$ 被选择为使得$\Vert f_1\Vert ,\Vert g_1\Vert$ 可以给出足够大的b值则可防御格攻击。

5. 总结

本文提出了一种基于NTRU签名算法可验证的秘密分享方案。该方案通过利用NTRU数字签名的高效性和抗量子性，结合随机掩码，防止了成员之间的欺骗行为和密码分享份额的恶意篡改，从而提升了整体安全性。与传统基于离散对数和大数分解的方案相比，NTRU基于格的安全性提供了更强的防御能力，尤其在量子计算环境中具有较强的抗攻击能力。该方案不仅有效提升了秘密分享的安全性，还具有较强的灵活性和可扩展性，适应现代信息保护和共享的多样化需求。

基金项目

国家自然科学基金(62472040)；中国版权保护中心版权研究课题(BQ2024017)；北京市教委科研计划资助(No. KM202110015004)；北京市高等教育学会2022年立项面上课题(MS2022093)；北京市教育委员会科学研究计划项目资助(KM202310015002)。

NOTES

^*通讯作者。