Closest vector problem .28CVP.29 Lattice problem

1 closest vector problem (cvp)

1.1 relationship svp
1.2 hardness results
1.3 sphere decoding

closest vector problem (cvp)

this illustration of closest vector problem (basis vectors in blue, external vector in green, closest vector in red).

in cvp, basis of vector space v , metric m (often l) given lattice l, vector v in v not in l. desired find vector in l closest v (as measured m). in



γ


{\displaystyle \gamma }

-approximation version





cvp


γ




{\displaystyle {\text{cvp}}_{\gamma }}

, 1 must find lattice vector @ distance @



γ


{\displaystyle \gamma }

.

relationship svp

the closest vector problem generalization of shortest vector problem. easy show given oracle





cvp


γ




{\displaystyle {\text{cvp}}_{\gamma }}

(defined below), 1 can solve





svp


γ




{\displaystyle {\text{svp}}_{\gamma }}

making queries oracle. naive method find shortest vector calling





cvp


γ




{\displaystyle {\text{cvp}}_{\gamma }}

oracle find closest vector 0 not work because 0 lattice vector , algorithm potentially output 0.

the reduction





svp


γ




{\displaystyle {\text{svp}}_{\gamma }}







cvp


γ




{\displaystyle {\text{cvp}}_{\gamma }}

follows: suppose input





svp


γ




{\displaystyle {\text{svp}}_{\gamma }}

problem basis lattice



b
=
[

b

1


,

b

2


,
…
,

b

n


]


{\displaystyle b=[b_{1},b_{2},\ldots ,b_{n}]}

. consider basis




b

i


=
[

b

1


,
…
,
2

b

i


,
…
,

b

n


]


{\displaystyle b^{i}=[b_{1},\ldots ,2b_{i},\ldots ,b_{n}]}

, let




x

i




{\displaystyle x_{i}}

vector returned





cvp


γ


(

b

i


,

b

i


)


{\displaystyle {\text{cvp}}_{\gamma }(b^{i},b_{i})}

. claim shortest vector in set



{

x

i


−

b

i


}


{\displaystyle \{x_{i}-b_{i}\}}

shortest vector in given lattice.

hardness results

goldreich et al. showed hardness of svp implies same hardness cvp. using pcp tools, arora et al. showed cvp hard approximate within factor




2


log

1
−
ϵ


⁡
(
n
)




{\displaystyle 2^{\log ^{1-\epsilon }(n)}}

unless



np
⊆
dtime
⁡
(

2

p
o
l
y
(
log
⁡
n
)


)


{\displaystyle \operatorname {np} \subseteq \operatorname {dtime} (2^{poly(\log n)})}

. dinur et al. strengthened giving np-hardness result



ϵ
=
(
log
⁡
log
⁡
n

)

c




{\displaystyle \epsilon =(\log \log n)^{c}}





c
<
1

/

2


{\displaystyle c<1/2}

.

sphere decoding

algorithms cvp, fincke , pohst variant, have been used data detection in multiple-input multiple-output (mimo) wireless communication systems (for coded , uncoded signals). in context called sphere decoding due radius used internal many cvp solutions.

it has been applied in field of integer ambiguity resolution of carrier-phase gnss (gps). called lambda method in field.