caa a22 4500 606148825 CHVBK 20210128100531.0 cr unu---uuuuu 210128e20150701xx s 000 0 eng 10.1007/s00145-013-9170-9 doi (NATIONALLICENCE)springer-10.1007/s00145-013-9170-9 Tsaban Boaz Department of Mathematics, Bar-Ilan University, 52900, Ramat Gan, Israel aut Polynomial-Time Solutions of Computational Problems in Noncommutative-Algebraic Cryptography [Elektronische Daten] [Boaz Tsaban] We introduce the linear centralizer method, and use it to devise a provable polynomial-time solution of the Commutator Key Exchange Problem, the computational problem on which, in the passive adversary model, the security of the Anshel-Anshel-Goldfeld (Anshel et al., Math. Res. Lett. 6:287-291, 1999) Commutator key exchange protocol is based. We also apply this method to solve, in polynomial time, the computational problem underlying the Centralizer key exchange protocol, introduced by Shpilrain and Ushakov in (Contemp. Math. 418:161-167, 2006). This is the first provable polynomial-time cryptanalysis of the Commutator key exchange protocol, hitherto the most important key exchange protocol in the realm of noncommutative algebraic cryptography, and the first cryptanalysis (of any kind) of the Centralizer key exchange protocol. Unlike earlier cryptanalyses of the Commutator key exchange protocol, our cryptanalyses cannot be foiled by changing the distributions used in the protocol. International Association for Cryptologic Research, 2013 Noncommutative-algebraic cryptography nationallicence Group theory-based cryptography nationallicence Braid-based cryptography nationallicence Commutator key exchange nationallicence Centralizer key exchange nationallicence Braid Diffie-Hellman key exchange nationallicence Linear cryptanalysis nationallicence Invertibility lemma nationallicence Schwartz-Zippel lemma nationallicence Linear centralizer method nationallicence Braid infinimum reduction nationallicence Algebraic cryptanalysis nationallicence Journal of Cryptology Springer US; http://www.springer-ny.com 28/3(2015-07-01), 601-622 0933-2790 28:3<601 2015 28 145 https://doi.org/10.1007/s00145-013-9170-9 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00145-013-9170-9 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Tsaban Boaz Department of Mathematics, Bar-Ilan University, 52900, Ramat Gan, Israel aut NATIONALLICENCE 773 0- Journal of Cryptology Springer US; http://www.springer-ny.com 28/3(2015-07-01), 601-622 0933-2790 28:3<601 2015 28 145