A survey of one-way functions in complexity theory

DOI10.1007/BF01374525zbMath0749.68037MaRDI QIDQ4009812

Selman, Alan L.

Publication date: 27 September 1992

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

zbMATH Keywords

cryptography; one-way function; isomorphism problem

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

68-02: Research exposition (monographs, survey articles) pertaining to computer science

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

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

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