TY - JOUR
T1 - A linear decomposition attack
AU - Myasnikov, Alexei
AU - Roman'Kov, VitalѤ
N1 - Publisher Copyright:
© 2015 by De Gruyter.
PY - 2015/5/1
Y1 - 2015/5/1
N2 - 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.
AB - 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.
KW - Algebraic cryptography
KW - Diffe-Hellman scheme
KW - cryptanalysis
KW - linear decomposition
KW - linear representation
UR - http://www.scopus.com/inward/record.url?scp=84928947553&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84928947553&partnerID=8YFLogxK
U2 - 10.1515/gcc-2015-0007
DO - 10.1515/gcc-2015-0007
M3 - Article
AN - SCOPUS:84928947553
SN - 1867-1144
VL - 7
SP - 81
EP - 94
JO - Groups, Complexity, Cryptology
JF - Groups, Complexity, Cryptology
IS - 1
ER -