2025/11/19 by McKemmie, Eilidh, Srivastava, Amol
Computer Science · #11T71 #20G40 20G40 #Coding theory and cryptography #Cryptographic Implementations and Security #FOS: Mathematics #Group Theory (math.GR) #Polynomial and algebraic computation
paper · doi:10.48550/arxiv.2511.15842
openalex publication_date 2025/11/19 · openalex created_date 2025/11/23 · openalex updated_date 2026/07/28
In 1991, Zémor proposed a hash function which provides data security using the difficulty of writing a given matrix as a product of generator matrices. Tillich and Zémor subsequently provided an algorithm finding short collisions for this hash function. We extend this collision attack to a stronger preimage attack, under the assumption that we can factor large integers efficiently. The Euclidean algorithm will factor a 2× 2 matrix with non-negative integer entries and determinant 1. This factorization is short if the matrix entries are all roughly the same size. Therefore, to factor a matrix we need only find an integer matrix with the listed properties which is congruent to the target matrix modulo p; finding such an integer matrix is equivalent to solving a Diophantine equation. We give an algorithm to solve this equation.