Complexity theory and cryptology. An introduction to cryptocomplexity.

DOI10.1007/3-540-28520-2zbMath1082.94002MaRDI QIDQ2484164

Jörg Rothe

Publication date: 29 July 2005

Published in: Texts in Theoretical Computer Science. An EATCS Series (Search for Journal in Brave)

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

zbMATH Keywords

computational complexity; public key cryptosystem; complexity hierarchy; cryptographic protocol; complexity class

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science

94A60: Cryptography

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

94A62: Authentication, digital signatures and secret sharing

94-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory

Related Items

Polynomial-time right-ideal morphisms and congruences, The complexity of computing minimal unidirectional covering sets, Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods, Path-disruption games: bribery and a probabilistic model, Verification in incomplete argumentation frameworks, Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections, On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P, Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules, The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions, Mind change optimal learning of Bayes net structure from dependency and independency data, Control complexity in Bucklin and fallback voting: a theoretical analysis, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Function operators spanning the arithmetical and the polynomial hierarchy