Source-linked AI summary
Strongly Multiplicative and 3-Multiplicative Linear Secret Sharing Schemes
Zhifang Zhang, Mulan Liu, Yeow Meng Chee, San Ling, Huaxiong Wang
TL;DR
The paper addresses the open question of efficiently constructing strongly multiplicative LSSS from general LSSS by introducing 3-multiplicative LSSS and studying their relationship to strong multiplicativity. It proves that 3-multiplicativity implies strong multiplicativity, provides code-based constructions, and reduces unbounded fan-in multiplication from five rounds to four. Efficient constructions for general access structures remain open.
Problem
Efficiently constructing strongly multiplicative LSSS from general LSSS remains open, despite their importance as building blocks for secure multiparty computation.
Method
The paper introduces 3-multiplicative LSSS, establishes their relationship with strong multiplicativity, and constructs examples from Reed-Muller and algebraic geometric codes.
Results
3-multiplicative LSSS imply strong multiplicativity, strongly multiplicative LSSS can be efficiently converted into 3-multiplicative LSSS, and unbounded fan-in multiplication drops from five rounds to four.
Takeaways & Limitations
3-multiplicative LSSS may provide easier-to-verify building blocks for secure multiparty computation while supporting lower round complexity.
Takeaways & Limitations
Efficient constructions for general access structures remain open, and the paper’s general constructions can produce exponentially sized schemes.
Abstract
from arXiv · showhide
Strongly multiplicative linear secret sharing schemes (LSSS) have been a powerful tool for constructing secure multiparty computation protocols. However, it remains open whether or not there exist efficient constructions of strongly multiplicative LSSS from general LSSS. In this paper, we propose the new concept of a 3-multiplicative LSSS, and establish its relationship with strongly multiplicative LSSS. More precisely, we show that any 3-multiplicative LSSS is a strongly multiplicative LSSS, but the converse is not true; and that any strongly multiplicative LSSS can be efficiently converted into a 3-multiplicative LSSS. Furthermore, we apply 3-multiplicative LSSS to the computation of unbounded fan-in multiplication, which reduces its round complexity to four (from five of the previous protocol based on strongly multiplicative LSSS). We also give two constructions of 3-multiplicative LSSS from Reed-Muller codes and algebraic geometric codes. We believe that the construction and verification of 3-multiplicative LSSS are easier than those of strongly multiplicative LSSS. This presents a step forward in settling the open problem of efficient constructions of strongly multiplicative LSSS from general LSSS.
1 Introduction
The paper introduces 3-multiplicative LSSS to simplify secure MPC and studies their relationship with strongly multiplicative LSSS. It proves structural relationships, improves multiplication round complexity, and develops construction approaches while leaving efficient general constructions open.
- 1. Introduction: Strongly multiplicative LSSS support secure multiplication against active adversaries, but efficient construction from general LSSS remains open.
- 1. Introduction: 3-multiplicative LSSS generalize multiplicative LSSS by expressing x1x2x3 as a linear combination of local share products.
- 1.1 Our Contribution: 3-multiplicative LSSS reduce unbounded fan-in multiplication from five to four rounds, improving the earlier strongly multiplicative protocol.
- 1.1 Our Contribution: Every 3-multiplicative LSSS is strongly multiplicative, and strongly multiplicative LSSS can be efficiently transformed into 3-multiplicative LSSS.
- 1.1 Our Contribution: The converse fails: the paper constructs a strongly multiplicative LSSS that is not 3-multiplicative.
- 1.1 Our Contribution: Verification is simpler for 3-multiplicativity, and Reed–Muller and algebraic geometric code constructions are given, although efficient general constructions remain open.
2 Preliminaries
The preliminaries define access and adversary structures, LSSS and MSP representations, and multiplicativity properties used to build secure MPC protocols. They also identify an open efficiency problem: existing general constructions of strongly multiplicative LSSS can have exponential size.
- Access and adversary structures: An access structure lists authorized player subsets, while an adversary structure lists potentially corrupted subsets; both have monotonicity properties.Authorized sets remain authorized when enlarged, whereas corrupted sets remain possible when reduced.
- Secret sharing and MSPs: An LSSS reconstructs secrets from authorized shares while revealing no information to unauthorized subsets, and linear LSSS use linear reconstruction over a finite field.The scheme is linear when the secret domain is K, randomness is K^(l−1), shares are vector spaces over K, and reconstruction is linear.
- Secret sharing and MSPs: An MSP of size d computes an access structure exactly when the corresponding LSSS of size d realizes it.The target vector lies in the span of rows labeled by a player set precisely when that set is authorized.
- Secret sharing and MSPs: An MSP with target vector e1 yields an LSSS by randomizing the remaining coordinates and distributing labeled row combinations as player shares.For secret s, the dealer samples ρ ∈ K^(l−1), computes M(s,ρ)^T, and sends each player the rows assigned to that player.
- Multiplicativity: Multiplicativity enables products of secrets to be reconstructed from local products of shares, while strong multiplicativity requires this after restricting to every possible corrupted subset.The access-structure characterization states that multiplicative LSSS exist exactly for Q2 structures, and strongly multiplicative LSSS exactly for Q3 structures.
- Construction challenge: Existing general constructions can transform a general LSSS into a multiplicative one efficiently, but general strongly multiplicative constructions remain open and known alternatives may be exponential.The two constructions described for strongly multiplicative LSSS produce exponential-size schemes and are therefore not efficient in general.
3 3-Multiplicative and λ-Multiplicative LSSS
This section introduces 3-multiplicative LSSS as a triple-product analogue of multiplicativity and generalizes the idea to λ products. It characterizes existence through Qλ conditions and connects these schemes to strongly multiplicative LSSS and reduced-round multiplication.
- MSP characterization: The matrix diamond product represents local pairwise multiplication by forming columns M_i ⋄ M_j, producing a matrix with nΣ_i d_i rows and l^2 columns.The induced row labeling assigns each product entry to the player owning both original entries.
- 3-multiplicativity: 3-multiplicativity extends the diamond product to entries x_i y_j z_k belonging to the same player and requires a recombination vector for reconstructing triple products.Its equivalent MSP condition is e1 ∈ span(M ⋄ M ⋄ M).
- 3-multiplicativity: A 3-multiplicative LSSS exists for an access structure if and only if the structure is Q3.The necessity follows because three adversary sets covering all players would make the corresponding triple local products vanish, contradicting 3-multiplicativity.
- Implications and constructions: A strongly multiplicative LSSS can be used to construct a 3-multiplicative LSSS, while Shamir-based general constructions have exponential complexity.λ-multiplicative schemes can reduce sequential-multiplication round complexity by a factor of 1/log λ in suitable cases, although Qλ is not necessary for secure computation itself.
- λ-multiplicativity: The λ-multiplicative generalization uses the diamond product of λ copies of an LSSS and supports reconstruction of products of λ secret values from local share products.The associated existence criterion is Qλ for λ-multiplicative schemes and Qλ+1 for strongly λ-multiplicative schemes.
4 Strong Multiplicativity and 3-Multiplicativity
The paper establishes a close relationship between 3-multiplicative and strongly multiplicative LSSS: 3-multiplicativity implies strong multiplicativity, while strong multiplicativity can be efficiently transformed into 3-multiplicativity.
- 3-multiplicative LSSS are algebraically defined and easier to verify than strongly multiplicative LSSS, whose verification requires conditions for every relevant adversary subset.The 3-multiplicative check requires one span condition, whereas strong multiplicativity requires multiple subset-indexed conditions.
- An efficient construction transforms any strongly multiplicative LSSS for a Q3 access structure into a 3-multiplicative LSSS.The construction combines the original scheme with a dual MSP derived from a diamond product.
- O(d^2) is the resulting scheme size when the input strongly multiplicative LSSS has size d.Theorem 2 gives this bound for Q3 access structures.
- The construction generalizes: a strongly λ-multiplicative LSSS yields a (λ + 1)-multiplicative LSSS of size O(d^λ).The generalized transformation applies to Qλ+1 access structures.
- 3-multiplicative LSSS are strongly multiplicative, but the converse fails.The paper provides an example of a strongly multiplicative LSSS that is not 3-multiplicative.
5 Constructions for 3-multiplicative LSSS
The paper presents two generally inefficient constructions of 3-multiplicative LSSS, based on Reed-Muller codes and algebraic geometric codes, and derives conditions guaranteeing λ-multiplicativity.
- Motivation: Polynomial-size 3-multiplicative LSSS remain difficult to construct for general Q3 access structures, and the presented general constructions may have exponential size.The paper identifies this inefficiency as a limitation of the two constructions.
- Reed-Muller codes: Reed-Muller-code schemes are λ-multiplicative LSSS whenever m > λr.For λ = 3, this gives 3-multiplicativity when m > 3r.
- Reed-Muller codes: The Reed-Muller construction takes f(v0) as the secret and distributes f(vi) as player Pi’s share.The code evaluates low-degree polynomials over all points of F2^m.
- Reed-Muller codes: The Reed-Muller proof uses products of three codewords, whose polynomial product has degree at most 3r, together with the dual-code structure.This establishes the required reconstruction identity for three shared values.
- Algebraic geometric codes: Algebraic geometric codes yield λ-multiplicative ramp LSSS under explicit curve, divisor, and degree conditions.These schemes retain the ramp property: sufficiently many players can recover the secret while fewer players have no information.
- Algebraic geometric codes: For the AG-code construction, λ-multiplicativity holds when m ≥ (λ−1)(n−1) + 2g.The theorem assumes an absolutely irreducible, projective, nonsingular curve and 2g −2 < m < n + 1, with supp(G) disjoint from D.
6 Implications of the Multiplicativity of LSSS
The paper connects 3-multiplicativity to MPC protocol efficiency: it supports secure computation against active adversaries, simplifies verification, and reduces unbounded fan-in multiplication from five rounds to four.
- Implications: 3-multiplicativity implies strong multiplicativity and is sufficient for building MPC protocols against active adversaries.Its verification requires checking conditions rather than an exponential number of equations associated with strong multiplicativity.
- MPC protocols: 3-multiplicative LSSS simplify local computation and reduce MPC round complexity for computing products of an arbitrary number of field elements.The round count is constant and independent of the number of multiplied inputs.
- MPC protocols: Four rounds replace five for unbounded fan-in multiplication when using a 3-multiplicative LSSS instead of a strongly multiplicative LSSS.The reduction occurs because Step (2) needs one interaction round rather than two.
- Applications: The round-complexity reduction also simplifies polynomial evaluation and solving linear systems of equations.These applications are stated as consequences of the improved unbounded fan-in multiplication procedure.
- Open problems: An efficient transformation from strongly λ-multiplicative LSSS to λ+1-multiplicative LSSS exists, while the reverse transformation remains open for Qλ+1 access structures.For λ = 2, this is the stated open problem of efficiently obtaining strongly multiplicative LSSS from general LSSS.
7 Conclusions
The paper proposes 3-multiplicative LSSS as a subclass of strongly multiplicative LSSS that may be easier to construct and verify while improving MPC round complexity. Efficient constructions for general access structures remain open.
- Conclusions: 3-multiplicative LSSS form a subclass of strongly multiplicative LSSS and can simplify secure multiparty computation.The paper presents them as candidate building blocks for further MPC research.
- Conclusions: 3-multiplicative LSSS are believed to be easier to construct and verify than strongly multiplicative LSSS.The paper specifically notes that efficient constructions for general access structures remain unresolved.
- Open problems: Efficient constructions of 3-multiplicative LSSS for general access structures remain an important open problem.This scope boundary limits the paper’s construction results beyond specific code-based settings.