Group-based Cryptography

Authors: Alexei Myasnikov, Alexander Ushakov, Vladimir Shpilrain

Publisher: Birkhäuser Basel

Book Series : Advanced Courses in Mathematics - CRM Barcelona

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Table of Contents

Frontmatter

Background on Groups, Complexity, and Cryptography

Frontmatter

Chapter 1. Background on Public Key Cryptography

Abstract

In this chapter we describe, very briefly, some classical concepts and cryptographic primitives that were the inspiration behind new, “non-commutative”, primitives discussed in our Chapter 4. It is not our goal here to give a comprehensive survey of all or even of the most popular public key cryptographic primitives in use today, but just of those relevant to the main theme of our book, which is using non-commutative groups in cryptography. In particular, we leave out RSA, the most common public key cryptosystem in use today, because its mechanism is based on Euler’s generalization of Fermat’s little theorem, an elementary fact from number theory that does not yet seem to have any analogs in non-commutative group theory.

Chapter 2. Background on Combinatorial Group Theory

Abstract

In this chapter, we first give the definition of a free group, and then give a brief exposition of several classical techniques in combinatorial group theory, namely methods of Nielsen, Schreier, Whitehead, and Tietze. We do not go into details here because there are two very well-established monographs where a complete exposition of these techniques is given. For an exposition of Nielsen’s and Schreier’s methods, we recommend [96], whereas [95] has, in our opinion, a better exposition of Whitehead’s and Tietze’s methods.

Chapter 3. Background on Computational Complexity

Abstract

In all instances, if not said otherwise, we use Turing machines as our principal model of computation. In this section we briefly recall some basic definitions and notation concerning Turing machines that are used throughout this chapter.

Non-commutative Cryptography

Frontmatter

Chapter 4. Canonical Non-commutative Cryptography

Abstract

In this chapter, we discuss various cryptographic primitives that use non-commutative (semi)groups as platforms, but at the same time do not depart from the canonical paradigm of a public-key protocol based on a one-way function. We include here the ground-breaking Anshel-Anshel-Goldfeld protocol [1] as well as protocols that are closer in spirit to classical protocols based on commutative (semi)groups.

Chapter 5. Platform Groups

Abstract

In Section 4.1, we have outlined some of the requirements on the platform group in a protocol based on the conjugacy search problem. Most of these requirements apply, in fact, to platform groups in any “canonical” (i.e., based on a one-way function) cryptographic protocol, so we summarize these general requirements here.

Chapter 6. Using Decision Problems in Public Key Cryptography

Abstract

In this chapter, we suggest using decision problems from combinatorial group theory as the core of a public key establishment protocol or a public key cryptosystem. Decision problems are problems of the following nature: given a property \( \mathcal{P} \) and and object \( \mathcal{O} \), find out whether or not the object \( \mathcal{O} \) has the property \( \mathcal{P} \). Decision problems may allow us to address (to some extent) the following challenge of public key cryptography: to design a cryptosystem that would be secure against (at least, some) “brute force” attacks by an adversary with essentially unlimited computational capabilities.

Generic Complexity and Cryptanalysis

Frontmatter

Chapter 7. Distributional Problems and the Average-Case Complexity

Abstract

One of the aims of the section is to set up a framework that would allow one to analyze behavior of algorithms at large, to study expected or average properties of algorithms, or its behavior on “most” inputs. The key point here is to equip algorithmic problems with probability distributions on their sets of instances.

Chapter 8. Generic Case Complexity

Abstract

In this section we discuss a general notion of generic complexity of algorithms and algorithmic problems. Our exposition here is along the lines of [48].

Chapter 9. Generic Complexity of NP-complete Problems

Abstract

In this chapter, following [48], we show that the NP-complete problems Subset Sum and 3-Sat have low generic complexity. As it is well known that these problems are easy most of the time, these results confirm our expectations. The difficult instances are rare: we discuss them, too.

Asymptotically Dominant Properties and Cryptanalysis

Frontmatter

Chapter 10. Asymptotically Dominant Properties

Abstract

In this chapter we develop some tools to study asymptotic properties of subgroups of groups. Throughout this chapter, by G we denote a group with a finite generating set X.

Chapter 11. Length-Based and Quotient Attacks

Abstract

Our exposition in this chater essentially follows [106].

Backmatter

Title: Group-based Cryptography
Authors: Alexei Myasnikov
Alexander Ushakov
Vladimir Shpilrain
Publisher: Birkhäuser Basel
Electronic ISBN: 978-3-7643-8827-0
Print ISBN: 978-3-7643-8826-3
DOI: https://doi.org/10.1007/978-3-7643-8827-0