本文共 1419 字，大约阅读时间需要 4 分钟。

概括：

• 陷门生成算法产生短基。
• 原像采样算法使用短基。

陷门生成函数生成格的陷门(即格的一个短(好的)基)，原像采样函数本质是一个单向函数，陷门被用来实现原像采样[GPV08]。

原像采样使用的采样函数一般为高斯函数(也可使用二项分布)

1 定义

• 定理(陷门生成算法).令整数$q>3,m>5n\log q$，存在一个有效的算法$TrapGen(q,m)$，该算法能够在多项式时间内生成一个矩阵$A\in {\mathbb{Z}}_q^{n\times m}$和格${\Lambda }^{\perp }(A)$的一个基$T_A\in {\mathbb{Z}}^{m\times m}$使得矩阵$A$的分布在统计上接近于${\mathbb{Z}}_q^{n\times m}$上的均匀分布且让$||{\tilde{\mathbf{T}}}_A||\le O(\sqrt{n\log q})$以压倒性的概率成立。

• 关于原像抽样算法

(高斯)域采样、向量原像采样、矩阵原像采样

基本定义(原像采样算法).令整数$m\ge n,q$为素数，${\Lambda }^{\perp }(A)$是由矩阵$A\in {\mathbb{Z}}_q^{n\times m}$定义的格，矩阵$T_A\in {\mathbb{Z}}^{m\times m}$是格${\Lambda }^{\perp }(A)$的一个基。如果参数$s\ge ||{\tilde{\mathbf{T}}}_A||\cdot \omega (\sqrt{\log q})$，那么对所有的$\mathbf{u}\in {\mathbb{Z}}_q^n$都存在一个多项式时间算法$SampIePre(\mathbf{A},\mathbf{B},s,\mathbf{u})$，它能够从一个统计接近于$G_{{\Lambda }^u(A),s}>$的分布中抽取一个向量$\mathbf{v}\in {\Lambda }^u(A)$。

2 共同点：

• 都是hash-and-sign格签名常用技术

3 不同

• 一个在setup过程。
• 一个在sign过程。
• Lyu2012提出无陷门的签名算法，即Fiat-shamir格签名方案中没有使用陷门(短基)，使用的是一个随机矩阵。

转载地址：http://rjtzi.baihongyu.com/