'Cryptanalysis of Semidirect Product KeyExchange by Matrices Over Noncommutative Rings' C. Battarbee

"Cryptanalysis of Semidirect Product Key Exchange Using Matrices Over Non-Commutative Rings" - Christopher Battarbee

Seminario del convegno UMI DeCifris del 2021.

Abstract: In 2013 an alternative to the Diffie-Hellman Key Exchange was proposed by Habeeb, Kahrobaei, Koupparis and Shpilrain, based on the semidirect product of two (semi)groups and believed to be quantum-safe. The algorithm in full generality is sometimes known as the non-commutative shift, and is proposed over a number of candidate platforms and applications. The candidate platform of our interest is a Matrix Action Key Exchange (MAKE), the novelty of which is to consider the semidirect product of the set of square matrices over finite fields Zp under two different operations, giving improved mixing. However, similar to attacks on the non- commutative shift algorithm given by Romankov and Myasnikov in 2015, MAKE turns out to be vulnerable to an attack by linear algebra. This latter attack relies on commutativity of the underlying ring Zp in order to invoke the Cayley-Hamilton theorem. In our work, we are able to show that under certain conditions, one can extend the attack to deal with non-commutative rings. In particular, the non- commutative group rings originally proposed as a platform for the non-commutative shift meet these conditions.