A linear decomposition attack

Alexei Myasnikov, VitalѤ Roman'Kov

Research output: Contribution to journalArticlepeer-review

36 Scopus citations

Abstract

We discuss a new attack, termed a dimension or linear decomposition attack, on several known group-based cryptosystems. This attack gives a polynomial time deterministic algorithm that recovers the secret shared key from the public data in all the schemes under consideration. Furthermore, we show that in this case, contrary to the common opinion, the typical computational security assumptions are not very relevant to the security of the schemes, i.e., one can break the schemes without solving the algorithmic problems on which the assumptions are based.

Original languageEnglish
Pages (from-to)81-94
Number of pages14
JournalGroups, Complexity, Cryptology
Volume7
Issue number1
DOIs
StatePublished - 1 May 2015

Keywords

  • Algebraic cryptography
  • Diffe-Hellman scheme
  • cryptanalysis
  • linear decomposition
  • linear representation

Fingerprint

Dive into the research topics of 'A linear decomposition attack'. Together they form a unique fingerprint.

Cite this