I simply mean an adversary who uses a quantum computer. Such an adversary can solve harder problems, so they can sometimes break the assumptions underlying a cryptosystem even if it is secure against classical computers.
There is a more interesting problem which arises against quantum adversaries however. For example, consider a psuedorandom function family. An efficient classical protocol can obviously only query the function at a polynomial number of points—each query takes time. But a quantum protocol can query the function in superposition at exponentially many points at once and then do something with the resulting quantum state. This is really a fundamental difference which is poorly understood.
Great post, thanks—this is exactly what I read LW to discover.
The term “quantum adversary” came up several times, but doesn’t seem to be defined in the main text.
I simply mean an adversary who uses a quantum computer. Such an adversary can solve harder problems, so they can sometimes break the assumptions underlying a cryptosystem even if it is secure against classical computers.
There is a more interesting problem which arises against quantum adversaries however. For example, consider a psuedorandom function family. An efficient classical protocol can obviously only query the function at a polynomial number of points—each query takes time. But a quantum protocol can query the function in superposition at exponentially many points at once and then do something with the resulting quantum state. This is really a fundamental difference which is poorly understood.