Michael Anshel May 27 15:00-15:30 Braid Group Cryptography and Quantum Cryptoanalysis 8th International Wigner Symposium May 27-30, 2003 GSUC-CUNY 365 Fifth Avenue, NY, NY 10016,USA Braid Group Cryptography and Quantum Cryptanalysis Michael Anshel, Department of Computer Sciences The City College of the City University of New York New York, NY 10031, USA http://www-cs.engr.ccny.cuny.edu/~csmma/ email: MikeAt1140@aol.com ABSTRACT: A central problem of Public Key Cryptography is to create protocols for securely transfering private keys over an insecure channel. One such protocol, Commutator Key Exchange (CKE) based on the difficulty of solving conjugacy equations in groups is discussed using Braid Groups (BCKE), together with a variation based on the Lawrence-Krammer (LK) representation, LK-CKE. We conclude with a challenge concerning the quantum cryptanalysis of LK-CKE. 1.1 Background: The Commutator Key Exchange, CKE was introduced in [AAG1999],[AAFG2001] to take advantage of over more then a century of research in Combinatorial Group Theory (CGT), the study of groups via presentations by generators and defining relations [MKS1977]. Incidentally, Wilhelm Magnus the foremost proponent of CGT in the 20th Century interacted on issues of importance to both Physics and Mathematics with Eugene Wigner. However my knowledge is anecdotal. Magnus and his students performed pioneering work in the study of Braid Groups [Bir1974]. Shor's quantum algorithm for discrete logarithms has been extended to elliptic curves in [PZ2003]. Should quantum computers be constructed to implement these algorithms as cryptanalytic tools, conventional public key cryptography would be put in some jeopardy. Thus the search for alternative cryptography protocols to defend against such attacks must be developed. Question: A central problem of Public Key Cryptography is to create protocols for securely transfering private keys over an insecure channel. Is there a scalable method to defend against both conventional and quantum cryptanalytic attacks? 2.1 Commutator Key Exchange : The CKE addresses the problem of creating protocols for securely transfering private keys over an insecure channel. A parallel development for extending public key cryptography is given in [KL CHKP2000]. In both cases Braid Groups where chosen to illustrate the method and provide challenges to spur development. We confine ourselves to the CKE since the methods of [KLCHKP 2000] are closely related to CKE [AAG2002]. The parties involved in the CKE protocol are Alice and Bob. They publish, respectively, words a(1), a(2), ... ,a(n) and b(1), b(2), ... ,b(m) specifying group elements from a group G = (S | D) with generating symbols S and defining relations D. The common key K is created by the following concurrent actions of Alice and Bob. ALICE'S ACTIONS: Alice transforms Bob's public words in the following manner: (1a) Alice selects a private word X in the subgroup of G generated by a(1),a(2), ... , a(n) and conjugates each b(i) by that X producing b*(1),b*(2), ...,b*(m). (2a) Alice selects a word B(i) in the generating symbols such that B(i) and b*(i) define the same element of G for i =1, ... ,m. (3a) Alice transmits to Bob the list B(1), B(2), ... ,B(m). BOB'S ACTIONS: Bob transforms Alice's public words in a similar manner: (1b) Bob selects a private word Y in the subgroup of G generated by b(1), b(2), ... ,b(m) and conjugates each a(i) by that Y producing a*(1), a*(2), ...,a*(n). (2b) Bob selects a word A(i) in the generating symbols such that A(i) and a*(i) define the same element of G for i = 1, ... ,n . (3b) Bob transmits to Alice the list A(1), A(2), ... ,A(n). COMMON ACTIONS: (4ab) Alice and Bob now compute, respectively, V and W each of which specifies the commutator C = [X,Y] defined by the words X and Y. (5ab) Alice and Bob compute a common key K = F(V) = F(W) where F is a one-way function from the words in the generating symbols to words in the same alphabet such that F(W) = F(Z) whenever W and Z define the same element of G. The function F is called a key extractor. Remarks: (4ab) is accomplished by noting that since X and Y are words X = x(a(1), ..., a(n) ) and Y = y( b(1), ...,b(m) ) then Alice may compute a word V representing the commutator C = [X,Y] from [X,Y] = X * (YXY')' = X * x(A(1),..., A(n) )' and Bob may compute a word V representing the commutator C = [X,Y] from [X,Y] = (XYX') * Y' = y( B(1), ..., B(m) ) * Y' where X' and Y' respectively denote the inverses of X and Y.F is said to be one-way if it is feasible to evaluate but difficult to reverse. Consult [Wel] for complexity, cryptography and physics. 3.1 The Braid Group Platform Braid Groups provide an ideal platform for studying the Commutator Key Exchange. However there is much debate in the cryptographic community as to whether or not Braid Commutator Key Exchange (BCKE) is sufficient for contemporary cryptographic applications. Some record of these discussions is currently maintained by Helger Lipmaa at http://www.tcs.hut.fi/~helger/crypto/link/public/braid/ The study of braids and braid groups has been traced to the notebooks of C.F.Gauss [Epp1998] Of interest to us here is the recent claims by [CJ2003] based in part on [Kram2002] where braid groups are shown to have a faithful linear representation (LK). The braid group platform we have in mind requires some modification of the commutator key exchange protocol previously discussed. Let B(n) denote the braid group given by the generators s(1),s(2),... ,s(n-1) and defining relations s(i)s(i+1)s(i) = s(i+1)s(i)s(i+1) 1<=i=2. 3.2 Lawrence-Krammer Representation Let LK(n) denote the matrix group arising from the Lawrence-Krammer representation of the braid group B(n). This matrix group consists certain of matrices of dimension N=n(n+1)/2 whose entries are represented by finite Laurent series in two variables. The form of these matrices are given in [Kram2002]. Again the parties involved in the protocol are Alice and Bob. They create, respectively, words a(1), a(2), ... ,a(n) and b(1), b(2), ... ,b(m) specifying group elements from a group G = (S | D) with generating symbols S and defining relations D. The common key K is created by the following concurrent actions of Alice and Bob. Now the Lawrence-Krammer CKE (LK-CKE) requires that the elements of the subgroups and their conjugates by transmitted as LK matrices. The computations required to perform LK-CKE are matrix computations rather than symbolic computations. 4.1 Conventionl Attacks Conventional attacks on BCKE use fast heuristic algorithms and have shown some success at small key size. From [Shpil 2003] we derive a countermeasure against fast conventional heuristic algorithmic attacks: using several rounds of BCKE and take the product resultant commutators. In fact [Shpil 2003] notes that "If, for example the probablity of success of a particular single round is .9, then the probability of success in say 50 rounds...is as good as 0.". Consult [BMS2002] for the ideas underlying Shpilrain's approach. Remarks: At a CCNY Mathematics Colloquium held at CCNY-CUNY in April 2003 Patrick Dehornoy of the University of Caen reported that the known braid group cryptosystems were secure against conventional attacks with the choice or correct parameters. The following week Sangjin Lee of KAIST voiced similar remarks following Joan Birman's Seminar at Columbia University. 4.2 Quantum Cryptanalytic Attacks Proposals subjecting braid group cryptosystems to quantum cryptanalysis have come to my attention since 2000. These proposals fall roughly into the following categories. (1) Quantum Search Algorithms (2) Hidden Subgroup Problems Techniques (3) Hybrid Quantum Algorithms Consult [NC2000] for references concerning quantum computation Consult [CJ2003] for results employing the LK representation. Employ LK-CKE with suitable choice of braid group parameters such that the number of elementary field operations required to solve the associated systems of linear equations is at least O(10^36). This overwhelms current conventional attacks and provides a challenge for quantum cryptanalysis. Postscript: In [Kent 2003] it is pointed out that that unconditional security quantum cryptography is unattainable for certain tasks such as bit commitment oblivious transfer and some secure two-party computations. Therefore it may be necessary to fall back on weaker notions of security. One possible approach is to assume that reliable bounds can be placed on the size of any quantum computer in the possession of an adversary, and to devise protocols which cannot be broken by quantum computers capable of manipulating no more than N qubits coherently. However, it is hard to tell at the moment whether future technological developments will allow for any such bounds. Perhaps braid group cryptosystems can provide meet this challenge. Acknowledgements: The author wishes to thank Vladimir Shpilrain for a copy of his working manuscript [Shpil 2003] which is now available on IACR Cryptology ePrint Archive. References: [AAG1999] I.Anshel,M.Anshel,and D.Goldfeld,"An Algebraic Method for Public-Key Cryptography", Math Research Letters 6 (1999) 1-5 [AAG2002] I.Anshel,M.Anshel,and D.Goldfeld, "Non-abelian key agreement protocols" Discrete Applied Math, Article 3129, (2002) electronic publication to appear in hardcopy 2003 [AAFG] I.Anshel,M.Anshel,B.Fisher,D.Goldfeld, "New Key Agreement Protocols in Braid Group Cryptography"in D.Naccache (ed), Topics in Cryptology- CT-RSA 2001, LNCS 2020 Springer-Verlag (2001), 13-27 [Bir1974] J.Birman, " Braids, Links and Mapping Class Groups", Annals of Math. Studies, Study 82, Princeton University Press (1974) [BMS] A.Borovik,A.G.Myasnikov,and V.Shpilrain,"Measuring sets in infinite groups", Contemporary Mathematics, AMS 298 (2002) pp 21-42 [CJ 2003] J.H.Cheon and B. Jun, "A Polynomial Time Algorithm for the Braid Diffie-Hellman Conjugacy Problem", (http://eprint.iacr.org/2003/019/ [Epp1998] M.Epple, "Orbits, Asteriods, a Braid, and the First Link Invariant", Mathematical Intelligencer, Volume 20, Number 1 (Winter 1998), 45-52 [Kent 2003] A. Kent, "A proposal for founding mistrustful quantum cryptography on coin tossing", arXiv: quant- ph/ 0111097 v3 12 Jun 2003 [KLCHKP] K.H.Ko, S.J.Lee, J.H.Chean, J.W.Han, J.S.Kang, C.Park,"New Public-Key Cryptosystem Using Braid Groups" in M.Bellare (Ed.) Advances in Cryptology- Crypto 2000 LNCS 1880 Springer-Verlag (2000), 166-183 [Kram2002] D. Krammer, "Braid groups are Linear", Annals of Math, Vol. 155 (2002). pp. 131-156 [NC20002] M.A.Nielsen and I.L.Chuang, "Quantum Computation and Quantum Information" CUP (2000) [PZ2003] J.Proos and C.Zalka "Shor's discrete logarithm quantum algorithm for elliptic curves" ,(arXiv: quant- ph/ 0301141 v1 25 Jan 2003) [Shpil 2003] V.Shpilrain,"Assessing security of some group based cryptosystems" http://eprint.iacr.org/2003/123 [Wel1993] D.J.A.Welsh, "Complexity: Knots,Colourings and Counting" LMS 186 CUP (1993)