Noncommutative cryptography and complexity of grouptheoretic problems
 Author/Creator
 Myasnikov, Alexei G., 1955
 Language
 English.
 Imprint
 Providence, R.I. : American Mathematical Society, c2011.
 Physical description
 xiv, 385 p. : ill. ; 26 cm.
 Series
 Mathematical surveys and monographs ; no. 177.
Access
Available online

Stacks

Unknown
QA3 .A4 V.177

Unknown
QA3 .A4 V.177
More options
Contributors
Contents/Summary
 Bibliography
 Includes bibliographical references and index.
 Publisher's Summary
 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 public key 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 public key 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.
(source: Nielsen Book Data)
Subjects
 Subject
 Combinatorial group theory.
 Cryptography.
 Computer algorithms.
 Number theory.
 Information and communication, circuits  Communication, information  Cryptography.
 Group theory and generalizations  Special aspects of infinite or finite groups  Word problems, other decision problems, connections with logic and automata.
 Computer science  Theory of computing  Analysis of algorithms and problem complexity.
 Information and communication, circuits  Communication, information  Authentication and secret sharing.
 Number theory  Finite fields and commutative rings (numbertheoretic aspects)  Algebraic coding theory; cryptography.
Bibliographic information
 Publication date
 2011
 Responsibility
 Alexei Myasnikov, Vladimir Shpilrain, Alexander Ushakov ; with an appendix by Natalia Mosina.
 Series
 Mathematical surveys and monographs ; v. 177
 ISBN
 0821853600
 9780821853603