Such a public key cryptosystem would be "quantum safe" in the sense that quantum computers cannot efficiently solve QMA hard problems.
$\begingroup$
$\endgroup$
2
asked Jun 29, 2018 at 4:59
-
2$\begingroup$ This doesn't directly answer your question but however, they may be relevant to what you're looking for: 1. Zero knowledge proof is possible for all NP statements (link.springer.com/chapter/10.1007/3-540-47721-7_11) 2. All problems in NP admit classical zero-knowledge proof systems, and under reasonable hardness assumptions for quantum computations, these proof systems can be made secure against quantum attacks (arxiv.org/abs/quant-ph/0511020) 3. Every problem in the complexity class QMA has a quantum zero-knowledge proof system (arxiv.org/abs/1604.02804) $\endgroup$– Sanchayan DuttaJun 29, 2018 at 6:44
-
2$\begingroup$ Interestingly, Watrous says in the abstract: "This paper proves that several interactive proof systems are zero-knowledge against general quantum attacks. This includes the well-known Goldreich–Micali–Wigderson classical zero-knowledge protocols for graph isomorphism and graph 3-coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). " Relevant: How do zero knowledge protocol with vertex-3-coloring work? $\endgroup$– Sanchayan DuttaJun 29, 2018 at 6:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
Please start by reading my answer here. I believe you've mistaken the requirements for post-quantum crypto. If you use a scheme which is QMA-hard, then that means either your problem is QMA-complete (in which case, you can decrypt the message using a quantum computer, but not with a classical computer unless NP=QMA), or not (in which case you cannot decrypt efficiently even on a quantum computer). What you typically want for post-quantum crypto is something for which the decryption (by the holder of the private key) can be performed efficiently on a classical computer.
There may be schemes out there which are designed to be run with quantum computers performing the (allowed) decryption, but I'm not aware of any, and they are not the main focus of research at the moment.
As I also described in the other answer, what you're more likely to be interested in is some form of typical case complexity. I suppose it's conceivable that cases with an NP-complete typical case complexity could have worst-case complexity that's QMA-hard.
answered Jun 29, 2018 at 6:54
-
$\begingroup$ I think the original question is worded ambiguously. Probably the OP is asking about decryption of the public message without having the "private key" (?). $\endgroup$ Jun 29, 2018 at 7:13
-
1$\begingroup$ @Blue Of course they are concerned that if you don't have the public key it must be hard to decrypt, but you also need that there exists a public key with which it is easy to decrypt, otherwise the scheme is kind of useless. My point is that these complexity classes prohibit that part of the scheme. $\endgroup$ Jun 29, 2018 at 7:23
-
$\begingroup$ @Blue: is right, I meant "decrypting by an eavesdropper" not "decrypting by the sender or the rightful receiver". I changed the title of the question to "decrypting by an eavesdropper" and then changed it again to just "hacking", let me know if it is still unclear. $\endgroup$ Jun 29, 2018 at 8:34
-
$\begingroup$ Again, I'm looking for some examples of classical public-key cryptosystems where it would be hard for a quantum computer to successfully hack. $\endgroup$ Jun 29, 2018 at 8:35
-
2$\begingroup$ Yes, but my point is that for it to be hard for a quantum computer to hack, the problem only has to not be in BQP, rather than being QMA-hard. For example, in the normal classical case of RSA, the central function is factoring. The problem is (assumed to be) outside P making it hard for a classical computer to hack, but inside NP (NOT NP-hard) so that the rightful receiver can decrypt it on a classical computer. $\endgroup$ Jun 29, 2018 at 8:48