All reports by Author Daniele Micciancio:

__
TR13-115
| 27th August 2013
__

Daniele Micciancio#### Locally Dense Codes

__
TR12-020
| 3rd March 2012
__

Daniele Micciancio#### Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction

Revisions: 1

__
TR10-014
| 2nd February 2010
__

Daniele Micciancio, Panagiotis Voulgaris#### A Deterministic Single Exponential Time Algorithm for Most Lattice Problems based on Voronoi Cell Computations

Revisions: 1

__
TR09-065
| 31st July 2009
__

Panagiotis Voulgaris, Daniele Micciancio#### Faster exponential time algorithms for the shortest vector problem

__
TR05-142
| 1st December 2005
__

Vadim Lyubashevsky, Daniele Micciancio#### Generalized Compact Knapsacks are Collision Resistant

__
TR05-093
| 24th August 2005
__

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan#### Concurrent Zero Knowledge without Complexity Assumptions

__
TR04-095
| 3rd November 2004
__

Daniele Micciancio#### Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions

__
TR03-066
| 2nd September 2003
__

Daniele Micciancio#### Almost perfect lattices, the covering radius problem, and applications to Ajtai's connection factor

__
TR02-045
| 8th July 2002
__

Daniele Micciancio, Erez Petrank#### Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol

__
TR00-074
| 12th July 2000
__

Daniele Micciancio, Bogdan Warinschi#### A Linear Space Algorithm for Computing the Hermite Normal Form

__
TR99-029
| 31st August 1999
__

Ilya Dumer, Daniele Micciancio, Madhu Sudan#### Hardness of approximating the minimum distance of a linear code

__
TR99-002
| 22nd January 1999
__

Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.#### Approximating shortest lattice vectors is not harder than approximating closest lattice vectors.

__
TR98-016
| 24th March 1998
__

Daniele Micciancio#### The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant.

Daniele Micciancio

The Minimum Distance Problem (MDP), i.e., the computational task of evaluating (exactly or approximately) the minimum distance of a linear code, is a well known NP-hard problem in coding theory. A key element in essentially all known proofs that MDP is NP-hard is the construction of a combinatorial object that ... more >>>

Daniele Micciancio

We prove that the Shortest Vector Problem (SVP) on point lattices is NP-hard to approximate for any constant factor under polynomial time reverse unfaithful random reductions. These are probabilistic reductions with one-sided error that produce false negatives with small probability, but are guaranteed not to produce false positives regardless of ... more >>>

Daniele Micciancio, Panagiotis Voulgaris

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, ...
more >>>

Panagiotis Voulgaris, Daniele Micciancio

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

Vadim Lyubashevsky, Daniele Micciancio

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

Daniele Micciancio, Shien Jin Ong, Amit Sahai, Salil Vadhan

We provide <i>unconditional</i> constructions of <i>concurrent</i>

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 (<b>coNP</b> forms of the) Shortest Vector ...
more >>>

Daniele Micciancio

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

Daniele Micciancio

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

Daniele Micciancio, Erez Petrank

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, ...
more >>>

Daniele Micciancio, Bogdan Warinschi

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

Ilya Dumer, Daniele Micciancio, Madhu Sudan

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

Oded Goldreich, Daniele Micciancio, Shmuel Safra and Jean-Pierre Seifert.

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

Daniele Micciancio

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 c<sqrt(2). We also give a deterministic reduction

based on a number theoretic conjecture.