Crypto puzzle as proof of randomness?

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.

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?

• "being able to influence it more than a few bits is a security risk" seems like a really weird requirement. Feb 3, 2013 at 17:18
• @CodesInChaos: the public key is used as a node id in the Kademlia DHT, being able to choose it allows for attacks like the Eclipse attack.
– orlp
Feb 3, 2013 at 17:27
• But a DHT usually has no authoritative server, so who would enforce the time limit or generate the nonce? Feb 3, 2013 at 17:29
• @CodesInChaos: the authoritative server :)
– orlp
Feb 3, 2013 at 18:09

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.

• The server is allowed to influence the public key.
– orlp
Feb 3, 2013 at 17:28
• I'm new to elliptic curve cryptography, how would the sum A and the sum a be calculated? A general answer is nice, but if you could comment on it using the terminology/functions used in the SUPERCOP implementation (also available from my github) that would be nice.
– orlp
Feb 3, 2013 at 18:23
• summing A would be called a group addition, summing s a scalar addition. Feb 3, 2013 at 18:43
• You can use the same technique with other elliptic curves, or even finite fields. For example Bitcoin Vanitygen uses it so that the party who uses a lot of computational power to find the meaningful address doesn't need to know the private key. Feb 4, 2013 at 11:06
• Allright, just for future reference, I added the implementation to my github ed25519 repo, available as the ed25519_add_scalar function.
– orlp
Feb 4, 2013 at 17:09