Complexity theory and cryptology. An introduction to cryptocomplexity.

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

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 possible winner with uncertain weights problem, Stability, vertex stability, and unfrozenness for special graph classes, 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, Structural control in weighted voting games, The possible winner problem with uncertain weights revisited, Complexity of nonemptiness in control argumentation frameworks, Controlling weighted voting games by deleting or adding players with or without changing the quota, Complexity of control in judgment aggregation for uniform premise-based quota rules, Acceptance in incomplete argumentation frameworks, Control complexity in Borda elections: solving all open cases of offline control and some cases of online control, Control complexity in Bucklin and fallback voting: a theoretical analysis, Optimizing social welfare in social networks, A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation, Function operators spanning the arithmetical and the polynomial hierarchy