Abstract
As quantum computing advances, traditional cryptographic protocols based on RSA and Elliptic Curve Cryptography (ECC) face significant security risks. This paper explores a novel approach to Secure Two-party Computation (2PC) specifically tailored for NTRUEncrypt, a leading lattice-based encryption scheme known for its post-quantum resilience. By integrating Oblivious Transfer (OT) and Private Set Intersection (PSI), the proposed framework enables two parties to collaboratively generate keys and perform decryption without exposing private inputs. The methodology focuses on secure polynomial multiplication and distributed key generation, providing a robust foundation for privacy-preserving operations in a post-quantum landscape.
Introduction
Secure Multi-party Computation (MPC) is a critical field in modern cryptography, allowing multiple parties to compute a function over their private inputs while maintaining data confidentiality. However, the impending era of quantum computing necessitates a shift toward "post-quantum" primitives. Lattice-based cryptography, and specifically the NTRUEncrypt scheme, has emerged as a primary candidate for this transition due to its efficiency and resistance to known quantum attacks.
Despite its advantages, implementing 2PC within the NTRU framework presents unique technical hurdles. NTRUEncrypt relies heavily on complex polynomial multiplications and specific "three-valued" (coefficients of -1, 0, or 1) polynomial structures. Performing these operations across two separate parties without leaking the underlying polynomial data is a complex task. This paper addresses these challenges by introducing a concrete protocol for 2PC within the NTRU framework, focusing on secure distributed key generation and decryption.
Methodology
The authors construct their 2PC scheme using several sophisticated cryptographic building blocks designed to handle the specific requirements of lattice-based math.
1. NTRUEncrypt-based Oblivious Transfer (OT)
The protocol utilizes an implementation of Oblivious Transfer that relies on the inherent hardness of lattice problems. This allows a receiver to obtain specific information from a sender without the sender learning which piece of information was selected, forming the basis for more complex interactions.
2. Secure Polynomial Multiplication
The technical core of the paper is the method for 2PC polynomial multiplication. To compute the product $f(x)g(x) = A(x) + B(x)$, where Alice holds $f$ and $A$, and Bob holds $g$ and $B$, the authors represent polynomial coefficients as bit strings. They then employ a series of OT operations to calculate the "cross-terms" of the multiplication securely. This ensures that neither party learns the other's full polynomial during the computation.
3. Private Set Intersection (PSI) for Key Generation
During the key generation phase, Alice and Bob generate segments of a private key locally. To ensure the resulting combined key remains a valid "three-valued" polynomial—a requirement for NTRU security—the authors use Private Set Intersection (PSI) with Cuckoo Hashing. This allows the parties to check for overlapping exponents in their monomials and resolve collisions without revealing the exponents themselves.
4. Security Model
The protocol is formally analyzed under the semi-honest (or "honest-but-curious") model. In this setting, it is assumed that both parties will follow the protocol as specified but may attempt to glean additional information from the data transcripts they receive during execution.
Key Insights
Hiding Polynomial Structure
A significant contribution of this work is the emphasis on hiding the actual structure of the polynomials. By expressing polynomials in a standard form with $N$ terms (including zero coefficients), the authors prevent an adversary from inferring the number of non-zero terms, which could otherwise leak sensitive information about the private key.
The PSI-Key Generation Link
The use of PSI during key generation is a particularly clever innovation. In NTRU, private keys must be sparse and adhere to strict coefficient rules. By leveraging PSI, the two parties can ensure their locally generated polynomial segments do not "collide" in a way that violates the mathematical requirements of the cryptosystem, all while maintaining total privacy.
Distributed Decryption
The paper demonstrates that decryption can be modeled as a joint polynomial multiplication problem. This facilitates a "threshold" style of decryption where both parties must cooperate to read a message, yet neither party ever possesses the full private key.
Results and Performance
Computational Complexity
The security analysis indicates that the protocol scales well with security requirements. For "Highest Security" settings where $N=743$, the authors calculate that an adversary would need to perform approximately $2^{556}$ operations to successfully brute-force the private key, providing a massive security margin against both classical and quantum threats.
Efficiency via OT Extension
To address the inherent latency of standard Oblivious Transfer, the authors utilize OT Extension. This significantly reduces the computational burden of the OPRF (Oblivious Pseudo-Random Function) used in their PSI protocol, making the overall system more viable for practical use.
Parameter Mapping
The research provides a detailed mapping of NTRU parameters ($N, q, p$) required to maintain security levels ranging from "Moderate" to "Highest," ensuring the protocol can be tuned for different application needs.
Limitations and Future Directions
While the paper presents a robust theoretical framework, several areas remain for future exploration:
- Malicious Model Security: The current protocol assumes semi-honest behavior. Extending the framework to remain secure against malicious actors—who might provide fraudulent inputs to subvert the protocol—is a necessary next step for real-world deployment.
- Communication Overhead: The polynomial multiplication method requires $(N+1)^2$ OT operations. Even with OT extension, the communication cost remains high for very large polynomials, suggesting a need for further optimization.
- Empirical Benchmarking: Future work should focus on providing wall-clock timing results and software implementations to evaluate the protocol's performance under various network conditions.
Summary updated