Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALGEBRAIC NUMBER THEORY:
Reports tagged with algebraic number theory:
TR06-147 | 27th November 2006
Chris Peikert, Alon Rosen

#### Lattices that Admit Logarithmic Worst-Case to Average-Case Connection Factors

Revisions: 1

We demonstrate an \emph{average-case} problem which is as hard as
finding $\gamma(n)$-approximate shortest vectors in certain
$n$-dimensional lattices in the \emph{worst case}, where $\gamma(n) = O(\sqrt{\log n})$. The previously best known factor for any class
of lattices was $\gamma(n) = \tilde{O}(n)$.

To obtain our ... more >>>

ISSN 1433-8092 | Imprint