格密码基础

格

给定 $b_1,b_2,\dots,b_n\in \mathbb{R}^m$ 是$n$个线性无关的列向量，由它们生成的格被定义为：

$\mathcal L(b_1,b_2,...,b_n)=\left\{\sum{x_ib_i}|x_i∈\mathbb Z\right\}$

其中$b_1,b_2,…,b_n$称作格的基。如果我们定义矩阵$B$是$m\times n$的矩阵，其列为$b_1,b_2,\dots,b_n$，则由矩阵$B$生成的格为：

$\mathcal L(B)=\mathcal L(b_1,b_2,...,b_n)=\left\{Bx|x∈\mathbb Z^n\right\}$

其中格的秩为$n$，维数为$m$，如果$n=m$，此时我们称该格为满秩格。

格的行列式

令$B=(b_1,b_2,\dots,b_n)$为格$\Lambda$的一组格基，则格$\Lambda=\mathcal L(B)$的行列式被定义为：

$det(\mathcal L(B))=\sqrt{det(B^TB)}$

格的基本域

给定格基$B=(b_1,b_2,\dots,b_n)\in \mathbb R^{n\times m}$，格的基本域定义为：

$\mathcal{P}(B)=\{\Sigma_{i=1}^nx_ib_i|x_i\in [0,1)\}$

逐次最小距离常量

给定一个格$\mathcal L$，使用$\lambda_i$表示格$\mathcal L$的第$i$个逐次最小长度。即$\lambda_i$定义为$\mathcal L$中以原点为中心，包含$i$个线性无关格向量的最小球的半径。

q模格

q模格满足$(q\mathbb Z)^m\subseteq\Lambda\subseteq\mathbb Z^m$。对于素数$s$、矩阵$A\in \mathbb Z_q^{n\times m}$、和向量$u\in \mathbb Z_q^n$，q模格定义如下：

$\begin{aligned} \Lambda_q(A)&=\{y\in\mathbb{Z}^ms.t.\exists s\in\mathbb{Z}_q^n,A^T s=y({\mathrm{mod}}q)\}\\\\\Lambda_q^\bot(A)&=\{y\in\mathbb{Z}^mst.Ay=0({\mathrm{mod}}q)\}\\\\ \end{aligned}$

其中，$\Lambda^\perp_q(A)$的陪集是$\Lambda_q^u(A)$

$\Lambda_q^u(A)=\{y\in\mathbb{Z}^ms.t.Ay=u({\mathrm{mod}}q)$

同时，$\Lambda_q^\perp(A)=q\cdot\Lambda_q(A)^$，$\Lambda_q(A)=q\cdot\Lambda_q^\perp (A)^$

对偶格

给定$m$维的格$\Lambda=\mathcal L(B)\subset \mathbb R^m$，对偶格$\Lambda^*$的定义为：

$\Lambda^*=\{y\in\mathbb R^m|\forall x\in\Lambda,\langle x,y\rangle\in\mathbb Z\}$

对偶格满足$\Lambda^\ast=\mathcal L((B^{-1})^T)$并且$det(\Lambda^\ast)=\frac{1}{det(\Lambda)}$

格上离散高斯分布^[GPV08]

对于任意$\sigma >0$和向量$c\in\mathbb R^m$，其中$\sigma$是高斯分布的标准差，$c$是高斯分布的中心。

定义m维的高斯分布$\rho_{\sigma,c}(x)=\exp(-\pi\frac{|x-c|^2}{\sigma^2})$和$\rho_{\sigma,\epsilon}(\Lambda)=\sum_{x\in\Lambda}\rho_{\sigma,\epsilon}(x)$，则

对于在格$\Lambda$上对于任意的$y\in\Lambda$，以$c$为中心，以$\sigma$为参数的高斯分布为：

$\mathcal{D}_{\Lambda,\sigma,c}\left(y\right)=\frac{\rho_{\sigma,c}(y)}{\rho_{\sigma,c}(\Lambda)}=\frac{\rho_{\sigma,c}(y)}{\sum_{x\in\Lambda}\rho_{\sigma,c}(x)}$

统计距离

对于同一集合$S$上的任意两个随机变量X与Y，它们之间的统计距离标记为:

$\Delta(X,Y)=\frac 1 2 (\sum_{k\in S}|P(X=k)-Q(Y=k)|)$

平滑参数^[MR07]

设n维格$\Lambda$，定义平滑参数为：

使得$\rho_{1/s}(\Lambda^*\{0\})\leq \varepsilon$成立的最小的s的值，记为$\eta_\varepsilon(\Lambda)$，其中$\varepsilon>0$。

拒绝采样定理^[Lyu12]

假设$V$是$\mathbb Z^m$的子集，并且其中所有元素的范数小于常数$T$，$\sigma$是$\mathbb R$上的元素并且满足$\sigma=w(T\sqrt{\log m})$，$h:V\rightarrow \mathbb R$是一个概率分布。存在常数$M=O(1)$使得算法$\mathcal A$的分布

$\begin{flalign} &\mathcal A: \nonumber \\ &1{:\mathbf{v}}\stackrel{\$}\leftarrow h& \nonumber \\ &2:\mathbf{z}\stackrel{\$}{\leftarrow}D_{\mathbf{v},\sigma}^m& \nonumber \\ &3:output\textit{ }(\mathbf{z},\mathbf{v})\textit{ with probability }\min\left(\frac{D_{\sigma}^{m}(\mathbf{z})}{MD_{\mathbf{v},\sigma}^{m}(\mathbf{z})},1\right)& \nonumber \\ \end{flalign}$

与算法$\mathcal F$的分布的统计距离不超过$\frac{2^{-w(\log m)}}{M}$

$\begin{flalign} &\mathcal F:& \nonumber\\ &1{:\mathbf{v}}\stackrel{\$}\leftarrow h& \nonumber \\ &2:\mathbf{z}\stackrel{\$}{\leftarrow}D_{\sigma}^m& \nonumber \\ &3:output\textit{ }(\mathbf{z},\mathbf{v})\textit{ with probability }\frac{1}{M}& \nonumber \end{flalign}$

第一个算法输出内容的概率至少为$\frac{1-2^{-\omega(\log m)}}{M}$

如果$\sigma=\alpha T$且$\alpha$是正数的时候，则$M=e^{12/\alpha+1/(2\alpha^2)}$，算法$\mathcal A$与算法$\mathcal F$的统计距离不会超过$\frac{2^{-100}}{M}$，算法$\mathcal A$输出结果的概率至少为$\frac{1-2^{-100}}{M}$

形如z=Sc+y的签名，z直接输出会导致密钥泄漏，因为z的分布与S的分布产生关联。拒绝采样技术可以使得输出签名的分布与密钥无关增强安全性

分叉引理^[PS00]

2000年，Pointcheval和Stern为了证明随机预言机下签名算法的安全性，引入了分叉引理。安全性证明中，挑战者为了利用敌手破解困难问题，需要执行两次挑战过程，使得第二次挑战过程中的输出结果与第一次输出过程的开始一段时间相同，某处发生改变，挑战者据此可以解决困难问题。分叉引理用于许多签名体制的不可伪造性。

引理（一般分叉引理）．设q是一个正整数，H是一个具有h＞2个元素的集合。令$\mathcal I\mathcal G$是参数生成算法，$\mathcal B$是一个随机算法，算法$\mathcal B$的输入是$\{x,h_1,\dots,h_q\}$，输出是$(J，\sigma)$，其中$x\in \{0,\dots,q\},h_i\in H(i\in [q])$

令算法B的接受概率acc为试验$EXP＝[x\leftarrow\mathcal I\mathcal G; h_1,\dots,h_q\leftarrow H;(J,\sigma)\leftarrow \mathcal B(x,h_1,\dots,h_q)]$中$J≥1$的概率。

令与$\mathcal B$相关的分叉算法$F_{\mathcal B}$表述如下：

算法$F_{\mathcal B}$输入$x$

随机选择$\rho\in\{0,1\}$

从集合H中随机选择$h_1,\dots,h_q$

$(I,\sigma)\leftarrow\mathcal B(x,h_1,\dots,h_q;\rho)$

如果$I＝0$，则返回$(0,\varepsilon,\varepsilon)$

从集合H中随机选择$h_1’,\dots,h_q’$

$(I’,\sigma’)\leftarrow\mathcal B(x,h_1,\dots,h_{I-1},h_I’,\dots,h_q’;\rho)$

如果$I=I’$并且$h\neq h’$，则输出$(1,\sigma,\sigma’)$；否则输出$(0,\varepsilon,\varepsilon)$，设$frk=Pr[b=1:x\leftarrow\mathcal I\mathcal G;(b,\sigma,\sigma’)\leftarrow F_{\mathcal B}(x)]$，则我们有
$frk\geq acc\cdot(\frac{acc}{q}-\frac 1h)$

如果一个敌手A能够以概率$acc$伪造一个数字签名方案的有效签名，则存在一个算法$F_{\mathcal B}$通过敌手以概率$frk\geq acc\cdot(\frac{acc}{q}-\frac 1h)$输出该签名方案的两个有效且相关的不同签名。

格上困难问题

最短向量问题（SVP）

给定格基$B$，找到一个非零格向量$v\in\mathcal L(B)$，满足对于任意的非零向量$u\in\mathcal L(B)$，$\lVert v\rVert\leq \lVert u\rVert$

最近向量问题（CVP）

给定格基$B\in\mathbb Z^{m\times n}$和目标向量$t\in\mathbb R^m$，找到一个非零格向量$v\in\mathcal L(B)$，满足对于任意的非零向量$u\in\mathcal L(B)$，$\lVert v-t\rVert\leq \lVert u-t\rVert$

有界距离解码问题

给定格$\mathcal L$和距离参数$\gamma>0$，以及一个目标向量$s\in\mathbb R^n$满足$dist(s,\mathcal L)<d=\gamma\cdot\lambda_1$，找到一个格向量$b\in\mathcal L$，使得$|b-s|<d$。

小整数解问题（SIS）

给定整数 $m、n、q$，$\mathbb{Z}_q$ 表示模 $q$ 的剩余类群，随机选择矩阵 $A\in\mathbb{Z}_q^{n\times m}$ 和一个阈值参数 $\beta$, 求解一个非零整数向量 $z\in\mathbb{Z}^m\backslash\{0\}$，满足 $Az= 0 $ mod $q$ 且 $|z|\leq\beta.$

双边小整数解问题（Bi-SIS）

给定一个矩阵$A\in\mathbb Z_q^{m\times m}$，寻找两个非零整数向量$z,y\in \mathbb Z^m$，且$|z|,|y|\leq\beta$，满足$Az=0\in\mathbb Z_q^m$和$y^TA=0^T\in\mathbb Z_q^{1\times m}$，其中$\beta$表示一个正实数

非齐次小整数解问题（ISIS）

给定整数 $m、n、q$，$\mathbb{Z}_q$ 表示模 $q$ 的剩余类群，随机选择矩阵 $A\in\mathbb{Z}_q^{n\times m}$ 向量$u\in\mathbb Z_q^n$和一个阈值参数 $\beta$, 求解一个非零整数向量 $z\in\mathbb{Z}^m\backslash\{0\}$，满足 $Az=u $ mod $q$ 且 $|z|\leq\beta.$

双边非齐次小整数解问题（Bi-ISIS）

给定一个矩阵$A\in\mathbb Z_q^{m\times m}$，选取两个随机向量$u_1,u_2\in\mathbb Z_q^m$，寻找两个非零整数向量$z,y\in \mathbb Z^m$，且$|z|,|y|\leq\beta$，满足$Az=u_1\in\mathbb Z_q^m$和$y^TA={u_2}^T\in\mathbb Z_q^{1\times m}$，其中$\beta$表示一个正实数

计算型双边非齐次小整数解问题（CBi-ISIS）

给定元组$(A\in\mathbb Z_q^{m\times m},Az,y^TA)$，其中向量$z,y\in\mathbb Z^m$且$|z|,|y|\leq\beta$，$\beta$表示一个正实数，计算$y^TAz$

环小整数解问题（RSIS）

给定整数 $m$、$n$、$q,\mathcal{R}$ 表示多项式环，$R_{q}$ 表示系数模 $q$ 的多项式环，随机选择矩阵 $A\in\mathbb{R}_q^{n\times m}$ 和一个阈值参数 $\beta$, 求解一个非零向量 $z\in\mathbb{R}^m$, 满足 $Az= 0$ mod $q$ 且$|z|\leq\beta.$

一次性非齐次小整数解问题（one-more ISIS）

格上抽样算法

TrapGen(1^n)^[Aja99,AP11]: 给定任意素数$q=poly(n)$，和任意$m\geq 6n\lg q $，存在概率性多项式算法$TrapGen(1^n)$，输入$1^n$，输出一对矩阵$(A\in\mathbb Z_q^{n\times m},B\in\mathbb Z^{m\times m})$，其中$A$在$Z_q^{n\times m}$是均匀分布的，$B$是$\Lambda_q^{\perp}(A)$的一个格基同时以极大的概率满足$|B| \leq O(n\log q)$和$|\tilde{B}| \leq O(\sqrt{n\log q})$

SamplePre(A,T,u,s):输入矩阵$A\in\mathbb Z_q^{n\times m}$,$\Lambda_q^{\perp}(A)$的短陷门基$T$，目标值$u\in\mathbb Z_q^n$和高斯参数$s\geq ||\tilde T||\omega\sqrt{\log m}$，输出向量$e\in\mathbb Z_q^n$其统计分布接近于$D_{\Lambda_{q}^{u}(A),s}$

SampleMat(A,T,s,U)：给定矩阵$A\in\mathbb Z_q^{n\times m}$，,$\Lambda_q^{\perp}(A)$的短陷门基$T$，$U\in\mathbb Z_q^n$是一个随机矩阵，高斯参数s，存在多项式时间算法输出矩阵$S\in\mathbb Z^{m\times k}$满足$AS=U\ mod\ q$并且$||S||\leq s\sqrt m$

SampleD(A,\sigma)：给定矩阵$A\in \mathbb Z_q^{n\times m}$，整数$\sigma\geq||\tilde B||\omega (\sqrt{n\lg q})$，输出采样$e\in D_{\mathbb Z^m,\sigma}$，使得$Ae$均匀分布于$\mathbb Z_q^n$。

SampleR(1^m)^[HKR16]：从$\mathbb Z^m$中抽取出一个可逆矩阵$R$，使得$R$的分布与$D^{m\times m}$的统计距离是可以忽略的

SampleLeft(A,B,R,T_A,u,s)^[ABB10]：输入秩为n的矩阵$A\in\mathbb Z_q^{n\times m}$，矩阵$B\in\mathbb Z_q^{n \times m_1}$，$A_{q}^{\perp}(A)$的一组基$T_{A}\in \mathbb Z_q^{m\times m}$，向量$u\in\mathbb Z_q^n$且高斯参数$s>\left|\tilde{T}_{A}\right|\cdot\omega(\sqrt{\log(m+m_1)})$ ，输出向量$e\in\mathbb Z^{m+m_1}$且$e$的分布接近于$D_{\Lambda_{q}^{u}(A|B),s}$

SampleRight(A,B,R,T_B,u,s)^[ABB10]：输入矩阵$A, B\in \mathbb{Z} _{q}^{n\times m}( B$的秩为$n) $，随机矩阵$R\in\{-1,1\}^{m\times m},A_{q}^{\perp}(B)$的一组基$T_{B}$和向量$u\in\mathbb{Z}_q^n$ 以及高斯参数 $s>\left|\tilde{T}_{B}\right|\cdot\sqrt{m}\cdot\omega(\sqrt{\log m})$ 的情况下，存在概率多项式时间算法$SampleRight\left(A,B,R,T_B,u,s\right)$，令矩阵 $F_2=\left(A|AR+B\right)\in\mathbb{Z}_q^{n\times2n},$算法输出向量 $e\in\mathbb{Z}^{2n}$且 $e$的分布接近于 $D_{\Lambda_{q}^{u}(F_{2}),s}$

格基委派算法

盆景树算法

盆景树算法将某个格的基作为根节点，运行算法，生成更大维数的格和一组基。

ExtBasis(A,B,T)^[CHKP12]：输入矩阵$A\in\mathbb Z_q^{n\times m}$，T是格$\Lambda_q^\perp(A)$上的一组基，$m>0$为任意的整数，$B\in \mathbb Z_q^{n\times m’}$为任意的矩阵，$A_1=(A|B\in Z_q^{n\times (m+m’)})$，存在该算法可以输出格$\Lambda^\perp(A_1)$的一组基$T_1$，且$|T|=|\widetilde T_1|$

RandBasis(A,T,s)^[CHKP12]：输入矩阵$A\in\mathbb Z_q^{n\times m}$，T是格$\Lambda_q^\perp(A)$上的一组基，$s>|\widetilde T|w(\sqrt{\log n})$，存在该算法可以输出$\Lambda^\perp(A)$的另一组基$T_1$，满足$|T_1|\leq s\sqrt m$

BasisDel(A,R,T_A,s)^[HKR16]：输入矩阵$A\in\mathbb{Z}_q^{n\times m}$，可逆矩阵$R\in\mathbb{Z}^{m\times m}$，$\Lambda_q^\perp(A)$的一组基 $T_A$和高斯参数 $s\in\mathbb{R}>0$，存在概率多项式时间的算法输出$\Lambda_q^\perp(B)$的一组基 $T_B$，其中$B=AR^{-1}\in\mathbb{Z}_q^{n\times m}$

参考文献

[Lyu12] Lyubashevsky V.Lattice Signatures without Trapdoors[C].In Proceedings of 31st Annual Inter-
national Conference on the Theory and Applications of Cryptographic Techniques,April 15-19, 2012,Cambridge,UK,Berlin,Heidelberg,2012:738–755.

[PS00] Pointcheval D, Stern J. Security arguments for digital signatures and blind signatures[J]. Journal of cryptology, 2000, 13: 361-396.

[MR07] Micciancio D, Regev O. Worst-case to average-case reductions based on Gaussian measures[J]. SIAM Journal on Computing, 2007, 37(1): 267-302.

[HKR16] Howe J, Khalid A, Rafferty C, et al. On practical discrete Gaussian samplers for lattice-based cryptography[J]. IEEE Transactions on Computers, 2016, 67(3): 322-334.

[GPV08] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions[C]//Proceedings of the fortieth annual ACM symposium on Theory of computing. 2008: 197-206.

[ABB10] AGRAWAL S, BONEH D, BOYEN X. Efficient Lattice (
H)IBE in the Standard Model[C]//IACR. 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 30-June 3, 2010, French Riviera. Heidelberg, Springer, 2010: 553-572.

[Aja99] M. Ajtai, Generating hard instances of the short basis problem, in: J. Wiedermann, P. van Emde Boas, M. Nielsen (Eds.), Automata, Languages and Programming, in: Lecture Notes in Computer Science, vol. 1644, Springer, Berlin, Heidelberg, 1999, pp. 1–9.
[AP11] J. Alwen, C. Peikert, Generating shorter bases for hard random lattices, Theory Comput. Syst. 48 (2011) 535–553, https://doi.org/10.1007/s00224-010-9278-3.

[CHKP12] Cash D, Hofheinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis[J]. Journal of cryptology, 2012, 25: 601-639.

格