SIS 问题从最坏情况到平均情况的规约

平均情况困难问题

小整数解(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 z1​a 1​+z2​a 2​+...+zm​a 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={a1​v 1​+⋯+an​v 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 z1​a 1​+⋯+zm​a 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 z1​a 1​+z2​a 2​+⋯+zm​a 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​)=z1​a 1​+⋯+zm​a 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 z1​a 1​+⋯+zm​a m​=y1​a 1​+⋯+ym​a 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−πx1​2/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−πx2​2/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 维高斯分布取点, 所取点到原点的距离近似为标准差.

高斯分布性质

  1. 是一个乘法分布: 可以把概率分布写成一维分布相乘的形式. ( ρ 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​))

  2. 球对称. x x x 的概率只和他到原点的距离有关, 和坐标轴如何选取无关, 因此直到概率之后也无法知道坐标轴是如何选取的.

  3. 在线段上可以产生均匀分布的元素

    ρ 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} Δ(Xj​modm,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} Δ((X1​modm1​,⋯,Xn​modmn​),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,1​10⋮0​μ3,1​μ3,2​1⋮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 问题从最坏情况到平均情况的规约
SIS 问题从最坏情况到平均情况的规约
SIS 问题从最坏情况到平均情况的规约

  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 次:

  1. 选取一个随机格点(红色)

  2. 以当前格点为中心进行高斯分布采样得到一个点(黄色) (按高斯分布采样得到的点不一定在网格上, 如果得到的点不在网格上, 可以舍入一下让其落在网格上)

  背景知识: 所有采样的点在 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 z1​a 1​+⋯+zm​a 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} λn​n ​ (高斯分布的标准差).

   z 1 s ⃗ 1 + ⋯ + z m s ⃗ m z_1\vec{s}_1 + \cdots + z_m\vec{s}_m z1​s 1​+⋯+zm​s 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 z1​s 1​+⋯+zm​s 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) (z1​v 1​+⋯+zm​v m​)+(z1​r 1​+⋯+zm​r m​) 也是一个格向量

  从而 z 1 r ⃗ 1 + ⋯ + z m r ⃗ m z_1\vec{r}_1 + \cdots + z_m\vec{r}_m z1​r 1​+⋯+zm​r m​ 也是一个格向量, 因为 z 1 v ⃗ 1 + ⋯ + z m v ⃗ m z_1\vec{v}_1 + \cdots + z_m\vec{v}_m z1​v 1​+⋯+zm​v 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 z1​r 1​+⋯+zm​r m​ 是一个短向量.

   r ⃗ i \vec{r}_i r i​ 近似为 λ n n \lambda_n \sqrt{n} λn​n ​, 此处要加上 m m m 个 r ⃗ i \vec{r}_i r i​, 范数就变成了 m λ n n m\lambda_n \sqrt{n} mλn​n ​, 在加的过程中一部分随机值会被消掉, 最终得到 m \sqrt m m ​ 乘以 r ⃗ i \vec{r}_i r i​ 的长度, 即 m λ n n \sqrt m \lambda_n \sqrt n m ​λn​n ​, 如果规约算法可以正确执行, 则可以保证得到一个格向量且其长度为 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​.

技术细节

  1. 无法按照均匀随机分布采样格点, 因此在证明的过程中需要在 R n / L \mathbb{R}^n/L Rn/L ( R n \mathbb{R}^n Rn 模格)下进行.

  2. 如果出现 z 1 r ⃗ 1 + ⋯ + z m r ⃗ m = 0 z_1\vec{r}_1 + \cdots + z_m\vec{r}_m=0 z1​r 1​+⋯+zm​r 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.
  3. 高斯采样得到的点不一定在网格上.

    可以通过一些确定性算法对点进行舍入操作, 把它移到网格上, 但是舍入会带来误差, 需要在点上加上某个长度才能移到网格上, 这种情况影响不大, 但是有更好的方法, 就是直接在网格上取点.

参考文献

[1] BIU Winter School - https://www.youtube.com/watch?v=P3I3kCJedIo&list=PL8Vt-7cSFnw2OmpCmPLLwSx0-Yqb2ptqO&index=2

上一篇:迪芝伦(Digilent)推出全新开发板PYNQ-Z1,支持python


下一篇:测试开发之前端——No8.HTML5中的媒介事件