Worst-case complexity, average-case complexity and lattice problems (Q1126836)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Worst-case complexity, average-case complexity and lattice problems |
scientific article |
Statements
Worst-case complexity, average-case complexity and lattice problems (English)
0 references
5 August 1998
0 references
The author presents a public-key cryptosystem based on the difficulty of a problem essentially similar to finding the shortest vector in a lattice. As part of the introduction, the author discusses the need for a problem that is hard in the average case; traditional complexity theory has focused on the worst-case complexity of problems.
0 references
lattice
0 references
worst-case
0 references
average-case
0 references
complexity
0 references
basis
0 references
shortest vector
0 references
public-key cryptosystem
0 references
