TL;DR
This paper introduces new, highly efficient protocols for Oblivious Linear Function Evaluation (OLE) based on the Ring Learning With Errors (RLWE) assumption. These protocols achieve state-of-the-art communication efficiency for both passive and active security, enabling over a million OLEs per second on standard hardware.
What Problem Does This Paper Address?
Oblivious Linear Function Evaluation (OLE) is a fundamental building block in secure multi-party computation (MPC), enabling secure multiplication and other critical operations. While OLE protocols exist, many are either computationally expensive, require significant communication, or are not practical for real-world deployment. This paper aims to bridge this gap by developing OLE protocols that are both theoretically sound (based on the well-studied RLWE assumption) and practically efficient, offering low communication and high throughput.
Methods
The authors present two main OLE protocols:
- Passively Secure Protocols: These protocols leverage recent advances in homomorphic secret sharing from RLWE. They are designed to be simple, requiring only one message per party. The key innovation lies in optimizing these schemes specifically for OLE, resulting in significantly reduced communication complexity compared to prior RLWE-based OLE constructions.
- Actively Secure Protocols: To achieve security against malicious adversaries, the authors extend their passively secure protocols using efficient amortized zero-knowledge (ZK) techniques. This involves developing new ZK arguments tailored for lattice relations, particularly for proving the well-formedness of secret-key RLWE ciphertexts. They also introduce a novel ZK argument for proving knowledge of short vectors in specific lattice relations, which is crucial for their constructions.
The protocols also utilize techniques like plaintext packing (SIMD) to efficiently perform OLEs over smaller rings (like Zm) by leveraging OLEs over larger polynomial rings (Rm).
Datasets
Not discussed in the paper.
Key Insights and Ideas
- OLE as a Primitive: The paper advocates for treating OLE as a standalone primitive, emphasizing its modularity and potential to simplify MPC analysis and proofs.
- RLWE for Efficiency: The choice of the RLWE assumption, combined with clever protocol design, is key to achieving both security and efficiency.
- Optimized Homomorphic Secret Sharing: Adapting existing homomorphic secret sharing schemes for the specific OLE functionality leads to significant communication savings.
- Amortized Zero-Knowledge for Active Security: The use of amortized ZK arguments is crucial for achieving efficient active security, especially when performing a large number of OLEs. The development of new ZK arguments for lattice relations is a notable contribution.
- Practical Performance: The paper demonstrates that these theoretically efficient protocols can achieve impressive real-world performance, exceeding one million OLEs per second.
Key Results
- State-of-the-Art Communication: The proposed passively secure protocols achieve the lowest communication complexity among practical RLWE-based OLE protocols, roughly halving the bandwidth of previous solutions.
- High Throughput: An implementation of the passively secure secret-key protocol can perform over 1 million OLEs per second on a standard laptop.
- Efficient Active Security: The actively secure protocols offer low amortized communication overhead, comparable to their passive counterparts when processing many OLEs.
- Reduced Complexity: The protocols are conceptually simple, with a single round of interaction for the case where the constant term 'b' is randomly chosen.
Limitations and Future Work
- Parameter Choices: The security and efficiency of the protocols depend on carefully chosen parameters for the RLWE problem, which are discussed in the evaluation section.
- Future Work: The authors suggest exploring the application of more recent amortized proofs and investigating how generic argument systems can be applied to the lattice setting for potentially better communication efficiency in specific scenarios. They also mention that their work can be extended to other zero-knowledge arguments.
Summary updated