Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with shortest vector problem:
TR97-059 | 22nd December 1997
Jin-Yi Cai, Ajay Nerurkar

Approximating the SVP to within a factor $\left(1 + \frac{1}{\mathrm{dim}^\epsilon}\right)$ is NP-hard under randomized reductions

Recently Ajtai showed that
to approximate the shortest lattice vector in the $l_2$-norm within a
factor $(1+2^{-\mbox{\tiny dim}^k})$, for a sufficiently large
constant $k$, is NP-hard under randomized reductions.
We improve this result to show that
to approximate a shortest lattice vector within a
factor $(1+ \mbox{dim}^{-\epsilon})$, for any
$\epsilon>0$, ... more >>>

TR98-010 | 22nd January 1998
Phong Nguyen, Jacques Stern

A Converse to the Ajtai-Dwork Security Proof and its Cryptographic Implications

Revisions: 1

Recently, Ajtai discovered a fascinating connection
between the worst-case complexity and the average-case
complexity of some well-known lattice problems.
Later, Ajtai and Dwork proposed a cryptosystem inspired
by Ajtai's work, provably secure if a particular lattice
problem is difficult. We show that there is a converse
to the ... more >>>

TR98-016 | 24th March 1998
Daniele Micciancio

The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant.

We show that computing the approximate length of the shortest vector
in a lattice within a factor c is NP-hard for randomized reductions
for any constant c<sqrt(2). We also give a deterministic reduction
based on a number theoretic conjecture.

more >>>

TR04-113 | 19th November 2004
Mårten Trolin

Lattices with Many Cycles Are Dense

We give a method for approximating any $n$-dimensional
lattice with a lattice $\Lambda$ whose factor group
$\mathbb{Z}^n / \Lambda$ has $n-1$ cycles of equal length
with arbitrary precision. We also show that a direct
consequence of this is that the Shortest Vector Problem and the Closest
Vector Problem cannot ... more >>>

TR09-065 | 31st July 2009
Panagiotis Voulgaris, Daniele Micciancio

Faster exponential time algorithms for the shortest vector problem

We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any $n$-dimensional lattice can be found in time $2^{3.199 n}$ and space $2^{1.325 n}$.
This improves the best previously known algorithm by Ajtai, Kumar ... more >>>

TR12-020 | 3rd March 2012
Daniele Micciancio

Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

Revisions: 1

We prove that the Shortest Vector Problem (SVP) on point lattices is NP-hard to approximate for any constant factor under polynomial time reverse unfaithful random reductions. These are probabilistic reductions with one-sided error that produce false negatives with small probability, but are guaranteed not to produce false positives regardless of ... more >>>

TR18-057 | 26th March 2018
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., Pasin Manurangsi

Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

The $k$-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb F_2$, which can be stated as follows: given a generator matrix $\mathbf A$ and an integer $k$, determine whether the code generated by $\mathbf A$ has distance at most $k$. Here, $k$ ... more >>>

TR19-115 | 4th September 2019
Arnab Bhattacharyya, Édouard Bonnet, László Egri, Suprovat Ghoshal, Karthik C. S., Bingkai Lin, Pasin Manurangsi, Dániel Marx

Parameterized Intractability of Even Set and Shortest Vector Problem

The k-Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over $\mathbb{F}_2$, which can be stated as follows: given a generator matrix A and an integer k, determine whether the code generated by A has distance at most k, or in other words, whether ... more >>>

TR22-156 | 15th November 2022
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms

We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that ... more >>>

TR22-170 | 15th November 2022
Huck Bennett

The Complexity of the Shortest Vector Problem

Computational problems on point lattices play a central role in many areas of computer science including integer programming, coding theory, cryptanalysis, and especially the design of secure cryptosystems. In this survey, we present known results and open questions related to the complexity of the most important of these problems, the ... more >>>

ISSN 1433-8092 | Imprint