Group-based cryptography (Q925085): Difference between revisions

Since about 35 years, asymmetric encryption has been a famous and still growing issue of research and application as well. Modern life would not work as it does without this. And from the very beginning it was coupled with group-theoretical problems. The book at hand has the aim to introduce the reader into the rich world of group-based asymmetric encryption. Although the very prominent older representants like RSA still dominate the applications, it may come the point were it would be not any longer secure enough. Other, even more secure encryptions might become necessary. Group theory delivers many interesting starting points for developing new methods, and it is interesting to see how a mathematical subject which seemed to be very abstract in former times now becomes more and more applied mathematics. It is well known that for asymmetric encryption one needs a mathematical construction which is rather simple to compute but whose inverse problem is very hard. Taking this into account, the marriage of group theory and cryptography might be not so surprising -- in group theory one can find several such problems, and those problems are presented by the authors in a very systematic manner. The basics necessary for the understanding are given in introducing chapters. Many hints for further reading are given. So, the book might be useful for the beginner, who wants to get a clear introduction, as well as for the expert, who gets an elaborate survey as well as much stimulation for proceeding research. The book is divided into four parts. The first one gives the background with respect to group theory as well as computational complexity, and cryptography. Relevant topics in group theory are, e.g., the word search problem, the conjugacy search problem, and the factorization search problem. Conjugating an element is easy, finding the element which conjugates a given element in another given element is difficult; multiplying two elements is simple, finding the decomposition of a given element into two factors is difficult. In the background chapter on computational complexity, deterministic, nondeterministic, and probabilistic Turing machines are introduced as well as the respective complexity classes. The second part deals with non-commutative cryptography. For example, cryptographic protocols basing on the conjugacy search problem belong to this class as well as many other interesting issues described here. The authors also demonstrate possible attacks against such protocols using linear algebra, and possible improvements to avoid them. While these protocols are described in general at first, another chapter of the second part deals with the platform groups which are more or less good candidates for the general introduced protocols. It is pointed out that the security of a protocol may depend on the platform group which is used. Investigated platform groups are, amongst others, braid groups, Thompson's group, groups of matrices over finite commutative rings, and solvable groups. The third part discusses generic complexity and its relation to cryptanalysis. Tools to analyze the behavior of algorithms are presented and the average-case complexity is discussed in detail as well as the generic complexity. Moreover, the generic complexity of NP-complete problems is investigated. The last part of the book deals with asymptotically dominant properties and cryptanalysis. After an introduction into the matter, including random subgroups and generating tuples, the relevance for cryptanalysis is explained. Length-based and quotient attacks and their conclusions for secure protocols are described in detail.