A quantum computer running Shor's algorithm would be famously useful for decrypting information encrypted by many classical public-key cryptography algorithms. Is there any reason (either a specific proposed protocol or a general heuristic argument) to suspect that a quantum computer could be useful for encrypting information in a way that's more secure than is possible with a classical computer with comparable resources? Ideally, secure even against attacks by quantum computers?

I'm not talking about "physics-based" quantum encryption schemes like quantum key distribution (discussed here) or other schemes that require transmitting a coherent quantum state over a quantum channel. I'm talking about more traditional "mathematics-based" encryption schemes, in which one or both parties have a quantum computer at each end, but they can only transmit the encoded information in the form of classical bit strings over an insecure classical channel (potentially after having transmitted a symmetric key out of band).

This question is inspired by Scott Aaronson's comments here and here on his blog. Apparently people regularly claim that quantum computers (not QKD) could be useful for encryption, but Prof. Aaronson has never understood why.


1 Answer 1


This is a purely hypothetical answer - I don't know if anybody has ever studied it, and have not attempted to find out - but think about public key cryptography. Current public key systems are based on the idea that some problems in the complexity class NP are probably hard to solve directly, but there exists a "proof" that lets you verify the solution easily. This proof constitutes the decryption key. If you've got it, the message is easy to decrypt. If you haven't, it's hard.

Now, the current problem is that everybody's favourite example is based on factoring, which is broken by a quantum computer. So, you'd like a quantum-secure replacement. Post-quantum crypto aims to do that via purely classical means. The theory being that if you base it on an NP-complete problem, the "probably hard to solve" part is probably still hard for a quantum computer. But you could conceivably base it on a QCMA-complete problem. These are problems for which the simple proof comprises classical data, but the proof is only simple for a quantum computer. This suggests the possibility of a public key cryptosystem where all the messages passed are classical (I have no idea if it's sufficient to have a classical proof to guarantee the existence of a system where all messages are classical, whether there's more to it, or whether it's simply impossible), but they need a quantum computer to encrypt/decrypt.

  • $\begingroup$ This is thought-provoking, but I'm not sure if I made my question clear. Please correct me if I'm misunderstanding, but you seem to be proposing a cryptosystem that's secure against classical attacks (perhaps even more so than RSA?), vulnerable to quantum attacks, and requires a quantum computer to both encrypt and decrypt. But I'm not sure what that's useful for, since RSA is already believed to be secure against classical attacks. I'm looking for a public-key cryptosystem that's secure even against quantum attacks. Is yours? $\endgroup$
    – tparker
    Commented Jan 3, 2020 at 5:17
  • $\begingroup$ @tparker this would be secure against quantum attacks to the extent that we believe QCMA and BQP are not equal, which is at least as strong a belief as you’d get from post quantum cryptography because QCMA contains NP. $\endgroup$
    – DaftWullie
    Commented Jan 3, 2020 at 6:29
  • $\begingroup$ I think a slight nitpick is that there aren't actually any cryptosystems that are based on NP-complete problems (which haven't already been broken). As discussed at stackoverflow.com/q/311064/5133482, NP-completeness isn't really relevant for cryptography, because it considers worst-case hardness, while average-case hardness is what's important for cryptography. But think your basic point still stands. $\endgroup$
    – tparker
    Commented Jan 4, 2020 at 23:10
  • $\begingroup$ Agreed. I was trying to avoid over-complicating the answer. $\endgroup$
    – DaftWullie
    Commented Jan 5, 2020 at 6:40

Your Answer

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

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