Paper 2020/816

Dispelling Myths on Superposition Attacks: Formal Security Model and Attack Analyses

Luka Music, Céline Chevalier, and Elham Kashefi

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
cryptographic protocolssuperposition attackpost-quantum securitysecurity modelYao's protocol
Contact author(s)
luka music @ lip6 fr
History
2020-07-06: received
Short URL
https://ia.cr/2020/816
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/816,
      author = {Luka Music and Céline Chevalier and Elham Kashefi},
      title = {Dispelling Myths on Superposition Attacks: Formal Security Model and Attack Analyses},
      howpublished = {Cryptology ePrint Archive, Paper 2020/816},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/816}},
      url = {https://eprint.iacr.org/2020/816}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.