The tale of one-way functions

DOI10.1023/A:1023634616182zbMath1077.94007MaRDI QIDQ2487080

Leonid A. Levin

Publication date: 17 August 2005

Published in: Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1023634616182

zbMATH Keywords

NP-completeness; quantum computing; one-way functions; Las Vegas algorithms; Turing Machines

Mathematics Subject Classification ID

94A60: Cryptography

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

94A15: Information theory (general)

Related Items

An Average Case NP-complete Graph Colouring Problem, Unnamed Item, Unnamed Item, Infinitely generated semigroups and polynomial complexity, One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions, A complete one-way function based on a finite rank free \(\mathbb{Z}\times\mathbb{Z}\)-module, Cryptographic transformations of non-Shannon sources of information, On complete one-way functions, Quantum one-way permutation over the finite field of two elements, Circuit complexity of linear functions: gate elimination and feeble security, On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \), Optimizing Segment Based Document Protection, Algebraic cryptography: new constructions and their security against provable break, Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization, An Infinitely-Often One-Way Function Based on an Average-Case Assumption, An infinitely-often one-way function based on an average-case assumption