Generating a product of three primes with an unknown factorization
It is shown how three or more parties can jointly generate an integer \(N\) which is the product of three prime numbers, \(N=pqr\). At the end of the protocol, \(N\) is publicly known, but no party knows the factorization of \(N\). The correctness of the primality test is shown by working in the two subgroups of \({\mathbb Z}_N [x]/(x^2 +1)^*\), namely \({\mathbb Z}_N^*\) and the twisted group \({\mathbb Z}_N [x]/(x^2 +1)^* /{\mathbb Z}_N^*\), where it is noted that \(x^2 +1\) is irreducible modulo \(N\). A restriction of the technique is that each of the three primes is \(3\) modulo \(4\), which is easily accommodated by coordinating the two lower bits of the generated shares of the primes. If two parties collude, the factors can be recovered, i.e. the protocol is \(1\)-private allowing two-out-of-three signature generation. When \(k\) parties participate in the primality test protocol, one can achieve \(\lfloor {{k-1} \over 2 } \rfloor\) privacy, where any minority of parties learn no information about the factors of \(N\). For the entire collection see [Zbl 0891.00022].
This page was built for publication: Generating a product of three primes with an unknown factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3840167)
