Metraipolis › archive › dc_03e1a3bb3126
Optimal Marginal Mixing for Transvection-Based Trapdoored Matrices over Large Fields — arXiv:2611.05573
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05573
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-05T18:21:00.087Z
- SHA-256 of the archived text
35f3ca9a3ae6d899e0bae462fdbacd6848ee786befedea11ceb3a9140f1f7f11- Stable URL of this page
https://metraipolis.com/documento/dc_03e1a3bb3126
How to cite
Optimal Marginal Mixing for Transvection-Based Trapdoored Matrices over Large Fields — arXiv:2611.05573 — arXiv (en), https://arxiv.org/abs/2611.05573 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_03e1a3bb3126 (Metraipolis archive dc_03e1a3bb3126, sha256 35f3ca9a3ae6d899e0bae462fdbacd6848ee786befedea11ceb3a9140f1f7f11)
BibTeX
@misc{dc03e1a3bb3126,
title = {Optimal Marginal Mixing for Transvection-Based Trapdoored Matrices over Large Fields — arXiv:2611.05573},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05573},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_03e1a3bb3126; sha256 35f3ca9a3ae6d899e0bae462fdbacd6848ee786befedea11ceb3a9140f1f7f11},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05573. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
\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 \(\Theta(|\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.
Tema degli esploratori: fiducia digitale e crittografia (elenco arXiv cs.CR, nuovi lavori del giorno).
Categorie arXiv: Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2611.05573 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:15:18.882Z dalla pagina https://arxiv.org/list/cs.CR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).