定理: 给decisionalCVP oracle, 可以有效解决searchCVP.
这里格和目标向量都在整点上取值, 格的秩为n. int[m][n] B, int[m][1] t.
证明:
首先, 是可以由判定器确定出最近距离是多少的.
对于任一格B,及目标向量t, 设r=dist(B,t), 下面估计r的上界.
令R:=|b1|+...+|bn|
t = t1b1+t2b2+...+tnbn
g=floor(t1)b1+...+floor(tn)bn
设g0是searchCVP的精确解,下用{x}表示数x-floor(x)
则|g0 - t| <=|g - t|=|{t1}b1+...+{tn}bn|<=|b1|+...+|bn|=R,
所以借助decisionalCVP oralcle, 利用二分法可以确定出optCVP.
最多问log(R^2)次, 这对于input size来说是多项式的.
一个观察是稀疏格的最近向量问题是容易解决的.
按照最近平面算法(the Nearest algorithm):
findCV_appr(B,t)
t=proj(t,spanB)
B~=GS(B)
b=t
for j=n to 1 do
b=b-round(miu(b,GS(B.col j)))*B.col j
return t-b
或者是写成递归调用的形式:
findCV_appr(B=[b1,...,bn],t)
if n=0 then return 0
else
B~=GS(B)
s=proj(t,span(b1,...,bn))
//find c s.t. the hyperspace c\*GS(B.col n)+span(b1,...,b n-1)
// as close as possible to s
c=round(miu(b,GS(B.col j)))
return c*bn+findCV_appr(B=[b1,...,b n-1], t-c*bn)
关于目标向量投影的注记
对于CVP, 目标向量t如果不在span(B)里面, 可以将t投影到其上.
设投影向量为t' , 如果 y 是离 t' 最近的格向量, 那么 y 是离 t 最近的格向量.
Claim: If y=searchCVP(B, t'), x=searchCVP_gamma(B,t')
then y=searchCVP(B,t), x=searchCVP_gamma(B,t)
由searchCVPγ(B,t')返回x, 则有|t'-x|2<=γ2 |t'-y|^2.
因为t-t'正交与span(B), 所以有t-t'垂直于t'-x和t'-y, 故而有下式:
|t-y|2=|t-t'|2(常值)+|t'-y|^2(投影里最近距离)
所以y=searchCVP(B,t);
|t-x|2=|t-t'|2+|t'-x|^2
<=|t-t'|2+γ2 |t'-y|^2
<=γ2(|t-t'|2+|t'-y|^2)
=γ2*|t-y|2
所以 x=searchCVP_gamma(B,t).
令 u = findCV_appr(B,t),
则|u-t|<=2^(n/2)dist(t,L(B))
我们的目标向量变为原目标+某个格向量, 对这个新目标来求最近向量的问题, 然后再把这个附加的格向量减掉, 就可以得到真正要求的了. 下面要做的就是稀疏化原来的格.
k取n+ceil(log r)
Sparser_1(B1,tt)
//其中B1张成了格L(B)的子格
//tt是t+v的形式, v是L(B)中的格向量
B'=(2*B1.col1, B1.col2, ...,B1.col n)
if B'.col1>=2^k*B.col 1 return (B', tt)
ans=isSmaller(L(B'), tt, r)
//query decisional CVP oracle
if ans==true
//t1离更稀疏的B'的距离小于等于r, 此时dist*(L(B'),tt)>=r
//那么说明dist(L(B2),tt)==r
Sparser_1(B',tt) //t2=t1
else //t1离B2的距离大于r, 即稀疏化以后, 离格的最近距离远了
tt=tt-B1.col1
Sparser_1(B',tt)
return (B',tt)
1.B'是B1的子格, B1是B的子格, 所以B'是B的子格
2.调用一次Sparser_1, tt要么不变, 要么变为tt-B1.col1, 都是 t+格点 的形式
3.最后返回的(B',tt), 满足dist(L(B'),tt)==r(本算法的关键)
事实上, 如果isSmaller == true, 上式成立
如果isSmaller == false, 注意到L(B1)=L(B')U(L(B')+B1.col1),
这说明在L(B')+B1.col1里面取格点达到最近向量,
所以dist(L(B')+B1.col1,tt)==r, 这等价于
dist(L(B'),tt-B1.col1)==r
Sparser_2(B1,t)
//改动部分如下, 其他处理不变
B'=(B1.col1, 2B1.col2, ...,B1.col n)
if B'.col2>=2^kB.col 2 return (B', tt)
于是我们可以给出求解searchCVP的程式
findCV(B,t)
t0=t
for i=1 to n do
(B,t)=Sparse_i(B,t)
g=findCV_appr(B,t)
v=t-t0
return g-v
从Sparser_1到Sparser_n, 共有n*k次迭代步骤
在n*k步以后, 得到(B*,t*)
B*=(2k*b1,...,2k*bn)
t*=t+某格点v
由k=n+ceil(log r), 得2k>=r*2n
λ1(L(B*))>=2k>=r*2n
则在L(B*)里的两个向量距离至少为r*2^n.
离t*第一近的格点到t的距离为r, 设离t第二近的格点到t*的距离为r',
则r+r'>=r*2^n, 所以r'>=r*2n-r>=2(n-1) r>2^(n/2)(n-1)r (n>2)
(n<=2的时候找最近向量是容易的, 穷举很快, 因为维数很低.)
可以得到最近平面算法更优的近似因子 γ=2(2/sqrt(3))^n.
所以findCV_appr(B*,t*)给出的最近格向量g-, 满足
|g--t*|=dist(B*,t*)=r, 所以最后return g-v.
**Theorem: Decisional CVP is NP-complete **
decisional CVP is NP
对于使 dist(t, L(B))<=r 的实例 (B,t,r)
令x为格向量, 满足|x-t|<=r
Claim: x 可以作为decisionalCVP为NP问题的一个证据
|x-t|<=r可以多项式间验证, 代入算即可
x的每一个分量xi的绝对值至多为|t|+r
|xi|<=|x|=|x-t+t|<=|t|+r
Remark:本篇| |均表示算二范数decisional CVP is NP-hard
a reduction from subset-sum problem
an instance of subset-sum:
given n+1 integers a1,a2,...,an, s
goal: find A, some subset of set {1,2,...,n}
s.t. sum of ai (i ∈A)=s
下面说明:
若有一个子集和问题的Yes实例, 就给出了一个isSmaller(B,t,sqrt(n))的Yes实例 ;
若有一个isSmaller(B,t,sqrt(n))的Yes实例, 就给出了子集和问题的一个Yes实例.
而子集和问题的decision版本又是NP-hard的, 而上面这段已经说明了两个问题可以互相规约到, 所以它们两个的复杂性是同等级别的, 又已知子集和问题是NP-hard的, 所以第二个claim成立.
这里的B和t的构造如下
B[n+1][n]={
{a1,a2,...,an},
{2, 0, ...,0 },
{0, 2, ...,0 },
...
{0, 0, ...,2 }
}
t[n+1][1]={
{s},
{1},
...
{1}
}
如果(a1,a2,...,an,s)是子集和问题的Yes实例, 则isSmaller(B,t,sqrt(n))是decisionalCVP的Yes实例;
如果isSmaller(B,t,sqrt(n))是decisionalCVP的Yes实例, 则(a1,a2,...,an,s)是子集和问题的Yes实例.
上面两个方向由B和t的构造容易说明.
SVP vs CVP
对于大于等于1的近似因子γ, 找到SVP的γ-近似解的难度<=找到CVP的γ-近似解.
给一个SVP的实例, 我们用CVP的procedure, 令目标向量为0. 但是这其实不行, 因为0向量的CV就是它本身.
remove some points of lattice to make a sublattice
try several sublattices, s.t. one of which is guaranteed to reveal the desired short vector.
a generalization of decisionalCVP: GapCVPγ
It's a promise problem.
(PI_YES, PI_NO)
对于在PI_YES∪PI_NO里的一个输入实例I, it decides I在PI_YES里还是在PI_NO里, 不像total decision problems, PI_YES∪PI_NO不必包含全部可能性
GapCVPγ:
yes 小于等于r
no >γ*r
当γ=1的时候, 就是确定性的CVP判定问题.
类似地可以给出GapSVPγ的定义
**定理(判定版): 给GapCVPγ oracle, 可以有效解决GapSVPγ **
证明: 令GapSVPγ要解决的实例为(B,r)
构造n个GapCVPγ oracle实例, 调用isCloser(格基,目标向量,查询距离)程式
isShorter(B,r)
flag == false
for i=1 to n do
Bi=(B.col1,...,2B.col i, ...,B.coln)
bi=B.col i
//Bi: 第i个列向量为原来B.col i的两倍, 其他的和B的列向量相同
//目标向量为bi
//查询距离为r
if isCloser(Bi, bi, r) == true
flag==true
return flag
return flag
//至少有一个closer, 返回Yes, 每个都更远的话, 返回no
下面证明, 用上面这个procedure, 确实可以回答GapSVPγ的问题
- 假设(B,r)是个No实例, 即有任何格向量长度都比查询长度r的γ倍要大,
对于每一个v ∈ L(Bi), 有v-bi ∈ L(B)-{0}, 所以|v-bi|>γ*r, 这时候isCloser(Bi,bi,r)确实返回No(对任意i). - 假设(B,r)是个Yes实例, 即有L(B)中的最短向量长度≤r, 令v是达到最短长度的格向量, |v|≤r. v=a1b1+...+anbn, 这里ai是整数. 则这些整系数里至少有一个是奇数. 若不然, 全部系数都是偶数的话, v/2会在格里面, 那么找到了一个长度更短的格向量, 矛盾.设ak是奇数, 则bk+v ∈ L(Bk), 所以有bk+v=x ∈ L(Bk), 所以dist(bk,L(Bk))<=|bk-x|=|v|<=r. 所以isCloser(Bk,bk,r)返回了true, 所以isShorter(B,k)会返回true.
上面说明了, 当给出Yes实例的时候, 确实会返回true; 当给出No实例的时候, 确实会返回False, 算法正确性得证.
**定理(搜索版): 给searchCVPγ oracle, 可以有效解决searchSVPγ **
证明: 令searchSVPγ要解决的实例为B, 秩为n.
构造n个searchCVPγ oracle实例, 调用findCV_appr(格基,目标向量)程式
findSV_appr(B)
for i=1 to n do
Bi=(B.col1,...,2*B.col i,....,B.col n)
bi=B.col i
//Bi: 第i个列向量为原来B.col i的两倍, 其他的和B的列向量相同
//目标向量为bi
xi=findCV_appr(Bi, bi)
k=1
//k keeps index
keep_dist=|x1-b1|
for i=2 to n do
if |xi-bi|<keep_dist
keep_dist=|xi-bi|
k=i
return xk
令v为达到最短长度的格向量, 则v的整系数表达式中, 至少有一个为奇数,该系数设为ak, 不然, 0.5倍该向量, 得到了一个更短的格向量, 矛盾. 于是v=L(Bk)的某向量 - bk, 故dist(bk,L(Bk))<=|v|,而这个距离要大于等于最短格向量的长度, 所以只能取等号.dist(bk,L(Bk))=|v|, 则|xk-bk|<=γ|v|, 所以可以返回某满足要求的xk.
**定理(最优版): 给optCVPγ oracle, 可以有效解决optSVPγ **
shortest_appr(B)
for i=1 to n do
Bi=(B.col1,...,2*B.col i,....,B.col n)
bi=B.col i
//Bi: 第i个列向量为原来B.col i的两倍, 其他的和B的列向量相同
//目标向量为bi
di=closest_appr(Bi, bi)
keep_dist=d1
for i=2 to n do
if di<keep_dist
keep_dist=di
return keep_dist
令v为达到最短长度的格向量, 则v的整系数表达式中, 至少有一个为奇数,该系数设为ak, 不然, 0.5倍该向量, 得到了一个更短的格向量, 矛盾. 于是v=L(Bk)的某向量 - bk, 故dist(bk,L(Bk))<=|v|,而这个距离要大于等于最短格向量的长度, 所以只能取等号.dist(bk,L(Bk))=|v|, 由于dk是由closest_appr(Bk, bk)返回, dk<=γdist(bk,L(Bk))=γλ1,而也成立dk=dist(0,L(Bk)-bk), 所以返回的满足optSVPγ的要求.
