Metraipolis › archive › dc_cb6fb3e02e48

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-04T19:07:52.345Z
SHA-256 of the archived text
3b3578617b79a3046127b2e50d95f24793c6d53c07999d6fba6f329e67cca53a
Stable URL of this page
https://metraipolis.com/documento/dc_cb6fb3e02e48

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_cb6fb3e02e48 (Metraipolis archive dc_cb6fb3e02e48, sha256 3b3578617b79a3046127b2e50d95f24793c6d53c07999d6fba6f329e67cca53a)
BibTeX
@misc{dccb6fb3e02e48,
  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_cb6fb3e02e48; sha256 3b3578617b79a3046127b2e50d95f24793c6d53c07999d6fba6f329e67cca53a},
  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-04T18:41:25.366Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).