TL;DR
This paper introduces a novel, efficient protocol for securely generating RSA keys in a distributed setting, leveraging the Miller-Rabin primality test. Their approach offers significant speedups over existing methods, particularly in honest majority scenarios, making distributed RSA key generation more practical for advanced cryptographic applications.
What Problem Does This Paper Address?
Generating RSA keys, especially in a distributed or threshold setting, is a critical but computationally intensive task. In distributed RSA, multiple parties collaborate to create an RSA modulus ($N=pq$) without any single party learning the prime factors ($p$ and $q$). This is essential for security applications like threshold cryptography and advanced protocols that rely on RSA groups of unknown order. Traditional methods often use the Boneh-Franklin bi-primality test, which requires many iterations to achieve a negligible error probability, making it slow. While the Miller-Rabin test is faster for primality testing, adapting it to a secure, distributed setting without revealing secret information has been a challenge, especially for more than a few parties. This paper aims to bridge this gap by presenting an efficient distributed RSA key generation protocol based on the Miller-Rabin test.
Methods
The core of this paper is a new protocol for distributed RSA key generation that utilizes the Miller-Rabin primality test. The authors build upon the work of Damgård and Mikkelsen [DM10], following a similar blueprint but introducing a novel divisibility test. This new test allows for efficient primality testing of candidate primes ($p$ and $q$) while keeping them secret, even when the modulus $N=pq$ is public.
Key techniques include:
- Miller-Rabin Test: Instead of the Boneh-Franklin test, they use the Miller-Rabin test, which offers a much lower error probability per iteration for sufficiently large moduli (e.g., 4096 bits).
- Novel Divisibility Test: A crucial contribution is a new divisibility test that enables the Miller-Rabin test to be performed securely in a distributed manner. This test requires secure computation modulo an auxiliary prime with a bit length of $O(k + \log n)$, which is significantly better than previous approaches requiring $O(nk)$.
- Modular Protocol Design: The protocol is designed modularly, using various sub-protocols (macros) for operations like secure multiplication, share conversion, inversion, and set-membership testing. This modularity allows for flexibility in instantiation and easier analysis.
- Semi-Honest and Malicious Security: The protocol is first presented for semi-honest security, assuming that parties follow the protocol but may try to learn extra information. The authors then discuss how to upgrade this to achieve active (malicious) security using existing compilers, with a small constant overhead.
Datasets
Not discussed in the paper. The paper focuses on cryptographic protocol design and evaluation, not on training or evaluating models on specific datasets.
Key Insights and Ideas
- Miller-Rabin is Viable for Distributed RSA: The paper demonstrates that the Miller-Rabin test, known for its efficiency in single-party primality testing, can be effectively adapted for secure distributed RSA key generation, offering a significant performance advantage over the Boneh-Franklin test.
- A New Divisibility Test is Key: The development of a novel, efficient divisibility test is central to enabling the secure application of Miller-Rabin in this context, overcoming previous limitations in handling secret-shared numbers.
- Modular Design Enhances Flexibility: The modular approach allows the protocol to be instantiated with different underlying secure multiplication protocols, supporting various security models (e.g., honest vs. dishonest majority) and thresholds.
- Performance Gains in Honest Majority: The protocol shows substantial performance improvements (latency and throughput) in honest majority settings, making it a practical choice for many real-world applications.
Key Results
The paper presents a novel protocol for distributed RSA key generation that is secure against semi-honest adversaries.
- Efficiency: For the honest majority case, the protocol is significantly faster than the Boneh-Franklin based approach. Experimental evaluations show latency improvements of 3.2x to 14x and throughput improvements of 42x to 77x for 3 parties.
- Scalability: The protocol scales well with the number of parties, with communication complexity increasing linearly and computation complexity showing only a modest increase.
- Malicious Security: The semi-honest protocol can be upgraded to achieve active security with only a small constant factor overhead, using existing compilers.
- Reduced Auxiliary Prime Size: The new divisibility test requires auxiliary primes of size $O(k + \log n)$, a significant improvement over previous methods.
Limitations and Future Work
- Dishonest Majority Performance: While efficient in honest majority settings, the protocol's performance degrades in dishonest majority scenarios due to the increased cost of secure multiplications.
- Malicious Security Implementation: The paper discusses how to achieve malicious security but notes that a full, working implementation was not completed.
- Optimization for Malicious Security: Future work could explore more optimized approaches for achieving malicious security, potentially beyond the compiler-based method.
- Further Performance Tuning: While the protocol is faster, further optimizations, especially for the online phase of multiplications, could be explored. The paper mentions achieving $O(1)$ online multiplications by pushing $O(n)$ multiplications to a preprocessing phase, but this comes with trade-offs.
Summary updated