The tale of one-way functions

DOI10.1023/A:1023634616182zbMath1077.94007OpenAlexW2170261589MaRDI 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-completenessquantum computingone-way functionsLas Vegas algorithmsTuring Machines

Mathematics Subject Classification ID

Cryptography (94A60) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Information theory (general) (94A15)

Related Items (16)

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

This page was built for publication: The tale of one-way functions