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 (19)

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

This page was built for publication: A survey of one-way functions in complexity theory