One-way permutations and self-witnessing languages

DOI10.1016/S0022-0000(03)00068-0zbMath1114.68046OpenAlexW2082576166MaRDI QIDQ1877694

Christopher M. Homan, Mayur Thakur

Publication date: 19 August 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(03)00068-0

zbMATH Keywords

One-way functionsPermutationsComplexity-theoretic cryptographyOne-to-one functionsSelf-witnessing languages

Mathematics Subject Classification ID

Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Query-monotonic Turing reductions, Computational tameness of classical non-causal models, ON THE CIRCUIT-SIZE OF INVERSES, Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions

Cites Work

• Unnamed Item
• On some natural complete operators
• On hardness of one-way functions
• One way functions and pseudorandom generators
• Complexity classes without machines: on complete languages for UP
• Relative complexity of checking and evaluating
• Upward separation for FewP and related classes
• Easy sets and hard certificate schemes
• Characterizing the existence of one-way permutations
• On characterizing the existence of partial one-way permutations
• Defying upward and downward separation
• Complexity Measures for Public-Key Cryptosystems
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Completeness, Approximation and Density
• Compression and Ranking
• A survey of one-way functions in complexity theory
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Tally languages and complexity classes