# 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. –  CodesInChaos Feb 3 '13 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 '13 at 17:27
But a DHT usually has no authoritative server, so who would enforce the time limit or generate the nonce? –  CodesInChaos Feb 3 '13 at 17:29
@CodesInChaos: the authoritative server :) –  orlp Feb 3 '13 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 '13 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 '13 at 18:23
summing A would be called a group addition, summing s a scalar addition. –  CodesInChaos Feb 3 '13 at 18:43
I managed to implement it, thanks a ton! This property of Ed25519 is really cool. –  orlp Feb 3 '13 at 19:58
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. –  CodesInChaos Feb 4 '13 at 11:06