The tale of one-way functions (Q2487080)

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.