Levin, L. A. The tale of one-way functions. (English. Russian original) Zbl 1077.94007 Probl. Inf. Transm. 39, No. 1, 92-103 (2003); translation from Prob. Peredachi Inf. 39, No. 1, 103-117 (2003). 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. Reviewer: Ivan Landjev (Sofia) Cited in 1 ReviewCited in 18 Documents MSC: 94A15 Information theory (general) 68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) 94A60 Cryptography Keywords:one-way functions; quantum computing; Las Vegas algorithms; NP-completeness; Turing Machines × Cite Format Result Cite Review PDF Full Text: DOI