Optimal mixing time found for trapdoored matrix generation over large fields
Optimal Marginal Mixing for Transvection-Based Trapdoored Matrices over Large Fields
Cryptography and Security
Summary
Some special matrices can be made so that anyone can multiply them by vectors quickly if they know a secret key. The authors studied how long it takes for a random process that builds these matrices to become 'well mixed,' meaning their entries look random. They found exact formulas for this mixing time that work for any part of the matrix and for large enough fields. This helps in making efficient trapdoored matrices that could be very useful for secure computing and cryptography. They also analyzed potential attacks and suggest directions for future work.
What this means in practice
- •For cryptographic engineers: Implement efficient matrix operations with secret trapdoors for cryptographic protocols using the authors' optimal mixing time results.
- •For high-performance computing developers: Design parallelizable matrix computations that exploit trapdoored matrices with guaranteed mixing properties over large finite fields.
Authors
Mark Braverman, Aayush Jain, Stephen Newman
Abstract
\emph{Trapdoored matrices} are pseudorandom matrices admitting a fast matrix-vector multiplication algorithm given the secret key. We study a candidate family of such matrices: matrices generated by short random \emph{transvection walks} on \(\mathrm{SL}_n(\mathbb{F}_q)\), whose steps are given by adding a random multiple of a random row of the current state to another. We show that the worst-case time for any nonempty set \(\mathcal{S}\subseteq [n]\times[n]\) of matrix entries to come within TV distance \(\varepsilon\leq \frac{1}{4}\) of its stationary marginal under this walk is \(Θ(|\mathcal{S}|+n\log(n/\varepsilon))\), uniformly over all \(\mathcal{S}\) and \(q\geq Q_\mathrm{all}(n)\). This is asymptotically optimal, and resolves open questions about the mixing times of transvection walks. We derive concrete upper and lower bounds for \(n\geq 256\). Surprisingly, our bounds also hold conditioned on the row-pair structure of the walk, except on a fraction at most \(\varepsilon\) of such structures. This implies that these walks may be pseudorandom even after conditioning on the row-pair structure, and therefore that trapdoored matrices built with these walks may be universal. Assuming the conjectured structure-conditioned pseudorandomness of short walks, we exhibit highly efficient, highly parallelizable, and universal trapdoored matrices over \(\mathrm{SL}_n(\mathbb{F}_q)\), \(\mathrm{GL}_n(\mathbb{F}_q)\), and \(\mathbb{F}_q^{n\times n}\). The families over \(\mathrm{SL}_n(\mathbb{F}_q)\) and \(\mathrm{GL}_n(\mathbb{F}_q)\) admit equally efficient trapdoors for their inverses, making them the first to do so for finite-field trapdoored matrices. We discuss attacks, analyzing one in detail, and lay out directions for further investigation.