5
$\begingroup$

Has it been proven, that a classical codec (encoder-decoder) (classical meaning one that doesn't require a quantum system for its operation) is possible, such that a quantum computer cannot crack it?

I'm assuming that a quantum computer can only solve problems from the NP class and problems that classical computers can solve, where an "NP class problem" is one for which a solution can not be found in polynomial time but if a correct answer is provided, its correctness can be checked in polynomial time.

$\endgroup$
6
  • 1
    $\begingroup$ Hi and welcome to Quantum Computing SE. The assumption number one is wrong. Gate based universal quantum computer can solve any problem a classical one can, i.e. also P problems. $\endgroup$ Dec 19, 2021 at 8:24
  • 2
    $\begingroup$ are you asking whether such a protocol is possible, or whether it has been proven that it exists? There is no proof that it is not possible, and there are protocols that are believed (but not proven) to be quantum-resistant, see en.wikipedia.org/wiki/Post-quantum_cryptography. $\endgroup$
    – glS
    Dec 19, 2021 at 9:43
  • $\begingroup$ @MartinVesely yeah, I knew so I assumed I but didn't explicitly mention it, I'll edit the question $\endgroup$ Dec 19, 2021 at 11:27
  • $\begingroup$ @glS I'm asking whether it has been proven that such a protocol is possible or not $\endgroup$ Dec 19, 2021 at 11:30
  • 1
    $\begingroup$ @ShahidKhan I don't know what you mean with a "proof of possibility". There is no proof of "impossibility" (i.e. non-existence). Isn't that already a "proof of possibility"? $\endgroup$
    – glS
    Dec 19, 2021 at 13:31

1 Answer 1

7
$\begingroup$

[0001] Regarding the OP's first paragraph and the comments therein, there is no protocol, call it $X$, that can be executed efficiently on classical computers, that has been proven to be secure against quantum computers. If we had such a proof then we would also know that P$\ne$NP. This follows because, as @Martin said, a quantum computer can efficiently simulate a classical computer. If we could prove $X$ to be secure against quantum computers, then it follows that $X$ is secure against classical computers. But if $X$ is efficient to execute, then it follows that $X$ is in NP, since verifying a solution must be efficient. If $X$ is further secure against classical computers, then $X$ would not be in P, which means that we have split P from NP and shown them not to be equal.

[0002] Nonetheless, as @gIS provides and as I think is the real intent of the question, there is a whole field called "post-quantum cryptography" - see the Wikipedia link (mentioned by gIS) as well as the links on a sister site, for example. Herein, although there may be no proof that such protocols are secure against a quantum computer, there is other evidence that such protocols may exist. There is an expectation that we may convert to such protocols if and when RSA is broken by a quantum computer capable of running large enough instances of Shor's algorithm. Many leading contenders for such post-quantum cryptography are based on lattices - the learning with errors class of problems being an example therein.

[0003] Regarding the OP's second paragraph, however, the relationship between what is efficient to execute on a quantum computer (researchers call the class of such problems BQP), and what is efficient to verify on a classical computer (as the OP correctly identified, researchers call the class of these problems NP), is really very rich and dynamic. Indeed, there are lots of reasons to believe that the class BQP and the class NP are incomparable - that is, there are problems (such as those in knot theory) that are easy to solve on a quantum computer, and are not even efficiently verifiable on a classical computer. There are interesting approaches to classical verification of quantum computation for such problems. See, e.g., this Quanta article on a breakthrough of Mahadev, who showed how a classically constrained verifier can force a quantum prover to tell the truth.

[0004] However, post-quantum cryptography for classically secure communication, as discussed above, is not based on or invalidated by the existence of problems in BQP but not in NP - which are precisely the kinds of problems Mahadev's protocol addresses. This is not to say that Mahadev's protocol doesn't rely on post-quantum cryptography (indeed it does), but rather, nothing is precluding us to adopt a post-quantum secure protocol even in the event that we never have cryptologically viable quantum computers.

$\endgroup$
6
  • $\begingroup$ Can you explain again how such a protocol would prove the inequality of P and NP? I read it like 6 times and I still don't get it $\endgroup$ Dec 21, 2021 at 6:34
  • $\begingroup$ And my understanding of your answer is: There's no such proof that proves the existence/inexistence possibility/impossibility of such a protocol, called X in your answer; although it may be possible. Am I right? $\endgroup$ Dec 21, 2021 at 6:36
  • $\begingroup$ And here's what I mean by such a codec: A codec is an algorithm that encrypts a message with a password, let's say, then it can only be decoded by that password. also, this scheme is secure against all computers (quantum or not) $\endgroup$ Dec 21, 2021 at 6:40
  • $\begingroup$ I just realized, what I am describing in the above comment is symmetric encryption but it can also be asymmetric. $\endgroup$ Dec 21, 2021 at 7:02
  • $\begingroup$ You want a proof that a public-key protocol, such as something different from RSA, is secure. No such proof exists yet. We can’t even yet show that RSA is secure for classical computers. If we could, then we have a problem- factoring- that is in NP, but not in P. But we haven’t proven that P does not equal NP. So if we could do what you are asking, then we would prove that P does not equal NP. As for your other questions, I would recommend asking another one on this site or on cryptography.stackexchange.com. $\endgroup$
    – Mark S
    Dec 21, 2021 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.