Complexity theory and cryptology. An introduction to cryptocomplexity.

DOI10.1007/3-540-28520-2zbMath1082.94002OpenAlexW141442529MaRDI 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 complexitypublic key cryptosystemcomplexity hierarchycryptographic protocolcomplexity class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Cryptography (94A60) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Authentication, digital signatures and secret sharing (94A62) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory (94-01)

Related Items (23)

The possible winner problem with uncertain weights revisited ⋮ On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P ⋮ Complexity of nonemptiness in control argumentation frameworks ⋮ Controlling weighted voting games by deleting or adding players with or without changing the quota ⋮ The complexity of computing minimal unidirectional covering sets ⋮ Complexity of control in judgment aggregation for uniform premise-based quota rules ⋮ The possible winner with uncertain weights problem ⋮ Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation ⋮ Minimizing envy and maximizing average Nash social welfare in the allocation of indivisible goods ⋮ Verification in incomplete argumentation frameworks ⋮ Acceptance in incomplete argumentation frameworks ⋮ Control complexity in Borda elections: solving all open cases of offline control and some cases of online control ⋮ Path-disruption games: bribery and a probabilistic model ⋮ Control complexity in Bucklin and fallback voting: a theoretical analysis ⋮ Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections ⋮ Polynomial-time right-ideal morphisms and congruences ⋮ Function operators spanning the arithmetical and the polynomial hierarchy ⋮ Optimizing social welfare in social networks ⋮ 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

This page was built for publication: Complexity theory and cryptology. An introduction to cryptocomplexity.