Building a hard to factor number without knowing its factorization It is possible to find an efficient algorithm for constructing a provably hard to factor number $N$, together with a witness that shows that it is indeed hard to factor. EDIT, since it was not clear: I also want to be sure that even the person that constructed the number cannot factor it.

Of course, a random large enough integer is going to be hard to factor with high probability, but we might be unlucky.

There are also multi-party protocols for shared generation of RSA moduli (such as http://crypto.stanford.edu/~dabo/abstracts/sharing.html), but I would like a non interactive technique.

Motivation: This was suggested by Poncho's answer to Compare two hashes with different salt
The zerocoin paper mentions such a technique:


  implementers can use the
  technique of Sander for generating so-called RSA UFOs
  for accumulator parameters without a trapdoor


and refers to:


  T. Sander, “Efficient accumulators without trapdoor extended
  abstract,” in Information and Communication Security, vol.
  1726 of LNCS, 1999, pp. 252–262.


I can't access it since it's behind a paywall, but according to a comment by Hal Finney they're rather large:


  As far as the Sander paper, trust can be minimized by seeding a random number generator from a public headline. The real problem with this approach is that it generates ridiculously large RSA moduli. One example they give in their paper is 40,000 bits!