Superposition attacks on cryptographic protocols

DOI10.1007/978-3-319-04268-8_9MaRDI QIDQ2948260zbMATH OpenOpenAlexFDO

Authors Jakob Funder, Jesper Buus Nielsen, Louis Salvail, Ivan B. Damgård

Publication date 30 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.6313

Mathematics Subject Classification ID

Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Abstract: Attacks on classical cryptographic protocols are usually modeled by allowing an adversary to ask queries from an oracle. Security is then defined by requiring that as long as the queries satisfy some constraint, there is some problem the adversary cannot solve, such as compute a certain piece of information. In this paper, we introduce a fundamentally new model of quantum attacks on classical cryptographic protocols, where the adversary is allowed to ask several classical queries in quantum superposition. This is a strictly stronger attack than the standard one, and we consider the security of several primitives in this model. We show that a secret-sharing scheme that is secure with threshold $t$ in the standard model is secure against superposition attacks if and only if the threshold is lowered to $t/2$. We use this result to give zero-knowledge proofs for all of NP in the common reference string model. While our protocol is classical, it is sound against a cheating unbounded quantum prover and computational zero-knowledge even if the verifier is allowed a superposition attack. Finally, we consider multiparty computation and show that for the most general type of attack, simulation based security is not possible. However, putting a natural constraint on the adversary, we show a non-trivial example of a protocol that can indeed be simulated.

Recommendations

• Dispelling myths on superposition attacks: formal security model and attack analyses
• Dispelling myths on superposition attacks: formal security model and attack analyses
• Quantum communication attacks on classical cryptographic protocols. (Invited talk)

Cited in

(22)

• Improved BV-based quantum attack on block ciphers
• Quantum indistinguishability for public key encryption
• Quantum attacks on some Feistel block ciphers
• Using Bernstein-Vazirani algorithm to attack block ciphers
• Cryptanalysis and improvement of verifiable quantum (k,n) secret sharing
• Quantum lightning never strikes the same state twice. Or: quantum money from cryptographic assumptions
• Correction to: ``Dispelling myths on superposition attacks: formal security model and attack analyses
• Complete analysis of Simon's quantum algorithm with additional collisions
• A quantum related-key attack based on the Bernstein-Vazirani algorithm
• Applications of Simon's algorithm in quantum attacks on Feistel variants
• Relationships between quantum IND-CPA notions
• Breaking symmetric cryptosystems using quantum period finding
• Semantic security and indistinguishability in the quantum world
• Quantum communication attacks on classical cryptographic protocols. (Invited talk)
• Dispelling myths on superposition attacks: formal security model and attack analyses
• Dispelling myths on superposition attacks: formal security model and attack analyses
• A note on the post-quantum security of (ring) signatures
• On security notions for encryption in a quantum world
• Tracing quantum state distinguishers via backtracking
• On security notions for encryption in a quantum world
• On quantum simulation-soundness
• Quantum cryptography beyond quantum key distribution

This page was built for publication: Superposition attacks on cryptographic protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2948260)