Random subgroups and analysis of the length-based and quotient attacks

DOI10.1515/JMC.2008.003zbMATH Open1195.94067arXiv0707.1501OpenAlexW2963909615MaRDI QIDQ3516765FDOQ3516765

Authors: Alexander Ushakov, Alexei Myasnikov 

Publication date: 11 August 2008

Published in: Journal of Mathematical Cryptology (Search for Journal in Brave)

Abstract: 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 length-based attacks on it. Furthermore, we design and analyze a new type of attacks, 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.

Full work available at URL: https://arxiv.org/abs/0707.1501

Recommendations

• Length Based Attack and Braid Groups: Cryptanalysis of Anshel-Anshel-Goldfeld Key Exchange Protocol
• Length-based attacks in polycyclic groups
• Public Key Cryptography - PKC 2006
• Length-based cryptanalysis: the case of Thompson's group
• Generic Subgroups of Group Amalgams

zbMATH Keywords

length-based attackbraid group cryptographycommutator key-exchangequotient attackrandom subgroup of a braid group

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Cryptography (94A60) Braid groups; Artin groups (20F36) Asymptotic properties of groups (20F69) Probabilistic methods in group theory (20P05)

Cited In (17)

• Length-based attacks in polycyclic groups
• Two general schemes of algebraic cryptography
• Polynomial-time solutions of computational problems in noncommutative-algebraic cryptography
• The conjugacy problem in the Grigorchuk group is polynomial time decidable.
• Random subgroups of acylindrically hyperbolic groups and hyperbolic embeddings
• SOLENOIDAL MAPS, AUTOMATIC SEQUENCES, VAN DER PUT SERIES, AND MEALY AUTOMATA
• Length-based cryptanalysis: the case of Thompson's group
• Homomorphism reconfiguration via homotopy
• Linear time algorithm for the conjugacy problem in the first Grigorchuk group
• Exponentially generic subsets of groups
• A parallel evolutionary approach to solving systems of equations in polycyclic groups
• A nonlinear decomposition attack
• Authenticated commutator key agreement protocol
• The status of polycyclic group-based cryptography: a survey and open problems
• Evolution of group-theoretic cryptology attacks using hyper-heuristics
• Random generation of Thompson group \(F\)
• On asymptotic densities and generic properties in finitely generated groups.

This page was built for publication: Random subgroups and analysis of the length-based and quotient attacks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3516765)