[Homepage]

Transpanent-Setup Hidden-Order Group from Factoring

There are some applications like vector commitments, verifiable delay functions [BBBF,Wes,HHKKP], or time-lock puzzles [RSW,TCML] where you need a hidden-order group. As far as I know there are essentially two candidates: the RSA group or a class group. If you want a transparent setup for the group it seems you can only use class groups. Here, I will explain how you can still use something similar to the RSA group. This comes at the cost of a multiplicative overhead roughly linear in the security parameter λ. So, it seems like a strictly theoretical contribution.

The basic idea is to sample λ many big numbers N₁,...,N_λ uniformly at random. Each of them has a constant probability of being hard to factor. As long as N_i is hard to factor the multiplicative group over N_i has a hidden order. Therefore, the multiplicative group over N₁·...·N_λ has a hidden order with all but negligible probability.

Random Number Hard to Factor?

As far as I can tell, a number is hard to factor if its second biggest prime factor is big. So, if I sample a random 3072-bit number and it happens to have two ≥1024-bit prime factors then it seems to be as hard to factor as a 2048-bit RSA modulus. As one can see in this math stackexchange post, the probability that the second largest prime factor of a random 3072-bit number is >1024-bit is around 15%. Therefore, to have a 2^-60 probability that one of the N_i is hard to factor, we need to sample ~256 numbers.

I've just been informed that this is already known. [Bach] analysed the size of prime factors of random integers and [CFGN,Sander] suggested using random prime numbers instead of RSA moduli in different applications.