Complexity Measures for Public-Key Cryptosystems
From MaRDI portal
Publication:3787917
DOI10.1137/0217018zbMath0644.94016OpenAlexW2085634981MaRDI QIDQ3787917
Joachim Grollmann, Selman, Alan L.
Publication date: 1988
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0217018
Related Items
The complexity of online bribery in sequential elections, On reductions of NP sets to sparse sets, A taxonomy of complexity classes of functions, One-way permutations and self-witnessing languages, Collapsing degrees via strong computation, An observation on associative one-way functions in complexity theory, A note on quadratic residuosity and UP, A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes, Nondeterministic functions and the existence of optimal proof systems, A general method to construct oracles realizing given relationships between complexity classes, The complexity of online manipulation of sequential elections, One-way functions and the nonisomorphism of NP-complete sets, Simultaneous strong separations of probabilistic and unambiguous complexity classes, Reductions between disjoint NP-pairs, Cluster computing and the power of edge recognition, The isomorphism conjecture holds and one-way functions exist relative to an oracle, Every polynomial-time 1-degree collapses if and only if P = PSPACE, A thirty year old conjecture about promise problems, How to define a linear order on finite models, Canonical disjoint NP-pairs of propositional proof systems, Tight lower bounds on the ambiguity of strong, total, associative, one-way functions, Structural properties for feasibly computable classes of type two, A survey of one-way functions in complexity theory, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, Unambiguous computations and locally definable acceptance types, Statistical zero knowledge and quantum one-way functions, Classes of representable disjoint \textsf{NP}-pairs, On the power of parity polynomial time, On the complexity of small description and related topics, Promise problems and access to unambiguous computation, Unnamed Item, ON THE CIRCUIT-SIZE OF INVERSES, Approximation of coNP sets by NP-complete sets, Logical Closure Properties of Propositional Proof Systems, An oracle builder's toolkit, Dimension and the structure of complexity classes, Polynomial-time axioms of choice and polynomial-time cardinality, The Shrinking Property for NP and coNP, On reducibility and symmetry of disjoint NP pairs., The shrinking property for NP and coNP, Proof system representations of degrees of disjoint NP-pairs, Computational indistinguishability between quantum states and its cryptographic application, The Complexity of Complexity, Robust machines accept easy sets, Unnamed Item, Complexity limitations on quantum computation, Inverting onto functions., Pseudo-deterministic Proofs, Tuples of disjoint \(\mathsf{NP}\)-sets, On sets polynomially enumerable by iteration, Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions, UP and the low and high hierarchies: A relativized separation, Strong self-reducibility precludes strong immunity, Oracles for structural properties: The isomorphism problem and public-key cryptography, On polynomial time one-truth-table reducibility to a sparse set, On polynomial-time Turing and many-one completeness in PSPACE, The complexity of unions of disjoint sets, Polynomial-time compression, Diagonalization, uniformity, and fixed-point theorems, One-way permutations, computational asymmetry and distortion., Absolute results concerning one-way functions and their applications, On the power of parity polynomial time, Partial bi-immunity, scaled dimension, and NP-completeness, Inseparability and strong hypotheses for disjoint NP pairs, Does the polynomial hierarchy collapse if onto functions are invertible?, The deduction theorem for strong propositional proof systems, UP and the low and high hierarchies: A relativized separation, The robustness of LWPP and WPP, with an application to graph reconstruction, If P \(\neq\) NP then some strongly noninvertible functions are invertible, Closure and nonclosure properties of the classes of compressible and rankable sets, An oracle separating conjectures about incompleteness in the finite domain, The Deduction Theorem for Strong Propositional Proof Systems, Unions of Disjoint NP-Complete Sets, Hard promise problems and nonuniform complexity, In a World of P=BPP, THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS, A hierarchy based on output multiplicity, P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle, Enumerative counting is hard, A second step towards complexity-theoretic analogs of Rice's Theorem, Characterizing the existence of one-way permutations, On the limits of nonapproximability of lattice problems, Oracle Quantum Computing, A note on the non-NP-hardness of approximate lattice problems under general Cook reductions., Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory, Restrictive Acceptance Suffices for Equivalence Problems, On the probabilistic closure of the loose unambiguous hierarchy, Quasi-injective reductions, On characterizing the existence of partial one-way permutations, A note on unambiguous function classes
