Cryptocomplexity and NP-completeness

DOI10.1007/3-540-10003-2_71MaRDI QIDQ3888962zbMATH OpenOpenAlexFDO

Authors Shimon Even, Yacov Yacobi

Publication date 1980

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-10003-2_71

zbMATH Keywords

cracking problemcryptocomplexitycryptosystemsknapsack problemNP-completenessNP-hardness

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Recommendations

• scientific article; zbMATH DE number 691465
• Complexity theory and cryptology. An introduction to cryptocomplexity.
• Complexity Measures for Public-Key Cryptosystems
• The complexity of promise problems with applications to public-key cryptography
• scientific article; zbMATH DE number 691485

Cited in

(19)

• NP is as easy as detecting unique solutions
• Promise problems complete for complexity classes
• On polynomial time one-truth-table reducibility to a sparse set
• Hard promise problems and nonuniform complexity
• On the reducibility of sets inside NP to sets with low information content
• Mathematical problems in cryptology
• An oracle separating conjectures about incompleteness in the finite domain
• Polynomial time quantum computation with advice
• Algebraic cryptography: new constructions and their security against provable break
• Implicit Computational Complexity of Subrecursive Definitions and Applications to Cryptographic Proofs
• The Shrinking Property for NP and coNP
• scientific article; zbMATH DE number 5320331 (Why is no real title available?)
• NP completeness of relocation cipher
• A Public-Key Cryptosystem Based on the Matrix Cover NP-Complete Problem
• The complexity of promise problems with applications to public-key cryptography
• scientific article; zbMATH DE number 691465 (Why is no real title available?)
• Promise problems and access to unambiguous computation
• The shrinking property for NP and coNP
• Non-repudiation without public-key

This page was built for publication: Cryptocomplexity and NP-completeness

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