TL;DR
This paper introduces PELTA, the first practical construction that allows multiparty fully homomorphic encryption (MFHE) schemes to be secure against malicious adversaries, not just honest-but-curious ones. PELTA achieves this by using zero-knowledge proofs to verify the correctness of critical MFHE operations, significantly outperforming existing approaches in terms of speed.
What Problem Does This Paper Address?
Multiparty Fully Homomorphic Encryption (MFHE) allows multiple parties to jointly compute on encrypted data while keeping it private. This is powerful for applications like distributed machine learning and secure data analytics. However, existing MFHE schemes only protect against "honest-but-curious" adversaries, meaning they assume all participants follow the protocol. A malicious party could disrupt the computation by providing incorrect inputs, generating faulty keys, or manipulating the decryption process, leading to incorrect results or privacy breaches. While theoretical solutions exist, they are often impractical. This paper tackles the challenge of building a practical MFHE system that can detect and prevent malicious behavior.
Methods
PELTA's core innovation is a commit-then-prove approach using zero-knowledge proofs to verify the correctness of MFHE operations. Specifically, it focuses on the interactive operations within MFHE, which are crucial for key generation, decryption, and other functionalities.
Here's a breakdown of their approach:
- Systematization of MFHE: They first categorize MFHE schemes (MkHE, ThHE, MgHE) and identify common operations that are vulnerable to malicious attacks.
- Commit-then-Prove: Each party commits to its intermediate cryptographic material (like secret keys or shares) and then provides a zero-knowledge proof that this material is correct and satisfies specific MFHE requirements.
- Lattice-Based Cryptography: They leverage efficient lattice-based commitment schemes (like BDLOP and Ajtai) and proof systems. This choice is strategic because it aligns with the underlying security assumptions of modern FHE schemes (like BFV, BGV, CKKS), ensuring post-quantum security and compatibility.
- Tailored Statements: They design specific "statements" (mathematical relations) that capture the correctness conditions for various MFHE operations, accounting for FHE's specific arithmetic and implementation optimizations (like NTT).
- Verifiable Aggregation: For operations where parties combine their shares (aggregation), they introduce a novel protocol based on the polynomial identity lemma to ensure the aggregator correctly combines these shares without needing to reveal them.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- The Need for Malicious Security in MFHE: The paper highlights that the existing focus on honest-but-curious adversaries leaves MFHE vulnerable to practical attacks, necessitating robust solutions.
- Lattice-Based Cryptography as a Natural Fit: Using lattice-based commitments and proofs is a key insight, as it naturally integrates with the security foundations of FHE schemes, avoiding the need for additional, potentially incompatible, cryptographic assumptions.
- Commit-then-Prove for Interactive MFHE: This paradigm is effective for proving the correctness of operations that involve secret inputs from multiple parties without revealing those secrets.
- Verifiable Aggregation is Crucial: Ensuring the aggregator correctly combines shares is as important as ensuring individual parties generate correct shares, as a malicious aggregator can still compromise the system.
- Performance Trade-offs: The paper demonstrates that by carefully designing statements and leveraging efficient lattice-based primitives, it's possible to achieve malicious security with manageable overhead, outperforming generic proof systems.
Key Results
- First Practical Malicious-Secure MFHE: PELTA is presented as the first practical construction that provides security against malicious adversaries in MFHE pipelines.
- Significant Speedup: PELTA achieves performance that is one to two orders of magnitude faster than existing techniques (based on malicious MPC and generic proof systems) for key MFHE operations like local key generation and collective decryption.
- Reduced Overhead: Compared to a SNARK-based approach, PELTA offers comparable proof sizes and significantly faster setup times (15x).
- Efficiency Gains: Multi-threading in PELTA can speed up operations by a factor of 1.5.
Limitations and Future Work
- Focus on Interactive Operations: While PELTA secures critical interactive operations, the paper notes that countermeasures for non-interactive operations (like homomorphic evaluation correctness and input correctness) are orthogonal and require further research.
- Homomorphic Evaluation Correctness: The paper points out that current techniques for verifying homomorphic evaluation are limited (e.g., to quadratic functions) or have compatibility issues with FHE schemes. Novel and efficient techniques are needed.
- Input Correctness Challenges: Verifying the correctness of input data and its encryption is a complex problem. While commitments and range proofs can help, they are inefficient for large coefficients, and malicious parties can still craft misleading inputs. Further research into statistical tests or authenticity checks on encrypted data is suggested.
- Trade-off between Runtime and Proof Size: The paper mentions that PELTA can achieve a trade-off between runtime and proof size by adjusting commitment polynomial ring parameters.
Summary updated