I need an untrusted client to generate a random public/private keypair (in particular, an Ed25519 keypair, which can be generated really fast), but I'm only allowed to see the public key. The randomness is important because the public key is used in attack-sensitive ways such that being able to influence it more than a few bits is a security risk.
I had the following idea:
- Create a nonce and send it to the client.
- Let the client create a public/private keypair such that
hash(public_key + nonce)starts with at least n zero bits and send it back.
- If the client returns a public/private keypair after t seconds, reject it.
Is this a correct scheme to ensure randomness of the keypair, given an appropriately chosen n and t?