PaperlayerView exact revision on arXiv

Source-linked AI summary

Function Tables for Secure Distributed Matrix Multiplication

Rafael G. L. D'Oliveira, Giulia Gaggero, Arturo Jaramillo Gil, Hiram H. López, Cecilia Martínez-Reyes, Divyesh Vaghasiya

arXiv:2609.08154v1cs.ITmath.IT

TL;DR

The paper asks how many workers and which fields support private secure distributed matrix multiplication against colluding workers. It uses unrestricted function tables to analyze linear schemes, establishing exact and general worker bounds, field-feasibility criteria, and constructions.

  • Problem

    The paper asks how many workers and which fields support secure distributed matrix multiplication while keeping inputs private against colluding workers.

    Source: §I · p. 1

  • Method

    Function tables represent coefficient functions and their pointwise products without restricting schemes to structured families.

    Source: §I · p. 2

  • Results

    The paper determines the exact T = 1 optimum, proves worker lower bounds for arbitrary T, and characterizes field feasibility by MDS-code existence.

    Source: B. Summary of Results · p. 3

  • Takeaways & Limitations

    The framework and its bounds apply to every linear scheme in the stated model, not only constructions based on structured coefficient functions.

    Source: §I · p. 2, B. Summary of Results · p. 3

Abstract

from arXiv · show

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

I. INTRODUCTION

The paper studies how many workers and which fields are needed for private secure distributed matrix multiplication under the outer-product partition. It introduces function tables to represent general linear schemes and study their worker requirements without restricting coefficient functions to structured families.

I. INTRODUCTION

  • The paper asks how many workers and which fields support secure multiplication of K row blocks by L column blocks against colluding workers.It focuses on the outer-product partition and linear encoding and decoding.Source: §I · p. 1
  • The user encodes both inputs with independent random masks, sends encoded pairs to workers, and combines their returned products to recover the block products.Privacy requires that any at most T workers' observations reveal no information about the inputs.Source: §I · p. 1

A. Related Work

  • Existing degree, cyclic, and algebraic-geometry constructions choose structured coefficient-function families and study how their products combine.Degree tables use sums of polynomial degrees, cyclic constructions combine degrees modulo a cycle, and algebraic-geometry tables record products of curve functions.Source: §I · p. 2

I. INTRODUCTION

  • Function tables represent every linear scheme in the model, while degree, cyclic, and related algebraic tables arise by restricting the coefficient functions.The framework supports construction of general linear schemes and proofs of bounds.Source: §I · p. 2

A. Related Work

  • For T = 1, prior constructions attain KL+K+L over suitable fields, but the optimum across all fields in the full linear model was unresolved.The paper focuses on worker responses in a fixed-block, one-product, full-response model; the response-count equivalence does not extend to multi-message or compressed-response schemes.Source: A. Related Work · p. 2
  • For T = 2, prior constructions span several worker counts, while the earlier MDS-mask converse gives N ≥ KL + max{K, L} + 2T − 1.Other partitions, precomputation, and compressed-response settings can change the worker-count comparisons or decoding model.Source: A. Related Work · pp. 2–3

B. Summary of Results

The paper introduces function tables as an entrywise representation of linear SDMM schemes, with privacy and decodability expressed through rank and independence conditions. It establishes exact and general worker bounds, field-feasibility criteria, and constructions with different worker-count and field-size tradeoffs.

B. Summary of Results

  • For T = 1, the exact minimum is KL + K + L workers when q ≥3 and KL + K + L + 1 when q = 2.The optimum is determined for every K, L, and finite field.Source: B. Summary of Results · p. 3
  • For arbitrary T, every private linearly decodable scheme satisfies N ≥ max{KL+K+L, T + max{K, L}}.These bounds also imply mask coefficient restrictions generating [K + T, T] and [L + T, T] linear MDS codes.Source: B. Summary of Results · p. 3
  • A scheme exists over Fq exactly when an [max{K, L}+T, T] linear MDS code exists; when it does, a Cartesian construction uses (K + T)(L + T) workers.For T = 2, existence is equivalent to q ≥ max{K, L} + 1.Source: B. Summary of Results · p. 3
  • For T = 2, the projective-line construction uses KL + K + L + 2 workers when KL + K + L divides q − 1.For K, L ≥2, its worker count matches CATx and requires an element of order KL + K + L.Source: B. Summary of Results · p. 3

A. The Function-Table Framework

  • A function table has coefficient functions as row and column labels, with their pointwise products as entries; desired products and mask-involving nuisance terms occupy distinct entries.The desired entries span AB, while nuisance entries span AV + UB + UV.Source: A. The Function-Table Framework · p. 3
  • Linear decodability holds exactly when the desired entries are linearly independent modulo the nuisance space.Equivalently, no nonzero linear combination of desired entries belongs to that space.Source: A. The Function-Table Framework · p. 3
  • Privacy for a worker set is equivalent to equality of the data-and-mask coefficient ranks with the mask ranks on both inputs.Full-rank mask restrictions on every set of at most T workers are a sufficient T-privacy condition.Source: A. The Function-Table Framework · pp. 3–4

B. Optimal Schemes for T = 1

The paper establishes exact worker counts for T=1, general worker lower bounds and field-feasibility criteria, and a T=2 projective-line construction with a near-optimal worker count.

B. Optimal Schemes for T = 1

  • For T=1, the exact minimum is KL+K+L workers when q≥3 and KL+K+L+1 when q=2.Over nonbinary fields, sharing a nonconstant function saves one nuisance dimension; over F2, z^2=z prevents that saving.Source: B. Optimal Schemes for T = 1 · p. 4

C. General Bounds and Field Feasibility

  • Every scheme requires N≥KL+K+L and N≥T+max{K,L}, without requiring either complete mask matrix to be MDS.The two MDS restrictions may apply to different worker subsets.Source: C. General Bounds and Field Feasibility · p. 4
  • A scheme exists over Fq exactly when an [max{K,L}+T,T] linear MDS code exists, and then a Cartesian construction uses (K+T)(L+T) workers.For T=2, existence is equivalent to q≥max{K,L}+1.Source: C. General Bounds and Field Feasibility · p. 4

D. The Projective-Line Construction for T = 2

  • When KL+K+L divides q−1, the T=2 projective-line construction uses KL+K+L+2 workers, within two of the lower bound.For K,L≥2, it matches CATx's worker count while requiring an element of order KL+K+L.Source: D. The Projective-Line Construction… · pp. 4–5

III. EXAMPLES

The examples instantiate function tables through explicit coefficient functions and worker encodings, verifying privacy and decodability for optimal T=1 schemes and a Cartesian construction over F4.

III. EXAMPLES

A. Optimal T = 1 Schemes over F3 and F2

  • Eight workers over F3 and nine over F2 are optimal for K=L=2 and T=1; over F2, z^2=z prevents the one-worker saving.The desired entries are linearly independent modulo nuisance functions in both constructions, and constant nonzero masks provide T=1 privacy.Source: A. Optimal T = 1 Schemes over F3 and F2 · pp. 5–6

B. The Cartesian Construction over F4

  • The Cartesian construction uses 25 workers over F4 for K=L=3 and T=2, the smallest possible field for these parameters.Tensor products make the table entries linearly independent, while repeated mask rows still provide privacy against two workers; the complete mask matrices are not MDS.Source: B. The Cartesian Construction over F4 · p. 6

C. The Projective-Line Construction over F16

A projective-line function table yields a private, linearly decodable 17-worker scheme over F16 for K = L = 3 and T = 2. Its evaluation points and exponent identifications produce independent desired entries modulo the nuisance space.

C. The Projective-Line Construction over F16

  • The construction evaluates homogeneous functions at the 17 points of P1(F16), identifying exponents modulo 15 except for endpoint functions h0 and h20.At nonzero points, t^15 = 1; the endpoints distinguish h0 from h20.Source: C. The Projective-Line Construction… · p. 7
  • The nine desired entries have labels 5, 6, 7, 9, 10, 11, 13, 14, and 15, while the nuisance labels complete the 17 independent labels.Thus, the desired functions are linearly independent modulo the nuisance space, giving decodability.Source: C. The Projective-Line Construction… · p. 7
  • Both mask coefficient matrices have every pair of rows linearly independent, so the scheme is private against any two workers.On the A-side, the map t → t^4 permutes the nonzero elements of F16 because gcd(4, 15) = 1; the B-side uses (1, t).Source: C. The Projective-Line Construction… · p. 7
  • 17 workers over F16 give a private, linearly decodable scheme for K = L = 3 and T = 2, matching CATx's worker count while using a smaller field than its F103 requirement.CATx requires a primitive seventeenth root of unity, so its smallest admissible field is F103.Source: C. The Projective-Line Construction… · p. 7

IV. DECODABILITY AND PRIVACY

Decodability is equivalent to linear independence of desired entries modulo the nuisance space. This characterization yields a worker-count bound from the dimensions of the desired and nuisance spaces.

A. Decodability

  • A decoding vector cancels nuisance terms by annihilating every function in the nuisance space, while selecting the coefficient of one desired entry.The converse argument isolates data-block pairs and mask terms to establish these conditions for each desired entry.Source: A. Decodability · pp. 7–8
  • The scheme is linearly decodable exactly when the desired entries are linearly independent modulo the nuisance space.Equivalently, no nonzero linear combination of desired entries belongs to that space.Source: A. Decodability · p. 8
  • A linearly decodable function table requires N ≥ KL + dim N, since the desired entries contribute KL independent classes in the quotient by the nuisance space.The quotient has dimension N − dim N.Source: A. Decodability · p. 8

B. Privacy

Privacy against a fixed worker set is characterized exactly by rank equalities between the restricted data and mask coefficient matrices. The mask matrices need not have independent rows if their linear relations also annihilate the data coefficients.

B. Privacy

  • Privacy holds exactly when rank[Aτ Uτ] = rank Uτ and rank[Bτ Vτ] = rank Vτ.These equalities mean the restricted data coefficient columns lie in the corresponding mask-column spans.Source: B. Privacy · p. 8
  • The rank conditions make each worker-set observation distribution independent of the inputs because the data shifts can be absorbed into the independent uniform masks.The argument applies to both encoded matrices and their joint observations.Source: B. Privacy · p. 8
  • The MDS mask condition is sufficient but not necessary: dependent mask rows are allowed when every relation among them also annihilates the data coefficients.Under the T-MDS condition, the mask rows span the entire restricted worker-coordinate space, which ensures privacy.Source: B. Privacy · pp. 8–9

V. OPTIMALITY FOR T = 1

For T = 1, the construction uses KL + K + L workers over fields with q ≥ 3, and one additional worker over F2. The converse establishes the matching nuisance-dimension requirements.

V. OPTIMALITY FOR T = 1

  • The converse normalizes the two mask functions to 1 and forces nuisance dimension at least K + L, with one additional dimension unavoidable over F2.This supplies the lower-bound requirements matching the two constructions.Source: §V · p. 9

A. Achievability

  • The nonbinary construction shares one nonconstant function across both sides, reducing nuisance dimension by one while its square remains distinct.The construction uses this distinction to reach the K + L nuisance-function count.Source: A. Achievability · p. 9
  • KL + K + L workers suffice when q ≥ 3, using KL desired functions and K + L nuisance functions that remain linearly independent after selecting worker points.The resulting scheme is linearly decodable and private against any single worker.Source: A. Achievability · p. 9
  • Over F2, KL + K + L + 1 workers suffice because all KL + K + L + 1 selected functions are distinct squarefree monomials.The construction is linearly decodable and private against any single worker.Source: A. Achievability · p. 9

B. Converse

The converse normalizes the masks for T=1 and bounds the nuisance space through the overlap of the two data-function spaces. It yields a stronger worker lower bound over F2 than the general bound.

B. Converse

  • For T=1, masks can be normalized to u1=v1=1 without increasing the number of workers.The proof removes workers with zero responses, then applies invertible rescalings.Source: B. Converse · pp. 9–10
  • With constant masks, dim N ≥ K+L; over F2, dim N ≥ K+L+1.The proof bounds the overlap of the spaces spanned by the constant function and each side’s data functions.Source: B. Converse · p. 10
  • The data functions on each side are linearly independent together with the constant function, giving dim P=K+1 and dim Q=L+1.Decodability rules out a nonzero combination of these data functions lying in the nuisance space.Source: B. Converse · p. 10
  • N ≥ KL+K+L generally, and N ≥ KL+K+L+1 over F2.The binary-field bound follows from the identity h^2=h.Source: B. Converse · p. 10

VI. GENERAL LOWER BOUND

The general lower bound reduces arbitrary mask spaces to a constant-mask case over an extension field. The field-feasibility analysis derives MDS restrictions on worker subsets and uses them to guide constructions.

VI. GENERAL LOWER BOUND

  • N ≥ KL+K+L follows by normalizing masks over an extension field and applying the constant-mask bound to an auxiliary decodable table.A nonvanishing function in each mask space enables pointwise division; the extension field is chosen with size greater than N.Source: §VI · pp. 10–11

VII. FIELD FEASIBILITY

  • Field feasibility is addressed by finding MDS restrictions within every private, linearly decodable scheme and using the required MDS codes in a construction.The section states this as its two-step approach.Source: §VII · p. 11

A. Necessary MDS Restrictions

  • The mask coefficients contain restrictions generating [K+T,T] and [L+T,T] linear MDS codes, which imply N ≥ max{K,L}+T.The two restrictions may occur on different worker sets.Source: A. Necessary MDS Restrictions · p. 11

B. The Cartesian Construction

The Cartesian construction pairs encodings from the two sides to form a function table. Its product basis gives linear decodability, while the MDS properties support privacy against up to T colluding workers.

B. The Cartesian Construction

  • A scheme must have an [max{K,L}+T,T] linear MDS code, by the restrictions on the two mask sides.One of the required [K+T,T] and [L+T,T] codes has the stated length.Source: B. The Cartesian Construction · p. 11
  • (K+T)(L+T) workers are used by pairing K+T A-side encodings with L+T B-side encodings.The A-side coefficients depend only on the first worker coordinate, and the B-side coefficients only on the second.Source: B. The Cartesian Construction · pp. 11–12
  • The Cartesian products of basis functions form a basis on the worker grid, making the desired entries linearly independent modulo the nuisance space.This establishes linear decodability for the construction.Source: B. The Cartesian Construction · p. 12
  • The construction satisfies T-privacy because the MDS property preserves the rank condition despite repeated rows among workers sharing a coordinate.The proof applies the rank argument separately to the first- and second-coordinate sets.Source: B. The Cartesian Construction · p. 12

C. Field-Size Consequences

MDS length bounds translate field size into necessary and sufficient conditions for scheme construction. For T=2, the resulting field-size threshold is exact.

C. Field-Size Consequences

  • For T≥2, q ≥ max{K,L}+1 is necessary, while q ≥ max{K,L}+T−1 is sufficient for a scheme.The sufficient condition uses an extended Reed–Solomon code and the field-feasibility result.Source: C. Field-Size Consequences · p. 12
  • When max{K,L}≥2, the dual-code argument also requires q≥T+1.This follows by applying the MDS length bound to the dual code.Source: C. Field-Size Consequences · p. 12
  • For T=2, q ≥ max{K,L}+1 is necessary and sufficient.The necessary and sufficient bounds coincide in this case.Source: C. Field-Size Consequences · p. 12
  • If the mask coefficients satisfy the T-MDS condition on all workers, then N≤q+T−1.The proof counts one-dimensional subspaces in a two-dimensional quotient over Fq.Source: C. Field-Size Consequences · p. 12

VIII. THE PROJECTIVE-LINE CONSTRUCTION FOR T = 2

The T = 2 projective-line construction uses homogeneous monomials evaluated on a multiplicative subgroup and the additional points 0 and ∞. When KL+K+L divides q−1, it is linearly decodable and 2-private with KL+K+L+2 workers.

VIII. THE PROJECTIVE-LINE CONSTRUCTION FOR T = 2

  • The row and column data functions are homogeneous monomials, and pointwise multiplication gives the corresponding product functions.The construction sets ak=fk and bℓ=gℓd, with two mask functions on each side.Source: §VIII · p. 12
  • The construction maps exponent sums modulo m to labels 1 through m, but keeps sums 0 and D separate as 0 and ∞.On subgroup points, exponents congruent modulo m agree; the endpoints distinguish the exceptional sums that would otherwise collide with desired entries.Source: §VIII · p. 13
  • The functions h0, h1, …, hm, and hD form a basis, so the desired entries are linearly independent modulo the nuisance space.The desired and nuisance labels occupy disjoint parts of this basis, which establishes linear decodability.Source: §VIII · pp. 13–14
  • Any two mask-coefficient rows are linearly independent on each side, yielding 2-privacy.The subgroup rows are distinct, and the workers at 0 and ∞ supply the endpoint rows; both mask families satisfy the 2-MDS mask condition.Source: §VIII · p. 14
  • KL+K+L+2 workers suffice for a linearly decodable, 2-private projective-line scheme when KL+K+L divides q−1.The divisibility condition guarantees the required subgroup; the construction uses m+2 workers, with m=KL+K+L.Source: §VIII · pp. 13–14

Related papers

Loading 2609.08154v1…