This post describes a research carried with Luigi and Vassil and briefly presents this paper.
As part of our research on the Verifiable Delay Functions (VDF), we have investigated RSA-based VDFs and you can see more details here.
The point with RSA-base VDFs is that there is a setup phase where we generate a public RSA modulus i.e., a product of two big primes p and q, N=p •q which is hard to factorize. However, knowledge of p and q allows to compute the private key φ(N)=(p-1)•(q-1) and any party having such a knowledge can evaluate the VDFs in an instant time.
This feature can be useful in some situations where an authority wants to evaluate quickly VDFs but IOTA’s vision is to build a fully decentralized system where no party has privileges. Thus, we need to be able to compute N in such a way that nobody can retrieve the values of p and q.
The research on distributed RSA keys generation started with a paper of Boneh and Franklin in 1997 and has been then followed by some research described in the original paper. The latest paper is from Frederiksen et al. where they present a two parties algorithm generating the algorithm in a few dozens of seconds instead of 15 minutes by using modern cryptographic methods. This algorithm runs in a semi-honest setting, which means that the dishonest nodes play by the rule but try to learn more than they should from the informations they receive or share among them.
The scope of our paper is to make a generalization of this two parties algorithm to n parties in order to leverage these new cryptographic techniques.
The high-level view of this algorithm is the following :
- Random number generation. The two active nodes P1 and P2 respectivelygenerate the numbers p_1, q_1 and p_2, q_2.
- Fast trial divisions. The active nodes run fast trial divisions by small primes numbers on both p = p_1 + p_2 and q = q_1 + q_2 to quickly discard wrong candidates. If p or q fail the test, the algorithm restarts from 1.
- RSA modulus computation. The two parties compute N = (p_1 +p_2)·(q_1 + q_2) in a distributed way without revealing information on key’s parts.
- Biprimality test. A biprimality test verifies whether N is a product of two prime numbers whp. If the biprimality test fails, the algorithm restarts from P.1.
In our paper, we are keeping the steps of this algorithm and only generalizing them for p=p_1+\dots+p_n and q=q_1+\dots+q_n and we are trying to stick to the idea of each computation when generalizing when it is possible.
This work can be useful and is a really timely research subject. At the Stanford Blockchain Conference held this February, there has been a work from Ligero team presented [Slides]