Embedding POW in an EC public key

Question

I have an application where it would be advantageous for an attacker to have to spend a long time generating public keys.

To do this, I require that the hash of the public key be less than a certain number. That way a typical user will take 1 second to generate a public key, and an attacker who is trying to DOS public resources will also have to spend more resources to do so than it costs for us to detect.

There are two mechanisms proposed:

1. Take a public key, hash it many times with an incrementing salt, and require the result to be less than a certain number.

2. Generate a public key, hash it once, and if the result is not less than a certain number, add one to the private key and add the generator to the public key.

The first mechanism helps mitigate DOS and spam attacks. The second mechanism helps mitigate some MITM attacks as well.

I like the features of the second, except for some drawbacks:

1. This reduces the number of valid public keys that exist, and could reduce search space for an attacker attempting in the process of brute forcing public keys. Since we're using a secure hash, it seems the DLP remains equally hard with or without this hash.
2. This relies on the point addition algorithm being highly efficient, and assumes an attacker may not have some new and better way to perform this operation. But this is as opposed to assuming efficient hashing, an equal assumption?
3. It's possible that an unprivileged attacker observing the initial POW generation could determine some information about the key. Not a huge deal since these keys are not frequently generated, but perhaps not.

Are there other things I should be thinking about? Is there a standard out there in the wild I haven't found?

Answer 1

I like the features of the second, except for some drawbacks:

I don't believe the drawbacks are as bad as you think.

1.This reduces the number of valid public keys that exist, and could reduce search space for an attacker attempting in the process of brute forcing public keys.

It doesn't help the attacker; if the attacker sees the public key, the knowledge that the hash is small doesn't help him (as he sees the exact value). And the additional hashing requirement doesn't help Pollard Rho or Big-Step-Little-Step (two algorithms for computing discrete logs)

2.This relies on the point addition algorithm being highly efficient, and assumes an attacker may not have some new and better way to perform this operation.

I believe that's a fairly safe assumption; it's hard to see how someone could generate $(x, xG)$ pairs in a manner that is significantly more efficient than your algorithm. In any case, the most significant threat is an attacker with a bot or DSP farm; that would allow him to generate a number of public keys considerably faster than an honest user.

3.It's possible that an unprivileged attacker observing the initial POW generation could determine some information about the key.

With your algorithm, the attacker has no knowledge of where you started the search. If he learns that you took a while, he can deduce that a $(x - \delta)G$ doesn't meet the hashing criteria for a number of $\delta$s, however, as he can see the value $xG$, he could verify that directly if he wanted to, and so it doesn't actually leak any information about the private key.

So, it looks safe; my only concern is that it might not provide as much DoS protection as you hoped (of course, I don't know how much protection you're looking for, and what assumptions you are willing to make about attacker capabilities...)