Source-linked AI summary
Improved Degree Tables for Secure Distributed Matrix Multiplication
John Byrne, Rafael G. L. D'Oliveira, Michael Tait
TL;DR
Secure distributed matrix multiplication seeks to compute a matrix product while protecting both inputs from up to T colluding servers, and degree tables help determine the recovery threshold. This paper develops a periodic-gap framework with two new constructions and proves lower bounds, including a balanced-case result matching SHIFT up to lower-order terms.
Problem
Secure distributed matrix multiplication requires computing AB with server assistance while preventing up to T colluding servers from learning either input; degree tables govern recovery thresholds for these codes.
Source: §I · p. 1Method
The paper develops a periodic-gap framework that includes established degree-table families and yields SHIFT_{r,s} and COVER_r constructions with derived recovery thresholds.
Source: §I · p. 1, A. The Periodic-Gap Framework · p. 3Results
For ordinary integer degree tables, N*(K, L, T) ≥ KL + (KLT^2)^(1/3); when K = L = T = n, N*(n, n, n) = n^2 + 3n^(4/3) + O(n^(7/6)), matching SHIFT up to lower-order terms.
Source: B. Main Contributions · p. 2Takeaways & Limitations
In the balanced setting, the lower bound matches SHIFT up to lower-order terms, making SHIFT asymptotically optimal among degree-table constructions.
Source: B. Main Contributions · p. 2
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
Secure distributed matrix multiplication must recover a matrix product while protecting both inputs from colluding servers. This introduction frames degree-table exponent selection as minimizing the recovery threshold, then presents a periodic-gap framework, two constructions, and new lower bounds.
I. INTRODUCTION
- The degree-table problem is to choose four exponent sets so useful product entries are unique, mask exponents are distinct, and the number of distinct table entries is minimized.That number is the recovery threshold for a sufficiently large field.Source: §I · p. 1
B. Main Contributions
- The new framework contains GASP_r, GASP_{r,s}, and DOG_{r,s} as special cases, introduces SHIFT_{r,s} and COVER_r, and derives their recovery thresholds.The constructions improve prior thresholds in explicit parameter regimes.Source: §I · p. 1, B. Main Contributions · p. 2
I. INTRODUCTION
- Fig. 2 illustrates examples where SHIFT_{2,4} lowers the threshold from 34 to 33 and COVER_2 lowers it from 57 to 56.The comparisons use K = 5, L = 3, T = 4 for SHIFT and K = L = 5, T = 6 for COVER.Source: Figure 2 · p. 2
A. Related Work
- Related work includes integer degree-table schemes –, root-of-unity and pole-number variants –[5], and approaches such as A3S and secure bivariate polynomial coding,.Degree-table methods have also been extended to other settings, including Gram matrix multiplication and private information retrieval [34],.Source: A. Related Work · p. 2
B. Main Contributions
- When T = ur = vs, N_DOG_{r,s} − N_SHIFT_{r,s} = s − r − 1, so SHIFT strictly improves DOG whenever s ≥ r + 2.COVER_r also improves GASP_big in identified regimes, including cases with a new best-known threshold.Source: B. Main Contributions · p. 2
- For ordinary integer degree tables, N*(K, L, T) ≥ KL + (KLT^2)^(1/3), while N*(n, n, n) = n^2 + 3n^(4/3) + O(n^(7/6)), matching SHIFT up to lower-order terms.The balanced result establishes asymptotic optimality among degree-table constructions.Source: B. Main Contributions · p. 2
II. TWO MOTIVATING EXAMPLES
Two examples show how the new constructions reduce recovery thresholds by increasing overlap among interference blocks or making one block redundant. The section then states the convention L ≤ K for the main results.
II. TWO MOTIVATING EXAMPLES
- The examples illustrate two distinct ways to reduce the number of degrees: overlap among interference blocks and complete redundancy of one block.Fig. 2 compares the new degree tables with the previous best constructions.Source: §II · p. 2, A. The SHIFT2,4 Construction for K =… · p. 2, B. The COVER2 Construction for K = L =… · p. 3
A. The SHIFT2,4 Construction for K = 5, L = 3, and T = 4
- The interference blocks’ union has 18 distinct values, giving recovery threshold N = 15 + 18 = 33, one fewer server than the previous best value 34.Source: A. The SHIFT2,4 Construction for K =… · p. 3
B. The COVER2 Construction for K = L = 5 and T = 6
- For K = L = 5, T = 6, COVER_2 has recovery threshold 56, one fewer server than the previous best value 57.A + D is contained in C + D, so that block contributes no new degrees.Source: B. The COVER2 Construction for K = L =… · p. 3
III. MAIN RESULTS
- The main-results discussion assumes L ≤ K, since the K < L case follows from AB = (B^T A^T)^T.It defines [a, b) as the integers from a through b − 1 when a < b, and as empty otherwise.Source: §III · p. 3
A. The Periodic-Gap Framework
The periodic-gap framework builds degree tables from periodically repeated intervals and unifies several established integer-exponent constructions. Its parameters control exponent-set shapes and placements, supporting both existing families and two new constructions.
A. The Periodic-Gap Framework
- A periodic-gap set takes the T smallest elements from width-w intervals repeated every P positions; intervals arise when w ≥ T.For example, gap(5, 7, 2) = {0, 1, 7, 8, 14}.Source: A. The Periodic-Gap Framework · p. 3
- The framework represents C and D as shifted periodic-gap sets, with P, r, and s setting their shapes and the shifts setting their relative placement.P[0, L) denotes {0, P, 2P, …, (L−1)P}.Source: A. The Periodic-Gap Framework · p. 3
- GASP_r uses period K with a width-r periodic-gap set C and interval D, while GASP_{r,s} uses width-r and width-s periodic-gap sets.GASP_r,s keeps the same period and placement as GASP_r but replaces D with a second periodic-gap set.Source: A. The Periodic-Gap Framework · p. 3
- DOG_{r,s} belongs to the framework but uses the larger period P = K + r and a different placement for its two periodic-gap sets.Its sets are C = K + gap(T, P, r) and D = P(L−1) + K + gap(T, P, s).Source: A. The Periodic-Gap Framework · p. 3
- SHIFTr,s increases overlap among interference blocks, while COVERr places one interference block entirely inside another.Both new constructions use periodic-gap sets within the same framework.Source: A. The Periodic-Gap Framework · p. 3
B. The SHIFTr,s Construction
SHIFTr,s changes the placement of periodic-gap exponent sets to increase overlap among interference blocks. Its recovery threshold is derived explicitly, and the construction is decodable and T-secure; under specified conditions it matches or improves on DOGr,s.
B. The SHIFTr,s Construction
- SHIFTr,s is decodable and T-secure, with widths r and s placed to increase overlap among its three interference blocks.The construction sets P = K + r and uses periodic-gap sets with the two widths.Source: B. The SHIFTr,s Construction · pp. 3–4
- N_SHIFTr,s = KL + (u + v − 1)(r + s − 1) + rL is the stated recovery threshold for SHIFTr,s.Here u = ⌈T/r⌉ and v = ⌈T/s⌉ count the blocks in the two periodic-gap sets.Source: B. The SHIFTr,s Construction · pp. 3–4
- When r and s both divide T, SHIFTr,s always matches or improves on DOGr,s.For T = ur = vs, it matches when s = r + 1 and strictly improves when s ≥ r + 2.Source: B. The SHIFTr,s Construction · p. 4
- For K = 5, L = 3, and T = 4, SHIFT2,4 lowers the compared recovery threshold from 34 to 33.The passage identifies 34 as the previous best value in that comparison.Source: B. The SHIFTr,s Construction · p. 4
C. The COVERr Construction
COVERr places the entire A + D interference block inside C + D, making A + D redundant. The construction is decodable and T-secure, and examples show lower recovery thresholds than GASPbig.
C. The COVERr Construction
- COVERr makes A + D redundant by placing the entire block inside C + D.The construction assumes K < T, chooses 1 ≤ r < T, and sets P = K + r.Source: C. The COVERr Construction · p. 4
- COVERr uses D = LP + [0, T) and is decodable and T-secure.Its stated recovery threshold is determined in Theorem 2, but the supplied passage does not give the expression.Source: C. The COVERr Construction · p. 4
- For K = 5, L = 3, and T = 6, COVER3 achieves threshold 40 versus 41 for GASPbig.For odd K ≥ 5 with L = 3 and T = K + 1, choosing r = (K + 1)/2 saves (K − 3)/2 servers over GASPbig.Source: C. The COVERr Construction · p. 4
- For K = L = 5 and T = 6, COVER2 lowers the stated best-known recovery threshold from 57 to 56.COVERr lies in the regime L ≤ K < T, where GASPbig has threshold 2KL + 2T − 1.Source: C. The COVERr Construction · p. 4
D. A General Lower Bound
The paper proves a lower bound on recovery thresholds for all positive integer partitioning and security parameters. In the balanced case, the supplied bound raises the asymptotic order of the excess above n^2 compared with the previously cited bound.
D. A General Lower Bound
- Theorem 3 gives a lower bound on degree-table recovery thresholds for all positive integers K, L, and T.The bound's full expression is not included in the supplied passage.Source: D. A General Lower Bound · p. 4
- For K = L = T = n, the bound gives N⋆(n, n, n) ≥ n^2 + n^(4/3), raising the excess above n^2 from order n to order n^(4/3).The cited earlier bound is n^2 + 3n for n ≥ 2; the passage says the leading coefficient is sharpened in the next subsection.Source: D. A General Lower Bound · p. 4
E. Optimality in the Balanced Regime
In the balanced setting, the paper proves a lower bound on the recovery threshold and shows that SHIFT matches its leading terms, making the construction asymptotically optimal up to lower-order terms.
E. Optimality in the Balanced Regime
- N⋆(n,n,n) ≥ n² + 3n^(4/3) − O(n^(7/6)), raising the excess lower bound above n² to order n^(4/3).The interference bound applies when |A+B|=|A||B|, so the useful degrees are distinct within their block.Source: E. Optimality in the Balanced Regime · p. 4
- N⋆(n,n,n) ≤ n² + 3n^(4/3) + O(n), an upper bound supplied by SHIFT.The corollary obtains the bound by choosing r=⌊n^(1/3)⌋ and s=⌊n^(2/3)⌋ for sufficiently large n.Source: E. Optimality in the Balanced Regime · p. 4
- N⋆(n,n,n)=n²+3n^(4/3)+O(n^(7/6)); SHIFT attains the leading term, leaving possible improvements only in lower-order terms.The n² useful degrees are unavoidable, and the excess is 3n^(4/3)+O(n^(7/6)).Source: E. Optimality in the Balanced Regime · p. 5
IV. PROOFS OF THE MAIN RESULTS
The proof section establishes the paper’s upper and lower bounds by organizing degree-table entries into four blocks and counting their distinct sums.
IV. PROOFS OF THE MAIN RESULTS
- The section proves upper bounds from Theorems 1 and 2 and lower bounds from Theorems 3 and 4.Source: §IV · p. 5
- It represents the exponent vectors as α=(α′,α′′) and β=(β′,β′′), separating data exponents from masking exponents.Source: §IV · p. 5
- The array α⊕β contains pairwise sums and is partitioned into useful UL and interference UR, LL, and LR blocks.For any subarray M, t(M) denotes its set of distinct entries.Source: §IV · p. 5
A. Upper bounds
The upper-bound proofs count distinct degrees across the interference blocks to obtain recovery thresholds for SHIFT, DOG, and COVER constructions.
A. Upper bounds
- For SHIFT, the useful block contributes KL distinct degrees, and the proof counts only new terms as it proceeds through LR, UR, and LL.Its resulting count is KL+(u+v−1)(r+s−1)−2r−2s+2+(u−v−1)+min{K−s+1,(r−ρ−σ+1)+}.Source: A. Upper bounds · pp. 5–6
- For DOG, C+D contributes (u+v−1)(r+s−1) terms and C+B adds Lr; A+D’s first r terms overlap C+B, with remaining gaps in C+D.Source: A. Upper bounds · p. 6
- N_SHIFT(n,n,n)=n²+3n^(4/3)+O(n), using r=⌊n^(1/3)⌋ and s=⌊n^(2/3)⌋ for sufficiently large n.Source: A. Upper bounds · p. 7
- For n=m³, choosing r=m and s=m² gives u=m², v=m, ρ=m, and σ=m² in Theorem 1’s exact formula.Source: A. Upper bounds · p. 7
- COVER’s count is KL+(K+r)(u−1)+T+ρ−1+Lr, with the additional Lr terms arising from C+B below PL.Terms of C+B at least PL are already in C+D; the remaining intervals below PL are disjoint because r<P.Source: A. Upper bounds · p. 7
B. Proof of the General Lower Bound
The general lower-bound proof uses a forbidden equality pattern to force many distinct terms in the LR interference block, yielding a cubic-root lower bound on the excess degrees.
B. Proof of the General Lower Bound
- Decodability forbids two equal UR entries, two equal LL entries, and a matching cross-sum equality unless the masking indices coincide.The proof adds the first two equalities and subtracts the cross-sum, forcing equal UL entries into the same position.Source: B. Proof of the General Lower Bound · p. 7
- If m counts distinct terms outside UL, repeated terms in LL and UR occur in at least LT/m rows and KT/m columns, respectively.Source: B. Proof of the General Lower Bound · pp. 7–8
- The corresponding LR rectangle must contain distinct terms, since any collision would create the forbidden equality pattern.Source: B. Proof of the General Lower Bound · pp. 7–8
- m≥(KLT²)^(1/3), so the total degree count satisfies |t(α⊕β)|≥KL+(KLT²)^(1/3).Source: B. Proof of the General Lower Bound · p. 8
C. Sharpening the lower bound in the balanced regime
In the balanced setting, the proof combines energy estimates with injectivity to sharpen the lower bound on the recovery threshold. It yields N*(n,n,n) ≥ n^2 + 3n^(4/3) − O(n^(7/6)).
C. Sharpening the lower bound in the balanced regime
- For |A| = |B| = |C| = |D| = n, the proof of Theorem 4 combines energy estimates with an injectivity argument.The energy estimates are for sum and difference representation counts of finite sets of real numbers.Source: C. Sharpening the lower bound in the… · p. 8
- The energy argument uses unique sums, |A + B| = |A||B|, which implies |A − B| = |A||B| and difference multiplicities at most one.The proof also uses disjointness of translated copies of B when the corresponding elements of A are distinct.Source: C. Sharpening the lower bound in the… · p. 8
- The proof partitions the interference union by which of its three sum sets has the most representations, then bounds representations outside those parts.Under the assumption |X| < 3n^(4/3), the cited estimates give an O(n^(11/6)) bound on the relevant exceptional representations.Source: C. Sharpening the lower bound in the… · pp. 8–9
- N*(n,n,n) ≥ n^2 + 3n^(4/3) − O(n^(7/6)) for decodable, n-secure degree tables when K = L = T = n.The useful terms are disjoint from the interference union, so the theorem's bound applies to that union.Source: C. Sharpening the lower bound in the… · p. 9