0
$\begingroup$

It seems not safe to exclude possibility of e.g. some next generation quantum computers being able to attack NP problems (e.g. 2WQC) - so maybe it is worth to start thinking of shifting the cryptography breaking difficulty into the next class - still practical polynomial space: PSPACE, based on problems from this class?

Assuming having hypothetical NP solver, we could ask it "for what cryptokey, deciphered prefix is not a noise" - in theory being able to break not only e.g. RSA, but also symmetric ciphers ... the question is how to design more difficult cryptography requiring hypothetical PSPACE solver instead for such potential attack?

PSPACE-complete problems are e.g. SAT with added forall general quantifier, many puzzles and games ... in theory we could make e.g. M2M authentication such a game.

There are also interesting reconfiguration problems - as search for a path satisfying some constraints - what resembles sequential decoding popular in error correction, and could be dependent on cryptographic key (e.g. http://arxiv.org/pdf/1204.5317 ).

Is PSPACE-based cryptography discussed in literature? Could we build some? How? Any other potential protections against hypothetical NP solver? (generally I would gladly discuss/collaborate)

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ For most deterministic classical cryptography, not even NP-complete problems are enough, we want the intersection of NP and coNP which is well within PSPACE and is not know to have complete problems. For some reasoning and caveats as to why see. crypto.stackexchange.com/a/52833/62415. For status of complete problems for this intersection see cstheory.stackexchange.com/questions/49/… $\endgroup$
    – Ilk
    Commented Sep 21, 2023 at 6:44
  • $\begingroup$ My question regards hypothetical situation with e.g. next general quantum computers allowing for practical attacks on NP problems - could we design cryptography still safe in such hypothetical situation? If so, we should search above NP, and still PSPACE - e.g. trying to adapt some PSPACE-complete problem for cryptographic applications. $\endgroup$
    – Jarek Duda
    Commented Sep 21, 2023 at 8:11
  • 1
    $\begingroup$ If you want your encryption/decryption algorithms to be deterministic and classical + consider P to be efficient than you would be bounded by the NP ∩ coNP asymptotically, no matter how efficient. Consider quantum computers communicating (and not allow QKD, instead working from complexity assumtpions), then this is talking about BQP vs QMA, QMA is in PSPACE, you might want to consider QMA-complete problems. PSPACE-complete problems would be no good unless in classical case PSPACE=NP ∩ coNP; or in case of quantum algorithms PSPACE = QMA; (and probably ∩ with coQMA) $\endgroup$
    – Ilk
    Commented Sep 21, 2023 at 8:30
  • 1
    $\begingroup$ Duplicate asked at crypto stack exchange at the same time. crypto.stackexchange.com/questions/108034/… $\endgroup$
    – kodlu
    Commented Sep 21, 2023 at 11:00
  • 1
    $\begingroup$ In practice, we could perhaps build secure post quantum cryptography even if something insane like BQP containing NEXPTIME is true. By having a function that is say O(n) to compute one way on a quantum computer, but O(n^8) to compute the other way or to reduce. But it would depend on what the algorithm looks like and other stuff besides worst case complexity as well. $\endgroup$
    – Colonizor48
    Commented Sep 21, 2023 at 23:26

0

Reset to default

Your Answer

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