GooSig

silver bullet.) The problem is, the owner of the cert might in principle know the factorization, so we didn't want to pick an active root cert. We settled on the AOL root cert because it's the oldest 4096-bit root cert we could find that (1) that saw widespread use, (2) was plausibly uncompromised, but (3) is no longer actively used. To us, this was the best candidate for a 4096-bit modulus for which the factorization is lost---exactly as you say. This is only a heuristic---someone might know the factorization, in which case they could generate false proofs. We think it's exceedingly unlikely, but each person must assess that risk for themselves. This is related to other issues with trusted setup, "toxic waste," etc. (see, e.g., [2] for a discussion of this in the ZCash context). Another way to generate an RSA modulus whose factorization is plausibly unknown is to use a multi-party computation ceremony. In cases like this, you can believe that the factorization is unknown if you trust some fraction of the parties in the computation (details vary). I've heard that Ethereum is planning to do this at some point in the future, but I do not know any other details. As a final point, if one does not want to trust an RSA modulus, an alternative is to work in an imaginary quadratic class group. It's widely believed that there is no efficient way of computing the order of such a (which is what we require for security), and unlike an RSA group there's no trusted setup---you just pick a random prime and that defines your group. The downside is that group operations are about 10x slower. We discuss this a bit more in the paper, and our Python implementation [3] supports both RSA groups and class groups. Please let me know if the above isn't clear! [1] https://en.wikipedia.org/wiki/RSA_Factoring_Challenge [2] https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/ [3] https://github.com/kwantam/GooSig