TL;DR
This paper introduces new, highly efficient Oblivious Linear Function Evaluation (OLE) protocols based on the Ring Learning With Errors (RLWE) assumption. These protocols achieve state-of-the-art communication complexity for practical OLE, offering both passive and active security with a simple, single-round design. Their implementation demonstrates over a million OLEs per second, making them a practical building block for secure computation.
What Problem Does This Paper Address?
Oblivious Linear Function Evaluation (OLE) is a fundamental primitive in secure multi-party computation (MPC). It allows two parties, a sender and a receiver, to compute $y = ax + b$ where the sender inputs $a$ and $b$, and the receiver inputs $x$. The receiver learns $y$ but nothing else about $a$ and $b$, while the sender learns nothing about $x$. OLE is crucial for tasks like secret-shared multiplication, private set intersection, and building secure arithmetic circuits. While OLE protocols exist, many are either theoretical, focus on asymptotic efficiency, or have high communication overhead. This paper aims to provide practical, efficient OLE protocols with low communication complexity, suitable for real-world MPC applications, and to achieve both passive and active security.
Methods
The authors build upon recent advances in homomorphic secret sharing (HSS) from the Ring Learning With Errors (RLWE) assumption. Their approach involves:
- Passively Secure OLE: They construct two new protocols. The first uses a public-key RLWE encryption scheme, while the second leverages a more specialized setup assumption (correlated secret keys) to achieve better efficiency. Both protocols are designed to be conceptually simple and achieve low communication complexity.
- Active Security: They upgrade the passively secure protocols to achieve active security by incorporating efficient amortized zero-knowledge (ZK) arguments. This involves proving that the ciphertexts and secret keys used are correctly formed and adhere to specific bounds.
- Novel ZK Arguments: For the secret-key based protocol, they design new variants of ZK arguments necessary to prove the well-formedness of secret-key RLWE ciphertexts, which is a non-trivial extension of existing techniques.
- SIMD for Lattice Primitives: They utilize Single Instruction, Multiple Data (SIMD) techniques, common in homomorphic encryption, to efficiently pack multiple OLE computations over $\mathbb{Z}_m$ into a single OLE over a larger ring $\mathbb{Z}_m[X]/(X^N+1)$.
Datasets
Not discussed in the paper. The paper focuses on cryptographic protocol design and analysis, not on training or evaluating models on datasets.
Key Insights and Ideas
- OLE as a standalone primitive: The authors advocate for studying OLE as a modular primitive, simplifying MPC analysis and proofs compared to monolithic approaches.
- Efficiency through HSS optimization: By adapting and optimizing existing homomorphic secret sharing techniques for the specific OLE functionality, they achieve significant improvements.
- Secret-key vs. Public-key OLE: They demonstrate that a dedicated setup assumption (correlated secret keys) can lead to more efficient secret-key OLE protocols compared to those relying on standard public-key infrastructure.
- Amortized ZK for active security: The use of efficient amortized zero-knowledge arguments is key to achieving active security with minimal overhead, especially for large batches of OLEs.
- Practical performance: The implementation results show that their protocols are not just theoretically efficient but also practically fast, achieving over a million OLEs per second.
Key Results
- Lowest Communication Complexity: Their passively secure OLE protocols achieve the lowest communication complexity among previously implemented practical OLE protocols based on RLWE and other assumptions, roughly halving the bandwidth of prior solutions.
- Single-Round Interaction: For the case where $b$ is randomly chosen, their protocols require only one round of interaction.
- High Throughput: An implementation of their passively secure secret-key protocol can perform over 1 million OLEs per second on a standard laptop.
- Active Security with Low Overhead: Active security is achieved using amortized ZK techniques, resulting in only a small communication overhead over the passive protocols, especially for large numbers of OLEs.
- Comparison to Prior Work: Their protocols offer significantly lower communication costs compared to previous RLWE-based OLEs and noisy Reed-Solomon encoding-based protocols.
Limitations and Future Work
- Parameter Selection: The security and correctness of the protocols depend on careful parameter selection, particularly concerning the bounds on noise and secret keys, and the soundness slack parameter in ZK proofs.
- ZK Argument Complexity: While amortized, the ZK arguments still contribute to the overall complexity. The paper mentions that generic argument systems might offer better communication for very large instances but at the cost of higher computation.
- Future Work: The authors suggest exploring the application of more recent ZK techniques, such as those with extended challenge spaces, to potentially further improve efficiency. They also note that their work can be extended to other settings, like multi-party computation.
Summary updated