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


1 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.

  • $\begingroup$ This suggests what i'm looking for is possible, that is if we relax the private key's size requirement to merely be "finite" and not upper bounded by any function of the size of the public key, it should be possible to accomplish this. The term "reasonable" might not be so anymore depending on the size of the private key. $\endgroup$ Commented Oct 28, 2020 at 0:52
  • $\begingroup$ If you want private keys to be too impractical to manage, I suppose so. $\endgroup$
    – Pseudonym
    Commented Oct 28, 2020 at 4:33

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.