Worst-case complexity, average-case complexity and lattice problems (Q1126836): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
| Property / author | |||
| Property / author: Miklós Ajtai / rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Jonathan P. Sorenson / rank | |||
Revision as of 14:54, 20 February 2024
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
