# 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: http://dx.doi.org/10.1090/surv/177

MathSciNet review: 2850384

MSC: Primary 68-02; Secondary 11T71, 20F10, 68P25, 68Q25, 94-02, 94A60, 94A62

### Table of Contents

**Front/Back Matter**

**Chapters**

**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 **

**Part 5. Word and conjugacy search problems in groups **

**Part 6. Word problem in some special classes of groups **

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