The tale of one-way functions (Q2487080)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The tale of one-way functions |
scientific article |
Statements
The tale of one-way functions (English)
0 references
17 August 2005
0 references
The author considers the problem of the existence of one-way functions and gives an unified treatment of this subject. He discusses various concepts related to this problem. In section 1, one way-functions are introduced in the classical context. Section 2 deals with some non-traditional computing models (quantum computers). In section 3, the author discusses Las Vegas algorithms and the problem of averaging the performance of a randomized algorithm over inputs with a given distribution. In the last section, the author addresses the following problem: given a function to invert, what is the complexity of the generation of hard instances. He also presents an example of a complete one-way function provided such functions do exist.
0 references
one-way functions
0 references
quantum computing
0 references
Las Vegas algorithms
0 references
NP-completeness
0 references
Turing Machines
0 references