Hardcover ISBN:  9780821853603 
Product Code:  SURV/177 
List Price:  $117.00 
MAA Member Price:  $105.30 
AMS Member Price:  $93.60 
Electronic ISBN:  9781470414047 
Product Code:  SURV/177.E 
List Price:  $110.00 
MAA Member Price:  $99.00 
AMS Member Price:  $88.00 

Book DetailsMathematical Surveys and MonographsVolume: 177; 2011; 385 ppMSC: Primary 94; 20; 68; 11;
This book is about relations between three different areas of mathematics and theoretical computer science: combinatorial group theory, cryptography, and complexity theory. It explores how noncommutative (infinite) groups, which are typically studied in combinatorial group theory, can be used in publickey cryptography. It also shows that there is remarkable feedback from cryptography to combinatorial group theory because some of the problems motivated by cryptography appear to be new to group theory, and they open many interesting research avenues within group theory.
In particular, a lot of emphasis in the book is put on studying search problems, as compared to decision problems traditionally studied in combinatorial group theory. Then, complexity theory, notably genericcase complexity of algorithms, is employed for cryptanalysis of various cryptographic protocols based on infinite groups, and the ideas and machinery from the theory of genericcase complexity are used to study asymptotically dominant properties of some infinite groups that have been applied in publickey cryptography so far.
This book also describes new interesting developments in the algorithmic theory of solvable groups and another spectacular new development related to complexity of grouptheoretic problems, which is based on the ideas of compressed words and straightline programs coming from computer science.ReadershipGraduate students and research mathematicians interested in the relations between group theory, cryptography, and complexity theory.

Table of Contents

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. Noncommutative cryptography

4. Canonical noncommutative 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 NPcomplete 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 groupbased cryptanalysis


Additional Material

Reviews

The world of cryptography is evolving; new improvements constantly open new opportunities in publickey cryptography. Cryptography inspires new grouptheoretic problems and leads to important new ideas. The book includes exciting new improvements in the algorithmic theory of solvable groups. Another exceptional new development is the authors' analysis of the complexity of grouptheoretic problems.
MAA Reviews


Request Review Copy

Get Permissions
 Book Details
 Table of Contents
 Additional Material
 Reviews

 Request Review Copy
 Get Permissions
This book is about relations between three different areas of mathematics and theoretical computer science: combinatorial group theory, cryptography, and complexity theory. It explores how noncommutative (infinite) groups, which are typically studied in combinatorial group theory, can be used in publickey cryptography. It also shows that there is remarkable feedback from cryptography to combinatorial group theory because some of the problems motivated by cryptography appear to be new to group theory, and they open many interesting research avenues within group theory.
In particular, a lot of emphasis in the book is put on studying search problems, as compared to decision problems traditionally studied in combinatorial group theory. Then, complexity theory, notably genericcase complexity of algorithms, is employed for cryptanalysis of various cryptographic protocols based on infinite groups, and the ideas and machinery from the theory of genericcase complexity are used to study asymptotically dominant properties of some infinite groups that have been applied in publickey cryptography so far.
This book also describes new interesting developments in the algorithmic theory of solvable groups and another spectacular new development related to complexity of grouptheoretic problems, which is based on the ideas of compressed words and straightline programs coming from computer science.
Graduate students and research mathematicians interested in the relations between group theory, cryptography, and complexity theory.

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. Noncommutative cryptography

4. Canonical noncommutative 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 NPcomplete 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 groupbased cryptanalysis

The world of cryptography is evolving; new improvements constantly open new opportunities in publickey cryptography. Cryptography inspires new grouptheoretic problems and leads to important new ideas. The book includes exciting new improvements in the algorithmic theory of solvable groups. Another exceptional new development is the authors' analysis of the complexity of grouptheoretic problems.
MAA Reviews