Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > WORST-CASE COMPLEXITY:
Reports tagged with worst-case complexity:
TR96-007 | 29th January 1996
Miklos Ajtai

Generating Hard Instances of Lattice Problems

Comments: 1

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


TR96-065 | 13th December 1996
Miklos Ajtai, Cynthia Dwork

A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence

Revisions: 1 , Comments: 1

We present a probabilistic public key cryptosystem which is
secure unless the following worst-case lattice problem can be solved in
polynomial time:
"Find the shortest nonzero vector in an n dimensional lattice
L where the shortest vector v is unique in the sense that any other
vector whose ... more >>>


TR03-066 | 2nd September 2003
Daniele Micciancio

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

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




ISSN 1433-8092 | Imprint