TL;DR
This paper introduces the first information-theoretic multi-party computation (MPC) protocols that work over non-commutative rings, a significant step beyond previous work limited to commutative rings or finite fields. This advancement is crucial for practical applications involving matrix rings, such as machine learning, by enabling secure computation with fewer assumptions and improved efficiency.
What Problem Does This Paper Address?
Secure multi-party computation (MPC) allows multiple parties to jointly compute a function on their private inputs without revealing those inputs. Traditionally, MPC protocols have relied on algebraic structures like finite fields, which have useful properties like the absence of zero divisors. However, many real-world applications, particularly in areas like machine learning and computer graphics, involve computations over non-commutative rings, such as matrix rings. Existing MPC techniques struggle to efficiently handle these non-commutative structures, often requiring complex workarounds or being limited to specific scenarios (e.g., a small number of corruptions). This paper tackles the challenge of designing efficient, information-theoretic MPC protocols that directly operate over general non-commutative rings, making MPC more applicable to a wider range of practical problems.
Methods
The authors generalize Shamir's secret sharing scheme to non-commutative rings. Their approach is based on the concept of "exceptional sets" within a ring, which are sets of elements whose pairwise differences are invertible.
- Generalization of Shamir's Secret Sharing: They adapt Shamir's scheme to work over rings where elements might not commute. This involves defining left and right linear secret sharing schemes.
- Leveraging Existing Work: The paper builds upon prior work on Reed-Solomon codes over non-commutative rings and adapts existing MPC protocols for commutative rings to their new setting.
- Black-Box Access: A key contribution is the development of protocols that only require black-box access to the ring operations and an exceptional set, meaning they don't need to know the internal structure of the ring.
- Preprocessing Model: The protocols operate in the common MPC paradigm of an "offline" preprocessing phase (generating correlated randomness) and an "online" phase (using this randomness to compute the function). This is particularly useful for non-commutative rings where direct online computation is challenging.
- Specific Constructions for Matrix Rings: The paper provides concrete, efficient protocols for the important case of matrix rings over $\mathbb{Z}_{2^k}$ ($M_{m \times m}(\mathbb{Z}_{2^k})$), which are widely used in practice. This involves adapting techniques like "Circuit Amortization Friendly Encodings" (CAFEs) and developing specialized preprocessing routines.
- Berlekamp-Welch Generalization: They generalize the Berlekamp-Welch decoding algorithm to the non-commutative setting, which is crucial for error correction in secret sharing.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Non-commutative rings are not an insurmountable barrier for MPC: The paper demonstrates that information-theoretic MPC is achievable even over non-commutative rings, significantly broadening the applicability of MPC.
- Exceptional sets are key: The existence of "exceptional sets" with specific commutativity properties within a ring is crucial for constructing these new MPC protocols.
- Generalization of secret sharing is powerful: Adapting Shamir's secret sharing to left/right linear schemes is a fundamental building block.
- Preprocessing is essential for efficiency: The offline/online model is particularly effective for handling the complexities of non-commutative multiplication.
- Matrix rings are a practical target: The specific constructions for $M_{m \times m}(\mathbb{Z}_{2^k})$ highlight the real-world impact of this research.
Key Results
- First information-theoretic MPC protocols for non-commutative rings: The paper presents protocols that are secure against active adversaries corrupting $t < n/3$ parties (guaranteed output delivery) and $t < n/2$ parties (security with abort).
- Efficient online phase for matrix rings: For $M_{m \times m}(\mathbb{Z}_{2^k})$ where $m \ge \log(n+1)$, their protocols offer significant improvements in communication and computation compared to prior state-of-the-art.
- Black-box access achieved: The general protocols require only black-box access to the ring operations, making them more versatile.
- Generalization of Berlekamp-Welch algorithm: A crucial tool for error correction in non-commutative settings is provided.
Limitations and Future Work
- Preprocessing complexity: While the online phase is efficient, the generic black-box preprocessing phase has a complexity of poly(n). The paper addresses this with specialized, more efficient preprocessing for matrix rings.
- Specific ring structures: The most efficient protocols are tailored for matrix rings. Extending these to other types of non-commutative rings could be a future direction.
- Further exploration of non-commutative linear systems: The paper notes that the theory of linear equations over general non-commutative rings is not well-understood, suggesting this as an area for future research.
Summary updated