Crypto puzzle as proof of randomness?

Question

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:

1. Create a nonce and send it to the client.
2. 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.
3. 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?

Answer 1

An alternative:

1. Client generates preliminary keypair $(t, T)$ with $T=tB$
2. Clients sends $T$ to server
3. Server sends a random scalar $n$ back(alternatively choose $n = \mathrm{HMAC}(k, T)$ with secret key $k$), and assigns the public key $A = T + nB$ to the client
4. Client uses $a = t+n$ as private and $A$ as public key.

That way the server decides the public key, without knowing the associated private key. If the server shouldn't be able to influence the public key either, you can use a commitment scheme that allows mutually distrusting parties to generate a random number.

---

Your proof-of-work approach doesn't really work since there isn't a good value for the timeout. For typical hash proofs, an attacker can easily have several thousand times the computational power of a defender. GPUs, FPGAs, using cloud computing to rent lots of power for a short time, etc.