You are here

Group-based Cryptography

Alexei Myasnikov, Vladimir Shpilrain, and Alexander Ushakov
Publication Date: 
Number of Pages: 
Advanced Courses in Mathematics CRM Barcelona
[Reviewed by
Darren Glass
, on

As most mathematicians probably know, the most common form of encryption used today is RSA encryption, a scheme whose security is based primarily on the idea that factoring large numbers is hard. However there are many other encryption schemes which come out of different areas of mathematics; in fact, one philosophy of cryptographers is that any mathematical operation which is ‘easy’ to do but ‘hard’ to undo can be turned into a method of encryption. One fruitful source of such operations is the field of combinatorial group theory, so it is not surprising that much recent work in cryptography has come from this direction. In 2007, a workshop on Group Based Cryptography was held at the Centre de Recerca Matemàtica in Barcelona, and the notes from these lectures have now been gathered and published by Birkhäuser Basel.

The lectures are divided into three different areas of mathematics which play off one another: combinatorial group theory, cryptography, and complexity theory. The first section of the book serves as an introduction to questions in combinatorial group theory which can be used to develop cryptographic protocols. An example of such a question is the conjugacy decision problem: given two elements x and y of a group G, is there a third element z so that y = zxz–1 or not and, if you know the elements are conjugate, can you find the conjugating element z? The authors go on to look at potential groups G that one might want to use as platforms for these cryptographic protocols by defining a number of characteristics that one would like from a group in order for the protocol to be easy to use but hard to break and then looking at whether a number of groups such as braid groups, matrix groups, and small cancelation groups satisfy these criteria.

The book also dedicates several chapters to complexity theory, making precise the notions of ‘easy’ and ‘hard.’ In particular, they spend time discussing the difference between worst case complexity, in which one wants to consider how difficult a problem could be depending on how unlucky (or lucky, depending on your point of view) the solver gets in making certain choices of inputs, and generic case complexity, in which one wants to consider how difficult a problem will most likely be. The latter notion is more subtle, especially when one is working with the infinite groups that cryptographic problems often demand, and it is harder to prove theorems, yet the authors do a good job of explaining much of what is known in the area.

As a collection of lecture notes by different authors, the book is not always as polished as one might like. There are some inconsistencies in the notation as well as the assumed prerequisites, and other topics are covered multiple times. However, the book manages to start at a fairly elementary level and work through a number of fascinating topics in mathematics. Anyone who has an interest in either cryptography, group theory, or complexity theory could pick up this book and learn about the other areas and the exciting mathematical questions which lie at their boundaries.

Darren Glass is an Assistant Professor of Mathematics at Gettysburg College whose research interests include Number Theory, Algebraic Geometry, and Cryptography. He can be reached at