Boaz Tsaban

Adi Ben-Zvi, Simon R. Blackburn, Boaz Tsaban

Anshel, Anshel, Goldfeld and Lemieaux introduced the Colored Burau Key Agreement Protocol (CBKAP) as the concrete instantiation of their Algebraic Eraser scheme. This scheme, based on techniques from permutation groups, matrix groups and braid groups, is designed for lightweight environments such as RFID tags and other IoT applications. It is proposed as an underlying technology for ISO/IEC 29167-20. SecureRF, the company owning the trademark Algebraic Eraser, has presented the scheme to the IRTF with a view towards standardisation. We present a novel cryptanalysis of this scheme. For parameter sizes corresponding to claimed 128-bit security, our implementation recovers the shared key using less than 8 CPU hours, and less than 64MB of memory.

Arkadius Kalka, Boaz Tsaban, Gary Vinokur

We solve the simultaneous conjugacy problem in Artin's braid groups and, more generally, in Garside groups, by means of a complete, effectively computable, finite invariant. This invariant generalizes the one-dimensional notion of super summit set to arbitrary dimensions. One key ingredient in our solution is the introduction of a provable high-dimensional version of the Birman--Ko--Lee cycling theorem. The complexity of this solution is a small degree polynomial in the cardinalities of our generalized super summit sets and the input parameters. Computer experiments suggest that the cardinality of this invariant, for a list of order $N$ independent elements of Artin's braid group $B_N$, is generically close to~1.

Matan Banin, Boaz Tsaban

We present a polynomial-time reduction of the discrete logarithm problem in any periodic (a.k.a. torsion) semigroup (SGDLP) to the same problem in a subgroup of the same semigroup. It follows that SGDLP can be solved in polynomial time by quantum computers, and that SGDLP has subexponential algorithms whenever the classic DLP in the corresponding groups has subexponential algorithms.

Ciaran Mullan, Boaz Tsaban

We study homomorphic hash functions into SL(2,q), the 2x2 matrices with determinant 1 over the field with $q$ elements. Modulo a well supported number theoretic hypothesis, which holds in particular for concrete homomorphisms proposed thus far, we provide a worst case to average case reduction for these hash functions: upto a logarithmic factor, a random homomorphism is as secure as _any_ concrete homomorphism. For a family of homomorphisms containing several concrete proposals in the literature, we prove that collisions of length O(log(q)) can be found in running time O(sqrt(q)). For general homomorphisms we offer an algorithm that, heuristically and according to experiments, in running time O(sqrt(q)) finds collisions of length O(log(q)) for q even, and length O(log^2(q)/loglog(q))$ for arbitrary q. While exponetial time, our algorithms are faster in practice than all earlier generic algorithms, and produce much shorter collisions.

Boaz Tsaban

We introduce the \emph{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 1999 \emph{Commutator} key exchange protocol is based. We also apply this method to the computational problem underlying the \emph{Centralizer} key exchange protocol, introduced by Shpilrain and Ushakov in 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.

Matan Banin, Boaz Tsaban

Bergman's Ring $E_p$, parameterized by a prime number $p$, is a ring with $p^5$ elements that cannot be embedded in a ring of matrices over any commutative ring. This ring was discovered in 1974. In 2011, Climent, Navarro and Tortosa described an efficient implementation of $E_p$ using simple modular arithmetic, and suggested that this ring may be a useful source for intractable cryptographic problems. We present a deterministic polynomial time reduction of the Discrete Logarithm Problem in $E_p$ to the classical Discrete Logarithm Problem in $\Zp$, the $p$-element field. In particular, the Discrete Logarithm Problem in $E_p$ can be solved, by conventional computers, in sub-exponential time.