Phong Nguyen, Jacques Stern

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

MÃ¥rten Trolin

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

Wenbin Chen, Jiangtao Meng

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

Subhash Khot, Preyas Popat, Nisheeth Vishnoi

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