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)

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

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)