  We initiate the study of multi-party computation for classical
functionalities (in the plain model) with security against malicious
polynomial-time quantum adversaries. We observe that existing techniques
readily give a polynomial-round protocol, but our main result is a construction
of *constant-round* post-quantum multi-party computation. We assume mildly
super-polynomial quantum hardness of learning with errors (LWE), and polynomial
quantum hardness of an LWE-based circular security assumption. Along the way,
we develop the following cryptographic primitives that may be of independent
interest:
  1. A spooky encryption scheme for relations computable by quantum circuits,
from the quantum hardness of an LWE-based circular security assumption. This
yields the first quantum multi-key fully-homomorphic encryption scheme with
classical keys.
  2. Constant-round zero-knowledge secure against multiple parallel quantum
verifiers from spooky encryption for relations computable by quantum circuits.
To enable this, we develop a new straight-line non-black-box simulation
technique against *parallel* verifiers that does not clone the adversary's
state. This forms the heart of our technical contribution and may also be
relevant to the classical setting.
  3. A constant-round post-quantum non-malleable commitment scheme, from the
mildly super-polynomial quantum hardness of LWE.
