Abstract
We introduce the linear centralizer method, and use it to devise a provable polynomial-time solution of the Commutator Key Exchange Problem, the computational problem on which, in the passive adversary model, the security of the Anshel–Anshel–Goldfeld (Anshel et al., Math. Res. Lett. 6:287–291, 1999) Commutator key exchange protocol is based. We also apply this method to solve, in polynomial time, the computational problem underlying the Centralizer key exchange protocol, introduced by Shpilrain and Ushakov in (Contemp. Math. 418:161–167, 2006).
This is the first provable polynomial-time cryptanalysis of the Commutator key exchange protocol, hitherto the most important key exchange protocol in the realm of noncommutative algebraic cryptography, and the first cryptanalysis (of any kind) of the Centralizer key exchange protocol. Unlike earlier cryptanalyses of the Commutator key exchange protocol, our cryptanalyses cannot be foiled by changing the distributions used in the protocol.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Since Diffie and Hellman’s 1976 key exchange protocol, few alternative proposals for key exchange protocols (KEPs) resisted cryptanalysis. This, together with the (presently, theoretical) issue that the Diffie–Hellman and other classic KEPs can be broken in polynomial time by quantum computers, is a strong motivation for searching for substantially different KEPs. Lattice-based KEPs [31] seem to be a viable potential alternative. All classic KEPs as well as the Lattice-based ones are based on commutative algebraic structures.
In 1999, Anshel, Anshel, and Goldfeld [2] (cf. [3]) introduced the Commutator KEP, a general method for constructing KEPs based on noncommutative algebraic structures. Around the same time, Ko, Lee, Cheon, Han, Kang, and Park [21] introduced the Braid Diffie–Hellman KEP, another general method achieving the same goal. The security of both KEPs is based on variations of the Conjugacy Search Problem: Given conjugate elements g,h in a noncommutative group, find x in that group such that x −1 gx=h. Both papers [2] and [21] proposed to use the braid group B N , a finitely presented, infinite noncommutative group parameterized by a natural number N, as the platform group.
The introduction of the Commutator KEP and the Braid Diffie–Hellman KEP was followed by a stream of heuristic attacks (e.g., [11–13, 15–18, 24–27, 29, 30]),Footnote 1 demonstrating that these protocols, when using the two most simple distributions on the braid group B N , are insecure. Consequently, a program was set forth, by several independent research groups, to find efficiently samplable distributions on the braid group that, when used with the above-mentioned protocols, foil all heuristic attacks (e.g., [1, 14, 22, 25]). The abstract of [14] concludes: “Proper choice … produces a key exchange scheme which is resistant to all known attacks”. Moreover, a very practical distribution is announced in [37], which foils the strongest known methods for solving the Conjugacy Search Problem in B N .
Most of the mentioned heuristic attacks address the Commutator KEP, and not the Braid Diffie–Hellman KEP. The reason is that in 2003, Cheon and Jun published an expected polynomial-time cryptanalysis of the Braid Diffie–Hellman KEP, using a novel representation theoretic method [8]. In their paper, Cheon and Jun stress that their cryptanalysis does not apply to the Commutator KEP and that an extra ingredient is needed. Thus far, no expected polynomial-time attack was found on the Commutator KEP, whose success does not depend on the distributions used in the protocols.
The main result of the present paper is a Las Vegas, provable expected polynomial-time solution of the Commutator Key Exchange Problem (also referred to as the Anshel–Anshel–Goldfeld Problem [28, §15.1.2]), the computational problem underlying the Commutator KEP. This forms a cryptanalysis of the Commutator KEP [2], in the passive adversary model, which succeeds regardless of the distributions used to generate the keys.
The linear centralizer method, developed for our solution of the Commutator Key Exchange Problem, is applicable to additional computational problems and KEPs in the context of group theory-based cryptography. We present an application of these methods to the Centralizer KEP, introduced by Shpilrain and Ushakov in 2006 [35], to obtain an expected polynomial-time attack. This is the first cryptanalysis, of any kind, of the Centralizer KEP.
We stress that the cryptanalyses presented here, like the Cheon–Jun cryptanalysis, while of expected polynomial time, are impractical for standard values of N (e.g., N=100). These results are of theoretic nature. Ignoring logarithmic factors, the complexity of our cryptanalyses is about N 17, times a cubic polynomial in the other relevant parameters. Incidentally, though, these cryptanalyses establish the first provable practical attacks in the case where the index N of the braid group B N is small, e.g., when N=8.
The paper is organized as follows. Section 2 introduces the Commutator KEP and the braid group. In Sect. 3, we eliminate a technical complexity theoretic obstacle. Section 4 applies a method of Cheon and Jun to reduce our problem to matrix groups over finite fields. Section 5 is the main ingredient of our cryptanalysis, presenting the new method and cryptanalyzing the Commutator KEP in matrix groups. This section is independent of the other sections and readers without prior knowledge of the braid group may wish to read it first. Section 6 fills a gap in our proof, by applying the Schwartz–Zippel Lemma to obtain a lower bound on the probability that certain random matrices are invertible. Section 7 is a cryptanalysis of the Centralizer KEP, using the methods introduced in the earlier sections. The Braid Diffie–Hellman KEP is introduced in Sect. 8, where we survey the Cheon–Jun cryptanalysis and explain why it does not apply to the Commutator KEP or to the Centralizer KEP. We also describe applications of the new methods to a generalized version of the Braid Diffie–Hellman KEP and to Stickel’s KEP. Some additional discussion is provided in Sect. 9.
2 The Commutator KEP and the Braid Group B N
We will use, throughout, the following basic notation.
Notation 1
For a noncommutative group G and group elements g,x∈G, g x=x −1 gx, the conjugate of g by x.
Useful identities involving this notation that are easy to verify, include g xy=(g x)y, and g c=g for every central element c∈G, that is, such that ch=hc for all h∈G.
The Commutator KEP [2] is described succinctly in Fig. 1.Footnote 2 In some detail:
-
1.
A noncommutative group G and elements a 1,…,a k ,b 1,…,b k ∈G are publicly given.Footnote 3
-
2.
Alice and Bob choose free group words in the variables x 1,…,x k , v(x 1,…,x k ) and w(x 1,…,x k ), respectively.Footnote 4
-
3.
Alice substitutes a 1,…,a k for x 1,…,x k , to obtain a secret element a=v(a 1,…,a k )∈G. Similarly, Bob computes b=w(b 1,…,b k )∈G.
-
4.
Alice sends the conjugated elements b 1 a,…,b k a to Bob, and Bob sends a 1 b,…,a k b to Alice.
-
5.
The shared key is the commutator a −1 b −1 ab.
As conjugation is a group isomorphism, we have
Thus, Alice can compute the shared key a −1 b −1 ab as a −1 v(a 1 b,…,a k b), using her secret a,v(x 1,…,x k ) and the public elements a 1 b,…,a k b. Similarly, Bob computes a −1 b −1 ab as w(b 1 a,…,b k a)−1 b.
For the platform group G, it is proposed in [2] to use the braid group B N , a group parameterized by a natural number N. Elements of B N are called braids, for they may be identified with braids on N strands. Braid group multiplication is motivated geometrically, but the details will play no role in the present paper. The interested reader will find detailed information on B N in almost each of the papers in the bibliography and, in particular, in the survey [6], but prior knowledge is not necessary: we quote here the information needed for the present paper.
Let S N be the symmetric group of permutations on N symbols. For our purposes, the braid group B N is a group of elements of the form
where i is an integer, and p is a finite (possibly, empty) sequence of elements of S N , that is, p=(p 1,…,p ℓ ) for some ℓ≥0 and p 1,…,p ℓ ∈S N . The sequence p=(p 1,…,p ℓ ) is requested to be left weighted (a property whose definition will not be used here), and p 1 must not be the involution p(k)=N−k+1.Footnote 5
For “generic” braids (i,(p 1,…,p ℓ ))∈B N , i is negative and |i| is O(ℓ), but this is not always the case. Note that the bit-length of an element (i,(p 1,…,p ℓ ))∈B N is O(log|i|+ℓNlogN).
Multiplication is defined on B N by an algorithm of complexity O(ℓ 2 NlogN+log|i|). Inversion is of linear complexity. Explicit implementations are provided, for example, in [7].
For a passive adversary to extract the shared key of the Commutator KEP out of the public information, it suffices to solve the following problem, also referred to as the Anshel–Anshel–Goldfeld Problem [28, §15.1.2].
Problem 2
(Commutator KEP Problem)
Let a 1,…,a k ,b 1,…,b k ∈B N , each of the form (i,p) with p of length ≤ℓ. Let a be a product of at most m elements of {a 1,…,a k }±1, and let b be a product of at most m elements of {b 1,…,b k }±1.
Given \(a_{1},\dots,a_{k},b_{1},\dots,b_{k},a_{1}^{b},\dots,a_{k}^{b},b_{1}^{a},\dots ,b_{k}^{a}\), compute a −1 b −1 ab.
Our solution of Problem 2 consists of several ingredients.
3 Reducing the Infimum
The infimum of a braid b=(i,p) is the integer inf(b):=i. As the bit-length of b is O(log|i|+ℓNlogN), an algorithm polynomial in |i| would be at least exponential in the bit-length. We first remove this obstacle.
In cases where p is the empty sequence, we write (i) instead of (i,p). The properties of B N include, among others, the following ones.
-
(a)
(i)⋅(j,p)=(i+j,p) for all integers i and all (j,p)∈B N .
In particular, (i)=(1)i for all i.
-
(b)
(2)⋅(i,p)=(i,p)⋅(2) for all for all (i,p)∈B N .
Thus, (2j) is a central element of B N for each integer j. If follows that, for each (i,p)∈B N ,
This way, every braid b∈B N decomposes to a unique product \(c\tilde{b}\), where c is of the form (2j) (and thus central), and \(\inf(\tilde{b})\in\{0,1\}\).
Consider the public information in Fig. 1. For each j=1,…,k, decompose as above
with c j ,d j central and \(\inf(\tilde{a}_{j}),\inf(\tilde{b}_{j})\in\{ 0,1\}\) for all j=1,…,k. Let
As the elements c j ,d j are central, we have
Similarly, \(\tilde{b}=d^{-1}b\). As c and d are central,
for all j=1,…,k. Thus, \(\tilde{a}_{j}^{\tilde{b}}\) can be computed for all j. Similarly, \(\tilde{b}_{j}^{\, \tilde{a}}\) can be computed. Now,
This shows that the Commutator KEP Problem is reducible, in linear time, to the same problem using \(\tilde{a}_{1},\dots,\tilde{a}_{k},\tilde{b}_{1},\dots,\tilde{b}_{k}\) instead of a 1,…,a k ,b 1,…,b k . Thus, we may assume that
to start with. Assume that henceforth.
For a braid x=(i,p), let ℓ(p) be the number of permutations in the sequence p. For integers i,s, let
We use the following basic facts about B N :
-
1.
If x 1∈[i 1,s 1] and x 2∈[i 2,s 2], then x 1 x 2∈[i 1+i 2,s 1+s 2].
-
2.
If x∈[i,s], then x −1∈[−s,−i].
Thus, for each x∈{a 1,…,a k ,b 1,…,b k }±1, x ±1∈[−ℓ−1,ℓ+1], and therefore, in the notation of our problem, a,b∈[−m(ℓ+1),m(ℓ+1)]. Thus,
Corollary 3
In the Commutator KEP Problem, a −1 b −1 ab∈[−4m(ℓ+1),4m(ℓ+1)].
4 Reducing to a Matrix Group over a Finite Field
In this section, we apply methods of Cheon and Jun [8] in our setting.
Let n be a natural number. As usual, we denote the algebra of all n×n matrices over a field \(\mathbb{F}\) by \(\operatorname {M}_{n}(\mathbb{F})\), and the group of invertible elements of this algebra by \(\operatorname {GL}_{n}(\mathbb{F})\). A matrix group is a subgroup of \(\operatorname{GL}_{n}(\mathbb{F})\). A faithful representation of a group G in \(\operatorname {GL}_{n}(\mathbb{F})\) is a group isomorphism from G onto a matrix group \(H\le\operatorname{GL}_{n}(\mathbb{F})\). A group is linear if it has a faithful representation.
Bigelow and, independently, Krammer, established in their breakthrough papers [5, 23] that the braid group B N is linear, by proving that the so-called Lawrence–Krammer representation
whose dimension is
is injective.Footnote 6 The Lawrence–Krammer representation of a braid can be computed in polynomial time.Footnote 7 It is proved implicitly in [23], and explicitly in [8], that this representation is also invertible in (similar) polynomial time. The following result follows from Corollary 1 of [8].
Theorem 4
(Cheon–Jun [8])
Let x∈[i,s] in B N . Let M≥max(|i|,|s|). Then:
-
1.
The degrees of t in \(\operatorname{LK}(x)\in\operatorname {GL}_{n}(\mathbb{Z}[t^{\pm1},\frac {1}{2}])\) are in {−M,−M+1,…,M}.
-
2.
The rational coefficients \(\frac{c}{2^{d}}\) in \(\operatorname {LK}(x)\) (c integer, d nonnegative integer) satisfy \(|c|\le2^{N^{2}M}, |d|\le2NM\).
In the notation of Theorem 4, Theorem 2 in Cheon–Jun [8] implies that inversion of \(\operatorname{LK}(x)\) is of order N 6logM multiplications of entries. Ignoring logarithmic factors and thus assuming that each entry multiplication costs NM⋅N 2 M=N 3 M 2, this accumulates to N 8 M 2. We will invert the function \(\operatorname{LK}\) as part of our cryptanalysis below. However, the complexity of the other steps in our cryptanalysis (in particular, the linear centralizer step—Sect. 5) dominate the complexity of inverting \(\operatorname{LK}\).
Let us return to the Commutator KEP Problem 2. By Corollary 3,
Let M=4m(ℓ+1). By Theorem 4, we have
the absolute values of the coefficients in this matrix are bounded by \(2^{N^{2}(M+1)}\), and the maximal degree of t in this matrix is bounded by 2M.
Let p be a prime slightly greater than \(2^{N^{2}M}\), and f(t) be an irreducible polynomial over \(\mathbb{Z}_{p}\), of degree d slightly larger than 2M. Then
under the natural identification of {−(p−1)/2,…,(p−1)/2} with {0,…,p−1}.
Let \(\mathbb{F}=\mathbb{Z}[t]/\langle p, f(t)\rangle= \mathbb {Z}[t^{\pm1},\frac {1}{2}]/\langle p, f(t)\rangle\). \(\mathbb{F}\) is a finite field of cardinality p d, where d is the degree of f(t). It follows that the complexity of field operations in \(\mathbb{F}\) is, up to logarithmic factors, of order
Thus, the key K can be recovered as follows:
-
1.
Apply the composed function \(\operatorname{LK}(x) \bmod(p, f(t))\) to the input of the Commutator KEP Problem, to obtain a version of this problem in \(\operatorname{GL}_{n}(\mathbb{F})\).
-
2.
Solve the problem there, to obtain \(\operatorname{LK}(K) \bmod (p, f(t))\).
-
3.
Compute \((2^{2NM}t^{M})\cdot\operatorname{LK}(K) \bmod(p, f(t)) = (2^{2NM}t^{M})\cdot\operatorname{LK}(K)\).Footnote 8
-
4.
Divide by (22NM t M) to obtain \(\operatorname{LK}(K)\).
-
5.
Compute K using the Cheon–Jun inversion algorithm.
It remains to devise a polynomial-time solution of the Commutator KEP Problem in arbitrary groups of matrices.
5 Linear Centralizers
In this section, we solve the Commutator KEP Problem in matrix groups. We first state the problem in a general form. As usual, for a group G and elements g 1,…,g k ∈G, 〈g 1,…,g k 〉 denotes the subgroup of G generated by g 1,…,g k . Throughout, we assume that the given groups are represented in an efficient way.
Problem 5
(Commutator KEP Problem)
Let G be a group. Let a 1,…,a k ,b 1,…,b k ∈G. Let a∈〈a 1,…,a k 〉,b∈〈b 1,…,b k 〉.
Given \(a_{1},\dots,a_{k},b_{1},\dots,b_{k},a_{1}^{b},\dots,a_{k}^{b},b_{1}^{a},\dots ,b_{k}^{a}\), compute a −1 b −1 ab.
We recall a classic definition.
Definition 6
Let \(S\subseteq\operatorname{M}_{n}(\mathbb{F})\) be a set. The centralizer of S (in \(\operatorname{M}_{n}(\mathbb{F})\)) is the set
For \(a_{1},\dots,a_{k}\in\operatorname{M}_{n}(\mathbb{F})\), C({a 1,…,a k }) is also denoted as C(a 1,…,a k ).
Basic properties of C(S) that are easy to verify, include:
-
1.
C(S) is a vector subspace (indeed, a matrix subalgebra) of \(\operatorname{M} _{n}(\mathbb{F})\).
-
2.
C(C(S))⊇S.
-
3.
\(C(S)=C(\operatorname{span}S)\).
-
4.
If \(S\subseteq\operatorname{GL}_{n}(\mathbb{F})\), then C(S)=C(〈S〉), where 〈S〉 is the subgroup of \(\operatorname{GL}_{n}(\mathbb {F})\) generated by S.
A key observation is the following one: Let V be a vector subspace of \(\operatorname{M}_{n}(\mathbb{F})\), and \(G\le\operatorname{GL}_{n}(\mathbb{F})\) be a matrix group such that V∩G is nonempty. It may be computationally infeasible to find an element in V∩G. However, it is easy to compute a basis for V∩U for any vector subspace U of \(\operatorname{M}_{n}(\mathbb{F})\). In particular, this is true for U=C(C(G)), which contains G. In certain cases, as the ones below, a “random” element in V∩C(C(G)) is as good as one in V∩G.
Algorithm 7 below addresses the Commutator KEP Problem in a matrix group \(G\le\operatorname{GL}_{n}(\mathbb{F})\). The analysis of this algorithm is based on the forthcoming Lemma 9, which shows that one can efficiently find an invertible matrix in a vector space of matrices containing at least one invertible matrix. To this end, we assume that \(|\mathbb{F}|/n\ge c>1\) for some constant c. In the above section, \(|\mathbb{F}|/n\) is at least exponential. Fix a finite set \(S\subseteq\mathbb{F}\) of cardinality greater than cn (the larger the better) that can be sampled efficiently. In the most important case, where \(\mathbb{F}\) is a finite field, take \(S=\mathbb{F}\). By random element of a vector subspace V of \(\operatorname {M}_{n}(\mathbb{F})\), with a prescribed basis {v 1,…,v d }, we mean a linear combination
with α 1,…,α k ∈S uniform, independently distributed.
It is natural to split the Commutator KEP Problem and the algorithm for solving it into an offline (preprocessing) phase and an online phase.
Algorithm 7
Offline phase:
-
1.
Input: b 1,…,b k ∈G.
-
2.
Execution:
-
(a)
Compute a basis S={s 1,…,s d } for C(b 1,…,b k ), by solving the following homogeneous system of linear equations in the n 2 entries of the unknown matrix x:
$$\begin{array}{rcl} b_1\cdot x & = & x\cdot b_1, \\ & \vdots\\ b_k\cdot x & = & x\cdot b_k. \end{array} $$ -
(b)
Compute a basis for C(S)=C(C(b 1,…,b k )), by solving the following homogeneous system of linear equations in the n 2 entries of the unknown matrix x:
$$\begin{array}{rcl} s_1\cdot x & = & x\cdot s_1, \\ & \vdots\\ s_d\cdot x & = & x\cdot s_d. \end{array} $$
-
(a)
-
3.
Output: A basis for C(C(b 1,…,b k )).
Online phase:
-
1.
Input: \(a_{1},\dots,a_{k},b_{1},\dots,b_{k},a_{1}^{b},\dots ,a_{k}^{b},b_{1}^{a},\dots,b_{k}^{a}\in G\), where a∈〈a 1,…,a k 〉, b∈〈b 1,…,b k 〉 are unknown.
-
2.
Execution:
-
(a)
Solve the following homogeneous system of linear equations in the n 2 entries of the unknown matrix x:
$$\begin{array}{rcl} b_1\cdot x & = & x\cdot{b_1}^{a}, \\ & \vdots\\ b_k\cdot x & = & x\cdot{b_k}^{a}. \end{array} $$ -
(b)
Fix a basis for the solution space, and pick random solutions x until x is invertible.
-
(c)
Solve the following homogeneous system of linear equations in the n 2 entries of the unknown matrix y:
$$\begin{array}{rcl} a_1\cdot y & = & y\cdot{a_1}^{b}, \\ & \vdots\\ a_k\cdot y & = & y\cdot{a_k}^{b}, \end{array} $$subject to the linear constraint that y∈C(C(b 1,…,b k )).
-
(d)
Fix a basis for the solution space, and pick random solutions y until y is invertible.
-
(e)
Output: x −1 y −1 xy.
-
(a)
Let ω be the matrix multiplication constant, that is, the minimal such that matrix multiplication is O(n ω+o(1)). For our applications, one may take ω=log27≈2.81. As usual, Las Vegas algorithm means an algorithm that always outputs the correct answer in finite time. For the proof of the following theorem, note that if g x=g y, then \(g^{xy^{-1}}=g\), or in other words, xy −1∈C(g). Finally, note that it does not make much sense to consider the case where k>n 2, in which the matrices become linearly dependent and thus redundant.
Theorem 8
Assume that \(|\mathbb{F}|/n\ge c>1\) for some constant c, and k≤n 2. Algorithm 7 is a Las Vegas algorithm for the Commutator KEP Problem, with running time, in units of field operations:
-
1.
Offline phase: O(n 2ω+2).
-
2.
Online phase: O(kn 2ω).
Proof
We use the notation of Algorithm 7. First, assume that the algorithm terminates. We prove that its output is a −1 b −1 ab.
The equations 2(a) in the online phase of Algorithm 7 assert that b i x=b i a for all i=1,…,k. Thus, xa −1∈C(b 1,…,b k ). As y∈C(C(b 1,…,b k )), y commutes with xa −1, and therefore so does y −1. Thus,
By the equations 2(c) in the online phase of Algorithm 7, a i y=a i b for all i=1,…,k. As a∈〈a 1,…,a k 〉, we have a y=a b. Indeed, let \(a=a_{i_{1}}^{\epsilon_{1}}\cdots a_{i_{m}}^{\epsilon_{m}}\). As conjugation is an isomorphism,
Thus,
Thus, the algorithm returns the correct answer when it terminates. It remains to analyze the running time of the algorithm, which we do step-by-step.
Offline phase, Step 2(a): These are kn 2 equations in n 2 variables, and thus the running time is O(k(n 2)ω)=O(kn 2ω).
Offline phase, Step 2(b): As C(b 1,…,b k ) is a vector subspace of \(\operatorname {M}_{n}(\mathbb{F})\), its dimension d is at most n 2. Thus, the running time of this step is O(n 2⋅n 2ω)=O(n 2ω+2).
Online phase, Step 2(a): The running time is O(kn 2ω), as in Step 2(a) of the offline phase.
Online phase, Step 2(b): There is an invertible solution to the equations 2(a), namely: a. Thus, by the Invertibility Lemma (Lemma 9 below), the probability that a random solution is not invertible may be assumed arbitrarily close to \(n/|\mathbb{F}|\le1/c<1\). Thus, the expected number of random elements picked until an invertible one is found is constant. To generate one random element, one takes a linear combination of a basis of the solution space. If m is the dimension, then m≤n 2 and the linear combination takes mn 2≤n 4 operations. Checking invertibility is faster. The total expected running time of this step is, therefore, O(n 4), and n 4≤n 2ω.
Online phase, Step 2(c): Let {s 1,…,s m } be the basis computed in the offline phase. Then m≤n 2. In the present step, one sets y=t 1 s 1+⋯+t m s m , with t 1,…,t m variables, and obtains kn 2 equations in the m≤n 2 variables t 1,…,t m . The complexity is \(O(\frac{kn^{2}}{m}m^{\omega})\), and \(\frac{kn^{2}}{m}m^{\omega}=kn^{2}\cdot m^{\omega-1}\le kn^{2\omega}\).
Online phase, Step 2(d): Using the same arguments as in Step 2(b), the running time of this step is O(n 2ω). □
6 Finding an Invertible Solution when There Is One
The results in the previous section assume that we are able to find, efficiently, an invertible matrix in any subspace of \(\operatorname {M}_{n}(\mathbb{F})\) containing an invertible element. This is taken care of by the following Lemma.
Lemma 9
(Invertibility Lemma)
Let \(a_{1},\dots,a_{m}\in\operatorname{M}_{n}(\mathbb{F})\) be such that
Let S be a finite subset of \(\mathbb{F}\). If α 1,…,α m are chosen uniformly and independently from S, then the probability that α 1 a 1+⋯+α m a m is invertible is at least \(1-\frac{n}{|S|}\).
Proof
Let
where t 1,…,t m are scalar variables. This is a determinant of a matrix whose coefficients are linear in the variables. By the definition of determinant as a sum of products of n elements, f is a polynomial of degree n. As \(\operatorname{span}\{a_{1},\dots,a_{m}\}\cap\operatorname {GL}_{n}(\mathbb{F})\neq\emptyset\), f is nonzero.
The proof is completed by applying the Schwartz–Zippel Lemma (Lemma below). □
For the reader’s convenience, we include a proof for the following classic lemma.
Lemma 10
(Schwartz–Zippel)
Let \(f(t_{1},\dots,t_{m})\in\mathbb{F}[t_{1},\dots,t_{m}]\) be a nonzero multivariate polynomial of degree n. Let S be a finite subset of \(\mathbb{F}\). If α 1,…,α m are chosen uniformly and independently from S, then the probability that f(α 1,…,α m )≠0 is at least \(1-\frac{n}{|S|}\).
Proof
We prove the lemma by induction on m.
If m=1, then f is a univariate polynomial of degree n, and thus has at most n roots.
For the inductive step, assume that m>1 and write
with k≤n maximal such that f k (t 2,…,t m ) is nonzero. The degree of f k (t 2,…,t k ) is at most m−k. For each choice of \(\alpha_{2},\dots,\alpha_{m}\in\mathbb{F}\) with f k (α 2,…,α m )≠0, f(t 1,α 2,…,α m ) is a univariate polynomial of degree k in the variable t 1. By the induction hypothesis (for m=1), for random α 1∈S, f(α 1,α 2,…,α m ) is nonzero with probability at least 1−k/|S|. By the induction hypothesis,
□
7 Application to the Centralizer KEP
Definition 11
For a group G and an element g∈G, the centralizer of g in G is the set
The Centralizer KEP, introduced by Shpilrain and Ushakov in 2006 [35], is described in Fig. 2. In this protocol, a 1 commutes with b 1 and a 2 commutes with b 2. Consequently, the keys computed by Alice and Bob are identical, and equal to a 1 b 1 ga 2 b 2.
As in the Commutator KEP, it is proposed in [35] to use the braid group B N as the platform group G. The group elements are chosen in a special way, so as to foil attacks attempted at earlier braid group-based KEPs. We apply the methods developed in the previous sections to obtain an expected polynomial-time cryptanalysis of this KEP. We omit some details, which are similar to those in the earlier sections.
Problem 12
(Centralizer KEP Problem)
Assume that g,a 1,b 2∈B N , \(g_{1},\dots,g_{k} \in C_{\mathbf{B}_{N}} (a_{1})\), \(h_{1},\dots,h_{k}\in C_{\mathbf{B}_{N}}(b_{2})\), each of the form (i,p) with p of length ≤ℓ. Let a 2 be a product of at most m elements of {h 1,…,h k }±1, and let b 1 be a product of at most m elements of {g 1,…,g k }±1.
Given g,g 1,…,g k ,h 1,…,h k ,a 1 ga 2,b 1 gb 2, compute a 1 b 1 ga 2 b 2.
7.1 Solving the Centralizer KEP Problem in Matrix Groups
For a group G, Z(G)=C G (G) is the set of all central elements of G. Consider the variation of the Centralizer KEP Problem 12, where the group is \(G\le\operatorname{GL}_{n}(\mathbb{F})\) instead of B N . The following variation of this problem is formally harder than this variation.Footnote 9
Problem 13
Let \(G\le\operatorname{GL}_{n}(\mathbb{F})\). Assume that g,a 1,b 2∈G, g 1,…,g k ∈C G (a 1), h 1,…,h k ∈C G (b 2), a 2∈〈{h 1,…,h k }∪Z(G)〉, and b 1∈〈{g 1,…,g k }∪Z(G)〉.
Given g,g 1,…,g k ,h 1,…,h k ,a 1 ga 2,b 1 gb 2, compute a 1 b 1 ga 2 b 2.
Following is an algorithm for solving Problem 13. As before, for \(S\subseteq\operatorname{M}_{n}(\mathbb{F})\), C(S) (without subscript) is the centralizer of S in the matrix algebra \(\operatorname {M}_{n}(\mathbb{F})\).
Algorithm 14
-
1.
Input: g,g 1,…,g k ,h 1,…,h k ,a 1 ga 2,b 1 gb 2∈G.
-
2.
Execution:
-
(a)
Compute bases for the subspaces C(g 1,…,g k ), C(C(h 1,…,h k )) of \(\operatorname{M}_{n}(\mathbb{F})\).
-
(b)
Solve
$$x\cdot g = a_1ga_2\cdot y $$subject to the linear constraints x∈C(g 1,…,g k ),y∈C(C(h 1,…,h k )).
-
(c)
Take random linear combinations of the basis of the solution space to obtain solutions (x,y), until y is invertible.
-
(a)
-
3.
Output: x⋅b 1 gb 2⋅y −1.
Theorem 15
Let \(G\le\operatorname{GL}_{n}(\mathbb{F})\). Assume that \(|\mathbb {F}|/n\ge c>1\) for some constant c, and k≤n 2. Algorithm 14 is a Las Vegas algorithm for Problem 13, with running time, in units of field operations, O(n 2ω+2).
Proof
The proof is similar to that of Theorem 8.
First, assume that the algorithm terminates. We prove that its output is a 1 b 1 ga 2 b 2. As x∈C(g 1,…,g k ) and b 1∈〈g 1,…,g k 〉, x commutes with b 1. As b 2 commutes with h 1,…,h k , b 2∈C(h 1,…,h k ). As y∈C(C(h 1,…,h k )), y commutes with b 2, and therefore so does y −1. Thus,
As xg=a 1 ga 2 y, xgy −1=a 1 ga 2. Thus,
The analysis of the running time of the algorithm is essentially identical to the analysis in Theorem 8. In Step 2(c), let
be the solution space, and let (x 1,y 1),…,(x d ,y d ) be a basis for H. As H is a subspace of \(\operatorname{M}_{n}(\mathbb{F})\times \operatorname{M}_{n}(\mathbb{F})\), d≤2n 2. Let H 2={y:(x,y)∈H}, the projection of H on the second coordinate. Then
\((a_{1},a_{2}^{-1})\in H\), and thus \(a_{2}^{-1}\in H_{2}\). In particular, there is an invertible element in H 2. By the Invertibility Lemma (Lemma 9), a random linear combination of y 1,…,y d is invertible with probability at least 1/c. The total expected running time of this step is, therefore, O(n 4), and n 4≤n 2ω. □
7.2 Solving the Centralizer KEP Problem in the Braid Group
We now address Problem 12. We begin by reducing to the case where our braids have a restricted form.
In Sect. 3, we explained how each x∈B N can be decomposed (in linear time) as \(x=c\tilde{x}\) with c central and inf(x)∈{0,1}.
We may assume that
Indeed, assume that we have an algorithm solving the problem when inf(g)∈{0,1}. Write \(g=c\tilde{g}\) with c central and inf(g)∈{0,1}. Compute
Apply the given algorithm to \(\tilde{g}, g_{1},\dots,g_{k},h_{1},\dots,h_{k}, a_{1}\tilde{g}a_{2},b_{1}\tilde{g}b_{2}\), to obtain \(a_{1}b_{1}\tilde{g}a_{2}b_{2}\). Multiply by c to obtain a 1 b 1 ga 2 b 2.
We may, in addition, assume that
since when we apply Algorithm 14 in the image of our group in a matrix group, we have in Problem 13 that
As in Sect. 3, it follows that
Let u=a 1 ga 2 and v=b 1 gb 2. Decompose \(u=c\tilde{u}\) and \(v=d\tilde{v}\) with c,d central and \(\inf(\tilde{u}),\inf(\tilde{v})\in\{0,1\}\). As g∈[0,ℓ+1] and a 1∈[inf(a 1),inf(a 1)+ℓ],
and thus
Similarly,
Finally,
Let M=(m+2)(4ℓ+6). Continue as in Sect. 3.
By Theorem 4, we have
the absolute values of the coefficients in this matrix are bounded by \(2^{N^{2}(M+1)}\), and the maximal degree of t in this matrix is bounded by 2M. Let p be a prime slightly greater than \(2^{N^{2}M}\), and f(t) be an irreducible polynomial over \(\mathbb{Z}_{p}\), of degree d slightly larger than 2M. Then
under the natural identification of {−(p−1)/2,…,(p−1)/2} with {0,…,p−1}. Let \(\mathbb{F}=\mathbb{Z}[t]/\langle p, f(t)\rangle= \mathbb {Z}[t^{\pm1},\frac {1}{2}]/\langle p, f(t)\rangle\). \(\mathbb{F}\) is a finite field of cardinality p d, where d is the degree of f(t). It follows that the complexity of field operations in \(\mathbb{F}\) is, up to logarithmic factors, of order
Thus, the key K can be recovered as follows:
-
1.
Apply the composed function \(\operatorname{LK}(x) \bmod(p, f(t))\) to
$$g,g_1,\dots,g_k,h_1,\dots,h_k, \tilde{u}= a_1g\bigl(c^{-1} a_2 \bigr),\tilde{v}=\bigl(d^{-1}b_1\bigr)gb_2, $$to obtain an input to Problem 13.
-
2.
Solve the problem there, to obtain \(\operatorname{LK}(K') \bmod (p, f(t))\).
-
3.
Compute \((2^{2NM}t^{M})\cdot\operatorname{LK}(K') \bmod(p, f(t)) = (2^{2NM}t^{M})\cdot\operatorname{LK}(K')\).
-
4.
Divide by (22NM t M) to obtain \(\operatorname{LK}(K')\).
-
5.
Compute K′ using the Cheon–Jun inversion algorithm.
-
6.
Multiply by cd to obtain a 1 b 1 ga 2 b 2.
8 Further Applications
8.1 The Braid Diffie–Hellman KEP
Figure 3 illustrates the well known Diffie–Hellman KEP. Here, G is a cyclic group of prime order, generated by a group element g, and exponentiation denotes ordinary exponentiation.
Interpreting exponentiation in noncommutative groups as conjugation leads to the Ko–Lee–Cheon–Han–Kang–Park Braid Diffie–Hellman KEP [21]. For subsets A,B of a group G, [A,B]=1 means that a and b commute, ab=ba, for all a∈A,b∈B. The Braid Diffie–Hellman KEP is illustrated in Fig. 4. Since, in the Braid Diffie–Hellman KEP, the subgroups A and B of G commute element-wise, the keys computed by Alice and Bob are identical. It is proposed in [21] to use Artin’s braid group B N as the platform group G for the Braid Diffie–Hellman KEP, hence the term Braid in the name of this KEP.
In the passive adversary model, the security of the Braid Diffie–Hellman KEP for a platform group G (Fig. 4) is captured by the following problem.
Problem 16
(Diffie–Hellman Conjugacy Problem)
Let A and B be subgroups of G with [A,B]=1, and let g∈G, be given. Given a pair (g a,g b) where a∈A and b∈B, find g ab.
The Cheon–Jun attack on the Braid Diffie–Hellman KEP [8] forms a solution to the Diffie–Hellman Conjugacy Problem in the case where G is the braid group B N . Their solution can be described, roughly, as follows. Using the methods described in Sect. 4, the problem is reduced to the case where \(G\le\operatorname{GL}_{n}(\mathbb{F})\), a matrix group over a finite field. Since we are dealing with solutions that are supposed to work for all problem instances, this problem is not harder than that where \(G=\operatorname{GL}_{n}(\mathbb{F})\), the group of all invertible matrices in \(\operatorname{M}_{n}(\mathbb{F})\). However, the latter problem is easy: Assume that B=〈b 1,…,b k 〉≤G. Solve the system
of (k+1)n 2 linear equations in the n 2 entries of the unknown matrix x. There is an invertible solution to this system, namely, a. Now, any invertible solution \(\tilde{a}\) of this system can be used to compute g ab: By the first equation,
By the remaining equations, \(\tilde{a}\) commutes with the generators of B, and consequently with all elements of B. Thus, we can compute
This essentially establishes that the Diffie–Hellman Conjugacy Problem in this scenario can be solved in time O(kn 2ω).
Comparison with Our Approach
The reason why the above-mentioned approach of Cheon and Jun is not applicable, as is, to the Commutator KEP or to the Centralizer KEP is that, in either case, there is no prescribed set of generators with which it suffices that the solution commutes: In the Commutator KEP (Fig. 1) it is not clear that a has to commute with anything. In the Centralizer KEP (Fig. 2), we need a 2 to commute with b 2, but b 2 is secret. The main ingredient in our solution, in both cases, is the replacement of membership in a subgroup with membership in the double centralizer (in the full matrix algebra) of that subgroup, and the observation that the latter is efficiently computable. In other words, instead of adding equations that guarantee that the solution commutes with prescribed elements, we enlarge the set of solutions by moving to the double centralizer, and prove the increase in the set of solutions is not too large.
The secondary ingredients of our approach also have something to contribute to the Cheon–Jun attack: First, in [8] the dependence of the complexity on the infimum i is exponential (in the bit-length of i). This can be eliminated using the infimum reduction methods of Sects. 3 and 7.2. Second, the fact that the solution to the above-mentioned system of equations is invertible with overwhelming probability is not proved in [8].Footnote 10 This gap may be filled using the Invertibility Lemma (Lemma 9). Third, our approach may be used to push most of the work to the offline phase.
Theorem 17
Assume that \(|\mathbb{F}|/n\ge c>1\). The Diffie–Hellman Conjugacy Problem for a matrix group \(G\le \operatorname{GL} _{n}(\mathbb{F})\) and B=〈b 1,…,b k 〉 is solvable in O(kn 2ω) offline time and O(n 2ω) online Las Vegas time. More precisely, the running time of the online phase is O(n 2ω), plus O(n ω) Las Vegas time.
Proof
Offline phase: Compute a basis for the centralizer C(B) in the matrix algebra \(\operatorname{M}_{n}(\mathbb{F})\), a solution space of a system of kn 2 linear equations in the n 2 entries of the variable matrix x. Since C(B) is a subspace of the vector space \(\operatorname {M}_{n}(\mathbb{F})\), its dimension d is at most n 2. Let c 1,…,c d be a basis for C(B).
Online phase: Given g a, solve xg a=gx subject to x∈C(B), a linear system of n 2 equations in d scalar variables. Let H be the solution space. Let \(h_{1},\dots,h_{\tilde{d}}\) be a basis for H. Then \(\tilde{d}\le d\).
There is an invertible element in H, namely: a. By the Invertibility Lemma (Lemma 9), if \(t_{1},\dots,t_{\tilde{d}}\) are chosen uniformly and independently from a large subset of \(\mathbb{F}\), then the matrix \(\tilde{a} = t_{1} h_{1}+\cdots+t_{\tilde{d}}h_{\tilde{d}}\) is invertible with probability at least 1/c. Having found such invertible \(\tilde{a}\), compute
The running time of the online phase is O(n 2ω), plus O(n ω) Las Vegas time for the expected constant number of n×n matrix inversions. □
Remark 18
In the complexity of the offline phase in Theorem 17, k can be taken to be the minimum among the number of generators of A and the number of generators of B, by exchanging the roles of A and B.
8.2 Double Coset KEPs
In 2001, Cha, Ko, Lee, Han and Cheon [7] proposed a variation of the Braid Diffie–Hellman KEP (Fig. 4). For this variation, Cheon and Jun [8] described a convincing variation of their attack. Another variation of this protocol was proposed in 2005, by Shpilrain and Ushakov [34]. Both variations, as well as the Braid Diffie–Hellman KEP, are special cases of the protocol illustrated in Fig. 5.
The methods of Theorem 17 extend to the Double Coset KEP. Here too, the restriction to matrix groups is with no loss of generality, and we obtain an expected polynomial-time solution of the underlying problem in the braid group B N .
Theorem 19
Assume that \(|\mathbb{F}|/n\ge c>1\). Let \(A_{1},A_{2},B_{1}=\langle b_{1},\dots,b_{k}\rangle,B_{2}=\langle b'_{1},\dots ,b'_{l}\rangle\le G\le\operatorname{GL}_{n}(\mathbb{F})\), with [A 1,B 1]=[A 2,B 2]=1, and g∈G. After an offline computation of complexity O((k+l)n 2ω), one can, given a 1 ga 2,b 1 gb 2, compute a 1 b 1 ga 2 b 2 in time O(n 2ω), plus O(n ω) Las Vegas time.
Proof
Offline phase: Compute a basis for the centralizers C(B 1),C(B 2) in the matrix algebra \(\operatorname{M}_{n}(\mathbb{F})\), by solving one system of kn 2 linear equations in n 2 variables, and another system of ln 2 linear equations in n 2 variables. Let \(c_{1},\dots,c_{d_{1}}\) be a basis for C(B 1), and \(c'_{1},\dots ,c'_{d_{2}}\) be a basis for C(B 2). d 1,d 2≤n 2.
Online phase: Given a 1 ga 2, solve x(a 1 ga 2)=gy subject to x∈C(B 1),y∈C(B 2), a system of n 2 equations in d 1+d 2≤2n 2 scalar variables. Let H be the solution space,
and let (h 1,g 1),…,(h d ,g d ) be a basis for H. d≤d 1+d 2≤2n 2.
Let H 1={x:(xy)∈H} be the projection of H on the first coordinate. Then {h 1,…,h d } spans H 1. There is an element (x,y)∈H with x (and y) invertible, namely: \((a_{1}^{-1},a_{2})\). Thus, there is an invertible element in H 1. By Lemma 9, if t 1,…,t d are chosen uniformly and independently from a large subset of \(\mathbb{F}\), then the matrix x=t 1 h 1+⋯+t d h d is invertible with probability at least 1/c. Let \(\tilde{a}_{2}= t_{1} g_{1}+\cdots+t_{d}g_{d}\). Then \((x,\tilde{a}_{2})\in H\). Compute \(\tilde{a}_{1}=x^{-1}\). Then
As x∈C(B 1), \(\tilde{a}_{1}\in C(B_{1})\). Compute
□
An interesting further application is to Stickel’s KEP [36]. This KEP was cryptanalyzed by Shpilrain in [33], describing a heuristic cryptanalysis and supporting it by experimental results. Stickel’s KEP is a special case of the Double Coset KEP, where \(G=\operatorname{GL}_{n}(\mathbb{F})\), A 1=B 1=〈{a}∪Z(G)〉, and A 2=B 2=〈b〉 (a,b public). By Theorem 19, Shpilrain’s cryptanalysis can be turned into a provable Las Vegas algorithm that runs in expected polynomial time, i.e., one supported by a rigorous mathematical proof. In particular, in this way, it is guaranteed that changing the distributions according to which the protocol chooses the involved group elements would not defeat the mentioned polynomial-time cryptanalysis.
9 Additional Comments
Ignoring logarithmic factors, the overall complexity of the algorithms presented here is n 2ω+2=N 4ω+4 field operations that are of complexity m 3 ℓ 3 N 2. Thus, the complexity of our algorithms is
ignoring logarithmic factors. While polynomial, this complexity is practical only for braid groups of small index N. However, these algorithms constitute the first provable polynomial-time cryptanalyses of the Commutator KEP and of the Centralizer KEP.
The main novelty of our approach lies in the usage of linear centralizers (and double centralizers). However, also the secondary ingredients of our analysis may be of interest. In particular, we have shown that the Invertibility Lemma can be used to turn the Cheon–Jun cryptanalysis of the Braid Diffie–Hellman KEP [8] and the Shpilrain cryptanalysis of Stickel’s KEP [33] into provable Las Vegas algorithm that runs in expected polynomial time, and that the infimum reduction method can be applied to the Cheon–Jun attack to eliminate the exponential dependence on the bit-length of the infimum.
The major challenge is to reduce the degree of N in the polynomial-time cryptanalyses. By Chinese Remaindering or p-adic lifting methods, it may be possible to reduce the complexity contributed by the field operations. Apparently, this may reduce the power of N by 1. It should be possible to make sure that the Invertibility Lemma is still applicable when these methods are used. Much of the complexity comes from the Lawrence–Krammer representation having dimension quadratic in N. Unfortunately, it is conjectured that there are no faithful representations of B N of smaller dimension. A more careful analysis of the Lawrence–Krammer representation may yield finer estimates. However, it does not seem that any of these directions would make the attacks practical for, say, N=100.
One may wonder whether, from the complexity theoretic point of view, this paper may be the end of braid-based cryptography. Our belief is that this is not the case. For example, consider Kurt’s Triple Decomposition KEP [28, 4.2.5], described in Fig. 6. In this figure, an edge between two subgroups means that these subgroups commute element-wise. This ensures that the keys computed by Alice and Bob are both equal to ab 1 a 1 b 2 a 2 b.
We do not, at present, know whether the Triple Decomposition KEP can be cryptanalyzed using the methods presented here, or whether there is a provable, efficient cryptanalysis at all. Additional KEPs to which the present methods do not seem to be applicable are introduced by Kalka in [19] and [20]. There are additional types of braid-based schemes (e.g., authentication schemes) that cannot be attacked using the methods presented here. Some examples are reviewed in the monograph [28].
Changing the platform group in any of the studied KEPs is a very interesting option. There are efficiently implementable, infinite groups with no faithful representations as matrix groups (e.g., the braided Thompson group).Footnote 11
Notes
In our diagrams, green letters indicate publicly known elements, and red ones indicate secret elements, known only to the secret holders. Results of computations involving elements of both colors may be either publicly known, or secret, depending on the context. The colors are not necessary to follow the diagrams.
By adding elements, if needed, we assume that the number of a i ’s is equal to the number of b i ’s.
A free group word in the variables x 1,…,x k is a product of the form \(x_{i_{1}}^{\;\epsilon_{1}}x_{i_{2}}^{\;\epsilon_{2}}\cdots x_{i_{m}}^{\; \epsilon_{m}}\), with i 1,…,i m ∈{1,…,k} and ϵ 1,…,ϵ m ∈{1,−1}, and with no subproduct of the form \(x_{i}x_{i}^{-1}\) or \(x_{i}^{-1}x_{i}\).
For readers familiar with the braid group, we point out that the sequence (i,(p 1,…,p ℓ )) encodes the left normal form Δi p 1⋯p ℓ of the braid, in Artin’s presentation, with Δ being the fundamental, half twist braid on N strands.
Bigelow proved this theorem for the coefficient ring \(\mathbb{Z}[t^{\pm1},q^{\pm1}]\) with two variables. Krammer proved, in addition, that one may replace q by any real number from the interval (0,1).
When the infimum i is polynomial in the other parameters, which we proved in Sect. 3 that we may assume. Alternatively, by computing the representation of (i) separately, using properties of the Lawrence–Krammer representation.
The equality here is over the integers.
Since Z(G)⊆C G (g) for every g∈G, the mentioned problems are, under mild technical hypotheses perhaps, equivalent. We will not use this feature.
An argument involving Zariski density is provided in [8], but this seems to be a heuristic argument; not one intended to be a rigorous proof.
As for finite nonabelian groups, we are pessimistic. For example, finite simple groups tend to be linear of small dimension, by the classification of finite simple groups, and our method would reduce the cryptanalysis to the problem of finding an efficient linear representation of small dimension. There are at present no signs that such representations must be harder to evaluate (or invert) than, say, computing discrete logarithms in \(\mathbb{Z}_{p}^{*}\). Indeed, results of Babai, Beals, and Seress seem to indicate otherwise [4].
References
B. An, K. Ko, A family of pseudo-Anosov braids with large conjugacy invariant sets. arXiv:1203.2320 (2012)
I. Anshel, M. Anshel, D. Goldfeld, An algebraic method for public-key cryptography. Math. Res. Lett. 6, 287–291 (1999)
I. Anshel, M. Anshel, B. Fisher, D. Goldfeld, New key agreement protocols in braid group cryptography, in CT-RSA 2001. Lecture Notes in Computer Science, vol. 2020 (2001), pp. 13–27
L. Babai, R. Beals, Á. Seress, Polynomial-time theory of matrix groups, in ACM STOC (2009), pp. 55–64
S. Bigelow, Braid groups are linear. J. Am. Math. Soc. 14, 471–486 (2001)
J. Birman, T. Brendle, Braids: a survey, in Handbook of Knot Theory, ed. by W. Menasco, M. Thistlethwaite (Elsevier, Amsterdam, 2005), pp. 19–103
J. Cha, K. Ko, S. Lee, J. Han, J. Cheon, An efficient implementation of braid groups, in ASIACRYPT 2001. Lecture Notes in Computer Science, vol. 2248 (2001), pp. 144–156
J. Cheon, B. Jun, A polynomial time algorithm for the braid Diffie–Hellman conjugacy problem, in CRYPTO 2003. Lecture Notes in Computer Science, vol. 2729 (2003), pp. 212–224
P. Dehornoy, Braid-based cryptography. Contemp. Math. 360, 5–33 (2004)
D. Garber, Braid group cryptography, in Braids: Introductory Lectures on Braids, Configurations and Their Applications, ed. by J. Berrick, F.R. Cohen, E. Hanbury, Y.L. Wong, J. Wu. IMS Lecture Notes Series, vol. 19 (National University of Singapore, Singapore, 2009), pp. 329–403
D. Garber, S. Kaplan, M. Teicher, B. Tsaban, U. Vishne, Probabilistic solutions of equations in the braid group. Adv. Appl. Math. 35, 323–334 (2005)
V. Gebhardt, A new approach to the conjugacy problem in Garside groups. J. Algebra 292, 282–302 (2005)
V. Gebhardt, Conjugacy search in braid groups. Appl. Algebra Eng. Commun. Comput. 17, 219–238 (2006)
R. Gilman, A. Miasnikov, A. Miasnikov, A. Ushakov, New developments in commutator key exchange, in Proceedings of the First International Conference on Symbolic Computation and Cryptography, Beijing (2008), pp. 146–150. http://www-calfor.lip6.fr/~jcf/Papers/scc08.pdf
D. Hofheinz, R. Steinwandt, A practical attack on some braid group based cryptographic primitives, in PKC 2003. Lecture Notes in Computer Science, vol. 2567 (2002), pp. 187–198
J. Hughes, A. Tannenbaum, Length-based attacks for certain group based encryption rewriting systems, in SECI02: Sécurité de la Communication sur Internet (2002). www.ima.umn.edu/preprints/apr2000/1696.pdf
J. Hughes, A linear algebraic attack on the AAFG1 braid group cryptosystem, in Information Security and Privacy. Lecture Notes in Computer Science, vol. 2384 (2002), pp. 107–141
A. Kalka, Representation attacks on the braid Diffie–Hellman public key encryption. Appl. Algebra Eng. Commun. Comput. 17, 257–266 (2006)
A. Kalka, Representations of braid groups and braid-based cryptography. PhD thesis, Ruhr-Universität Bochum (2007). www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/KalkaArkadiusG/
A. Kalka, Non-associative public key cryptography. 1210.8270 (2012)
K. Ko, S. Lee, J. Cheon, J. Han, J. Kang, C. Park, New public-key cryptosystem using braid groups, in CRYPTO 2000. Lecture Notes in Computer Science, vol. 1880 (2000), pp. 166–183
K. Ko, J. Lee, T. Thomas, Towards generating secure keys for braid cryptography. Des. Codes Cryptogr. 45, 317–333 (2007)
D. Krammer, Braid groups are linear. Ann. Math. 155, 131–156 (2002)
S. Lee, E. Lee, Potential weaknesses of the commutator key agreement protocol based on braid groups, in EUROCRYPT 2002. Lecture Notes in Computer Science, vol. 2332 (2002), pp. 14–28
S. Maffre, A weak key test for braid-based cryptography. Des. Codes Cryptogr. 39, 347–373 (2006)
A. Miasnikov, V. Shpilrain, A. Ushakov, A practical attack on some braid group based cryptographic protocols, in CRYPTO 2005. Lecture Notes in Computer Science, vol. 3621 (2005), pp. 86–96
A. Miasnikov, V. Shpilrain, A. Ushakov, Random subgroups of braid groups: an approach to cryptanalysis of a braid group based cryptographic protocol, in PKC 2006. Lecture Notes in Computer Science, vol. 3958 (2006), pp. 302–314
A. Miasnikov, V. Shpilrain, A. Ushakov, Non-commutative Cryptography and Complexity of Group-Theoretic Problems. American Mathematical Society Surveys and Monographs, vol. 177 (2011)
A. Miasnikov, A. Ushakov, Length based attack and braid groups: cryptanalysis of Anshel–Anshel–Goldfeld key exchange protocol, in PKC 2007. Lecture Notes in Computer Science, vol. 4450 (2007), pp. 76–88
A. Myasnikov, A. Ushakov, Random subgroups and analysis of the length-based and quotient attacks. J. Math. Cryptol. 2, 29–61 (2008)
D. Micciancio, O. Regev, Lattice-based cryptography, in Post-quantum Cryptography, ed. by D. Bernstein, J. Buchmann (Springer, Berlin, 2008)
A. Lubotzky, Braid group cryptography, in CS Theory Seminar, Hebrew University, March (2001). http://www.cs.huji.ac.il/theorys/2001/Alex_Lubotzky
V. Shpilrain, Cryptanalysis of Stickel’s key exchange scheme, in Computer Science in Russia. Lecture Notes in Computer Science, vol. 5010 (2008), pp. 283–288
V. Shpilrain, A. Ushakov, Thompson’s group and public key cryptography, in ACNS 2005. Lecture Notes in Computer Science, vol. 3531 (2005), pp. 151–164
V. Shpilrain, A. Ushakov, A new key exchange protocol besed on the decomposition problem, in Algebraic Methods in Cryptography, ed. by L. Gerritzen, D. Goldfeld, M. Kreuzer, G. Rosenberger, V. Shpilrain. Contemporary Mathematics, vol. 418 (2006), pp. 161–167
E. Stickel, A new method for exchanging secret keys, in Proceedings of the Third International Conference on Information Technology and Applications (ICITA05) (2005), pp. 426–430
B. Tsaban, The conjugacy problem: cryptoanalytic approaches to a problem of Dehn, Minicourse, Düsseldorf University, Germany, July–August 2012. http://reh.math.uni-duesseldorf.de/~gcgta/slides/Tsaban_minicourses.pdf
Acknowledgements
I worked on the Commutator KEP, from various other angles, since I was introduced to it at the Hebrew University CS Theory seminar, by Alex Lubotzky [32]. I thank Oleg Bogopolski for inviting me, earlier this year (2012), to deliver a minicourse [37] in the conference Geometric and Combinatorial Group Theory with Applications (Düsseldorf, Germany, July 25–August 3, 2012). Preparing this minicourse, I discovered the linear centralizer attack. Initially, I addressed the Centralizer KEP (Sect. 7). When I moved to consider the Commutator KEP, Arkadius Kalka pointed out an obstacle, mentioned by Shpilrain and Ushakov, that struck me as solvable by linear centralizers. I am indebted to Kalka for making the right comment at the right time.
I also thank David Garber, Arkadius Kalka, and Eliav Levy, and the referees, for comments leading to improvements in the presentation of this paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Nigel Smart.
Rights and permissions
About this article
Cite this article
Tsaban, B. Polynomial-Time Solutions of Computational Problems in Noncommutative-Algebraic Cryptography. J Cryptol 28, 601–622 (2015). https://doi.org/10.1007/s00145-013-9170-9
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-013-9170-9
Key words
- Noncommutative-algebraic cryptography
- Group theory-based cryptography
- Braid-based cryptography
- Commutator key exchange
- Centralizer key exchange
- Braid Diffie–Hellman key exchange
- Linear cryptanalysis
- Invertibility lemma
- Schwartz–Zippel lemma
- Linear centralizer method
- Braid infinimum reduction
- Algebraic cryptanalysis