6
$\begingroup$

I've been thinking about the following problem and haven't yet found a solution.

We have an arbitrary and public hash function $\text{Hash}$.

Could I possibly publish a function $F$ (that is, publish an algorithm that returns $F(M)$ given $M$) such that

  • $F(M)=K$ whenever $\text{Hash}(M)=0$, where $K$ is a previously defined private key that only I know;
  • There's no better way, for a stranger, to obtain $K$ than to find a zero of $\text{Hash}$ and pass it to $F$

A positive answer to this question would imply imply that it is possible to publish ``bounties'' for people achieving some computational work: for instance $K$ could be the private key of a cryptocurrency wallet. It could also allow for a timelock encryption mechanism based on proof-of-work.

Thanks in advance!

$\endgroup$
4
  • $\begingroup$ Not putting it as an answer, because it's not really a cryptography answer, but a number of cryptocurrencies already support this directly, and already have "bounty" wallets that you can unlock with the solution to a problem. $\endgroup$
    – James_pic
    Commented Jun 25 at 8:51
  • $\begingroup$ This sounds similar to the Hashcash algorithm. $\endgroup$ Commented Jun 25 at 15:28
  • $\begingroup$ @James_pic could you expand on that? What cryptos in particular? $\endgroup$
    – aleph2
    Commented Jun 25 at 20:10
  • $\begingroup$ Ethereum has Turing complete smart contracts, as do a few others, so it's possible to make payment conditional on anything that can be evaluated by a Turing machine. Even bitcoin support "bitcoin script", which whilst not Turing complete is sufficient to support "puzzle" wallets, that require you to know the preimage of a given hash. Of course this isn't what you asked for - there's no secret key K to be unlocked, you unlock the wallet with the solution to the problem directly. $\endgroup$
    – James_pic
    Commented Jun 26 at 14:25

1 Answer 1

9
$\begingroup$

What you describe is witness encryption. In normal encryption, you encrypt a payload so that anyone with the corresponding decryption key can read it. In witness encryption, you encrypt so that anyone with the solution to a puzzle can read it. The person encrypting doesn't need to know the/a solution, and doesn't even need to know whether a solution exists.

I quote from the paper that introduced witness encryption, which motivates the problem similarly to you:

When we encrypt a message using a public-key encryption scheme, we allow the receiver to learn our message only if he knows a secret key corresponding to his public key. What if we don’t really care if he knows a secret key, but we do care if he knows a solution to a crossword puzzle that we saw in the Times? Or if he knows a short proof for the Goldbach conjecture? Or, in general, the solution to some NP search problem?

...

There are multiple real life examples where a monetary award has been offered for the solution to a puzzle or problem including: the Clay Institute Millennium Prize Problems [Ins] and the Eternity Puzzle [Web]. For these challenges one could consider encoding the problem in terms of an NP-complete problem and encrypting the password to a bank account containing the funds.

More formally, you encrypt with respect to a polynomial-time predicate $P$, and anyone who can produce a witness $w$ such that $P(w)=1$ can decrypt. In this case $P$ is the predicate that checks whether $\text{Hash}(w)\overset?= 0$.

Witness encryption is a theoretical feasibility, and can be constructed using very heavy machinery. I don't think you would be able to realistically implement your stated goal in practice, though.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.