  It is of folkloric belief that the security of classical cryptographic
protocols is automatically broken if the Adversary is allowed to perform
superposition queries and the honest players forced to perform actions
coherently on quantum states. Another widely held intuition is that enforcing
measurements on the exchanged messages is enough to protect protocols from
these attacks.
  However, the reality is much more complex. Security models dealing with
superposition attacks only consider unconditional security. Conversely,
security models considering computational security assume that all supposedly
classical messages are measured, which forbids by construction the analysis of
superposition attacks. Boneh and Zhandry have started to study the quantum
computational security for classical primitives in their seminal work at
Crypto'13, but only in the single-party setting. To the best of our knowledge,
an equivalent model in the multiparty setting is still missing.
  In this work, we propose the first computational security model considering
superposition attacks for multiparty protocols. We show that our new security
model is satisfiable by proving the security of the well-known One-Time-Pad
protocol and give an attack on a variant of the equally reputable Yao Protocol
for Secure Two-Party Computations. The post-mortem of this attack reveals the
precise points of failure, yielding highly counter-intuitive results: Adding
extra classical communication, which is harmless for classical security, can
make the protocol become subject to superposition attacks. We use this newly
imparted knowledge to construct the first concrete protocol for Secure
Two-Party Computation that is resistant to superposition attacks. Our results
show that there is no straightforward answer to provide for either the
vulnerabilities of classical protocols to superposition attacks or the adapted
countermeasures.
