0

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)

Jarek Duda
  • 325
  • 1
  • 11
  • 2
    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. https://crypto.stackexchange.com/a/52833/62415. For status of complete problems for this intersection see https://cstheory.stackexchange.com/questions/49/consequences-of-complete-problems-for-np-intersects-conp – Ilk Sep 21 '23 at 06:44
  • 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. – Jarek Duda Sep 21 '23 at 08:11
  • 1
    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) – Ilk Sep 21 '23 at 08:30
  • This is similar to the case of not being able to base classical cryptography on NP-complete problems unless NP=coNP. As discussed in the first linked answer in the first comment. Also the reason for QMA is that QMA is to BQP as NP is to P in a sense important for polynomially scaling encryption with respect to the bits of security see, https://www.cs.umd.edu/class/fall2019/cmsc657/projects/group_8.pdf – Ilk Sep 21 '23 at 08:36
  • For non-asymptotic, concrete arguments, you would probably still be bounded by P, but you would consider gaps in constants between best encryption(with public key)/decryption(with private key) and best decryption(with public key), some interesting ideas on this front are in the work on "Post-quantum RSA" https://eprint.iacr.org/2017/351.pdf But then you are working non-asymptotically so complexity classes lose their meaning and talking about P or PSPACE makes little sense to me – Ilk Sep 21 '23 at 08:48
  • 1
    Duplicate asked at crypto stack exchange at the same time. https://crypto.stackexchange.com/questions/108034/could-we-build-pspace-based-cryptography-more-secure-post-quantum – kodlu Sep 21 '23 at 11:00
  • 1
    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. – Colonizor48 Sep 21 '23 at 23:26
  • Dope has been closed on crypto site... – Maarten Bodewes Sep 22 '23 at 03:16

0 Answers0