Hashing with (some sort of) Public and Private keys/salt/nonce

Question

I'm trying to design a protocol where hashing can involve some public and private components. The idea is that Alice hashes a value with minimal computation and sends the hash to Bob. For Bob it should be exponentially harder to re-create / verify the hash against a given value with the hash he received from Alice.

The hash function Alice is going to use will be something like this, with constant time:

$$H_A = \text{hash_generate}(\mathit{input}, \mathit{private\_component}, \mathit{public\_component})$$

The hash / verification function Bob is going to use will be something like this, with exponential time:

$$\text{hash_verify}(H_A, \mathit{input}, \mathit{public}\_component)$$

---

What I have devised is the following:

This is what Alice does, (this is constant time)

1. Alice creates random $n$ bits as $\mathit{public\_component}$
2. Alice creates random $n$ bits as $\mathit{private\_component}$
3. Alice salts the input with both components and hashes it, say $\text{SHA-3}(input \mathbin \| (\mathit{private\_component} \mathbin \| \mathit{public\_component}))$
4. Alice sends the $\mathit{public\_component}$ and the hash result $H_A$ to Bob

And what Bob does in order to verify is the following:

1. Bob creates random $n$ bits as (replacement) $\mathit{private\_component}^{rand}$
2. Bob salts the input with both components and hashes it, say $\text{SHA-3}(input \mathbin \| (\mathit{private\_component^{rand}} \mathbin \| \mathit{public\_component}))$
3. If the hash result is the same as Alice's hash result, he has verified it
4. If the hash result is the not same as Alice's hash result, goto 1 (or fail with a given repeat count based on $n$, guaranteeing we have done enough permutations to prove that we can't verify the hash)

So the expected complexity of Bob's operation should be around $\mathcal{O}(2^n)$

This protocol is what we have came up with; it's similar to proof of work in a way.

---

Are there protocols for such a use-case? If yes, how are they called?

Answer 1

What you are describing here looks like a thing, indeed. For instance, in the case of passwords, you have human-created password, whose entropy is generally weak and who are often found in dictionaries...

So, suppose you'd like to store the user's password in your database in a way that would prevent an attacker obtaining the database to deduce the actual password used by any given user, the simplest way around it might be to simply hash the passwords and store the hashes, right?

Well, if you just hash the passwords, then an attacker could simply take a dictionary and hash its content and compare it to the hashes he found in your database... So it wouldn't prevent the adversary to possibly find some passwords.

So, the next step is obviously to salt the hashes you are storing, in order to increase the cost of the dictionary attack for your adversary. And you can even use a different salt for each password, thus increasing the cost of a dictionary attack even more.

Note that modern hash functions, such as Blake2, sometimes includes support for salted and even for keyed hashing out of the box.

Modern password hashing algorithm, such as Argon2 are actually very similar to "proof of work", as you noticed, since you want to make your adversary consume as much time and power as possible.

There are also other cases where you'd want something like this (see how HMAC works, for instance.)