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