We give a random class of n dimensional lattices so that, if
there is a probabilistic polynomial time algorithm which finds a short
vector in a random lattice with a probability of at least 1/2
then there is also a probabilistic polynomial time algorithm which
solves the following three lattice ... more >>>

We show that the shortest vector problem in lattices
with L_2 norm is NP-hard for randomized reductions. Moreover we
also show that there is a positive absolute constant c, so that to
find a vector which is longer than the shortest non-zero vector by no
more than a factor of ... more >>>

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

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 Ajtai-Dwork ... more >>>

A lattice in euclidean space which is an orthogonal sum of
nontrivial sublattices is called decomposable. We present an algorithm
to construct a lattice's decomposition into indecomposable sublattices.
Similar methods are used to prove a covering theorem for generating
systems of lattices and to speed up variations of the LLL ... more >>>

Lattices have received considerable attention as a potential source of computational hardness to be used in cryptography, after a breakthrough result of Ajtai (STOC 1996) connecting the average-case and worst-case complexity of various lattice problems. The purpose of this paper is twofold. On the expository side, we present a rigorous ... more >>>

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

A clone is a set of functions that is closed under generalized substitution.
The set FP of functions being computable deterministically in polynomial
time is such a clone. It is well-known that the set of subclones of every
clone forms a lattice. We study the lattice below FP, which ... more >>>

The generalized knapsack problem is the following: given $m$ random
elements $a_1,\ldots,a_m\in R$ for some ring $R$, and a target $t\in
R$, find elements $z_1,\ldots,z_m\in D$ such that $\sum{a_iz_i}=t$
where $D$ is some given subset of $R$. In (Micciancio, FOCS 2002),
it was proved that for appropriate choices of $R$ ... more >>>

We give the first representation-independent hardness results for
PAC learning intersections of halfspaces, a central concept class
in computational learning theory. Our hardness results are derived
from two public-key cryptosystems due to Regev, which are based on the
worst-case hardness of well-studied lattice problems. Specifically, we
prove that a polynomial-time ... 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 results, we ... more >>>

We show that for any $p \geq 2$, lattice problems in the $\ell_p$
norm are subject to all the same limits on hardness as are known
for the $\ell_2$ norm. In particular, for lattices of dimension
$n$:

* Approximating the shortest and closest vector in the
... more >>>

We present a radically new approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled fully homomorphic encryption schemes (capable of evaluating arbitrary polynomial-size circuits), {\em without Gentry's bootstrapping procedure}.

We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, $t$-designs, and $t$-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. ... more >>>

The question of list decoding error-correcting codes over finite fields (under the Hamming metric) has been widely studied in recent years. Motivated by the similar discrete structure of linear codes and point lattices in $R^{N}$, and their many shared applications across complexity theory, cryptography, and coding theory, we initiate the ... more >>>