Classical knowledge for quantum security (extended abstract)

Ellie D’Hondt, Mehrnoosh Sadrzadeh

Published Jan 1, 2008• 0 citations

OpenAlex

Abstract

Related papers

Classical Knowledge for Quantum Security

Ellie D’Hondt, Mehrnoosh Sadrzadeh

Aug 26, 20081 citation

Classical Knowledge for Quantum Security

D'Hondt, Ellie, Mehrnoosh Sadrzadeh

arXiv:0808.3574Aug 26, 20080 citations

Classical Knowledge for Quantum Security

Ellie D’Hondt, Mehrnoosh Sadrzadeh

We propose a decision procedure for analysing security of quantum cryptographic protocols, combining an algebraic logic rewrite system with an operational semantics for quantum distributed computations. We apply our approach to reasoning about security properties of a recently developed quantum secret sharing protocol.

Electronic Notes in Theoretical Computer ScienceFeb 1, 20112 citations

Classical Knowledge for Quantum Cryptographic Reasoning

Vincent Danos A, Ellie D’Hondt

Electronic Notes in Theoretical Computer ScienceNov 1, 20083 citations

Superposition Attacks on Cryptographic Protocols

Ivan Damgård, Jakob Funder, Jesper Buus Nielsen +1 more

arXiv:1108.6313Lecture notes in computer scienceJan 1, 201455 citations

An Epistemic Measurement System for Quantum Security

Elham Kashefi, Mehrnoosh Sadrzadeh

Jan 1, 20070 citations

Classical knowledge for quantum security (extended abstract)

Ellie D’Hondt, Mehrnoosh Sadrzadeh

Published Jan 1, 2008• 0 citations

OpenAlex

Abstract

Related papers

Classical Knowledge for Quantum Security

Ellie D’Hondt, Mehrnoosh Sadrzadeh

We propose a decision procedure for analysing security of quantum cryptographic protocols, combining a classical algebraic rewrite system for knowledge with an operational semantics for quantum distributed computing. As a test case, we use our procedure to reason about security properties of a recently developed quantum secret sharing protocol that uses graph states. We analyze three different scenarios based on the safety assumptions of the classical and quantum channels and discover the path of an attack in the presence of an adversary. The epistemic analysis that leads to this and similar types of attacks is purely based on our classical notion of knowledge.We propose a decision procedure for analysing security of quantum cryptographic protocols, combining a classical algebraic rewrite system for knowledge with an operational semantics for quantum distributed computing. As a test case, we use our procedure to reason about security properties of a recently developed quantum secret sharing protocol that uses graph states. We analyze three different scenarios based on the safety assumptions of the classical and quantum channels and discover the path of an attack in the presence of an adversary. The epistemic analysis that leads to this and similar types of attacks is purely based on our classical notion of knowledge.

Aug 26, 20081 citation

Classical Knowledge for Quantum Security

D'Hondt, Ellie, Mehrnoosh Sadrzadeh

arXiv:0808.3574Aug 26, 20080 citations

Classical Knowledge for Quantum Security

Ellie D’Hondt, Mehrnoosh Sadrzadeh

Electronic Notes in Theoretical Computer ScienceFeb 1, 20112 citations

Classical Knowledge for Quantum Cryptographic Reasoning

Vincent Danos A, Ellie D’Hondt

We prove that quantum key distribution is secure against several types of attacks within the framework of classical knowledge knowledge for quantum systems, a formal model which was developed in [D'Hondt, E. and P. Panangaden, Reasoning about quantum knowledge, in: Proceedings of the 25th Conference on Foundations of Software Technology and Theoretical Computer Science, LNCS 3821, 2005, p. 0544c (to appear), quant-ph/0507176]. In particular we rephrase security as a logical property and use meta-logic reasoning on the finite state machine corresponding to the quantum key distribution protocol. While these security issues have been studied before, it is the logical-based approach that is original here.We prove that quantum key distribution is secure against several types of attacks within the framework of classical knowledge knowledge for quantum systems, a formal model which was developed in [D'Hondt, E. and P. Panangaden, Reasoning about quantum knowledge, in: Proceedings of the 25th Conference on Foundations of Software Technology and Theoretical Computer Science, LNCS 3821, 2005, p. 0544c (to appear), quant-ph/0507176]. In particular we rephrase security as a logical property and use meta-logic reasoning on the finite state machine corresponding to the quantum key distribution protocol. While these security issues have been studied before, it is the logical-based approach that is original here.

Electronic Notes in Theoretical Computer ScienceNov 1, 20083 citations

Superposition Attacks on Cryptographic Protocols

Ivan Damgård, Jakob Funder, Jesper Buus Nielsen +1 more

Attacks on cryptographic protocols are usually modeled by allowing an adversary to ask queries to 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. Even if the protocol is quantum, the queries are typically classical. In this paper, we introduce a new model of quantum attacks on protocols, where the adversary is allowed quantum access to the primitive, i.e., he may 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$ . This holds for all classical as well as all known quantum secret sharing schemes. We then consider zero- knowledge and first show that known protocols are not, in general, secure in our model by designing a superposition attack on the well-known zero-knowledge protocol for graph isomorphism. We then use our secret-sharing result to design 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 give a characterization of a class of protocols that can be shown secure, though not necessarily with efficient simulation. We show that this class contains non-trivial protocols that cannot be shown secure by running a classical simulator in superposition.Attacks on cryptographic protocols are usually modeled by allowing an adversary to ask queries to 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. Even if the protocol is quantum, the queries are typically classical. In this paper, we introduce a new model of quantum attacks on protocols, where the adversary is allowed quantum access to the primitive, i.e., he may 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$$ . This holds for all classical as well as all known quantum secret sharing schemes. We then consider zero- knowledge and first show that known protocols are not, in general, secure in our model by designing a superposition attack on the well-known zero-knowledge protocol for graph isomorphism. We then use our secret-sharing result to design 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 give a characterization of a class of protocols that can be shown secure, though not necessarily with efficient simulation. We show that this class contains non-trivial protocols that cannot be shown secure by running a classical simulator in superposition.

arXiv:1108.6313Lecture notes in computer scienceJan 1, 201455 citations

An Epistemic Measurement System for Quantum Security

Elham Kashefi, Mehrnoosh Sadrzadeh

We develop a formal system to reason about knowledge properties of quantum security protocols. The formalism is obtained via a marriage of measurement calculus [3], an algebraic framework for measurementbased quantum computing [7], with the algebra of epistemic actions and their appearance maps [1, 8]. Measurement calculus has also proven to be a proper language to describe and to analyse distributed quantum protocols [4]. Protocols (here referred to as measurement pattern) are described by a combination of commands: 1-qubit preparations Ni (prepares qubit i in state |+〉i), 2-qubit entanglement operators Eij: = ∧Zij (controlled-Z operator), 1-qubit measurements M α i, and 1-qubit Pauli corrections Xi and Zi, where i, j represent the qubits on which each of these operations apply, and α ∈ [0, 2π). Measurement M α i is defined by orthogonal projections P |+α〉 i (with outcome si = 0) and P |−α〉 i (with outcome si = 1). 1 Dependent corrections, used to control non-determinism, will be written X sj i and Zsj i, with X0 i = Z0 i = I, X1 i = Xi, and Z1 i = Zi. Any pattern can be put in a standard form, where all the preparation and entanglementWe develop a formal system to reason about knowledge properties of quantum security protocols. The formalism is obtained via a marriage of measurement calculus [3], an algebraic framework for measurementbased quantum computing [7], with the algebra of epistemic actions and their appearance maps [1, 8]. Measurement calculus has also proven to be a proper language to describe and to analyse distributed quantum protocols [4]. Protocols (here referred to as measurement pattern) are described by a combination of commands: 1-qubit preparations Ni (prepares qubit i in state |+〉i), 2-qubit entanglement operators Eij: = ∧Zij (controlled-Z operator), 1-qubit measurements M α i, and 1-qubit Pauli corrections Xi and Zi, where i, j represent the qubits on which each of these operations apply, and α ∈ [0, 2π). Measurement M α i is defined by orthogonal projections P |+α〉 i (with outcome si = 0) and P |−α〉 i (with outcome si = 1). 1 Dependent corrections, used to control non-determinism, will be written X sj i and Zsj i, with X0 i = Z0 i = I, X1 i = Xi, and Z1 i = Zi. Any pattern can be put in a standard form, where all the preparation and entanglement

Jan 1, 20070 citations

t

in the standard model is secure against superposition attacks if and only if the threshold is lowered to

t/2

. This holds for all classical as well as all known quantum secret sharing schemes. We then consider zero- knowledge and first show that known protocols are not, in general, secure in our model by designing a superposition attack on the well-known zero-knowledge protocol for graph isomorphism. We then use our secret-sharing result to design 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 give a characterization of a class of protocols that can be shown secure, though not necessarily with efficient simulation. We show that this class contains non-trivial protocols that cannot be shown secure by running a classical simulator in superposition.