You are here

Non-commutative Cryptography and Complexity of Group-theoretic Problems

Alexei Myasnikov, Vladimir Shpilrain, and Alexander Ushakov
American Mathematical Society
Publication Date: 
Number of Pages: 
Mathematical Surveys and Monographs 177
[Reviewed by
Nicolae S. Constantinescu
, on

First study science and then follow
the practice born of that science.
Leonardo Da Vinci (1452–1519)

Cryptography has been studied intensely by mathematicians, who have covered many aspects of the subject. Nevertheless, Non-commutative Cryptography and Complexity of Group-Theoretic Problems manages to offer a new perspective on how non-commutative groups can be used in public-key cryptography and how group theory can answer various problems in cryptography. Another purpose of the book is to study developments in combinatorial and computational group theory that can play a useful role in cryptography. It represents a good example of pure and applied mathematics working together.

In what follows, I will explain the steps for secure communications and my reader can safely assume that the mathematical justification for each assertion can be found in the book. Everything is carefully developed and proved.

The book is divided into six parts containing 19 chapters. The first part provides background on public-key cryptography, combinatorial group theory and computational complexity. The first chapter focuses on the major concern of the book: public-key (asymmetric) cryptography. In public-key cryptography each user or the device taking part in the communication have a pair of keys, a public key and a private key, and a set of cryptographic operations associated with the keys. Only the particular user/device knows the private key whereas the public key is distributed to all users/devices taking part in the communication. Since the knowledge of public key does not compromise the security of the algorithms, it can be safely exchanged online.

In public key cryptography, keys and messages are expressed numerically and the operations are expressed mathematically. The private and public key of a device are related by a “one-way function.” One-way functions are mathematical functions in which the forward operation can be done easily but the reverse operation is so difficult that it is effectively impossible. The public key is calculated using the forward operation on the private key. Obtaining the private key from the public key requires the reverse operation. If the reverse operation can be done easily, then the public key algorithm for the particular key is cracked. Thus, the reverse operation should get difficult as the key size increases.

Public key algorithms work with large numbers to make the reverse operation computationally impractical and thus make the system secure. The book describes several. The Diffie-Hellman key exchange scheme is one of the best known methods of exchanging cryptographic keys. It is resistant only to passive attacks. The ElGamal cryptosystem relies on the discrete logarithm problem and is inspired by the Diffie-Hellman scheme. The most widely used public-key encryption algorithm is RSA, which is described in the book even though it has no non-commutative analogue. RSA is based on the difficulty of factoring large integers. The Rabin cryptosystem, also described, is another asymmetric cryptographic technique based on the difficulty of factorization.

The second chapter deals with algorithmic problems of group theory. In chapter three, basic definitions and notations concerning Turing machines are presented. A Turing machine can be thought of as a primitive, abstract computer. Turing's hypothesis is the widely held belief that a function is computable if and only if it can be computed by a Turing machine. This implies that Turing machines can solve any problem that a modern computer program can solve. There are problems that cannot be solved by a Turing machine (e.g., the halting problem); thus, these problems cannot be solved by a modern computer program.

In part two of the book we find methods of using the complexity of non-commutative groups in public-key cryptography. The idea is to base cryptographic schemes on search problems which are versions of the traditional decision problems of combinatorial group theory. The authors call this “canonical cryptography” and discuss it in chapter four. In chapter five we have an analysis of several groups to determine whether they can be used as platforms for cryptographic public-key protocols. Chapter six follows the same idea as chapter four, but here we have descriptions of some “non-commutative” cryptographic protocols with less impact. The groups that are used as platforms in chapter six are different from those used in chapter four.

Part three of the book contains an analysis of two measures of complexity of an algorithm, average-case and generic-case. The authors argue that one should consider generic-case complexity in the analysis of cryptographic schemes. In particular, chapter eleven shows that the NP-complete problems Subset Sum and 3-Sat have low generic complexity. The subset sum decision problem is NP-complete, but the optimization problem is routinely solved in practice and gives a solution to the decision problem. Here we can see that difficult instances of subset sum are rare; the explanation is followed by an account of a linear time algorithm which works on a generic set of inputs.

Part four deals with asymptotic properties of finitely generated subgroups of groups. It begins with the introduction of a methodology to deal with asymptotic properties of subgroups in a given finitely generated group. The focus is on one particular example, the Anshel-Goldfeld key exhange protocol. The authors give mathematical reasons behind the high success rate of length based attacks (LBA) in breaking the AAG protocol. Quotient attacks seem to be another class of powerful attacks on the AAG scheme. Quotient attacks are based on a standard group-theoretic idea: to solve a computational problem in a group G it suffices, on most inputs, to solve it in a suitable quotient G/N, provided G/N has a fast decision algorithm for the problem. Chapter fourteen provides us with tools to study asymptotic properties of subgroups of groups and discussions about properties of subgroups of G that have an important role in the cryptanalysis of group-based cryptographic schemes.

In part five of the book the authors highlight various search problems in group theory, the word and conjugacy search problems in some specific groups and in groups given by random finite presentations. The first chapter of part five contains a study of the generic properties of van Kampen diagrams over finitely presented groups. For these groups a new generically fast algorithm is proposed for the word search problem. They also obtain positive results regarding the conjugacy problem in groups: the generic-case complexity of the conjugacy search problem is studied and an algorithm, similar to the Todd-Coxeter algorithm for the word search problem, is presented.

Part six, “Word Problem in some Special Classes of Groups”, starts with a study of the computational complexity of other algorithmic problems related to the word problem in free solvable groups. The authors present a uniform decision algorithm for solving the word problem. Their approach to the word problem in free solvable groups is based on the Fox theorem, using binary tree search techniques and associative arrays to compute Fox’s derivative of elements w of a free solvable group. The method used by the authors has as a result a faster algorithm to compute images of elements under the Magnus embedding. The appendix “Probabilistic Group-based Cryptanalysis” has as a main goal to link probability theory and cryptanalysis, by introducing new techniques for security analysis of group-based protocols. This is a very interesting subject, treated very well by the author.

The world of cryptography is evolving; new improvements constantly open new opportunities in public-key cryptography. Cryptography inspires new group-theoretic problems and leads to important new ideas. The book includes exciting improvements in the algorithmic theory of solvable groups. Another exceptional new development is the authors’ analysis of the complexity of group-theoretic problems.

Nicolae S. Constantinescu ( is Associate Professor at University of Craiova and holds a research fellowship at University Paris Orsay, France. He has written more than 50 papers in domain of Applied Mathematics in Information Security. His current interests are in elliptic curves and cryptographic applications.