Cryptosystems whose hardness depends on solving the halting problem?

Question

There has been a lot of work on building cryptosystems whose general security guarantees are attached to famous complexity classes.

This post Gives a list of some famous cryptosystems whose underlying problem is NP-Hard problem.

While I don't expect this to have much practical merit it really does beg what I think is an interesting theoretical question. Can we construct cryptosystems whose underlying problem is undecidable, such as the halting problem or automated theorem proving or the group word problem?

The way such a scheme might behave is that you declare some arbitrary conjecture/instance of other general undecidable problem as a public key, and people can use this conjecture to encrypt their messages, and only the person having the proof of the conjecture could decrypt, vice versa.

Someone Else thought of this too: http://www.cs.utsa.edu/~wagner/PKC/pkc.pdf

Some rebuttals on the practicality of such systems: https://crypto.stackexchange.com/questions/81114/updated-utilizing-a-non-computable-function-to-create-a-one-way-function/81115#81115

Answer 1

For any reasonable public key cryptosystem that I can think of, no, this is not possible. You cannot base a practical public key cryptosystem on any complexity class larger than EXPTIME.

If the private key is linear in the size of the public key (i.e. if the public key is $b$ bits in size, then the private key is no larger than $\alpha b + \beta$ bits for some constants), then you can test all possible private keys (in exponential time) and see which one decrypts a message.