Shortest vector problem .28SVP.29 Lattice problem

this illustration of shortest vector problem (basis vectors in blue, shortest vector in red).

in svp, basis of vector space v , norm n (often l) given lattice l , 1 must find shortest non-zero vector in v, measured n, in l. in other words, algorithm should output non-zero vector v such



n
(
v
)
=
λ
(
l
)


{\displaystyle n(v)=\lambda (l)}

.

in



γ


{\displaystyle \gamma }

-approximation version





svp


γ




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

, 1 must find non-zero lattice vector of length @



γ
⋅
λ
(
l
)


{\displaystyle \gamma \cdot \lambda (l)}

given



γ
≥
1


{\displaystyle \gamma \geq 1}

.

hardness results

the exact version of problem known np-hard randomized reductions.

by contrast, equivalent problem respect uniform norm known np-hard.

algorithms euclidean norm

to solve exact version of svp under euclidean norm, several different approaches known, can split 2 classes: algorithms requiring superexponential time (




2

ω
(
n
)




{\displaystyle 2^{\omega (n)}}

) ,




p
o
l
y

(
n
)


{\displaystyle \mathrm {poly} (n)}

memory, , algorithms requiring both exponential time , space (




2

Θ
(
n
)




{\displaystyle 2^{\theta (n)}}

) in lattice dimension. former class of algorithms notably includes lattice enumeration , random sampling reduction, while latter includes lattice sieving, computing voronoi cell of lattice, , discrete gaussian sampling. open problem whether algorithms solving exact svp exist running in single exponential time (




2

o
(
n
)




{\displaystyle 2^{o(n)}}

) , requiring memory scaling polynomially in lattice dimension.

to solve



γ


{\displaystyle \gamma }

-approximation version





svp


γ




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





γ
>
1


{\displaystyle \gamma >1}

euclidean norm, best known approaches based on using lattice basis reduction. large



γ
=

2

Ω
(
n
)




{\displaystyle \gamma =2^{\omega (n)}}

, lenstra–lenstra–lovász (lll) algorithm can find solution in time polynomial in lattice dimension. smaller values



γ


{\displaystyle \gamma }

, block korkine-zolotarev algorithm (bkz) commonly used, input algorithm (the blocksize



β


{\displaystyle \beta }

) determines time complexity , output quality: large approximation factors



γ


{\displaystyle \gamma }

, small block size



β


{\displaystyle \beta }

suffices, , algorithm terminates quickly. small



γ


{\displaystyle \gamma }

, larger



β


{\displaystyle \beta }

needed find sufficiently short lattice vectors, , algorithm takes longer find solution. bkz algorithm internally uses exact svp algorithm subroutine (running in lattices of dimension @



β


{\displaystyle \beta }

), , overall complexity closely related costs of these svp calls in dimension



β


{\displaystyle \beta }

.