Just out of curiosity: is a similar problem (generate a valid public key that surely nobody including myself can know the private key of) solvable for RSA?
This is a great question. To rephrase: is it possible to come up with an RSA modulus that even you don't know the factorization of?
The answer, I believe, is we have no way of doing that so far. The closest thing that exists is "multiparty" or "distributed" generation of an RSA modulus. Roughly, in the two party case of Alice and Bob, this means Alice picks some pair of numbers (P1, Q1) and Bob similarly picks some (P2, Q2). Then, Alice and Bob engage in some secure multiparty computation protocol whereby they obliviously a) check P1+P2 and Q1+Q2 are prime, and b) if so, output N=(P1+P2)(Q1+Q2) to both Alice and Bob.
At the end of the protocol (after repeating enough times that it succeeds), both parties have derived an N whose factorization they don't know.
I don't know much about this area of study, but searching multiparty RSA modulus generation should bring up relevant papers.
That problem can't be solvable in any context. There's no way to rule out the possibility that someone else in the world knows your mathematical secret.
Let’s try it this way: what if two people, unlikely as it may be, generate the same key pair? Two people know the private key, and factoring is still hard.
The answer, I believe, is we have no way of doing that so far. The closest thing that exists is "multiparty" or "distributed" generation of an RSA modulus. Roughly, in the two party case of Alice and Bob, this means Alice picks some pair of numbers (P1, Q1) and Bob similarly picks some (P2, Q2). Then, Alice and Bob engage in some secure multiparty computation protocol whereby they obliviously a) check P1+P2 and Q1+Q2 are prime, and b) if so, output N=(P1+P2)(Q1+Q2) to both Alice and Bob.
At the end of the protocol (after repeating enough times that it succeeds), both parties have derived an N whose factorization they don't know.
I don't know much about this area of study, but searching multiparty RSA modulus generation should bring up relevant papers.