The complexity of promise problems with applications to public-key cryptography
From MaRDI portal
Publication:3722415
DOI10.1016/S0019-9958(84)80056-XzbMath0592.94012WikidataQ29543805 ScholiaQ29543805MaRDI QIDQ3722415
Selman, Alan L., Yacov Yacobi, Shimon Even
Publication date: 1984
Published in: Information and Control (Search for Journal in Brave)
Turing machines; Turing reducibility; NP-complete sets; NP-hard cracking problems; partial decision problem
94A60: Cryptography
68P25: Data encryption (aspects in computer science)
03B25: Decidability of theories and sets of sentences
03D15: Complexity of computation (including implicit computational complexity)
Related Items
On sets bounded truth-table reducible to $P$-selective sets, Monotonous and randomized reductions to sparse sets, How to Achieve Perfect Simulation and A Complete Problem for Non-interactive Perfect Zero-Knowledge, General Properties of Quantum Zero-Knowledge Proofs, An Equivalence Between Zero Knowledge and Commitments, Assisted Problem Solving and Decompositions of Finite Automata, NP is as easy as detecting unique solutions, Promise problems complete for complexity classes, Unambiguous computations and locally definable acceptance types, Practic zero-knowledge proofs: Giving hints and using deficiencies, Separating complexity classes with tally oracles, Graph isomorphism is low for PP, A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm, Hard promise problems and nonuniform complexity, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, A hierarchy based on output multiplicity, A taxonomy of complexity classes of functions, On the limits of nonapproximability of lattice problems, A note on the non-NP-hardness of approximate lattice problems under general Cook reductions., On the reducibility of sets inside NP to sets with low information content, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, Mathematical problems in cryptology, On membership comparable sets, Reductions between disjoint NP-pairs, Graph Isomorphism is in SPP, A common algebraic description for probabilistic and quantum computations, On polynomial-time truth-table reducibility of intractable sets to P-selective sets, Absolute results concerning one-way functions and their applications
