CS Paper Radar

Hardness Self-Amplification in Linear Algebra and Fine-Grained Cryptography

Geoffroy Couteau, Nikolas Melissaris, Thejas Radhika Sajith

cs.CC ·submitted 2026-11-03 11:04 UTC · v1

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Worst-Case to Average-Case Reductions for Basic Linear Algebra

cs.DS cs.CC ·2026-11-02 ·Or Zamir
similarity 0.80
Abstract

We study worst-case to average-case reductions for basic linear-algebraic problems over finite fields. A seminal work of Blum, Luby, and Rubinfeld established that any algorithm that successfully multiplies more than $75\%$ of matrix pairs over any finite field, implies an algorithm with essentially the same running time multiplying any pair of matrices. A sequence of follow-ups reduced the needed fraction of successful input pairs to any positive constant. Despite most of the other basic linear algebraic operations being computationally equivalent to matrix multiplication in the worst case, no such worst-case to average-case reductions were known for them. Recently, Vaikuntanathan and Zamir introduced a cryptographic primitive called trapdoor matrices and used them to prove such worst-case to average-case reductions for matrix inversion, solving a linear system, and computing the determinant, all conditioned on common cryptographic assumptions. Our main result is the first unconditional time-preserving worst-case to average-case reduction for matrix inversion. Any algorithm that correctly inverts any constant positive fraction of uniformly random invertible matrices implies a worst-case such algorithm. We also significantly strengthen the conditional reductions based on trapdoored matrices: We establish reductions for deciding invertibility and computing rank at the optimal success thresholds, and qualitatively improve the success threshold needed in the reduction for determinant computation---while previous reductions all required the success probability to be at least $1/2$, we show that any fixed positive average-case success probability suffices for exact worst-case determinant computation over infinitely many finite fields.

0.30

Improved Quantum Random Self-Reduction for Linear Problems

cs.CC quant-ph ·2026-09-30 ·Vahid R. Asadi, Shuichi Hirahara, Nobutaka Shimizu
similarity 0.64
Abstract

We study quantum random self-reductions for linear problems over finite fields. Let $M\in\mathbb{F}^{n\times n}$ be an arbitrary matrix, and let $\mathcal{O}$ be an oracle that agrees with the linear map $x\mapsto Mx$ on an $\varepsilon$-fraction of inputs $x\sim\mathbb{F}^n$. Given coherent access to $\mathcal{O}$ and coherent entry access to $M$, we give a uniform quantum reduction that computes $Mx$ on any prescribed input $x$ with probability at least $2/3$ in time $\widetilde{O}(nT^{1/3})$, for $n\le T\le n^{3/2}$ and constant field size and $\varepsilon$, where $T$ is the cost of one coherent query to $\mathcal{O}$. In particular, when $T=\widetilde{O}(n)$, the reduction runs in time $\widetilde{O}(n^{4/3})$, improving the $\widetilde{O}(n^{3/2}+T)$ reduction of Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA 2024). Our reduction uses the Bogolyubov--Ruzsa subspace guaranteed by additive combinatorics, but it avoids learning this subspace explicitly, which was computationally expensive for the previous reduction; in particular, it does not recover a basis for its orthogonal complement. The main technical step is to decompose the inputs into sparse pieces and find a vector that lies outside the Bogolyubov--Ruzsa subspace via a quantum search based on amplitude amplification. This yields a tunable tradeoff between the cost of querying the average-case oracle and the cost of verifying matrix-vector products.

0.27

Polynomial-Factor Deterministic NP-Hardness for SVP in Every $\ell_p$ Norm with $p>2$

cs.CC ·2026-08-14 ·Isaac M Hair, Amit Sahai
theory similarity 0.63
Abstract

We prove that for every constant $2<p<\infty$, the shortest vector problem in the $\ell_p$ norm is NP-hard to approximate within a polynomial factor under a deterministic reduction. More precisely, for lattices of rank $M$, we obtain a factor of $M^\varepsilon$ for every constant $0<\varepsilon<\min\{(p-2)/(4p),1/8\}$. For $p=\infty$, the same holds for every constant $0<\varepsilon<1/8$. Our reduction adapts OpenAI's encoding of a satisfying assignment for the closest vector problem ("Ten Advances in Mathematics and Theoretical Computer Science"). The encoding has one block of coordinates for each evaluation of a polynomial, with one position for each possible value. We allow the entries in a block to be arbitrary field elements, which can cancel when we take weighted sums of powers of these values. We show that on an unsatisfiable formula, a nonzero codeword with small support must have many nonzero entries in each block it uses. Applying a Hadamard matrix to each block, as in a work by Hair and Sahai (STOC 2026), gives the gap in vector length. The main results of this paper were discovered by Codex / ChatGPT 5.6 Sol Ultra using harness components from the UCLA Moonshot Harness Project, in response to a general strategy suggested by the authors. See the end of the introduction for a discussion.

0.32

Function Tables for Secure Distributed Matrix Multiplication

cs.IT ·2026-09-08 ·Rafael G. L. D'Oliveira, Giulia Gaggero, Arturo Jaramillo Gil, Hiram H. López, Cecilia Martínez-Reyes +1 more
theory similarity 0.63
Abstract

We introduce function tables, an entrywise representation of the coefficient functions that appear in the worker responses of a secure distributed matrix multiplication (SDMM) scheme. We work under the outer-product partition, with $K$ row blocks, $L$ column blocks, and privacy against any $T$ colluding workers, in the general model of linear encoding and linear decoding. In this representation, privacy is a rank condition on the data and mask coefficients, and decodability is linear independence of the desired entries modulo the nuisance space. Degree tables, cyclic-addition tables, and algebraic-geometry constructions are the special cases obtained by restricting the coefficient functions to a structured family; we impose no such restriction, so our converses bind every linear scheme. For $T=1$, we determine the exact optimum over every finite field $\mathbb{F}_q$: it is $KL+K+L$ when $q\geq3$, and $KL+K+L+1$ over $\mathbb{F}_2$, where the identity $z^2=z$ forces one more worker. For arbitrary $T$, we prove $N\geq KL+K+L$ and $N\geq\max\{K,L\}+T$ with no MDS hypothesis on the masks; the first is stronger than the previously known bound $KL+\max\{K,L\}+2T-1$ whenever $\min\{K,L\}\geq2T$. We then reduce field feasibility exactly to MDS existence: a scheme exists over $\mathbb{F}_q$ if and only if an $[\max\{K,L\}+T,T]$ linear MDS code does, and whenever it does, a Cartesian construction attains $N=(K+T)(L+T)$ over that same field. For $T=2$ this makes $q\geq\max\{K,L\}+1$ necessary and sufficient, and we give a projective-line construction with $N=KL+K+L+2$ whenever $KL+K+L$ divides $q-1$; for $K,L\geq2$ it matches the best known worker count while requiring only an element of order $KL+K+L$.

0.25

Strongly Refuting Semirandom Linear Systems in Subexponential Time

cs.DS ·2026-09-24 ·Pravesh K. Kothari, Andrew D. Lin, Peter Manohar
theory similarity 0.62
Abstract

In this paper, we consider the problem of refuting $\mathbb{F}_2$-linear equations with random right-hand sides. Formally, we give a sub-exponential $2^{O(n/\log n)}$-time randomized algorithm that takes as input an arbitrary $m \times n$ matrix $A$ and a uniformly random vector $b \in \mathbb{F}_2^m$, and outputs a witness showing that no assignment satisfies more than a $\frac{1}{2}+ε$ fraction of the equations provided that $m \geq 2^{O(n/\log n)}$. The setting above is the semirandom refutation variant of the famous work [BKW03] that gives a $2^{O(n/\log n)}$-time search algorithm for the learning parity with noise (LPN) problem with $m \geq 2^{O(n/\log n)}$ equations. Building on the search algorithm of [Lyub05], we also give a $2^{O(n/\log \log n)}$-time refutation algorithm that succeeds with only $m \geq n^{1 + γ}$ equations, for a small constant $γ$. Finally, we prove that our algorithm is not captured by the sum-of-squares hierarchy by proving a degree-$Ω(n)$ sum-of-squares lower bound, showing that ''[BKW03]-style'' algorithms achieve better runtime than can be done under sum-of-squares. We thus obtain a natural example of a noise-tolerant signal recovery problem that exhibits a nontrivial gap between the performance of efficient algorithms and that of those based on the sum-of-squares hierarchy.

0.35

One-Sided-Error Parameterized Reductions for the Minimum Distance and Shortest Vector Problems

cs.CC ·2026-08-14 ·Shuichi Hirahara, Kazuki Ogitsuka
theory similarity 0.62
Abstract · Full version of RANDOM 2026

It is notoriously difficult to obtain deterministic reductions for the Minimum Distance Problem (MDP) and the Shortest Vector Problem (SVP). Under two-sided-error randomized reductions, Bennett, Cheraghchi, Guruswami, and Ribeiro (STOC 2023) proved parameterized hardness of approximation for these problems. We partially derandomize their reductions and present one-sided-error randomized reductions: MDP is W[1]-hard to approximate within an arbitrary constant factor under FPT many-one one-sided-error randomized reductions; For every $p \ge 1$, SVP in the $\ell_p$ norm is W[1]-hard to approximate within an arbitrary constant factor below $2^{1/p}$. We demonstrate the usefulness of one-sided-error randomized reductions by showing that they can be conditionally derandomized when the target problem has an OR function. Under a standard hardness-vs-randomness assumption, namely a plausible lower-bound assumption against nondeterministic circuits, we prove a general theorem formalizing this derandomization. Here, an OR function combines several instances into one instance that preserves their disjunction. We construct such OR functions for the relevant MDP and SVP gap problems, and thereby obtain deterministic W[1]-hardness for approximating MDP over every fixed finite field within every constant factor, and for approximating SVP in $\ell_p$ norms for every fixed integer $p$ within every factor below $2^{1/p}$. Applying the same framework to Micciancio's one-sided-error randomized reduction (ToC 2012) yields, under the same circuit lower-bound assumption, deterministic polynomial-time NP-hardness of approximating Euclidean SVP within every constant factor.

0.15

Improved Degree Tables for Secure Distributed Matrix Multiplication

cs.IT math.CO ·2026-09-06 ·John Byrne, Rafael G. L. D'Oliveira, Michael Tait
theory similarity 0.62
Abstract

In secure distributed matrix multiplication, a user wishes to compute the product of two matrices with the assistance of servers, in such a way that any $T$ colluding servers learn nothing about either matrix. Degree tables are a combinatorial tool for constructing polynomial codes for this problem and underlie several state-of-the-art schemes, including $\mathsf{GASP}_r$, $\mathsf{GASP}_{r,s}$, and $\mathsf{DOG}_{r,s}$. We introduce a periodic-gap framework for constructing degree tables that contains these three families as special cases and leads to two new constructions, $\mathsf{SHIFT}_{r,s}$ and $\mathsf{COVER}_r$. We determine their exact recovery thresholds and show that, in many cases, they outperform the current state of the art. We also prove a new lower bound on the recovery threshold of ordinary integer degree tables. In the balanced case, in which the partitioning parameters and the security parameter are equal, we sharpen this bound to match $\mathsf{SHIFT}_{r,s}$ up to lower-order terms, showing that it is asymptotically optimal among degree-table constructions.

0.14

Solving Linear Programs in the Matrix Multiplication Time

cs.DS ·2026-11-05 ·Zhao Song
similarity 0.62
Abstract · 124 pages, 5 figures

We give a randomized algorithm for feasible bounded-box linear programs with $n$ variables and $d\le n=O(d)$ linearly independent equality constraints. For additive accuracy $ε$, its expected running time is $O((n^ω+n^2\log n)\log(1/ε))$, where $ω$ is the matrix multiplication exponent. This answers the matrix-multiplication-time open question posted in Song's Ph.D. thesis [Son19] in this setting.

0.34