Title: Worst-Case Complexity, Average-Case Complexity and Lattice Problems

There is a need both from a theoretical and from a practical point of view to create computational problems (in NP) that are hard (that is, they have no polynomial time solutions). Currently there are no methods to prove that such problemx exist at all. We may assume however as an axiom, that certain problems are hard, where the choice of the problems may have historical or theoretical motivations. These problems however are usually worst-case problems, while, e.g. for cryptographic application, we need hard average-case problems. In this paper we desrcibe two different average-case problems, and their cryptographic applications, which are at least as difficult as some well-known worst-case problems concerning lattices.

1991 Mathematics Subject Classification: lattice, worst-case, average-case, complexity, basis, shortest vector 68Q15

Keywords and Phrases: lattice, worst-case, average-case, complexity, basis, shortest vector

Full text: dvi.gz 16 k, dvi 37 k, ps.gz 57 k.

Home Page of DOCUMENTA MATHEMATICA