Complexity Measures for Public-Key Cryptosystems

Recommendations

The Complexity of Public-Key Cryptography
scientific article; zbMATH DE number 3846870
Complexity theoretic aspects of some cryptographic functions
scientific article; zbMATH DE number 2000415
Kolmogorov complexity and cryptography
Some Perspectives on Complexity-Based Cryptography
scientific article; zbMATH DE number 4106765
Complexity results for security protocols with Diffie-Hellman exponentiation and commuting public key encryption
scientific article; zbMATH DE number 503190
Complexity and Cryptography

Cited in

(only showing first 100 items - show all)

On reductions of NP sets to sparse sets
Reductions between disjoint NP-pairs
Simultaneous strong separations of probabilistic and unambiguous complexity classes
On polynomial-time truth-table reducibility of intractable sets to P-selective sets
Restrictive Acceptance Suffices for Equivalence Problems
A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
Cluster computing and the power of edge recognition
Characterizing the existence of one-way permutations
On characterizing the existence of partial one-way permutations
On polynomial time one-truth-table reducibility to a sparse set
Unions of disjoint NP-complete sets
Pseudo-deterministic proofs
Robust machines accept easy sets
On polynomial-time Turing and many-one completeness in PSPACE
An oracle separating conjectures about incompleteness in the finite domain
The complexity of promise problems with applications to public-key cryptography
A note on quadratic residuosity and UP
The Deduction Theorem for Strong Propositional Proof Systems
P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
A survey of one-way functions in complexity theory
A note on unambiguous function classes
The combinatorial complexity of masterkeying
\(\mathrm{UP}\) and the low and high hierarchies: a relativized separation
Inseparability and strong hypotheses for disjoint NP pairs
Nondeterministic functions and the existence of optimal proof systems
The Complexity of Complexity
Hard promise problems and nonuniform complexity
Classes of representable disjoint \textsf{NP}-pairs
Promise problems and access to unambiguous computation
Tuples of disjoint \(\mathsf{NP}\)-sets
Enumerative counting is hard
On the circuit-size of inverses
One-way permutations and self-witnessing languages
Oracle Quantum Computing
Gaps, ambiguity, and establishing complexity-class containments via iterative constant-setting
scientific article; zbMATH DE number 691465 (Why is no real title available?)
scientific article; zbMATH DE number 4106765 (Why is no real title available?)
Polynomial-time compression
The deduction theorem for strong propositional proof systems
The complexity of online bribery in sequential elections
If P \(\neq\) NP then some strongly noninvertible functions are invertible
On the probabilistic closure of the loose unambiguous hierarchy
Dimension and the structure of complexity classes
The Shrinking Property for NP and coNP
A taxonomy of complexity classes of functions
Basing Weak Public-Key Cryptography on Strong One-Way Functions
On reducibility and symmetry of disjoint NP pairs.
An observation on associative one-way functions in complexity theory
Complexity limitations on quantum computation
Relativized cryptography
A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes
Cryptocomplexity and NP-completeness
Polynomial-time axioms of choice and polynomial-time cardinality
scientific article; zbMATH DE number 7350778 (Why is no real title available?)
In a world of \(\mathrm{P}=\mathrm{BPP}\)
Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
A second step towards complexity-theoretic analogs of Rice's Theorem
Unambiguous computations and locally definable acceptance types
Cryptographic security of individual instances
Proof system representations of degrees of disjoint NP-pairs
An oracle builder's toolkit
The robustness of LWPP and WPP, with an application to graph reconstruction
scientific article; zbMATH DE number 169207 (Why is no real title available?)
UP and the low and high hierarchies: A relativized separation
scientific article; zbMATH DE number 975406 (Why is no real title available?)
Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
Collapsing degrees via strong computation
Cryptosystems involving one-factorizations of graphs
Statistical zero knowledge and quantum one-way functions
Does the polynomial hierarchy collapse if onto functions are invertible?
On the complexity of small description and related topics
Closure and nonclosure properties of the classes of compressible and rankable sets
The complexity of online manipulation of sequential elections
Some consequences of cryptographical conjectures for S 2 1 and EF
Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
Quasi-injective reductions
Partial bi-immunity, scaled dimension, and NP-completeness
A general method to construct oracles realizing given relationships between complexity classes
On the limits of nonapproximability of lattice problems
Computational indistinguishability between quantum states and its cryptographic application
The shrinking property for NP and coNP
scientific article; zbMATH DE number 1482586 (Why is no real title available?)
On sets polynomially enumerable by iteration
Absolute results concerning one-way functions and their applications
A hierarchy based on output multiplicity
One-way permutations, computational asymmetry and distortion.
A thirty year old conjecture about promise problems
Structural properties for feasibly computable classes of type two
A thirty year old conjecture about promise problems
Approximation of coNP sets by NP-complete sets
Every polynomial-time 1-degree collapses if and only if P = PSPACE
Diagonalization, uniformity, and fixed-point theorems
Flexible constraint satisfiability and a problem in semigroup theory
Oracles for structural properties: The isomorphism problem and public-key cryptography
THE INFORMATIONAL CONTENT OF CANONICAL DISJOINT NP-PAIRS
Logical Closure Properties of Propositional Proof Systems
How to define a linear order on finite models
The isomorphism conjecture holds and one-way functions exist relative to an oracle
Inverting onto functions.
Strong self-reducibility precludes strong immunity

This page was built for publication: Complexity Measures for Public-Key Cryptosystems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3787917)