Oracles for structural properties: The isomorphism problem and public-key cryptography

DOI10.1016/0022-0000(92)90023-CzbMath0757.68055OpenAlexW2174367614MaRDI QIDQ1190988

Selman, Alan L., Homer, Steven

Publication date: 27 September 1992

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

Full work available at URL: https://doi.org/10.1016/0022-0000(92)90023-c

zbMATH Keywords

relativizationisomorphism conjecturepublic-key cryptosystems\(p\)-isomorphismcryptographic complexity

Mathematics Subject Classification ID

Cryptography (94A60) Data encryption (aspects in computer science) (68P25) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (13)

Collapsing degrees via strong computation ⋮ Canonical disjoint NP-pairs of propositional proof systems ⋮ Classes of representable disjoint \textsf{NP}-pairs ⋮ An oracle builder's toolkit ⋮ Dimension and the structure of complexity classes ⋮ The Shrinking Property for NP and coNP ⋮ The shrinking property for NP and coNP ⋮ Non-uniform reductions ⋮ On the topological size of p-m-complete degrees ⋮ Inseparability and strong hypotheses for disjoint NP pairs ⋮ The deduction theorem for strong propositional proof systems ⋮ The Deduction Theorem for Strong Propositional Proof Systems ⋮ THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS

Cites Work

• Unnamed Item
• On some natural complete operators
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• Relativizations of Unambiguous and Random Polynomial Time Classes
• Complexity Measures for Public-Key Cryptosystems
• Natural Self-Reducible Sets
• Relativized Questions Involving Probabilistic Algorithms
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• The isomorphism conjecture fails relative to a random oracle
• On the Computational Complexity of Algorithms

This page was built for publication: Oracles for structural properties: The isomorphism problem and public-key cryptography