Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CLOSEST VECTOR PROBLEM:
Reports tagged with Closest Vector Problem:
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 >>>

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 >>>

TR06-052 | 15th April 2006
Wenbin Chen, Jiangtao Meng

#### Inapproximability Results for the Closest Vector Problem with Preprocessing over infty Norm

We show that the Closest Vector
Problem with Preprocessing over infty Norm
is NP-hard to approximate to within a factor of $(\log n)^{1/2-\epsilon}$. The result is the same as Regev and Rosen' result, but our proof methods are different from theirs. Their
reductions are based on norm embeddings. However, ... more >>>

TR11-119 | 4th September 2011
Subhash Khot, Preyas Popat, Nisheeth Vishnoi

#### $2^{\log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not \subseteq$DTIME$(2^{{\log^{O(1/\epsilon)} n}})$, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than $2^{\log ^{1-\epsilon}n}.$ This improves upon the previous hardness factor of $(\log n)^\delta$ for some \$\delta ... more >>>

ISSN 1433-8092 | Imprint