We define number-theoretic error-correcting codes based on algebraic
number fields, thereby providing a generalization of Chinese Remainder
Codes akin to the generalization of Reed-Solomon codes to
Algebraic-geometric codes. Our construction is very similar to
(and in fact less general than) the one given by (Lenstra 1986), but
the ... more >>>

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