TL;DR
This paper introduces a new primitive called Incremental Function Secret Sharing (IFSS) to design more efficient secure multi-party computation (MPC) protocols. They achieve information-theoretic security for a broader range of functions, including non-abelian programs and tree-structured circuits, while maintaining low bottleneck complexity (BC), which is crucial for large-scale applications.
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. While communication complexity (total bits sent) and round complexity (number of interactions) are standard metrics, this paper focuses on bottleneck complexity (BC). BC measures the maximum communication load on any single party, aiming for better load balancing, especially in scenarios with many participants. Prior work achieved low BC but often relied on computationally expensive techniques like fully homomorphic encryption (FHE) or had limitations on the types of functions they could handle. This paper aims to extend BC-efficient MPC to a wider class of functions and to the information-theoretic setting, which offers stronger security guarantees without relying on computational assumptions like one-way functions.
Methods
The core technical contribution is the introduction of Incremental Function Secret Sharing (IFSS). IFSS is a primitive that allows parties to evaluate a hidden function on a joint input by aggregating "shares" incrementally along a chain. This differs from traditional function secret sharing by its emphasis on BC-efficient communication.
IFSS is instantiated in two ways:
- Information-Theoretic Security: Using a technique similar to the One-Time Truth-Table (OTTT) protocol, achieving perfect security.
- Computational Security: Based on garbled circuits, which can be built from one-way functions.
The paper then uses IFSS to construct BC-efficient protocols for several function classes:
- Abelian Programs: Functions of the form $f(\sum x_i)$, generalized from prior work.
- 'Read-k' Non-Abelian Programs: Functions involving products in non-abelian groups, extending the expressiveness.
- 'Tree-based' read-k generalized formulas: Functions represented as tree-like structures with multi-input gates.
A key technique across these constructions is the use of masking to hide intermediate values and ensure privacy, combined with the incremental aggregation of shares along a chain to maintain low BC.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- IFSS as a Unifying Primitive: IFSS provides a clean abstraction that elegantly unifies both computational and information-theoretic approaches to BC-efficient MPC for various function classes.
- Information-Theoretic BC-Efficiency is Achievable for Complex Functions: The paper demonstrates that it's possible to achieve information-theoretic security with low BC for functions beyond simple abelian programs, extending to non-abelian structures and tree-like circuits.
- Bottleneck Complexity is Key for Load Balancing: The focus on BC highlights its importance in practical MPC, especially when dealing with a large number of participants, as it directly addresses the maximum load any single party might experience.
- Non-Abelian Programs Offer Greater Expressiveness: The paper shows that non-abelian programs can capture functions that are difficult or impossible to express efficiently with abelian programs within BC constraints, making them more suitable for certain problems.
Key Results
The paper presents several BC-efficient protocols with information-theoretic security:
- Abelian Programs: BC of $O(\log |G|)$, where $|G|$ is the size of the abelian group.
- 'Read-k' Non-Abelian Programs: BC of $O(k \log |G|)$ for information-theoretic security.
- 'Tree-based' read-k generalized formulas: BC of $O(k \cdot \log |G| \cdot \log(kn))$ for information-theoretic security.
These results achieve sublinear BC in the number of parties ($n$) as long as parameters like $k$, depth, and group size are sufficiently small relative to $n$. The paper also provides computational variants with slightly higher BC, often involving the security parameter $\lambda$.
Limitations and Future Work
- Correlated Randomness Size: For the information-theoretic variant of IFSS, the size of correlated randomness can be exponential in the input size, although the BC remains sublinear.
- Function Class Characterization: The paper poses an open problem: to fully characterize the functions for which BC-efficient protocols exist, especially understanding which functions can be computed efficiently even without security guarantees.
- Generalization of Tree-based Protocols: While the paper focuses on binary trees for exposition, it notes that the approach can be generalized to $m$-ary trees and $k$-read settings, though this increases notation complexity.
- Efficiency of Non-Abelian Programs: While non-abelian programs are more expressive, the paper notes that for some functions, an abelian program might still yield a constant BC, which is ideal. The trade-offs between expressiveness and BC for different function classes are an ongoing area of interest.
Summary updated