Probabilistic Solutions of Equations in the Braid Group
arXiv:math/0404076 · doi:10.1016/j.aam.2005.03.002
Abstract
Given a system of equations in a "random" finitely generated subgroup of the braid group, we show how to find a small ordered list of elements in the subgroup, which contains a solution to the equations with a significant probability. Moreover, with a significant probability, the solution will be the first in the list. This gives a probabilistic solution to: The conjugacy problem, the group membership problem, the shortest representation of an element, and other combinatorial group-theoretic problems in random subgroups of the braid group. We use a memory-based extension of the standard length-based approach, which in principle can be applied to any group admitting an efficient, reasonably behaving length function.
Small updates
References in corpus (1)
Cited by in corpus (10)
- Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography
- Braid Group Cryptography
- Cryptanalysis of group-based key agreement protocols using subgroup distance functions
- Length-based cryptanalysis: The case of Thompson's Group
- On an authentication scheme based on the Root Problem in the braid group
- A new key exchange protocol based on the decomposition problem
- The conjugacy search problem in public key cryptography: unnecessary and insufficient
- Evolution of Group-Theoretic Cryptology Attacks using Hyper-heuristics
- An authentication scheme based on the twisted conjugacy problem
- The conjugacy problem and related problems in lattice-ordered groups