Cryptanalysis of the Algebraic Eraser and short expressions of permutations as products
Authors:
- Arkadius KalkaAKArkadius Kalka
- Mina TeicherMTMina Teicher
- Boaz TsabanBTBoaz Tsaban
Preprint
Abstract
On March 2004, Anshel, Anshel, Goldfeld, and Lemieux introduced the _Algebraic Eraser_ scheme for key agreement over an insecure channel. This scheme is based on semidirect products of algebraic structures, and uses a novel hybrid of infinite and finite noncommutative groups. They also introduced the_Colored Burau Key Agreement Protocol (CBKAP)_, a concrete realization of this scheme. We present an efficient method to extract the shared key out of the public information provided by CBKAP, assuming that the keys are chosen with standard distributions. Our methods come from probabilistic group theory, and seem to have not been used before in cryptanalysis. Of independent interest may be a simple heuristic algorithm we propose for finding short expressions of permutations as products of given random permutations. According to heuristic analysis supported by experiments, our algorithm gives expressions of length O(n^2log n) in running time O(n^4log n).Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Cryptanalysis of the Anshel-Anshel-Goldfeld-Lemieux Key Agreement ProtocolGroups - Complexity - Cryptology, 2009
- Handbook of Computational Group Theory2005
- An Algorithm for Solving the Factorization Problem in Permutation GroupsJournal of Symbolic Computation, 1998
- The probability of generating the symmetric groupJournal of Combinatorial Theory, Series A, 1989
- Seifert Fibre Spaces and Braid GroupsProceedings of the London Mathematical Society, 1982
- The probability of generating the symmetric groupMathematische Zeitschrift, 1969