Modern cryptography relies heavily on the elegant properties of finite fields. In a finite field, arithmetic behaves perfectly: you can add, subtract, multiply, and crucially, divide by any non-zero element. This makes finite fields the natural home for Shamir’s secret sharing and Secure Multi-Party Computation (MPC).
To share a secret using Shamir's scheme, one hides the secret as the intercept of a random polynomial $f(x)$ and distributes evaluations $f(x_i)$ to different parties. Reconstructing the secret requires Lagrange interpolation, a process that inherently requires dividing by the differences between evaluation points $(x_i - x_j)$. Because every non-zero element in a finite field has a multiplicative inverse, finding distinct evaluation points is trivial.
However, real-world computing does not happen in finite fields; it happens in rings. Modern CPUs perform arithmetic modulo $2^{32}$ or $2^{64}$, which are rings ($\mathbb{Z}/2^k\mathbb{Z}$) containing numerous elements that lack multiplicative inverses (specifically, all even numbers). Furthermore, advanced applications like privacy-preserving machine learning operate on matrices, which form non-commutative rings where the order of multiplication matters and zero-divisors abound.
As noted by Desmedt et al. and Abspoel et al., forcing ring-based applications into field-based MPC protocols introduces massive computational overhead. This has driven a major research direction: generalizing secret sharing and MPC to operate directly over rings, polynomial rings, and non-commutative algebraic structures.
The Evaluation Point Bottleneck in Finite Rings
If we attempt to implement Shamir’s secret sharing directly over a ring like $\mathbb{Z}/2^k\mathbb{Z}$, we immediately run into a mathematical wall. To reconstruct the secret, the differences between the chosen evaluation points $x_i$ must be invertible. In $\mathbb{Z}/2^k\mathbb{Z}$, an element is invertible if and only if it is odd. Consequently, the difference between any two evaluation points must be odd, which strictly limits us to at most two valid evaluation points (one even, one odd). This makes large-scale secret sharing impossible.
To overcome this bottleneck, Abspoel et al. proposed shifting the computation from the base ring to an algebraic extension known as a Galois ring.
$$\mathbb{Z}/p^k\mathbb{Z} \quad \xrightarrow{\text{Extension}} \quad GR(p^k, d)$$
A Galois ring possesses a structural component called a residue field, which behaves like a standard finite field. By choosing a sufficiently large extension degree $d$, the residue field provides an abundant supply of elements whose differences are guaranteed to be invertible within the larger Galois ring. The authors demonstrated that this algebraic framework allows Shamir-style secret sharing to scale to an arbitrary number of participants while maintaining native compatibility with the underlying CPU-friendly base ring.
However, moving to Galois rings introduces a new challenge for MPC: the multiplicative property. In MPC, parties need to securely multiply two shared secrets by multiplying their individual shares locally. While this property is well-understood in finite fields, Abspoel et al. showed that the multiplicative property does not automatically transfer when lifting cryptographic codes to Galois rings, requiring specialized linear secret sharing schemes (LSSS) to ensure secure multiplication gates.
Navigating Non-Commutativity and Zero Divisors
While Galois rings solve the problem for commutative structures like integers modulo $2^k$, they do not apply to matrix rings, where multiplication is non-commutative ($A \cdot B \neq B \cdot A$). Machine learning models rely heavily on matrix multiplications, making direct MPC over non-commutative rings highly desirable.
As Dalskov et al. argue, traditional MPC protocols break down in these environments because they assume that scalars and shares commute during secret reconstruction and verification. Furthermore, non-commutative rings often contain zero divisors—non-zero elements that multiply together to equal zero—which complicates security proofs that traditionally rely on the cancellation properties of fields.
To resolve this, Escudero et al. generalized Shamir's scheme by decoupling it into distinct left and right linear secret sharing schemes.
┌───────────────────────────┐
│ Secret Matrix M │
└─────────────┬─────────────┘
│
┌─────────┴─────────┐
▼ ▼
Left-LSSS Shares Right-LSSS Shares
(Handles Left- (Handles Right-
Multiplication) Multiplication)
By tracking how shares are multiplied on the left versus the right, the authors made it possible to compute arbitrary matrix circuits without needing to decompose matrices into individual, scalar-field elements. This architectural shift allows fully secure MPC protocols to run efficiently over any finite ring, as further advanced by Dalskov et al. to guarantee output delivery even in the presence of malicious adversaries.
Unification via Polynomial Rings and the Chinese Remainder Theorem
Another powerful facet of this research direction focuses on polynomial rings as a foundational tool to unify and extend secret sharing paradigms.
Instead of evaluating a polynomial at scalar points, why not operate entirely within a ring of polynomials? Cao et al. demonstrated that evaluating polynomials whose coefficients represent the secret over a polynomial ring provides an elegant, non-ad-hoc mechanism for constructing evolving secret sharing schemes, where the threshold and the number of participants can grow dynamically over time.
This polynomial approach also bridges the gap between competing secret sharing philosophies. Historically, there have been two primary ways to build threshold schemes:
- Shamir's Scheme: Based on polynomial interpolation.
- Asmuth-Bloom Scheme: Based on the Chinese Remainder Theorem (CRT) over integers.
Yu et al. showed that if you apply the Chinese Remainder Theorem to polynomial rings over a finite field rather than to integers, the distinction between these two paradigms disappears.
$$\text{Shamir's Interpolation} \equiv \text{CRT over } \mathbb{F}[x]$$
By treating Shamir's scheme as a specific instance of a generalized CRT-based polynomial ring scheme, the authors unlocked a highly flexible framework for constructing ideal, weighted secret sharing schemes with optimal information rates.
Broader Algebraic Abstractions
As the field moves away from rigid finite-field constraints, researchers are uncovering even broader mathematical abstractions to handle complex organizational policies and functionalities:
- Integer Polymatroids: Farràs et al. utilized integer polymatroids to create a unified framework for complex, non-threshold access structures (such as hierarchical or compartmented groups), proving that these intricate real-world structures can be modeled as configurations of the same underlying mathematical object.
- Group-Theoretic Abstractions: For advanced primitives like homomorphic secret sharing (HSS) and pseudorandom correlation functions (PCFs), Abram et al. abstracted core operations into pure group-theoretic properties, allowing for trustless setups and active security independent of standard, specific cryptosystems.
- Non-Abelian Programs: Moving beyond rings entirely, Paskin-Cherniavsky et al. designed communication-efficient MPC protocols capable of handling products in non-abelian groups, expanding the expressiveness of secure computation to highly complex algebraic structures.
By systematically dismantling the requirement for finite fields, this research direction transforms secret sharing from a rigid geometric trick into a versatile tool capable of navigating the complex algebraic landscapes of modern computing hardware and applications.
Key Foundational Work
On Secure Multi-party Computation in Black-Box Groups (2007) — contributed 1 concept elements to this direction.
Natural Generalizations of Threshold Secret Sharing (2012) — contributed 1 concept elements to this direction.