Could quantum computers be useful for sending encrypted information over a classical channel?

Question

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.

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.