On the AAGL Protocol

Recently the AAGL (Anshel-Anshel-Goldfeld-Lemieux) has been proposed which can be used for RFID tags. We give algorithms for the problem (we call the MSCSPv) on which the security of the AAGL protocol is based upon. Hence we give various attacks for general parameters on the recent AAGL protocol proposed. One of our attacks is a deterministic algorithm which has space complexity and time complexity both atleast exponentialin the worst case. In a better case using a probabilistic algorithm the time complexity canbe O(|XSS(ui')^L5*(n^(1+e)) and the space complexity can be O(|XSS(ui')|^L6), where the element ui' is part of a public key, n is the index of braid group, XSS is a summit type set and e is a constant in a limit. The above shows the AAGL protocol is potentially not significantly more secure as using key agreement protocols based on the conjugacy problem such as the AAG (Anshel-Anshel-Goldfeld) protocol because both protocols can be broken with complexity which do not significantly differ. We think our attacks can be improved.

• Publication year

  2007

• Venue

  arXiv.org

• Publication date

  2007-08-17

• Fields of study

  Computer Science

• Identifiers
  arXiv 0708.2397
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Key Agreement

  2007influential reference
• On the Security of the Cha-Ko-Lee-Han-Cheon Braid Group Public Key Cryptosystem

  2007cited by this paper
• Cryptanalysis of the shifted conjugacy authentication protocol

  2007cited by this paper
• Using shifted conjugacy in braid-based cryptography

  2006cited by this paper
• A new key exchange protocol based on the decomposition problem

  2005cited by this paper
• A New Approach to the Conjugacy Problem in Garside Groups

  2003cited by this paper
• Computation of Centralizers in Braid groups and Garside groups

  2002influential reference
• New Signature Scheme Using Conjugacy Problem

  2002cited by this paper
• LENGTH-BASED CONJUGACY SEARCH IN THE BRAID GROUP

  2002influential reference
• New Public-Key Cryptosystem Using Braid Groups

  2000cited by this paper
• An algebraic method for public-key cryptography

  1999influential reference
• Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces

  1997cited by this paper
• ALGORITHMS FOR POSITIVE BRAIDS

  1994influential reference
• THE BRAID GROUP AND OTHER GROUPS

  1969cited by this paper
• Korea

  1967cited by this paper

• No citing papers are available for this paper.