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

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

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 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.

Original languageEnglish
Pages (from-to)29-61
Number of pages33
JournalJournal of Mathematical Cryptology
Volume2
Issue number1
DOIs
StatePublished - Apr 2008

Keywords

  • Braid group cryptography
  • Commutator key-exchange
  • Length-based attack
  • Quotient attack
  • Random subgroup of a braid group

Fingerprint

Dive into the research topics of 'Random subgroups and analysis of the length-based and quotient attacks'. Together they form a unique fingerprint.

Cite this