CS Paper Radar

Improved Degree Tables for Secure Distributed Matrix Multiplication

John Byrne, Rafael G. L. D'Oliveira, Michael Tait

cs.IT math.CO ·submitted 2026-09-06 19:14 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.76
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

New Minimum Storage Regenerating Codes With Small Sub-packetization Levels for All Admissible Repair Degrees

cs.IT ·2026-10-11 ·Jie Li, Xiaohu Tang, Linqi Song
similarity 0.69
Abstract · 14 pages

In this paper, {we propose a new family of $(n, k)$ Minimum Storage Regenerating (MSR) codes} for distributed storage systems. By structuring the parity-check matrix as a block Vandermonde matrix composed of diagonal matrices and generalized permutation matrices, the proposed code achieves a sub-packetization level of $N = (d-k+1)^{\lceil\frac{n}{2}\rceil}$ and supports any repair degree $k+1\le d<n$. A key innovation of the new construction lies in relaxing the strict commutativity condition previously required for the building blocks in the parity-check matrices of Ye-Barg codes. We introduce a novel proof technique to establish the MDS property without relying on full commutativity, thereby generalizing the applicability of block Vandermonde matrices and enriching the family of Ye-Barg codes. Additionally, the sparsity of the parity-check matrix enhances encoding and decoding efficiency by reducing computational complexity. This work provides new insights into the construction of MSR codes.

0.21

Explicit matrix hitting points for noncommutative algebraic branching programs

cs.CC math.RAmath.CO ·2026-10-11 ·Zhipeng Lu
similarity 0.66
Abstract · 24 pages. There's statement about reproducibility and Lean verification in section 5

We give a deterministic polynomial-resource black-box identity test for noncommutative algebraic branching programs (ABPs), using ordinary matrix evaluations of the output polynomial. Given an alphabet of size $m\ge1$ and an ABP vertex bound $S\ge1$, we construct one fixed tuple of integer matrices of order $R=(m+2)d(d+1)/2$, where $d=(m+2)S$, with entry bit length $O(d\log(d+1))$. Every nonzero polynomial computed by an ABP with at most $S$ vertices has a nonzero evaluation at this tuple. The construction accesses neither the hidden ABP nor its intermediate gates. A rectangular variant improves the order to $O(m^{3/2}S^2)$. Matrix order, description length, and all returned entries are counted; the total resources are polynomial. The result holds in characteristic zero and in characteristic $p>\binom d2$. The main ingredient is a fixed polynomial frame spanning the joint cyclic module of every matrix tuple from every prescribed vector. A compensating block makes a tagged encoding nilpotent of index at most three, while preserving the original cyclic module. A differential exterior-vector argument then gives a single triangular recurrence with polynomially many outputs. Its shared left-linear circuit is converted into actual integer query matrices by coefficient duality. Two-sided pairing further gives deterministic nonadaptive reconstruction of an equivalent ABP from polynomially many output-only matrix queries. The same frame gives polynomial-cardinality explicit trace separators for simultaneous-conjugation orbit closures, and a fixed nilpotent substitution for bounded-dimensional recognizable series. The latter also tests rational formulas whose given syntax is defined at the scalar origin. We provide complete proofs, construction costs, and exact implementation checks.

0.16

Encoding-Sensitive Nullstellensatz Certificates for Syndrome Exclusion in LDPC Codes: Sharp Local Bounds and a Linear Separation

cs.IT ·2026-10-23 ·Malihe Aliasgari, Hassan Khodaiemehr, Khadijeh Bagheri
theory similarity 0.66
Abstract · 48 pages, 4 tables. Extended journal version of a paper submitted to IEEE ITW 2027

Certifying that a parity-check matrix has no nonempty set of at most t variable nodes leaving at most b checks unsatisfied arises in minimum-distance and trapping-set analysis. Such absence is the infeasibility of a polynomial system, provable by an independently checkable Nullstellensatz certificate. The degree of these certificates depends strongly on how the two cardinality constraints are encoded, although the encodings have identical solutions. For a local encoding with inclusion-exclusion and cardinality obstructions, we construct explicit certificates of degree at most t + b + K + 1, with K logarithmic in the maximum check degree; this bound is independent of the block length and cannot be improved in general. For a standard counting encoding, a generalized planted-knapsack theorem, which pulls back a knapsack functional with an arbitrary target, gives lower bounds linear in the block length for cycle codes, regular codes of girth at least six near the feasibility boundary, array-based quasi-cyclic codes and minimum-distance certificates for arrays of circulant permutation matrices, where the local degree stays bounded. On array codes and regular codes of girth at least eight, planted column pairs extend these bounds to odd column weight with no unsatisfied checks. The planting argument is optimal among such pullbacks. All computed degrees and certificates are verified in exact rational arithmetic; bounds are distinguished from exact minimum degrees. Local certificates for quasi-cyclic matrices, including a lifted fifth-generation New Radio base graph, pass two independent verifiers.

0.23

SEC: One-Share Everywhere-Short Secret Sharing from Lossless Expanders

cs.CR cs.IT ·2026-11-12 ·Muhammad Arzaki, Muhammed F. Esgin, Amin Sakzad, Ron Steinfeld
theory similarity 0.65
Abstract · 84 pages, 3 figures. Also available as Cryptology ePrint Archive, Paper 2026/2841: https://eprint.iacr.org/2026/2841

We introduce SEC, an expander-code-based ramp secret sharing scheme over $\mathbb{Z}$-modules, particularly suitable for lattice-based distributed cryptography. It is everywhere-short: bounded secret coefficients yield bounded share coefficients, and the integer reconstruction vectors have bounded entries. Moreover, each participant receives exactly one share, regardless of the number of parties and the privacy and reconstruction thresholds. This improves on prior schemes with bounded share coefficients and bounded entries in the integer reconstruction vectors, in which the number of sub-shares or shares per participant grows either with the number of parties and the threshold or with the security parameter. The construction rests on a coding-theoretic observation: in the bi-adjacency matrix of a lossless bipartite expander, unique-neighbor peeling completes every sufficiently small set of columns to a square unimodular submatrix. We prove correctness, everywhere-shortness, and linearity, and give a publicly computable entrywise bound on the reconstruction vector our algorithm returns for each authorized set. For privacy, we introduce hard-core local leakage resilience, which strengthens the leakage-resilience notion of Nielsen and Simkin (EUROCRYPT 2020) to protect a hard-core function of the secret, and we prove that SEC satisfies it against correlated multi-query local leakage under the MatrixHint-MLWE problem, which admits a reduction from the standard MLWE problem. For $n=60$ participants and security parameter $κ=128$, SEC achieves privacy threshold 6 against $2^{64}$ leakage queries and empirical reconstruction threshold 46. The ideal entropy-coded secret and share sizes are about 3.5 KiB and 6.4 KiB, respectively.

0.31

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

cs.DS cs.CC ·2026-11-02 ·Or Zamir
similarity 0.65
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

Low-Rank Masking for Single-Server Matrix Multiplication

cs.IT cs.CR ·2026-09-16 ·Alejandro Cohen, Rafael G. L. D'Oliveira, Alex Sprintson
theory similarity 0.64
Abstract

We study the statistical privacy of outsourcing matrix multiplication over a finite field ${\mathbb F_q}$ to a single server using additive masks of rank at most $r$. For independent uniform $n\times n$ inputs, we show that uniform \emph{rank-ball masks} and products of independent uniform factors give maximal-correlation secrecy of at most $q^{-r}$ against the complete server view, with $O(n^2r)$ field operations for encoding and decoding. This secrecy captures how effectively the server is prevented from estimating functions of the inputs. We prove an asymptotically matching lower bound of this secrecy measure for $r=o(n)$, showing that both sampling methods are asymptotically optimal among input-independent additive masks of rank at most $r$, even when secret invertible transformations are allowed. We also characterize the posterior distribution for uniform rank-ball masks under arbitrary joint input distributions and prove approximate individual security for rows and columns under independent uniform inputs. Finally, we show that every input-independent additive mask of rank at most $r=o(n)$ requires $δ\to1$ in entry-level $(\varepsilon,δ)$-differential privacy for fixed field size $q$ and bounded $\varepsilon$.

0.10

CPM-LDPC Codes Attaining the Minimum-Distance Bound

cs.IT ·2026-09-15 ·Kenta Kasai
theorycode/data similarity 0.64
Abstract · 13 pages, 1 figure, 2 tables. Verification code and data: https://github.com/kasaikenta/cpm-ldpc-distance

We study binary quasi-cyclic LDPC codes whose parity-check matrices are full arrays of single circulant permutation matrices (CPMs), referred to here as CPM-LDPC codes. Their minimum distance is at most $(J+1)!$, where $J$ is the column weight. For every fixed pair of column and row weights $2\le J<L$, we show that this bound is attained for all sufficiently large integer lift sizes. First, we give one integer exponent matrix independent of the lift size $P$. Second, we show that independent uniform exponent choices attain the bound with probability $1-O_{J,L}(P^{-1})$. Both proofs use cycle conditions required by low-weight codewords and a lower bound on the number of terms in vectors satisfying polynomial check equations. Neither construction requires $P$ to be prime. We also give small-lift arrays attaining the bound 24 for $J=3$, $L=4,\ldots,8$, and arrays with distance at least 28 for $J=4$, $L=5,\ldots,8$, together with computational distance verification.

0.35