We give deterministic $2^{O(n)}$-time algorithms to solve all the most important computational problems on point lattices in NP, including the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), and Shortest Independent Vectors Problem (SIVP). This improves the $n^{O(n)}$ running time of the best previously known algorithms for CVP (Kannan, Math. ... more >>>

We present new faster algorithms for the exact solution of the shortest vector problem in arbitrary lattices. Our main result shows that the shortest vector in any $n$-dimensional lattice can be found in time $2^{3.199 n}$ and space $2^{1.325 n}$. This improves the best previously known algorithm by Ajtai, Kumar ... 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 provide unconditional constructions of concurrent statistical zero-knowledge proofs for a variety of non-trivial problems (not known to have probabilistic polynomial-time algorithms). The problems include Graph Isomorphism, Graph Nonisomorphism, Quadratic Residuosity, Quadratic Nonresiduosity, a restricted version of Statistical Difference, and approximate versions of the (coNP forms of the) Shortest Vector ... more >>>

We investigate the average case complexity of a generalization of the compact knapsack problem to arbitrary rings: given $m$ (random) ring elements a_1,...,a_m in R and a (random) target value b in R, find coefficients x_1,...,x_m in S (where S is an appropriately chosen subset of R) such that a_1*x_1 ... 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 show how to efficiently transform any public coin honest verifier zero knowledge proof system into a proof system that is concurrent zero-knowledge with respect to any (possibly cheating) verifier via black box simulation. By efficient we mean that our transformation incurs only an additive overhead, both in terms of ... more >>>

Computing the Hermite Normal Form of an $n\times n$ matrix using the best current algorithms typically requires $O(n^3\log M)$ space, where $M$ is a bound on the length of the columns of the input matrix. Although polynomial in the input size (which is $O(n^2\log M)$), this space blow-up can easily ... more >>>

We show that the minimum distance of a linear code (or equivalently, the weight of the lightest codeword) is not approximable to within any constant factor in random polynomial time (RP), unless NP equals RP. Under the stronger assumption that NP is not contained in RQP (random quasi-polynomial time), we ... more >>>

We show that given oracle access to a subroutine which returns approximate closest vectors in a lattice, one may find in polynomial-time approximate shortest vectors in a lattice. The level of approximation is maintained; that is, for any function $f$, the following holds: Suppose that the subroutine, on input a ... more >>>

We show that computing the approximate length of the shortest vector in a lattice within a factor c is NP-hard for randomized reductions for any constant cmore >>>