AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution

Non-commutative Cryptography and Complexity of Group-theoretic Problems

About this Title

Alexei Myasnikov, Stevens Institute of Technology, Hoboken, NJ, Vladimir Shpilrain, City College of New York, New York, NY and Alexander Ushakov, Stevens Institute of Technology, Hoboken, NJ

Publication: Mathematical Surveys and Monographs
Publication Year: 2011; Volume 177
ISBNs: 978-0-8218-5360-3 (print); 978-1-4704-1404-7 (online)
DOI: https://doi.org/10.1090/surv/177
MathSciNet review: 2850384
MSC: Primary 68-02; Secondary 11T71, 20F10, 68P25, 68Q25, 94-02, 94A60, 94A62

View full volume as PDF

Read more about this volume

Table of Contents

Download chapters as PDF

Front/Back Matter

• View this volume's front and back matter

Chapters

• Introduction

Part 1. Background on groups, complexity, and cryptography

• 1. Background on public key cryptography
• 2. Background on combinatorial group theory
• 3. Background on computational complexity

Part 2. Non-commutative cryptography

• 4. Canonical non-commutative cryptography
• 5. Platform groups
• 6. More protocols
• 7. Using decision problems in public key cryptography
• 8. Authentication

Part 3. Generic complexity and cryptanalysis

• 9. Distributional problems and the average case complexity
• 10. Generic case complexity
• 11. Generic complexity of NP-complete problems
• 12. Generic complexity of undecidable problems
• 13. Strongly, super, and absolutely undecidable problems

Part 4. Asymptotically dominant properties and cryptanalysis

• 14. Asymptotically dominant properties
• 15. Length based and quotient attacks

Part 5. Word and conjugacy search problems in groups

• 16. Word search problem
• 17. Conjugacy search problem

Part 6. Word problem in some special classes of groups

• 18. Free solvable groups
• 19. Compressed words
• Appendix A. Probabilistic group-based cryptanalysis