A survey of one-way functions in complexity theory

DOI10.1007/BF01374525zbMath0749.68037OpenAlexW1970439855MaRDI QIDQ4009812

Selman, Alan L.

Publication date: 27 September 1992

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01374525

zbMATH Keywords

cryptographyone-way functionisomorphism problem

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

A taxonomy of complexity classes of functions, One-way permutations and self-witnessing languages, An observation on associative one-way functions in complexity theory, A note on quadratic residuosity and UP, The isomorphism conjecture holds and one-way functions exist relative to an oracle, Tight lower bounds on the ambiguity of strong, total, associative, one-way functions, Unambiguous computations and locally definable acceptance types, Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions, NP-Creative sets: A new class of creative sets in NP, Strong polynomial-time reducibility, One-way permutations, computational asymmetry and distortion., Complexity classes of equivalence problems revisited, Function operators spanning the arithmetical and the polynomial hierarchy, If P \(\neq\) NP then some strongly noninvertible functions are invertible, A hierarchy based on output multiplicity, Reductions in circuit complexity: An isomorphism theorem and a gap theorem, Characterizing the existence of one-way permutations, Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory, On characterizing the existence of partial one-way permutations

Cites Work

• Unnamed Item
• On some natural complete operators
• On one-one polynomial time equivalence relations
• Reductions among polynomial isomorphism types
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• On one-way functions and polynomial-time isomorphisms
• The complexity of optimization problems
• Relative complexity of checking and evaluating
• Riemann's hypothesis and tests for primality
• Positive Relativizations of Complexity Classes
• Complexity Measures for Public-Key Cryptosystems
• Natural Self-Reducible Sets
• Completeness, Approximation and Density
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Polynomial Time Enumeration Reducibility
• The isomorphism conjecture fails relative to a random oracle
• Recursively enumerable sets of positive integers and their decision problems
• Creative sets