Speeding up Deciphering by Hypergraph Ordering
This work addresses a computational bottleneck in cryptography by providing theoretical bounds on algorithm efficiency, but it is incremental as it builds on prior methods without introducing a new paradigm.
The paper tackles the problem of speeding up the Gluing Algorithm for solving sparse systems of linear equations over GF(q) with at most three unknowns per equation, showing that the best achievable exponent in the average running time is between c1m and c2m for some positive constants c1 and c2 when the number of unknowns equals m.
The "Gluing Algorithm" of Semaev [Des.\ Codes Cryptogr.\ 49 (2008), 47--60] --- that finds all solutions of a sparse system of linear equations over the Galois field $GF(q)$ --- has average running time $O(mq^{\max \left\vert \cup_{1}^{k}X_{j}\right\vert -k}), $ where $m$ is the total number of equations, and $\cup_{1}^{k}X_{j}$ is the set of all unknowns actively occurring in the first $k$ equations. Our goal here is to minimize the exponent of $q$ in the case where every equation contains at most three unknowns. %Applying hypergraph-theoretic methods we prove The main result states that if the total number $\left\vert \cup_{1}^{m}X_{j}\right\vert$ of unknowns is equal to $m$, then the best achievable exponent is between $c_1m$ and $c_2m$ for some positive constants $c_1$ and $c_2.$