Usual post-quantum crypto, like the isogeny-based algorithm, has its value lying in that no one yet has found a quick way to break it with quantum computer. This makes me wonder why don't we build post-quantum crypto based on undecidable problems? Yes, in some case quantum computers can be much faster than traditional ones, but they are still weaker than Turing machines, which can not solve the undecidable problems.

What's the difficulty and why few people consider it?

  • $\begingroup$ So, how would you decide a cryptosystem based on, say, the halting problem (that is, if you can break this cryptosystem, you can solve general halting-problem instances)? $\endgroup$
    – poncho
    Jul 1, 2020 at 20:35
  • 2
    $\begingroup$ Yehuda Lindell's answer for (updated) Utilizing a non-computable function to create a one-way function is very related for you. $\endgroup$
    – kelalaka
    Jul 1, 2020 at 21:09
  • $\begingroup$ Also related is my answer crypto.stackexchange.com/questions/773/… - if an unbounded adversary can break a public key encryption, it can't be built on the halting problem (because that is unsolvable, even with unbounded computation) $\endgroup$
    – poncho
    Jul 1, 2020 at 21:24
  • $\begingroup$ @kelalaka thank you! That makes much sense to me. To solve the problem posted by Lindell we need to find a noncomputable function that is also hard to solve on average cases. Haven't heard of anything like that. -poncho thanks for your comments too.. thought I have to admit I don't really understand what you mean. $\endgroup$
    – Student
    Jul 2, 2020 at 11:05


Your Answer

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

Browse other questions tagged or ask your own question.