Metraipolis › archive › dc_fcaa4e1e0b79
Hardness Self-Amplification in Linear Algebra and Fine-Grained Cryptography — arXiv:2611.04680
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04680
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T13:00:26.804Z
- SHA-256 of the archived text
91cdb4d71c7ff1be1aee604042eb947f9e05784db4b58271a658e49e287079db- Stable URL of this page
https://metraipolis.com/documento/dc_fcaa4e1e0b79
How to cite
Hardness Self-Amplification in Linear Algebra and Fine-Grained Cryptography — arXiv:2611.04680 — arXiv (en), https://arxiv.org/abs/2611.04680 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fcaa4e1e0b79 (Metraipolis archive dc_fcaa4e1e0b79, sha256 91cdb4d71c7ff1be1aee604042eb947f9e05784db4b58271a658e49e287079db)
BibTeX
@misc{dcfcaa4e1e0b79,
title = {Hardness Self-Amplification in Linear Algebra and Fine-Grained Cryptography — arXiv:2611.04680},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04680},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fcaa4e1e0b79; sha256 91cdb4d71c7ff1be1aee604042eb947f9e05784db4b58271a658e49e287079db},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04680. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the possibility of basing fine-grained cryptography on the hardness of fundamental problems in linear algebra. Our main technical contribution is a hardness self-amplification method based on random low-rank updates: we show how to turn an algorithm that solves an inverse-polynomial fraction of random linear systems into a solver which succeeds for every right-hand side of almost every matrix. Our reduction increases the runtime only linearly in the inverse of the original success probability. In particular, this yields fine-grained one-way functions from the almost worst-case hardness of linear systems over large enough fields. Using the same approach, we also obtain tighter worst-case to average-case reductions for matrix multiplication and online matrix-vector multiplication, as well as variants of our reductions that recover exact solutions from approximate algorithms, whose expected coordinate agreement is only $1/q+\varepsilon$, with inverse-quadratic dependence on $\varepsilon$ up to logarithmic factors, over every finite field. Finally, we also use it to connect the existence of fine-grained key agreement to the problem of computing the rank of a matrix: over a suitable sequence of growing characteristic-two fields, the almost-everywhere average-case hardness of rank computation (for any of a large class of distributions) implies infinitely-often fine-grained key agreement. Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno). Categorie arXiv: Computational Complexity (cs.CC). Pagina del lavoro: https://arxiv.org/abs/2611.04680 — 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-04T12:35:32.299Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).