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)
- Alice creates random $n$ bits as $\mathit{public\_component}$
- Alice creates random $n$ bits as $\mathit{private\_component}$
- Alice salts the input with both components and hashes it, say $\text{SHA-3}(input \mathbin \| (\mathit{private\_component} \mathbin \| \mathit{public\_component}))$
- 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:
- Bob creates random $n$ bits as (replacement) $\mathit{private\_component}^{rand}$
- Bob salts the input with both components and hashes it, say $\text{SHA-3}(input \mathbin \| (\mathit{private\_component^{rand}} \mathbin \| \mathit{public\_component}))$
- If the hash result is the same as Alice's hash result, he has verified it
- 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?