平均情况困难问题
小整数解(SIS)问题
给定 Z q n \mathbb{Z}_q^n Zqn 中的 m m m 个随机向量 a ⃗ 1 , ⋯ , a ⃗ m \vec{a}_1, \cdots, \vec{a}_m a 1,⋯,a m, 在 Z q n \mathbb{Z}_q^n Zqn 中随机选取 a i a_i ai, 在 { − 1 , 0 , 1 } \{-1, 0, 1\} {−1,0,1} 中找到一组非平凡的 z 1 , ⋯ , z m z_1, \cdots, z_m z1,⋯,zm(所有的系数只能是 − 1 , 0 , 1 {-1, 0, 1} −1,0,1 ), 使得 z 1 a ⃗ 1 + z 2 a ⃗ 2 + . . . + z m a ⃗ m = 0 z_1\vec{a}_1 + z_2\vec{a}_2 + ... + z_m \vec{a}_m = 0 z1a 1+z2a 2+...+zma m=0. (这里 { − 1 , 0 , 1 } \{-1, 0, 1\} {−1,0,1} 不是固定的, 也可以限定其他范围, 如果没有取值范围的限制这个问题就是容易的, 很容易通过高斯消元解决, 有了限制才变成困难问题)
SIS 与格困难问题的关系
下面去掉上面对解的范围的限制, 回顾格的定义: L = { a 1 v ⃗ 1 + ⋯ + a n v ⃗ n ∣ a i ∈ Z } L=\{a_1\vec{v}_1+\cdots + a_n\vec{v}_n | a_i \in \mathbb{Z}\} L={a1v 1+⋯+anv n∣ai∈Z}. 假设 S \mathcal{S} S 是所有满足 z 1 a ⃗ 1 + ⋯ + z m a ⃗ m = 0 ( m o d q ) z_1\vec{a}_1 + \cdots + z_m \vec{a}_m=0 \pmod q z1a 1+⋯+zma m=0(modq) 的整数解向量 z ⃗ = ( z 1 , ⋯ , z m ) \vec{z} = (z_1, \cdots, z_m) z =(z1,⋯,zm)的集合, 显然任意两个解的和也满足上述等式, 因此 S \mathcal{S} S 就是一个格. 而 SIS 问题就是在 S \mathcal{S} S 中找到某些范式下(此处为 { − 1 , 0 , 1 } \{-1, 0, 1\} {−1,0,1} )的一个短向量.
两种格:
-
L ( B ) = { z : z = B x ⃗ f o r x ⃗ ∈ Z n } L(B)=\{z:z=B\vec{x}\ for\ \vec{x} \in \mathbb{Z}^n\} L(B)={z:z=Bx for x ∈Zn} ( n n n 维格)
-
L ⊥ ( A ) = { z ⃗ ∈ Z m : A z ⃗ = 0 ( m o d q ) } L^\perp (A)=\{\vec{z} \in \mathbb{Z}^m: A\vec{z}=0 \pmod q\} L⊥(A)={z ∈Zm:Az =0(modq)} ( m m m 维格)
最坏情况下困难问题到平均情况困难问题的规约: 如果可以解决 SIS 问题, 那么也可以解决格中的最坏情况困难问题. (如果可以在格 L ⊥ ( A ) L^\perp (A) L⊥(A) 中找到一个短向量, 则可以在所有格中找到短向量.)
并不是所有格都可以写成 L ⊥ ( A ) L^\perp (A) L⊥(A) 的形式, 在 L ⊥ ( A ) L^\perp (A) L⊥(A) 中寻找短向量和在其他格中寻找短向量的困难程度是一样的. (任何格都可以写成 L ( B ) L(B) L(B) 的形式)
抗碰撞哈希函数
基于 SIS 构造抗碰撞哈希函数, 如果可以破解哈希函数, 则可以解决 SIS 问题.
SIS 问题: 给定 Z q n \mathbb{Z}_q^n Zqn 中的随机向量 a ⃗ 1 , ⋯ , a ⃗ m \vec{a}_1, \cdots, \vec{a}_m a 1,⋯,a m, 在 { − 1 , 0 , 1 } \{-1,0,1\} {−1,0,1} 中找到满足 z 1 a ⃗ 1 + z 2 a ⃗ 2 + ⋯ + z m a ⃗ m = 0 z_1\vec{a}_1 + z_2\vec{a}_2 + \cdots + z_m\vec{a}_m=0 z1a 1+z2a 2+⋯+zma m=0 的非平凡解 z 1 , ⋯ , z m z_1, \cdots, z_m z1,⋯,zm.
构造哈希函数:
有 A = ( a ⃗ 1 , ⋯ , a ⃗ m ) A=(\vec{a}_1, \cdots, \vec{a}_m) A=(a 1,⋯,a m), 定义 h A : { 0 , 1 } m → Z q n h_A:\{0,1\}^m\to \mathbb{Z}_q^n hA:{0,1}m→Zqn, h A ( z 1 , ⋯ , z m ) = z 1 a ⃗ 1 + ⋯ + z m a ⃗ m h_A(z_1, \cdots, z_m)=z_1\vec{a}_1 + \cdots + z_m\vec{a}_m hA(z1,⋯,zm)=z1a 1+⋯+zma m. ( z 1 , ⋯ , z m z_1, \cdots, z_m z1,⋯,zm 相当于要进行哈希的数据的 0 , 1 0, 1 0,1 比特位的值)
h h h 的定义域为 { 0 , 1 } m \{0,1\}^m {0,1}m, 其大小为 2 m 2^m 2m; 值域为 Z q n \mathbb{Z}_q^n Zqn, 其大小为 q n q^n qn. 对于哈希函数来说 2 m 2^m 2m 应该大于 q n q^n qn, 从而可以得到 m > n log q m>n\log q m>nlogq.
抗碰撞与 SIS 困难问题的关系:
假设可以找到一个碰撞, 即
z 1 a ⃗ 1 + ⋯ + z m a ⃗ m = y 1 a ⃗ 1 + ⋯ + y m a ⃗ m z_1\vec{a}_1 + \cdots + z_m\vec{a}_m=y_1\vec{a}_1 + \cdots + y_m\vec{a}_m z1a 1+⋯+zma m=y1a 1+⋯+yma m
则有, ( z 1 − y 1 ) a ⃗ 1 + ⋯ + ( z m − y m ) + a ⃗ m = 0 (z_1-y_1)\vec{a}_1 + \cdots + (z_m-y_m) + \vec{a}_m=0 (z1−y1)a 1+⋯+(zm−ym)+a m=0, 其中 z i − y i ∈ { − 1 , 0 , 1 } z_i-y_i \in \{-1,0,1\} zi−yi∈{−1,0,1} 即为 SIS 问题的一个解.
格与高斯分布
一维高斯分布
ρ s ( x ) = ( 1 / s ) e − π x 2 / s 2 \rho_s(x)=(1/s)e^{-\pi x^2/s^2} ρs(x)=(1/s)e−πx2/s2
标准分布: 中心为 0 0 0, 标准差为 s 2 π \frac{s}{\sqrt{2\pi}} 2π s. s s s 越大曲线越平滑.
二维高斯分布
x 1 x_1 x1 轴上的一维高斯分布: ρ s ( x 1 ) = ( 1 / s ) e − π x 1 2 / s 2 \rho_s(x_1)=(1/s)e^{-\pi {x_1}^2/s^2} ρs(x1)=(1/s)e−πx12/s2.
x 2 x_2 x2 轴上的一维高斯分布: ρ s ( x 2 ) = ( 1 / s ) e − π x 2 2 / s 2 \rho_s(x_2)=(1/s)e^{-\pi {x_2}^2/s^2} ρs(x2)=(1/s)e−πx22/s2.
二维的点的概率取值就是两个轴上一维高斯分布概率的乘积:
ρ
s
(
x
1
,
x
2
)
=
ρ
s
(
x
1
)
⋅
ρ
s
(
x
2
)
=
(
1
/
s
)
e
−
π
x
1
2
/
s
2
⋅
(
1
/
s
)
e
−
π
x
2
2
/
s
2
=
(
1
/
s
)
2
e
−
π
(
x
1
2
+
x
2
2
)
/
s
2
\rho_s(x_1,x_2)=\rho_s(x_1)\cdot \rho_s(x_2)=(1/s)e^{-\pi x_1^2/s^2}\cdot (1/s)e^{-\pi x_2^2/s^2}=(1/s)^2e^{-\pi (x_1^2 + x_2^2)/s^2}
ρs(x1,x2)=ρs(x1)⋅ρs(x2)=(1/s)e−πx12/s2⋅(1/s)e−πx22/s2=(1/s)2e−π(x12+x22)/s2
综上可以得到, ρ s ( x ) = ( 1 / s ) 2 e − π ∥ x ∥ 2 / s 2 \rho_s(x)=(1/s)^2e^{-\pi \parallel x \parallel ^2/s^2} ρs(x)=(1/s)2e−π∥x∥2/s2. 即 e e e 的指数上的参数只和 x x x 的范数有关, 或者说只与点到原点的距离有关.
n n n 维高斯分布
ρ s ( x ) = ( 1 / s ) n e − π ∥ x ∥ 2 / s 2 \rho_s(x)=(1/s)^n e^{-\pi \parallel x \parallel ^2/s^2} ρs(x)=(1/s)ne−π∥x∥2/s2
n n n 维标准分布: 中心为 0 0 0, 标准差为 s / 2 π s/\sqrt{2\pi} s/2π
如果按照 n n n 维高斯分布取点, 所取点到原点的距离近似为标准差.
高斯分布性质
-
是一个乘法分布: 可以把概率分布写成一维分布相乘的形式. ( ρ s ( x ) = ρ s ( x 1 ) × ⋯ × ρ s ( x n ) \rho_s(x)=\rho_s(x_1)\times \cdots \times \rho_s(x_n) ρs(x)=ρs(x1)×⋯×ρs(xn))
-
球对称. x x x 的概率只和他到原点的距离有关, 和坐标轴如何选取无关, 因此直到概率之后也无法知道坐标轴是如何选取的.
-
在线段上可以产生均匀分布的元素
ρ s ( x ) = ( 1 / s ) e − π x 2 / s 2 \rho_s(x)=(1/s)e^{-\pi x^2/s^2} ρs(x)=(1/s)e−πx2/s2, 令 s = 5 M , M > 0 s=5M, M>0 s=5M,M>0, M M M 为线段的最大长度.
如果 X ∼ ρ s X\sim\rho_s X∼ρs, 对任意 m < M m<M m<M, X X X 的分布与 [ 0 , m ) [0,m) [0,m) 的均匀分布类似: Δ ( X m o d m , U n i f o r m [ 0 , m ) ) < 2 − 110 \Delta(X \bmod m, Uniform\ [0,m))<2^{-110} Δ(Xmodm,Uniform [0,m))<2−110.
例: 要产生一个点, 这个点的概率分布在模任意小于 10 10 10 的数的情况下是均匀的.
在模 2 n 2^n 2n 下生成对应的点. 2 n 2^n 2n 并不等于所有小于 10 10 10 的数的乘积, 但是很接近, 这样统计距离可以满足条件. 如果按高斯分布取点, 只需要按高斯分布取点, 并且把标准差设为接近 2 2 2, 这样所取的点在模任意小于 M M M 的数后都是均匀随机的.
在 n n n 维平行多面体中生成均匀元素
在 n n n 维盒子中生成均匀元素
假设有一个盒子 B B B 的维度为 ( m 1 , ⋯ , m n ) (m_1, \cdots, m_n) (m1,⋯,mn), 其中 m i < M m_i < M mi<M.
生成 X 1 , ⋯ , X n ∼ ρ s ( x ) = ( 1 / s ) e − π x 2 / s 2 X_1, \cdots, X_n \sim \rho_s(x)=(1/s)e^{-\pi x^2/s^2} X1,⋯,Xn∼ρs(x)=(1/s)e−πx2/s2 其中 s = 5 M s=5M s=5M.
对任意 j j j, Δ ( X j m o d m , U n i f o r m [ 0 , m j ) ) < 2 − 110 \Delta(X_j \bmod m, Uniform [0,m_j)) < 2^{-110} Δ(Xjmodm,Uniform[0,mj))<2−110.
由于在每个维度上都是均匀分布的, 因此在整个盒子内也是均匀分布的:
Δ ( ( X 1 m o d m 1 , ⋯ , X n m o d m n ) , U n i f o r m ( B ) ) < n 2 − 110 \Delta((X_1 \bmod m_1, \cdots, X_n \bmod m_n), Uniform(B)) < n2^{-110} Δ((X1modm1,⋯,Xnmodmn),Uniform(B))<n2−110
因此, 如果 X ∼ ρ s ( x ) = ( 1 / s ) n e − π ∣ x ∣ 2 / s 2 X \sim \rho_s(x)=(1/s)^n e^{-\pi \mid x\mid ^2 /s^2} X∼ρs(x)=(1/s)ne−π∣x∣2/s2, 其中 s = 5 M s=5M s=5M, 则有 Δ ( X m o d B , U n i f o r m ( B ) ) < n 2 − 110 ≈ 0 \Delta(X \bmod B, Uniform(B)) < n2^{-110}\approx 0 Δ(XmodB,Uniform(B))<n2−110≈0.
在 n n n 维旋转过的盒子中生成均匀元素
由于 ρ s ( x ) \rho_s(x) ρs(x) 是球对称的, 与坐标无关, 因此旋转盒子后只需要对坐标进行旋转, 不影响概率分布.
在 n n n 维平行多面体中生成均匀元素
设 B = A U B=AU B=AU 且有 d e t ( U ) = 1 det(U)=1 det(U)=1, 如果 1) U U U 是一个整数矩阵, 或者 2) U U U 是一个对角线元素都是 1 1 1 的上三角形矩阵, 则存在 X m o d A i s u n i f o r m → X m o d B i s u n i f o r m X\bmod A\ is\ uniform \to X \bmod B\ is\ uniform XmodA is uniform→XmodB is uniform.
1) 的证明
假设 n n n 维空间 R n \mathbb{R}^n Rn 被分割成非常好的网格, 任意两个行列式相等的平行多面体中都包含同样数量的格点.
在模 A A A 的陪集( R n / A \mathbb{R}^n/A Rn/A)和模 B B B 的陪集( R n / B \mathbb{R}^n/B Rn/B)下做一一映射: B = A U B=AU B=AU. 如果可以建立这样的一一映射, 这就意味着如果某个分布在其中一个群中是均匀的, 则这个分布在另一个群中也是均匀的.
对任意用 A A A 生成的平行多面体中的点 a = A z , z ∈ [ 0 , 1 ) n a=Az, z\in [0,1)^n a=Az,z∈[0,1)n, a m o d B a \bmod B amodB 都是不同的, 也就是说不存在两个不同的 a a a 映射到了同一个点上. 这等价于如果 X m o d A X \bmod A XmodA 是均匀的, 那么 X m o d B X \bmod B XmodB 也是均匀的.
证明:
由于 U U U 是一个整数矩阵, 那么 L ( A ) = L ( B ) L(A) = L(B) L(A)=L(B).
通过反证法证明, 假设存在 z ⃗ 1 , z ⃗ 2 ∈ [ 0 , 1 ) n \vec{z}_1, \vec{z}_2 \in [0,1)^n z 1,z 2∈[0,1)n, 使得 A z ⃗ 1 ( m o d B ) = A z ⃗ 2 ( m o d B ) A\vec{z}_1 \pmod B = A \vec{z}_2 \pmod B Az 1(modB)=Az 2(modB).
则有 A ( z ⃗ 1 − z ⃗ 2 ) = 0 ( m o d B ) A(\vec{z}_1-\vec{z}_2)=0 \pmod B A(z 1−z 2)=0(modB), 这意味着 A ( z ⃗ 1 − z ⃗ 2 ) A(\vec{z}_1-\vec{z}_2) A(z 1−z 2) 在由 B B B 生成的格 L ( B ) L(B) L(B) 中. 根据格的定义, z ⃗ 1 − z ⃗ 2 \vec{z}_1-\vec{z}_2 z 1−z 2 是一个整数向量, 由于 z ⃗ 1 , z ⃗ 2 ∈ [ 0 , 1 ) n \vec{z}_1, \vec{z}_2 \in [0,1)^n z 1,z 2∈[0,1)n, 想要 z ⃗ 1 − z ⃗ 2 \vec{z}_1-\vec{z}_2 z 1−z 2 为整数向量, 唯一的可能就是 z ⃗ 1 − z ⃗ 2 = 0 \vec{z}_1-\vec{z}_2 = 0 z 1−z 2=0, 从而 z ⃗ 1 = z ⃗ 2 \vec{z}_1=\vec{z}_2 z 1=z 2, 得证.
2) 的证明
证明方式和 1) 的证明类似, 假设存在 z ⃗ 1 , z ⃗ 2 ∈ [ 0 , 1 ) n \vec{z}_1, \vec{z}_2 \in [0,1)^n z 1,z 2∈[0,1)n, 使得 A z ⃗ 1 ( m o d B ) = A z ⃗ 2 ( m o d B ) A\vec{z}_1 \pmod B = A \vec{z}_2 \pmod B Az 1(modB)=Az 2(modB).
那么有 A ( z ⃗ 1 − z ⃗ 2 ) = 0 ( m o d B ) A(\vec{z}_1-\vec{z}_2)=0 \pmod B A(z 1−z 2)=0(modB), 从而 B U − 1 ( z ⃗ 1 − z ⃗ 2 ) BU^{-1}(\vec{z}_1-\vec{z}_2) BU−1(z 1−z 2) 在 L ( B ) L(B) L(B) 中, 即 U − 1 ( z ⃗ 1 − z ⃗ 2 ) U^{-1}(\vec{z}_1-\vec{z}_2) U−1(z 1−z 2) 是一个整数向量. 同理可得 z ⃗ 1 − z ⃗ 2 = 0 \vec{z}_1-\vec{z}_2=0 z 1−z 2=0.
Gram-Schmidt 矩阵
B B B 是一个格的基, B B B 可以写成 B = B ~ U B=\tilde{B}U B=B~U 的形式, 其中 B ~ \tilde{B} B~ 是正交基.
[ ∣ ∣ ∣ ⋯ ∣ b ~ 1 b ~ 2 b ~ 3 ⋯ b ~ n ∣ ∣ ∣ ⋯ ∣ ] ⏟ B ~ [ 1 μ 2 , 1 μ 3 , 1 ⋯ μ n , 1 0 1 μ 3 , 2 ⋯ μ n , 2 0 0 1 ⋯ μ n , 3 ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 ⋯ 1 ] ⏟ U = B \underbrace{\begin{bmatrix} \Big| &\Big| & \Big| & \cdots & \Big|\\ \tilde{b}_1 & \tilde{b}_2 & \tilde{b}_3 & \cdots & \tilde{b}_n \\ \Big| & \Big| & \Big| & \cdots & \Big| \end{bmatrix}}_{\tilde{B}} \underbrace{\begin{bmatrix} 1 & \mu_{2,1} & \mu_{3,1} & \cdots & \mu_{n,1}\\[4pt] 0 & 1 & \mu_{3,2} & \cdots & \mu_{n,2} \\[4pt] 0 & 0 & 1 & \cdots & \mu_{n,3} \\[4pt] \vdots & \vdots & \vdots & \ddots & \vdots \\[4pt] 0 & 0 & 0 & \cdots & 1 \end{bmatrix}}_{U}=B B~ ⎣⎢⎢⎡∣∣∣b~1∣∣∣∣∣∣b~2∣∣∣∣∣∣b~3∣∣∣⋯⋯⋯∣∣∣b~n∣∣∣⎦⎥⎥⎤U ⎣⎢⎢⎢⎢⎢⎢⎢⎡100⋮0μ2,110⋮0μ3,1μ3,21⋮0⋯⋯⋯⋱⋯μn,1μn,2μn,3⋮1⎦⎥⎥⎥⎥⎥⎥⎥⎤=B
假设存在 X ∼ ρ s ( x ) = ( 1 / s ) n e − π ∥ x ∥ 2 / s 2 X \sim \rho_s(x)=(1/s)^ne^{-\pi \parallel x\parallel ^2 /s^2} X∼ρs(x)=(1/s)ne−π∥x∥2/s2, X m o d A X \bmod A XmodA 是均匀的, 如果 A A A 是 B B B 的 Gram-Schmidt 正交基, 则 X m o d B X \bmod B XmodB 也是均匀的. 进一步的, 如果 A A A 是 B U BU BU 的Gram-Schmidt 正交基, 其中 U U U 是任意行列式为 1 1 1 的整数矩阵, 结论同样成立.
同样, 如果 A A A 是 B U BU BU 的 Gram-Schmidt 正交基, 其中 U U U 是任意整数矩阵, 结论同样成立. (因为 L ( B U ) L(BU) L(BU) 是 L ( B ) L(B) L(B) 的子格, 因此 ( m o d B U ) \pmod {BU} (modBU) 蕴含了 ( m o d B ) \pmod B (modB)).
假设 B B B 是一个格基, C = B U C=BU C=BU 是子格基, C C C 中所有向量的长度不超过 λ n ( B ) \lambda_n(B) λn(B). 对 C C C 做 Gram-Schmidt 正交化得到 C ~ \tilde{C} C~, C ~ \tilde{C} C~ 中所有向量的长度也不会超过 λ n ( B ) \lambda_n(B) λn(B). (正交向量的长度不会超过原始向量的长度)
高斯分布的参数与格参数之间的关系
如果 s > 5 λ n ( B ) , X ∼ ρ s ( x ) = ( 1 / s ) n e − π ∣ x ∣ 2 / s 2 s>5\lambda_n(B), X\sim \rho_s(x)=(1/s)^n e^{-\pi \vert x\vert ^2/s^2} s>5λn(B),X∼ρs(x)=(1/s)ne−π∣x∣2/s2, 则有:
X m o d C ~ X \bmod \tilde{C} XmodC~ 是均匀的 ⇒ \Rightarrow ⇒ X m o d C X \bmod C XmodC 是均匀的 ⇒ \Rightarrow ⇒ X m o d B X\bmod B XmodB 是均匀的.
也就是说, 如果把 s s s 选为 5 λ n ( B ) 5\lambda_n(B) 5λn(B), 所得到的概率分布对格进行取模后是均匀的.
格上的均匀分布
[定理 (Micciancio & Regev '04)]
如果 s > 5 λ n ( B ) s>5\lambda_n(B) s>5λn(B), X ∼ ρ s ( x ) = ( 1 / s ) n e − π ∥ x ∥ 2 / s 2 X\sim \rho_s(x)=(1/s)^n e^{-\pi \parallel x \parallel ^2/s^2} X∼ρs(x)=(1/s)ne−π∥x∥2/s2, 则有 Δ ( X m o d B , U n i f o r m ( B ) ) < n 2 − 110 \Delta (X\bmod B, Uniform(B)) < n2^{-110} Δ(XmodB,Uniform(B))<n2−110.
规约
[Ajtai '96, Micciancio & Regev '04]
最坏情况到平均情况的规约
如果可以解决 SIS, 则也可以解决 SIVP.
基本思想: 假设有了格基, 利用 SIS 在格中找到一个短向量, 使得这个向量也在给定基所在的格中.
假设已知了一组格基, 假设这组格基不是特别好, 对空间进行人为的划分, 用小一点的平行多面体对空间进行划分, 一般划分成
O
(
n
)
O(n)
O(n) 份, 此处为
3
3
3 份. 然后对每一份进行标记, 从原点开始, 原点标记为
(
0
,
0
)
(0,0)
(0,0), 每个坐标轴依次标记为
0
,
1
,
2
0, 1, 2
0,1,2, 到下一个格点再重新开始标记, 这样, 所有格点都被标记为了
(
0
,
0
)
(0,0)
(0,0), 利用 SIS Oracle 来在任意格中寻找短向量.
SIS Oracle: 给定 n n n 个向量, 可以找到这 n n n 个向量的一个短的线性组合, 使得 n n n 个向量的和模 q q q 等于 0 0 0. 图中 q = 3 q=3 q=3.
把下面的算法重复 m m m 次:
-
选取一个随机格点(红色)
-
以当前格点为中心进行高斯分布采样得到一个点(黄色) (按高斯分布采样得到的点不一定在网格上, 如果得到的点不在网格上, 可以舍入一下让其落在网格上)
背景知识: 所有采样的点在 Z q n \mathbb{Z}_q^n Zqn 下都是均匀的. (把高斯分布参数选为比 5 λ n 5\lambda_n 5λn 更大的值, 这意味着这些点在平行多面体中是均匀分布的, 也就是说, 如果把这些点模平行多面体, 这些点在平行多面体中是均匀分布的. 这等价于随机选一个格点, 然后按高斯分布选取偏移量, 只要标准差足够大, 这些点的分布在平行多面体中就是均匀的, 而平行多面体又在 Z q n \mathbb{Z}_q^n Zqn 上.)
把 m m m 个在 Z q n \mathbb{Z}_q^n Zqn 中采样的点 a ⃗ 1 , ⋯ , a ⃗ m \vec{a}_1, \cdots, \vec{a}_m a 1,⋯,a m 给 SIS Oracle, Oracle 输出 z 1 , ⋯ , z m ∈ { − 1 , 0 , 1 } z_1, \cdots, z_m \in \{-1, 0, 1\} z1,⋯,zm∈{−1,0,1} 使得
z 1 a ⃗ 1 + ⋯ + z m a ⃗ m = 0 z_1\vec{a}_1 + \cdots + z_m\vec{a}_m=0 z1a 1+⋯+zma m=0
红点: v ⃗ i \vec{v}_i v i, 黄点: s ⃗ i \vec{s}_i s i
v ⃗ i + r ⃗ i = s ⃗ i \vec{v}_i + \vec{r}_i = \vec{s}_i v i+r i=s i
r i r_i ri 是 v ⃗ i \vec{v}_i v i 到 s ⃗ i \vec{s}_i s i 的距离, 近似等于 λ n n \lambda_n \sqrt{n} λnn (高斯分布的标准差).
z 1 s ⃗ 1 + ⋯ + z m s ⃗ m z_1\vec{s}_1 + \cdots + z_m\vec{s}_m z1s 1+⋯+zms m 是一个格向量, 因为 z 1 s ⃗ 1 + ⋯ + z m s ⃗ m = 0 ( m o d q ) z_1\vec{s}_1 + \cdots + z_m\vec{s}_m=0\pmod q z1s 1+⋯+zms m=0(modq)
因此 z 1 ( v ⃗ 1 + r ⃗ 1 ) + ⋯ + z m ( v ⃗ m + r ⃗ m ) z_1(\vec{v}_1+\vec{r}_1) + \cdots + z_m(\vec{v}_m + \vec{r}_m) z1(v 1+r 1)+⋯+zm(v m+r m) 也是一个格向量
( z 1 v ⃗ 1 + ⋯ + z m v ⃗ m ) + ( z 1 r ⃗ 1 + ⋯ + z m r ⃗ m ) (z_1\vec{v}_1 + \cdots + z_m\vec{v}_m) + (z_1\vec{r}_1 + \cdots + z_m\vec{r}_m) (z1v 1+⋯+zmv m)+(z1r 1+⋯+zmr m) 也是一个格向量
从而 z 1 r ⃗ 1 + ⋯ + z m r ⃗ m z_1\vec{r}_1 + \cdots + z_m\vec{r}_m z1r 1+⋯+zmr m 也是一个格向量, 因为 z 1 v ⃗ 1 + ⋯ + z m v ⃗ m z_1\vec{v}_1 + \cdots + z_m\vec{v}_m z1v 1+⋯+zmv m 是一个格向量.
(此处 a i a_i ai 是 s i s_i si 在网格中的坐标表示.)
由于 r ⃗ i \vec{r}_i r i 都是短向量, 而 z i ∈ { − 1 , 0 , 1 } z_i\in \{-1, 0, 1\} zi∈{−1,0,1}, 因此 z 1 r ⃗ 1 + ⋯ + z m r ⃗ m z_1\vec{r}_1 + \cdots + z_m\vec{r}_m z1r 1+⋯+zmr m 是一个短向量.
r ⃗ i \vec{r}_i r i 近似为 λ n n \lambda_n \sqrt{n} λnn , 此处要加上 m m m 个 r ⃗ i \vec{r}_i r i, 范数就变成了 m λ n n m\lambda_n \sqrt{n} mλnn , 在加的过程中一部分随机值会被消掉, 最终得到 m \sqrt m m 乘以 r ⃗ i \vec{r}_i r i 的长度, 即 m λ n n \sqrt m \lambda_n \sqrt n m λnn , 如果规约算法可以正确执行, 则可以保证得到一个格向量且其长度为 m n λ n \sqrt m \sqrt n \lambda_n m n λn, m \sqrt m m 与 n \sqrt n n 类似, 因此可以记为 n λ n n\lambda_n nλn.
技术细节
-
无法按照均匀随机分布采样格点, 因此在证明的过程中需要在 R n / L \mathbb{R}^n/L Rn/L ( R n \mathbb{R}^n Rn 模格)下进行.
-
如果出现 z 1 r ⃗ 1 + ⋯ + z m r ⃗ m = 0 z_1\vec{r}_1 + \cdots + z_m\vec{r}_m=0 z1r 1+⋯+zmr m=0 的情况怎么办?
- 可以证明在很高的概率下不为 0 0 0.
- 给定一个 s ⃗ i \vec{s}_i s i, 会有很多可能的 r ⃗ i \vec{r}_i r i, Oracle 不知道 r ⃗ i \vec{r}_i r i 的值是多少, 因此可以证明在不可忽略的概率下, 回复的向量和不为 0 0 0.
-
高斯采样得到的点不一定在网格上.
可以通过一些确定性算法对点进行舍入操作, 把它移到网格上, 但是舍入会带来误差, 需要在点上加上某个长度才能移到网格上, 这种情况影响不大, 但是有更好的方法, 就是直接在网格上取点.
参考文献
[1] BIU Winter School - https://www.youtube.com/watch?v=P3I3kCJedIo&list=PL8Vt-7cSFnw2OmpCmPLLwSx0-Yqb2ptqO&index=2