TY - JOUR
T1 - Random subgroups and analysis of the length-based and quotient attacks
AU - Myasnikov, Alexei G.
AU - Ushakov, Alexander
PY - 2008/4
Y1 - 2008/4
N2 - In this paper we discuss generic properties of "random subgroups" of a given group G. It turns out that in many groups G (even in most exotic of them) the random subgroups have a simple algebraic structure and they "sit" inside G in a very particular way. This gives a strong mathematical foundation for cryptanalysis of several group-based cryptosystems and indicates on how to chose "strong keys". To illustrate our technique we analyze the Anshel-Anshel-Goldfeld (AAG) cryptosystem and give a mathematical explanation of recent success of some heuristic lengthbased attacks on it. Furthermore, we design and analyze a new type of attack, which we term the quotient attacks. Mathematical methods we develop here also indicate how one can try to choose "parameters" in AAG to foil the attacks.
AB - In this paper we discuss generic properties of "random subgroups" of a given group G. It turns out that in many groups G (even in most exotic of them) the random subgroups have a simple algebraic structure and they "sit" inside G in a very particular way. This gives a strong mathematical foundation for cryptanalysis of several group-based cryptosystems and indicates on how to chose "strong keys". To illustrate our technique we analyze the Anshel-Anshel-Goldfeld (AAG) cryptosystem and give a mathematical explanation of recent success of some heuristic lengthbased attacks on it. Furthermore, we design and analyze a new type of attack, which we term the quotient attacks. Mathematical methods we develop here also indicate how one can try to choose "parameters" in AAG to foil the attacks.
KW - Braid group cryptography
KW - Commutator key-exchange
KW - Length-based attack
KW - Quotient attack
KW - Random subgroup of a braid group
UR - http://www.scopus.com/inward/record.url?scp=73649139782&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=73649139782&partnerID=8YFLogxK
U2 - 10.1515/JMC.2008.003
DO - 10.1515/JMC.2008.003
M3 - Article
AN - SCOPUS:73649139782
SN - 1862-2976
VL - 2
SP - 29
EP - 61
JO - Journal of Mathematical Cryptology
JF - Journal of Mathematical Cryptology
IS - 1
ER -