Distributed Function Secret Sharing and Applications

Distributed Function Secret Sharing and Applications

Speakers: Pengzhi Xing

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=5J5rUtUfXd8

Overview

This talk, presented by Pengzhi Xing at the NDSS Symposium, delves into the critical advancements in Distributed Function Secret Sharing (DFSS) and its practical applications within the realm of Secure Multi-Party Computation (MPC). The research addresses fundamental limitations of existing FSS schemes, primarily the reliance on a trusted dealer and the inability to efficiently handle arithmetic inputs and outputs. By introducing a novel dealerless FSS scheme supporting both arithmetic Distributed Point Function (DPF) and Distributed Comparison Function (DCF), this work significantly enhances the practicality, security, and performance of privacy-preserving computations.

The core motivation behind this research stems from the increasing demand for privacy-preserving technologies in various domains, such as machine learning inference and data analytics. While MPC offers a robust framework for such applications, its widespread adoption has been hampered by communication overheads and the complexities of setting up secure protocols. Function Secret Sharing (FSS) emerged as a powerful cryptographic primitive to mitigate these issues by dividing computation into efficient offline and online phases. However, the requirement for a central dealer in traditional FSS schemes introduces a single point of trust and weakens security guarantees, while prior dealerless solutions struggled with arithmetic operations and large input sizes.

This article explores the technical innovations proposed by Xing, detailing how a dealerless FSS scheme for arithmetic DPF and DCF is constructed. It covers the underlying cryptographic mechanisms, the development of essential building blocks, and their integration into complex function evaluation protocols for scientific computing. The talk highlights significant communication and runtime improvements demonstrated through an open-source implementation, underscoring the potential of this research to accelerate the deployment of truly privacy-preserving and efficient MPC systems in real-world scenarios.

Background

▶ Watch: Introduction to MPC and Function Secret Sharing (FSS) (0:00)

Secure Multi-Party Computation (MPC) stands as a cornerstone in modern cryptography, enabling multiple parties to collectively compute a function over their private inputs without revealing those inputs to each other. This powerful paradigm protects user privacy in sensitive applications, such as privacy-preserving model inference. In such a scenario, a client might submit private data (e.g., medical records) using an encryption or secret sharing scheme to an MPC protocol, while a server holding a proprietary model weight similarly submits its private data. Through a series of interactions, the client receives a confidential inference result without either party disclosing their original private inputs. The primary challenge and overhead in these MPC protocols typically arise from the extensive communication required between parties.

In recent years, Function Secret Sharing (FSS) has emerged as a particularly potent cryptographic primitive to address the communication bottleneck in MPC. FSS schemes are designed to construct online-efficient MPC protocols by dividing the computation into two distinct phases: an offline phase and an online phase. During the offline phase, a traditional FSS scheme requires a dealer to generate "FSS keys" based on the function to be computed. These keys are then distributed to the participating parties. In the subsequent online phase, the parties use these pre-shared keys to evaluate the function, performing minimal communication. This design significantly reduces the communication complexity during the online phase, often to a constant number of rounds and a few ring elements, making online interactions much faster.

Despite the advantages of FSS, existing schemes present two significant challenges that limit their practicality and security. The first and most critical issue is the ubiquitous requirement for a trusted dealer during the offline phase. This dealer is responsible for generating and distributing the FSS keys, which creates a single point of trust and potential failure. Such a centralized entity is often unrealistic in decentralized privacy-preserving applications and inherently weakens the overall security guarantees of the system. If the dealer is compromised, the privacy of the entire computation can be jeopardized.

The second challenge relates to the limitations of previously proposed dealerless FSS implementations. While attempts have been made to remove the dealer, these solutions often suffer from limited practicality. Specifically, they are typically unable to support both arithmetic input and output simultaneously, primarily providing boolean (1-bit) outputs. Furthermore, they frequently encounter performance bottlenecks when dealing with large bit-lengths of input, which is a common requirement in many real-world applications involving numerical data. These limitations collectively hinder the widespread adoption of FSS in complex, high-performance MPC scenarios.

Key Findings

▶ Watch: Overview of proposed dealerless FSS scheme and contributions (3:25)

The research presented by Pengzhi Xing delivers several key findings and contributions that significantly advance the field of Function Secret Sharing and Secure Multi-Party Computation:

1. Novel Dealerless FSS Scheme: The central contribution is the proposal of a new dealerless FSS scheme. This scheme eliminates the requirement for a trusted third-party dealer during the key generation phase, thereby enhancing the security guarantees and practicality of FSS-based MPC protocols.
2. Arithmetic DPF and DCF Support: Crucially, the proposed scheme is capable of supporting both arithmetic Distributed Point Function (DPF) and Distributed Comparison Function (DCF). This is a significant improvement over prior dealerless FSS solutions, which were often limited to boolean outputs or struggled with arithmetic operations and large input sizes. Arithmetic support is essential for most real-world numerical computations.
3. FSS-Based Building Blocks: Based on the new dealerless DPF and DCF, the researchers have constructed several foundational FSS-based building blocks. These include efficient protocols for equality testing, comparison, truncation, reduction, and digital decomposition, which are vital components for building more complex MPC functionalities.
4. Complex Function Evaluation Protocols: Leveraging these building blocks, the work demonstrates the construction of protocols for evaluating complex functions, particularly in the domain of scientific computing. Specific applications include efficient implementations of lookup tables, polynomial approximations, and trigonometric evaluations.
5. Significant Performance Improvements: An open-source implementation of the proposed solution unequivocally demonstrates significant improvements in both communication complexity and runtime performance compared to prior work. For instance, dealerless DPF and DCF keys can be generated in "few seconds," and trigonometric evaluation shows substantial gains. This empirical validation underscores the practical efficiency and viability of the new approach.
6. Enhanced Security and Decentralization: By removing the need for a dealer, the scheme inherently improves the overall security posture of MPC protocols. It eliminates a single point of trust and potential compromise, leading to more robust and decentralized privacy-preserving systems.

Technical Deep Dive

▶ Watch: Understanding the Distributed Point Function (DPF) concept (4:50)

The construction of a dealerless FSS scheme, particularly one supporting arithmetic operations, involves overcoming several non-trivial cryptographic challenges. The talk meticulously details the approach, building upon the foundations of Distributed Point Functions (DPF).

Distributed Point Function (DPF)

A Distributed Point Function (DPF) is a core primitive in FSS. Conceptually, a DPF allows a function that evaluates to 1 at a specific "point" alpha and 0 everywhere else, to be secret-shared among multiple parties. When these parties evaluate their shares, they collectively reconstruct the function's output.

In dealer-based DPF, the key generation process relies on a GGM tree (Goldreich-Goldwasser-Micali tree). This is a binary tree completely defined by its root node. Each node in the tree is formatted into a label and a one-bit control bit. For a DPF, there's a special "target point" alpha. A unique path, referred to as the special path, leads from the root to the node corresponding to alpha. The DPF environment requires that all nodes on this special path have their control bit set to 1, while all off-path nodes have their control bit set to 0. The final control bit of the target node will be the secret share of 1, and others will be shares of 0.

When a dealer generates a DPF key, it first constructs a random GGM-style binary tree. The control bits generated by the GGM PRF (Pseudo-Random Function) would typically be pseudo-random. To enforce the DPF environment (on-path=1, off-path=0), the dealer computes correction words. These correction words are essential to "correct" the pseudo-random control bits to maintain the required DPF structure. A DPF key, therefore, consists of a root seed (which determines the full random tree) and the correction words for each level of the tree.

Dealerless DPF: Challenges and Solutions

Constructing a dealerless DPF without a central entity to generate the GGM tree and correction words poses two primary challenges:

1. Traversing the GGM Tree Without Knowing the Special Path

In a dealerless setting, no single party knows the exact special path to the target node alpha. This makes it impossible for parties to independently traverse the tree and identify on-path/off-path nodes.

The solution leverages a crucial observation: although parties don't know the exact path, they know that all off-path nodes should sum to zero in a secret-shared manner. The protocol uses two-party computation (2PC) protocols to collectively traverse the GGM tree. By summing the off-path nodes together, the result will be consistent with what is known about the special path. A secure selection protocol is then employed to achieve the correct result without revealing the actual path information to either party. This allows the distributed generation of the GGM tree structure and its associated control bits without a central coordinator.

2. Supporting Arithmetic Output

Traditional DPFs primarily provide a boolean (1-bit) output, as the final control bit simply becomes a share of 0 or 1. To support arithmetic output (i.e., a general ring element), extra data or correction words are required. The talk references an FSS scheme by Boiler (from Eurocrypt), highlighting the most crucial part: calculating an equation involving (-1)^(T1), where T1 is a control bit held by Party 1.

The difficulty arises because T1 is a private, one-bit value (0 or 1) distributed between the parties. Directly computing (-1)^(T1) in a distributed 2PC setting is non-trivial. The proposed solution simplifies this by recognizing that T1 is binary. Instead of directly computing the power, the problem is transformed into determining which party holds the larger value. An efficient comparison protocol is developed for this purpose. This comparison protocol focuses on extracting only the last two bits of the values being compared, significantly reducing complexity. The final computation then relies on a few AND gates implemented via a secure AND protocol. This optimized approach allows for the distributed generation of arithmetic correction words.

Distributed Comparison Function (DCF)

The Distributed Comparison Function (DCF) is closely related to DPF and enables parties to compare secret-shared values without revealing them. The talk explains that DCF can be constructed using DPF as a building block. Initially, one could use generic 2PC protocols to compute the necessary correction words for DCF functionalities.

However, the speaker presents an optimization: after computing the initial correction words (VCW), parties can locally compute the required v_alpha values. This is achieved by locally subtracting the previous multiplexer output, directly yielding the necessary purple-marked values. This local computation significantly reduces communication overhead compared to a generic 2PC approach.

Basic Building Blocks

The dealerless DPF and DCF enable the construction of several fundamental building blocks crucial for complex MPC protocols:

• Equality Test: A straightforward test to check if two secret-shared values are equal. It typically involves a single DPF invocation using a masked value (k + r, where r is a random mask).
• Comparison: A more complex operation than equality, as it needs to handle potential overflows. If k + r overflows, it can lead to incorrect results, especially if one party's value overflows while the other's does not. The solution is to check if K (the original value) is greater than K + R (the masked value) during an offline stage, allowing for correct interval handling.
• Truncate and Reduce: Protocols designed to change a value from a larger ring (e.g., 64-bit integers) to a smaller ring (e.g., 32-bit integers) or to perform modular reduction, which is essential for managing precision and preventing overflow in fixed-point arithmetic.
• Digital Decomposition: A protocol to decompose a larger secret-shared value into several smaller, secret-shared segments or bits. This is often required for bit-wise operations or when processing values in different granularities.

These building blocks, powered by the efficient dealerless arithmetic DPF and DCF, form the bedrock for developing practical and performant privacy-preserving applications.

Demo / Proof of Concept

▶ Watch: Enabling arithmetic output for DPF beyond boolean (7:00)

The efficacy and practicality of the proposed dealerless FSS scheme are substantiated through an open-source implementation and its application in scientific computing. While the talk does not feature a live demo in the traditional sense, it presents the results of extensive evaluations and highlights specific use cases that serve as a proof of concept.

The research focuses on two efficient functionalities for scientific computing:

1. Lookup Table (LUT): This functionality allows parties to privately query a shared lookup table. This is crucial for applications where complex, non-linear functions need to be evaluated, but direct computation is too expensive or involves proprietary data. The FSS building blocks enable efficient private lookups.
2. Polynomial Approximation: Many complex functions can be approximated using polynomials. The talk demonstrates how the new DPF and DCF implementations facilitate efficient polynomial approximation. A key aspect of this is managing the truncated bits. By carefully handling truncation, the scheme avoids the performance bottlenecks typically incurred by large input bit-lengths, which was a significant limitation of prior dealerless FSS solutions. This allows for practical evaluation of approximations over larger data ranges.
3. Trigonometric Evaluation: The paper also addresses the secure evaluation of trigonometric functions (e.g., sine, cosine). This is achieved by leveraging periodic properties and sum-to-product identities in conjunction with the FSS building blocks. Trigonometric functions are fundamental in many scientific and engineering computations, and their secure evaluation opens doors for privacy-preserving simulations and analyses.

The evaluation results presented in the talk are compelling. For the core dealerless DPF and DCF schemes, the key generation process is remarkably fast, completing in "few seconds." This rapid key generation is a testament to the efficiency of the dealerless construction and addresses one of the major hurdles of previous FSS schemes.

Furthermore, experiments comparing the trigonometric evaluation protocol against prior work demonstrate "much improvements." While specific percentage figures are not provided in the transcript, the qualitative statement indicates a significant performance gain, likely in terms of reduced communication rounds, bandwidth, or computation time. This suggests that the optimized building blocks and application-specific techniques contribute to a substantial leap in efficiency.

Finally, the research includes two "case studies" which further illustrate the efficiency of the entire solution. These case studies serve to validate the practical applicability of the dealerless FSS framework in more comprehensive scenarios, showcasing its readiness for deployment in real-world privacy-preserving scientific computations. The open-source nature of the implementation allows other researchers and developers to build upon this work, fostering further advancements in the field.

Defensive Implications

▶ Watch: Novel comparison protocol for arithmetic DPF output (8:40)

The advancements in Distributed Function Secret Sharing (DFSS) presented by Pengzhi Xing carry profound defensive implications for organizations and individuals concerned with data privacy and security. This research provides a more robust and practical foundation for building and deploying Secure Multi-Party Computation (MPC) systems, which are inherently defensive tools against privacy breaches and data misuse.

Firstly, the elimination of the trusted dealer is a critical defensive improvement. Traditional FSS schemes, and indeed many MPC protocols, often rely on a third party to generate cryptographic keys or facilitate setup. This dealer represents a single point of failure and a potential target for attackers. By proposing a dealerless FSS scheme, this research removes this central point of trust, distributing the responsibility and enhancing the overall security guarantees. Defenders can now deploy FSS-based MPC solutions with greater confidence, knowing that the system's integrity is not dependent on the unwavering trustworthiness or invulnerability of a single entity. This decentralization of trust aligns with best practices in secure system design.

Secondly, the ability to support arithmetic input and output in a dealerless FSS scheme significantly expands the range of privacy-preserving applications that can be efficiently secured. Many real-world data analytics, machine learning models, and scientific computations involve numerical data and complex arithmetic operations. Prior dealerless FSS solutions, limited to boolean outputs or struggling with large bit-lengths, could not adequately protect such computations. With arithmetic DPF and DCF, defenders can now leverage FSS for more sophisticated privacy-preserving tasks, such as:

• Privacy-preserving statistical analysis: Computing averages, sums, correlations, or regressions over sensitive datasets held by multiple parties without revealing individual data points.
• Secure machine learning inference: Deploying models where the input data, model weights, or both remain private during the prediction phase.
• Private financial computations: Enabling secure audits, fraud detection, or risk assessments across financial institutions without exposing confidential transaction data.

Thirdly, the demonstrated significant communication and runtime improvements are crucial for the practical adoption of MPC. High overheads have historically been a major barrier. By making FSS-based protocols faster and more efficient, this research makes privacy-preserving technologies more palatable for deployment in performance-sensitive environments. Defenders can now consider MPC for applications where it might have previously been deemed too slow or resource-intensive, thus expanding the scope of data that can be securely processed.

Finally, the development of efficient building blocks like equality tests, comparisons, truncations, and digital decompositions provides a strong toolkit for defenders. These primitives are the foundation upon which complex privacy-preserving applications are built. Having optimized, dealerless versions of these tools means that new secure protocols can be developed more quickly and with higher confidence in their underlying security and performance. This work enables a shift from "can we achieve privacy with MPC?" to "how efficiently and securely can we achieve privacy with MPC without relying on a trusted third party?" empowering organizations to better protect sensitive data in an increasingly interconnected and data-driven world.

Key Takeaways

• Elimination of Trusted Dealer: The research introduces a novel dealerless FSS scheme, fundamentally improving security and practicality by removing the single point of trust inherent in traditional FSS setups.
• Arithmetic DPF and DCF Support: The proposed scheme is the first to efficiently support both arithmetic Distributed Point Function (DPF) and Distributed Comparison Function (DCF) in a dealerless manner, crucial for real-world numerical computations beyond simple boolean operations.
• Overcomes Performance Bottlenecks: The solution effectively addresses previous limitations concerning large bit-length inputs and output, ensuring efficient performance for complex arithmetic operations.
• Robust Building Blocks: The work provides optimized FSS-based building blocks, including equality tests, comparisons (with overflow handling), truncation, and digital decomposition, which are essential for constructing advanced MPC protocols.
• Significant Performance Gains: Experimental evaluations confirm substantial improvements in key generation time (few seconds for DPF/DCF) and runtime for complex functions like trigonometric evaluation compared to prior work, making MPC more viable for practical applications.
• Enables Advanced Privacy-Preserving Applications: By enhancing the efficiency and security of FSS, this research paves the way for more widespread and practical deployment of privacy-preserving computations in scientific computing, machine learning, and data analytics.

About the Speaker(s)

Pengzhi Xing is a researcher in the field of secure multi-party computation and cryptography. His work, as demonstrated in this talk, focuses on advancing fundamental cryptographic primitives like Function Secret Sharing to enhance the privacy, security, and efficiency of distributed computations. His expertise lies in developing practical, dealerless schemes for complex arithmetic functions and building robust cryptographic protocols for real-world applications.