<p>It seems not safe to exclude possibility of e.g. some next generation quantum computers being able to attack NP problems (e.g. <a href="https://arxiv.org/pdf/2308.13522" rel="nofollow noreferrer">2WQC</a>) - so maybe it is worth to start thinking of shifting the cryptography breaking difficulty into the next class - still practical polynomial space: <a href="https://en.wikipedia.org/wiki/PSPACE" rel="nofollow noreferrer">PSPACE</a>, based on problems from this class?</p>
<p>Assuming having <strong>hypothetical NP solver</strong>, we could ask it &quot;for what cryptokey, deciphered prefix is not a noise&quot; - 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?</p>
<p><strong><a href="https://en.wikipedia.org/wiki/PSPACE-complete" rel="nofollow noreferrer">PSPACE-complete</a></strong> problems are e.g. <strong>SAT with added forall</strong> general quantifier, many puzzles and <strong>games</strong> ... in theory we could make e.g. M2M authentication such a game.</p>
<p>There are also interesting <strong><a href="https://en.wikipedia.org/wiki/Reconfiguration" rel="nofollow noreferrer">reconfiguration</a> problems</strong> - 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. <a href="http://arxiv.org/pdf/1204.5317" rel="nofollow noreferrer">http://arxiv.org/pdf/1204.5317</a> ).</p>
<p>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)</p>

CC BY-SA 4.0
2023-09-21T06:44:30.247Z
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
CC BY-SA 4.0
2023-09-21T08:11:03.673Z
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
CC BY-SA 4.0
2023-09-21T08:30:22.327Z
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
CC BY-SA 4.0
2023-09-21T08:36:19.853Z
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
CC BY-SA 4.0
2023-09-21T08:48:40.800Z
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
CC BY-SA 4.0
2023-09-21T11:00:54.777Z
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
CC BY-SA 4.0
2023-09-21T23:26:50.083Z
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
CC BY-SA 4.0
2023-09-22T03:16:44.153Z
Dope has been closed on crypto site...
Maarten Bodewes
<np-hardness><cr.crypto-security><pspace>
Could we build PSPACE-based cryptography - more secure post-quantum?
Jarek Duda
# Could we build PSPACE-based cryptography - more secure post-quantum?

(Asked by: username_0 on 2023-09-21)

It seems not safe to exclude possibility of e.g. some next generation quantum computers being able to attack NP problems (e.g. [2WQC](https://arxiv.org/pdf/2308.13522)) - so maybe it is worth to start thinking of shifting the cryptography breaking difficulty into the next class - still practical polynomial space: [PSPACE](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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)

**Tags:** np-hardness, cr.crypto-security, pspace

> **Comments:**
> **username_1**: 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  
> **username_0**: 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.  
> **username_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)  
> **username_1**: 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  
> **username_1**: 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  
> **username_2**: 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  
> **username_3**: 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.  
> **username_4**: Dope has been closed on crypto site...  

---

## 0 answers

