一些格中常见的知识、问题形式介绍。

基础知识

定义

格 $\Lambda$：给定一组线性无关的基向量 $v_1, v_2, v_3,…, v_n$, 那么这些基向量的所有整系数线性组合 $a_1v_1+a_2v_2+…+a_nv_n, a_i\in Z$ 所形成的集合，就叫作这组基向量所张成的格。

（格就是 $\Z^m$ 上的一个满秩可加子群）

一个点 $a\in \Z^m$ 与格 $\Lambda$ 的距离：$d(a,\Lambda):=min_{\textbf{x}\in \Lambda}\Arrowvert a-\textbf{x}\Arrowvert$；

格中的最短非零向量长度：$\lambda_1(\Lambda):=min_{a\in \Lambda/{0}}\Arrowvert a\Arrowvert$。

矩阵表示：$\textbf{A}\in \Z_q^{m×n},m\ge n$ （使前 $n$ 行构成可逆矩阵），则定义格为：

​ $\mathcal{L}(A):={\textbf{z}\in \Z^m\mid \exists \textbf{s} \in \Z^n:z=As^T\ mod\ q}$，简单地以 $A,A^T$ 来表示一个格（两种不同的方式）。

也有：

$\mathcal{L}^\perp (A)={z\in \Z^n\mid Az^T=0\ mod\ q}$

注：并不是所有格都能够写成第二种形式。

eg

 

Lemma 1

若 $B,C$ 是两不同基底，使得其张成的格相同的充要条件是：存在单模矩阵 $U$ ( an n x n matrix with integer entries and det(U) = ±1)。

because： $B=CU$ and $C=BU^{-1}$，so $\mathcal{L}(B)\subseteq \mathcal{L}(C)$ and $\mathcal{L}(C)\subseteq \mathcal{L}(B)$ so ok.

而 U 为可逆矩阵，故 det = +-1。

Lemma 2

对于基底 $B$，有 $det(\mathcal{L}(B))=\sqrt{det(B^{\mathcal{T}}B)}$

两大难题

广义上的 NP-hard

SVP (最短向量问题)

给定lattice和基向量，找到lattice中的一个长度最短的非零向量。

CVP (最近向量问题)

给定lattice和基向量，以及一个不在lattice上的目标向量，找到lattice中一个距离目标向量最近的格向量。

 

Minkowski’s First Theorem

对于任意 n 维的满秩格基，都有 $SVP(L)\le \sqrt n(det(L))^{1\over n}$

 

二维格中的高斯格基约减算法

有点像 GCD

这个算法用于寻找 SVP。

设 L 为两个基向量 v1, v2 所张成的 2 维lattice，假定 $\arrowvert v_1\arrowvert < \arrowvert v_2\arrowvert$，我们现在通过减去 v1 的某个倍数来使得 v2 变短。$v_2^{\ast} = v_2 - \frac{v_1 \cdot v_2}{ {\Arrowvert v_1\Arrowvert} ^2} v_1$，我们就得到了新向量 v2* 正交于 v1，且使得 v2 变成了目前的最短状态。

但现在在 lattice 中，不能减去任意倍数的 v1，只能减去整数倍的 v1。

所以利用下式来替代：$v_2 -= m v_1, m = \lceil \frac{v_1 \cdot v_2}{ {\Arrowvert v_1\Arrowvert}^2} \rceil$

若 v1 > v2* 则交换之，继续操作；否则结束。

代码如下：

def GaussLatticeReduction(v1, v2):
    while True:
        if v2.norm() < v1.norm():
            v1, v2 = v2, v1
        m = round( v1*v2 / v1.norm()^2 ) # round() 四舍五入
        if m == 0:
            return (v1, v2)
        v2 = v2 - m*v1

参考链接:

从一道CTF题初探NTRU格密码

格基约减算法与实现

 

LLL 算法

在所有基向量经过至少一次规约后，LLL 返回新基，按长度进行大致排序。

规约的主要目的是，将这组任意给定的基转化为一组正交性较好的优质基（格基点在整数点上，故无法直接应用 GS 正交化），并使得这个优质基中的各个向量尽量短。

前置知识

Gram-Schmidt 正交化

给定一组 $m$ 维子空间的基 ${b_i\in \R ^ n}$，定义： \(b_1^*=b_1\\ b_2^*=b_2-\mu_{2,1}b_1^*,\mu_{2,1}={b_2·b_1^*\over b_1^*·b_1^*}\\ \vdots\\ b_m^*=b_m-\sum\limits_{i<m}\mu_{m,i}b_i^*,\mu_{m,i}={b_m·b_i^*\over b_i^*·b_i^*}\) 最后单位化向量 ${b_i^*}$。

LLL 规约基

令一组基为 $\textbf{B}={b_1,…,b_n}$；且 $\textbf{B}^={b_1^,…,b_n^}$，表示相应的 GS 正交基。设 $\mu_{i,j}:={b_j·b_i^\over b_i^·b_i^}$，则 LLL-reduced $B$ 满足：

其中 $\eta\in [0.5,\sqrt{\delta}),\delta\in (0.25,1.0]$，当且仅当 $\delta<1$，有时间复杂度在多项式时间 $O(n^6log^3B)$ 内。最初取值 $\eta = 0.5, \delta = 0.75$， Sage 中一般取 $\eta = 0.501, \delta = 0.99$。

简易代码

def LLL(B, delta):
    Q = gram_schmidt(B)

    def mu(i,j):
        v = B[i]
        u = Q[j]
        return (v*u) / (u*u)   

    n, k = B.nrows(), 1
    while k < n:

        # length reduction step
        for j in reversed(range(k)):
            if abs(mu(k, j)) > .5:
                B[k] = B[k] - round(mu(k, j))*B[j]
                Q = gram_schmidt(B)

        # swap step
        if Q[k]*Q[k] >= (delta - mu(k,k-1)**2)*(Q[k-1]*Q[k-1]):
            k = k + 1
        else:
            B[k], B[k-1] = B[k-1], B[k]
            Q = gram_schmidt(B)
            k = max(k-1, 1)

   return B

这里的 def mu() 就是 GS正交化 中的 $\frac{v_i \cdot v_j}{ {\Arrowvert v_i\Arrowvert}^2}$

参考链接: Building Lattice Reduction (LLL) Intuition、

Lemma

对格基 $\mathcal{L}$，LLL 算法输出的规约基满足： \(\Arrowvert \textbf{v}_1\Arrowvert \le \Arrowvert \textbf{v}_2\Arrowvert \le \cdots \le \Arrowvert \textbf{v}_i\Arrowvert \le 2^{n(n-1)\over 4(n+1-i)}det(\mathcal{L})^{1\over n+1-i}\) 也即能推出上面的性质 2、3。

BKZ

定义

​ 以 $\textbf{B}:={b_1,…,b_n}$ 为基的格，而 $\pi_i:\R^m\rightarrow span(b_1,…,b_{i-1})^\perp$ 表示由 B 的各个向量张成空间 的正交空间。（$\pi_i$ 为一恒等映射）

​ 而：$\pi_i(b_j)=b_j^-\sum\limits_{i\le k<j}\mu_{k,i}b_k^\ if\ i\le j\ else\ 0$。

​ （存疑，不知道是个什么，随 i 增加而 norm 减少，直观上是：只考虑了与前 i-1 维正交化后的基）

​ $\mathcal{L}_{[i,j]}:={a_i\pi_i(b_i)+…+a_j\pi_i(b_j)\mid a_k\in Z}\subset \R^n$

算法过程

BKZ

 

如果我们想找到 SVP $\textbf{x}=\sum x_i\textbf{b}_i$，

一种方法是：

​ 枚举所有格点 $\textbf{y}:\Arrowvert \textbf{y}\Arrowvert \le R,R=\Arrowvert \textbf{b}_1\Arrowvert$。既然 SVP 一定满足 $\Arrowvert \pi_i(x)\Arrowvert \le R\ \forall i\in [1,n]$，以 $R\ge \Arrowvert \pi_n(\textbf{x})\Arrowvert=…=\mid x_n\mid·\Arrowvert \textbf{b}_n^*\Arrowvert$ 为例：这说明对 $x_n$ ，我们的选择是有限的。由此可推广到所有系数（存疑，我看这个book不等式符号都反了。。）。

​ 于是如此枚举（Enumeration）（搜索）：创建一棵树，对 Xn 所有可能值建立子节点，再到 Xn-1 …，每一层的条件是范数小于等于 R（由于前面的不等式符号反了，故存疑）。但这样太朴素了，故需要剪枝。

​ （在 blocksize 较小的情况下表现不错）

第二种方法是：筛 (Sieving)：

​ 从晶格中的一组向量开始，然后把这些向量组合成更小的向量，使列表中的向量的长度迭代地变小。

​ 大体朴素地，设 $L:{x_n};R:\forall \textbf{x},\Arrowvert \textbf{x}\Arrowvert \le R,\gamma<1$，然后创建 $L’:\forall \textbf{x},\textbf{y}\in L^2,\textbf{x}\ne ±\textbf{y}$，若 $\Arrowvert \textbf{x} ± \textbf{y}\Arrowvert <\gamma R$，则添加进 $L’$。

​ （渐进式地更快）

 

rHF：$\delta = (\mid \textbf{b}_0\mid /Vol(\textbf{B})^{1\over n})^ {1\over n}$

对 $\beta$ 较小情况下，[GN08b] 中实验性地计算了 rHF，较大时遵循 [Che13] 中的渐进公式 $\delta(\beta)^{2(\beta-1)}=(\beta/(2\pi e))(\beta \pi)^{1\over \beta}$，趋于 1。

高斯启发式（Gaussian Heuristic）：

​ 估计 SVP 长度约为 $\lambda_1(\Lambda) \approx \sqrt{n\over 2\pi e}det(\Lambda)^{1\over n}$

几何级数假设（Geometric Series Assumption / GSA）：

​ 一个被充分规约的格基，其高斯正交化向量满足：$\Arrowvert \textbf{b}^_{m-i}\Arrowvert \approx \delta_0^{2i} \Arrowvert \textbf{b}_m^\Arrowvert$

​ 对 BKZ-β 来说，即有 $\Arrowvert \textbf{b}^\Arrowvert \approx \delta(\beta)^{-2}\Arrowvert \textbf{b}_{i-1}^\Arrowvert$。

 

GGH

“Dead cryptosystem”

前提

对于格中的某一格点 p，向其添加一个长度为 $\delta$ 的随机向量 e，就可以产生一个随机点 c = p + e。如果 $\delta$ 较小，那么 p 就是 c 在格中的最近向量。虽然 CVP 是 NP-hard 的，但如果近似因子 (here refer to $\delta $) 比较大，则存在多项式时间的算法解决 app-CVP 问题。而求解之的结果与 $\delta$ 以及输入基的质量密切相关（规约基与非规约基）。

利用这种特性，可以构造单向陷门函数。故 GGH 加密方案诞生了。

基本思想

在 GGH 中，系统产生了同一个格的两个不同基，其中一个作为私钥的规约基 R，从 R 推导出一个普通基 B​ 作为公钥。

加密者用 B 把消息转化成格中的某个点 p，同时随机产生一个扰动向量 e，形成密文 c = p + e。扰动向量 e 的长度不超过 $\delta $。 由于解密者拥有规约基，因此他有较高的概率找到距离 c 最近的格点 p，从而恢复明文。

方案保证攻击者既无法通过公钥来正确恢复 p，也保证不能从公钥中推导出私钥。

简要来说： $c = mB+e$

 

Nyguen’s Attack

有个叫做 Nyguen 的人在 GGH 提出几年后，就把作者挂在网上的五个挑战日掉了，后来有个作者就宣布了：GGH is “dead”。

接下来我们就介绍这种攻击方法：

首先设一个 all-sigma vector s (sigma, sigma, …, sigma) \(c=mB+e\\ c+s=mB+(e+s)\\ c+s\equiv mB\ (mod\ 2*sigma)\\ since\ we\ know\ c,s\ and\ B,we\ can\ get:m2s\equiv m\ (mod\ 2*sigma)\\\) 那么接下来我们就能拿到： \({ {c-m2s*B}\over{2*sigma} }=({ {m-m2s}\over {2*sigma} })B+{e\over {2*sigma} }\) 这样我们就拿到了一个更简单的 CVP 问题，扰动向量更小，故我们可以用传统方法 embedded technique 将这个 CVP 转化为 SVP 解答并求出明文。

注：这里的分母 2*sigma 可能导致方程两边系数为非整数，在两边同乘上 2 即可。

 

Embedded technique

hxp 的 wp 中写得非常形象。

在一维中，假定给出如下 CVP 实例：

cvp_eg

黑点即为格点，红点为 c = mB + e。

我们将扩展一维，将一维的 CVP 转化为二维的 SVP。

cvp_svp

其中灰点为拓展后新增的格点，原目标点移动到了格中。

现在使用 LLL 求出该格的 SVP，如图所示，若代表 SVP 的向量为 $\delta$，则将原目标点在原格中偏移 $-\delta$ 即可求得 CVP。(“-“ stands for: from outer lattice to inside lattice)

cvp_svp

具体做法如下：

设原基底矩阵为 B，CVP 目标点为 c = (100, 100, 100)。

eg

将 c 作为基底向量添加进 B，再将原向量添加一维 0，c 的新增维度设为 1 (或其他)。

eg

这样一来既保证了 c 在新格内，也保证了最后求出的 SVP 极大概率就是扰动向量。

eg

那么 CVP = (100, 100, 100) - (0, 1, 0) = (100, 99, 100)。

参考链接：

Cryptanalysis of the Goldreich–Goldwasser–Halevi Cryptosystem from Crypto’97

The GGH Cryptosystem

Algorithms for the Closest and Shortest Vector Problems

hxp_XXY_writeup

 

NTRU

referred to https://latticehacks.cr.yp.to/ntru.html、https://pdfs.semanticscholar.org/67e7/020ce5649947e2199bc0eb8bd62b9a31ca4e.pdf

由 Hoffstein, Pipher, and Silverman 在 1998 年提出。

然后介绍一下工具代码：

Zx.<x> = ZZ[]
def convolution(f,g): # return f * g in (x^n - 1)
  return (f * g) % (x^n - 1)

def balancedmod(f,q): # return f where coef in f \in (-q//2, q//2)
  g = list(((f[i] + q//2) % q) - q//2 for i in range(n))
  return Zx(g)

def randomdpoly(d): # return a random polynomial which has d non-zero coefs \in {1, -1}
  assert d <= n
  result = n*[0]
  for j in range(d):
    while True:
      r = randrange(n)
      if not result[r]: break
    result[r] = 1-2*randrange(2)
  return Zx(result)

def invertmodprime(f,p): # invert f^-1 in (x^n - 1) for 'x' and p for coef
  # which means that f * invertmodprime(f, p) = 1 + p*u, u is a polynomial
  T = Zx.change_ring(Integers(p)).quotient(x^n - 1)
  return Zx(lift(1 / T(f)))

def invertmodpowerof2(f,q): # sage cannot deal with non-primes
  assert q.is_power_of(2)
  g = invertmodprime(f,2) # f * g = 1 + 2 * u
  while True:
    r = balancedmod(convolution(g,f),q)
    if r == 1: return g # yes, f * g = 1 + q*u indeed
    g = balancedmod(convolution(g,2 - r),q)
        # no, so: g' = g*(2-(1+2*u)) = (1-4*u**2) // f
        
def randommessage(): # return a polynomial whose coefs are \in {-1, 0, 1}
  result = list(randrange(3) - 1 for j in range(n))
  return Zx(result)

Parameters

NTRU 常使用 $n\in (250,2500)$ 的多项式。

整数 q，通常是 2 的幂次；p 一般是 3（远远小于 q），因为多项式 $f, g, r$ 的系数为 ${-1,0,1}$，且多为 0（$D_f, D_g , D_r$ 较小）。

主体代码

def keypair():
  while True:
    try:
      f = randomdpoly(Df)
      f3 = invertmodprime(f,3)
      fq = invertmodpowerof2(f,q)
      break
    except:
      pass
  g = randomdpoly(Dg)
  publickey = balancedmod(3 * convolution(fq,g),q)
  secretkey = f, f3
  return publickey, secretkey

def encrypt(message,publickey):
  r = randomdpoly()
  return balancedmod(convolution(publickey,r) + message,q)

def decrypt(ciphertext,secretkey):
  f, f3 = secretkey
  a = balancedmod(convolution(ciphertext,f),q)
  return balancedmod(convolution(a,f3),3)

这里需要注意：最后解密时 $a = fc=r3g+f*m\ mod\ q$

p

Attack

格中，λ 为任意正整数，[h_i] 即为公钥向量。规约出的结果即为 $(\lambda f \parallel g)$ （$\parallel$ 指连接符）

（$g_i = \Sigma f_j*H_{n+i-j}$，所以要转置一大波）

p

p1

Code

def attack(publickey):
  recip3 = lift(1/Integers(q)(3))
  publickeyover3 = balancedmod(recip3 * publickey,q)
  M = matrix(2 * n)
  for i in range(n):
    M[i,i] = q
  for i in range(n):
    M[i+n,i+n] = 1
    c = convolution(x^i,publickeyover3)
    for j in range(n):
      M[i+n,j] = c[j]
  M = M.LLL()
  for j in range(2 * n):
    try:
      f = Zx(list(M[j][n:]))
      f3 = invertmodprime(f,3)
      return (f,f3)
    except:
      pass
  return (f,f)

n = 120
q = 2^32
d = 81

publickey,secretkey = keypair()
donald = attack(publickey)
print donald[0]
try:
  m = randommessage()
  c = encrypt(m,publickey)
  assert decrypt(c,donald) == m
  print 'attack successfully decrypts'
except:
  print 'attack was unsuccessful'

后来 May 发觉 $f,g$ 中有大量的 0，所以他弄了个新格，其中 θ 为某个大整数，这样方便规约。

p

BDD(Bounded Distance Decoding) Problem

给定格 $\Lambda$、点 $\textbf{a}:d(\textbf{a},\Lambda)<{1\over 2}\lambda_1(\Lambda)$，找到离该点最近的格点 $\textbf{x}$。

SIS (Short Integer Solution)

找到一非平凡的向量 $0\ne v\in \Z^m:Av=0\ mod\ q;\Arrowvert v\Arrowvert \le \beta < q\in \Z$，其中 $A\in Z_q^{n×m}$。也即找到小向量 $v\in \mathcal{L}^\perp(A)$，一般来说 $v\in {0,1,-1}^m$。

LWE

定义

令 $n,q\in \Z,\mathcal{X}$ 为一（以 0 为中心的）概率分布，给出秘密 $s\in \Z^n_q$，则称 $L_{n,q,\mathcal{X} }$ 表示在 $\Z_q^n × \Z_q$ 上的 LWE-Distribution。

具体地，均匀随机地取一 $a\in \Z^n_q$，$ e$ 遵循 $\mathcal{X}$ 生成，则 LWE 实例为 $(a,a·s+e)\in \Z^n_q×\Z_q$。

Search LWE-problem

给定 $m$ 组 $LWE$ 实例 $a_i,a_i·s+e_i$，我们建立如下矩阵表示：

寻找秘密向量 $s\in \Z_q^n$，称之为 ~ 问题。

LWE

Decision LWE-problem

给定 $m$ 组实例 $(a_i,b_i)\in \Z_q^n×\Z_q$，区分样本是从均匀随机分布 $\mathcal{U}(Z_q^n×Z_q)$ 选取的或是 LWE 实例 $L_{n,q,\mathcal{X}}$，被称之为 ~ 问题。

Ring-LWE

对一个密码系统来说，公钥至少需要 $n$ 个 LWE 实例 $\mathcal{a},b\in \Z^n_q×\Z_q$ 构成，则公钥大小至少为 $n^2$。为减少之，可以在公钥中添加一些结构：如，定义操作 $\sigma:(a_0,…,a_{n-1})\rightarrow (-a_{n-1},a_0,…,a_{n-2})$，则公钥只需要 $a,{b_i}$，剩余的 $a_i=\sigma^i(a)$。这就如同多项式上的操作，于是我们由此引出 RLWE。

令 $f(x)=x^n+1,R_q=\Z_q[x]/<f(x)>;s=s(x)\in R_q,a\in R_q$，则 RLWE 即如此 $(a,a·s+e)$，具体定义待补充。

 

 

这里给个例子：

from sage.crypto.lwe import LWE
from sage.stats.distributions.discrete_gaussian_integer \
    import DiscreteGaussianDistributionIntegerSampler as DGDIS
import uuid

n = len(secret)
q = random_prime(1<<512, proof=False, lbound=1<<511)

lwe = LWE(n=n, q=q, D=DGDIS(1<<128)) 
# A: 1xn; q: mod; D: error; 
# output: (A, b)
lwe._LWE__s = vector(Zmod(q), secret)

L = [lwe() for _ in range(2*n)]

讲解一下基本用法：

已知一个 mxn 的矩阵 $A$，一个 mx1 的 $b = Ax + e$，其中 $e$ 是一个 m 维的扰动向量，$x$ 是一个 nx1 的向量。

这显然像一个CVP，可以构造一个 Matrix[32 + 64 + 1, 64 + 32 + 1]，然后 LLL 拿 CVP。

前 [32, 64] 为 64 个 A，[32, 64:96] 是 1，求系数；[32:96, 64] 是 q 求模； [-1, 64] 是 CVP ($b$)，[-1, -1] 来个 1 即可。

 

Knapsack

比较经典的背包问题：

给定 $M = (M_1,M_2,…,M_n)$，其中 $M_i > 0$。

将明文转换为一系列二进制数 $x=x_1,x_2,…,x_n$，那么 $S = \Sigma_{i=1} ^ n x_iM_i$

给定 $M,S$ 找到满足 $S$ 的序列 $x$。

Attacks

Meet-in-Middle

显然有时空复杂度都为 $O(2^{n\over 2})$ 的暴力算法：

枚举出所有可能的 $n\over 2$ 个 $x$ 组合，对于 $M_{0-{n\over 2} }$ 存下所有的 $Mid = S - S_{0-{n\over 2} }$，然后求出 $S_{ {n\over 2}-n }$ 并一一与 $Mid$ 匹配。

LLL Attack

构造矩阵求解 SVP 即可。以下两个矩阵在某些情况下会有不同效果。

eg

eg

这里一并介绍类似问题及其矩阵构造：

For such prob, we can find $X=(x_1,…,x_n)$ as solution of SVP.

将之转化为：$b_1x_1+…+b_{n-1}x_{n-1}=x_n\ (mod\ N)$，减少一维。

然后构造如下即可：

eg

若 $x_1\approx … \approx x_n \approx N^{1\over n}$，那么可以知道 $x$ 是一个 short vector。

则我们可以拿到 $(x_1,…,x_{n-1},y)$

 

 

 

 

Hidden Number Problem

refer to Return of the Hidden Number Problem, Keegan Ryan

我们所寻找的 Hidden Number，形如 $\arrowvert t\alpha -u\arrowvert < n $ (限制范围) 中的 $\alpha$，其中 $n$ 是接近 $\arrowvert t\alpha -u\arrowvert$ 的边界。

这里 $u$ 可以有多种含义，而下面讲述的是：已知 (多组) $MSB_{l_i,n}(x)$ 从而拿到 Hidden Number 的方法。

我们所要找到的是满足不等式组：$\arrowvert \lfloor t_i\alpha \rfloor - u_i \arrowvert_q< {q\over 2^{l_i+1} } for\ all\ i\in {1,…,d }$ 的 Hidden Number $\alpha\in [1,q-1]$。

 

$\arrowvert \sum\limits_{j=1}^n\lfloor A_{ij}s_j \rfloor - b_{ij} + 16\arrowvert_q< 16+16=32={q\over 2^3}$

 

举个例子，假设：

q = getPrime(128)
(tα).bit_length() == 120

那么这里的 u = 1 « (120 - 1)，$\arrowvert t\alpha -u\arrowvert < u \le {q\over 2^{l+1} }$，那么 l = 128 - 120 = 8

于是我们可以构造如下矩阵：

eg

那么易知该格上有向量 $xB=(2^{l_1+1}\lfloor t_1\alpha \rfloor_q,…,2^{l_d+1}\lfloor t_d\alpha \rfloor_q,\alpha)$

而我们由以上不等式知道向量 $u=(2^{l_1+1}u_1,…,2^{l_d+1}u_d,0)$ 与之十分接近，于是我们可以使用 Embedded technique 来找到这个CVP。即可构造矩阵：

eg

那么目标 SVP 为 $(xB-u,-q)$，其倒数第二项即为 $\alpha $

据paper中提到，一般来说 ${SVP}_2$ 即为目标向量。

 

 

丢番图问题

待续

令 $\alpha_1,…,\alpha_n \in R, \epsilon > 0$。丢番图近似问题就是：

令 $Q\ge \epsilon^{-n} \in N$，找到 $0<q\le Q$ 使得 $\mid \alpha_i - {p_i\over q}\mid \le {\epsilon \over q}, 1\le i \le n$。

Method

令 $\alpha_1,…,\alpha_n \in \Q$，其分子、分母绝对值上界为 $X$。令 $0<\epsilon < 1$，则我们可以在多项式时间内得到满足条件的 $(q,p_1,…,p_n)$，其中 $0<q<2^{ {n(n+1)\over 4} }\epsilon ^{-(n+1) }$。

Proof

令 $Q=2^{ {n(n+1)\over 4} }\epsilon ^{-n}$，然后考虑如下格基：

eg

其大小为 $(n+1)^2,det(L)=2^{ -{n(n+1)\over 4} }\epsilon ^{n+1}$

规约得到的向量 ${\cal v} = (q\epsilon/Q,q\alpha_1 - p_1,…,q\alpha_n-p_n)$，由闵可夫斯基界，$\Arrowvert {\cal v}\Arrowvert \le \epsilon < 1$

显然 $q>0$，又 $\Arrowvert {\cal v}\Arrowvert_{\infin} \le \Arrowvert {\cal v}\Arrowvert$，后面感觉有点问题，不算了。

RSA

见 RSA 1.0.1。