Quantum entanglement establishment between two strangers

This paper presents the first quantum entanglement establishment scheme for strangers who neither pre-share any secret nor have any authenticated classical channel between them. The proposed protocol requires only the help of two almost dishonest third parties (TPs) to achieve the goal. The security analyses indicate that the proposed protocol is secure against not only an external eavesdropper’s attack, but also the TP’s attack.

This research is partially supported by the Ministry of Science and Technology, Taiwan, R.O.C., under the Contract No. MOST 104-2221-E-006-102.

Authors and Affiliations

1. Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Rd., Tainan City, 701, Taiwan, ROC

   Tzonelih Hwang, Tzu-Han Lin & Shih-Hung Kao

Corresponding author

Correspondence to Tzonelih Hwang.

Appendix: Formal security model and analysis

In this section, we define the adversarial model of the two public discussions in Step 2 and Step 3 of the proposed scheme. The security of the first public discussion (Step 2) is analyzed in “The first public discussion” section and then, the second public discussion (Step 3) is analyzed in “The second public discussion” section.

1.1 The first public discussion

In the following analyses, the public discussion between Alice and TP1 is analyzed. Note that the security of the public discussion between Bob and TP1 is the same as the one between Alice and TP1; hence, we omit that in the following description.

1.1.1 Formal security model

The security model of the interactions between an adversary and the protocol participants occurs only via oracle queries which model the adversary’s capabilities in a real attack. Let A denote Alice, TP1 denote TP1, and P1 is the public discussion they participate. The participants of P1 can launch more than one instance. Here we allow a probabilistic polynomial time (PPT) adversary \(\mathscr {A}\) to potentially control all the communication in the network via accessing to a set of oracles as defined below. Let \(A^{i}\) denotes the instance i of A. \(TP1^{\text {j}}\) is the instance j of TP1.

Execute (\(A^{i},TP1^{j}\)): The query models the passive attack. An adversary can obtain all messages exchanged between \(A^{i}\) and \(TP1^{j}\).

Reveal (\(A^{i}\)) : In this query model, if the oracle has accepted, it returns the secret quantum state between \(A^{i}\) and \(TP1^{j}\) to the adversary; otherwise, it returns the null value to the adversary.

Send (\(A^{i}/TP1^{j},m\)): This query models an active attack. It returns the information corresponded to an input m that \(A^{i}\) or \(TP1^{j}\) would send to each other.

Corrupt (\(A^{i},a\)): This query models corruption capability of the adversary. If \(a=0\), it returns a null value; otherwise, it returns the secret quantum states between \(A^{i}\) and \(TP1^{j}\).

Test (\(TP1^{j}\)): This query measures whether the public discussion is secure or not. By throwing an unbiased coin, b, if \(b=1\), it returns a random bit sequence with the same length as \(A^{i}\)’s measurement result. The query can only be called once.

In this model, we consider two kinds of adversaries. A passive adversary is allowed to issue the Execute and Test queries, and an active adversary is additionally allowed for sending the Send query.

1.1.2 Definitions of security

To demonstrate the security of the first public discussion, we will give the security definition as follows.

Definition 1

(Partnering) \(A^{i}\) and \(TP1^{j}\) are partnered, if they mutually authenticate each other.

Definition 2

(Freshness) An entity \(A^{i}\) with the partner \(TP1^{j}\) is freshness if the following two conditions hold:

1. (1)

   If it has accepted an measurement result \(MR\ne null\) and both the entity and its partner have not been sent a Reveal query.

2. (2)

   There is no Corrupt query has been asked before the query Send has been asked.

The advantage of the adversary \(\mathscr {A}\) is measured by the ability of distinguish a legal measurement result from a random value. We define Succ to be an event that \(\mathscr {A}\) correctly guesses the bit b, which is chosen in the Test query. Hence, the advantage of \(\mathscr {A}\) in the attacked scheme P1 is defined as: \(Adv_{P1}\left( \mathscr {A}\right) =\left| 2\times Pr\left[ Succ\right] -1\right| \). We argue that the public discussion P1 is secure, as \(Adv_{P1}\left( \mathscr {A}\right) \) is negligible. Precisely, the adversary \(\mathscr {A}\) does not have any advantage to obtain the correct measurement result between the participants.

1.1.3 Security analysis

In the following description, we show that the public discussion, P1, holds several security properties, which are required for a secure quantum cryptographic public discussion. Let the maximum advantage of the adversary with running time Tm be for a certain task denoted as \(Adv_{Task}\left( Tm\right) \). The following advantages will be used in the analyses.

\(Adv_{Qubit}^{Clone}\left( Tm\right) \): The advantage for cloning a qubit.

\(Adv_{A}^{Forge}\left( Tm\right) \): The advantage for impersonate himself/herself as Alice (A).

Lemma 1

The advantage for cloning a qubit, \(Adv_{Qubit}^{Clone}\left( Tm\right) \), is negligible.

Proof

The quantum no-cloning theory has already been well-proven in several researches [21], here, we briefly describe the proof. \(\square \)

Assume that for an input qubit \(q_{i}\) with an arbitrary state, there exists a clone operation U. The clone operation can be defined as follows:

where \(\left| e\right\rangle _{o}\) denotes the output qubit, and \(\left| e\right\rangle \) is an arbitrary initial state.

Because \(\left| +\right\rangle _{i}=\frac{1}{\sqrt{2}}\left( \left| 0\right\rangle +\left| 1\right\rangle \right) _{i}\), it implies that \(U\left| +\right\rangle _{i}\left| e\right\rangle _{o}= \frac{1}{\sqrt{2}}\left( U\left| 0\right\rangle _{i}\left| e\right\rangle _{o}\right. \left. +U\left| 1\right\rangle _{i}\left| e\right\rangle _{o}\right) = \frac{1}{\sqrt{2}}\left( \left| 0\right\rangle _{i}\left| 0\right\rangle _{o}+\left| 1\right\rangle _{i}\left| 1\right\rangle _{o}\right) \). However, \(U\left| +\right\rangle _{i}\left| e\right\rangle _{o}= \left| +\right\rangle _{i}\left| +\right\rangle _{o}= {\frac{1}{\sqrt{2}}\left( \left| 0\right\rangle _{i}\left| 0\right\rangle _{o}+\left| 0\right\rangle _{i}\left| 1\right\rangle _{o}+\left| 1\right\rangle _{i}\left| 0\right\rangle _{o}+\left| 1\right\rangle _{i}\left| 1\right\rangle _{o}\right) }\), which is not equal to \(\frac{1}{\sqrt{2}}\left( \left| 0\right\rangle _{i}\left| 0\right\rangle _{o}\right. \left. +\left| 1\right\rangle _{i}\left| 1\right\rangle _{o}\right) \). The contradiction shows that the qubit cannot be cloned. \(Adv_{Qubit}^{Clone}\left( Tm\right) \) is negligible.

Lemma 2

Suppose that there exists an attacker \(\mathscr {A}\), who impersonates as Alice (A) with the running time Tm in the public discussion. Then the advantage of \(\mathscr {A}\), \(Adv_{A}^{Forge}\left( Tm\right) =Adv{}_{Qubit}^{Clone}\left( Tm\right) \).

Proof

Suppose that \(\mathscr {A}\) impersonates as Alice. In Step 1 of the proposed scheme, TP1 sends a quantum sequence to Alice and discusses the decoy photons with Alice in Step 2. If \(\mathscr {A}\) can successfully impersonate as Alice, then she can send her fake photon to Alice, and TP1 cannot detect the problem. \(\square \)

When TP1 sends the qubit sequence \(S_{1}\) to Alice, \(\mathscr {A}\) constructs an attack \(\beta \) to clone every qubit in \(S_{1}\). The sequence of the cloning outputs is denoted as \(\hat{S_{1}}\). Then, \(\beta \) sends the original sequence \(S_{1}\) to Alice. Alice will acknowledge TP1 that she has received the qubits. Then TP1 will announce the bases and positions of the decoy photons to Alice. Alice will select the corresponding qubits from \(S_{1}\) and measure them in the bases TP1 announced. Alice then transmits all the measurement results to TP1 and TP1 can compare the measurement results and his/her initial states of decoy photons to detect the existence of the eavesdroppers. Because these public classical information are transmitted via the authenticated channel shared between Alice and TP1, \(\beta \) cannot forge or modify them. Here, \(\beta \)’s goal is to successfully clone the qubits from \(S_{1}\) to \(\hat{S_{1}}\). \(\beta \) runs a subroutine and simulates its attack environment and gives all the required public parameters to \(\mathscr {A}\). Without losing the generality, assume that \(\mathscr {A}\) does not ask queries on the same message more than once. \(\beta \) maintains a list \(L_{CloneQubit}\) to ensure identical responding and avoid collision of the queries. \(\beta \) simulates the oracle queries of \(\mathscr {A}\) as follows:

Send-query: The send query is classified into the following types:

• Send\(\left( TP1^{j},S_{1}\right) \): \(\beta \) clones every qubits in the quantum sequence \(S_{1}\), and forms the output qubits as a new sequence \(\hat{S_{1}}\). \(\beta \) returns \(\hat{S_{1}}\) to \(\mathscr {A}\).

• Send\(\left( A^{i},ok\right) \): Alice sends the acknowledgement to TP1 for receiving qubits. \(\beta \) direct pass the collected information to \(\mathscr {A}\).

• Send\( \left( TP1^{j},pos \& bases\right) \): TP1 announces the positions and bases of the decoy photons to Alice. \(\beta \) direct pass the collected information to \(\mathscr {A}\).

• Send\(\left( A^{i},mr\right) \): Alice sends the measurement results to TP1. \(\beta \) stores these results for the test query.

Execute-query: When \(\mathscr {A}\) asks for an Execute(\(A^{i},TP1^{j}\)) query, \(\beta \) returns the transcript \( \left\langle \hat{S_{1}},\text{ Send }\left( A^{i},ok\right) ,\text{ Send }\left( TP1^{j},pos \& bases\right) \right\rangle \) to \(\mathscr {A}\) by using the simulation of send query.

Test-query: When \(\mathscr {A}\) makes the test query, if the query is not asked in the first session, then \(\beta \) will abort it; otherwise, \(\beta \) randomly chooses a bit b. If \(b=0\), \(\beta \) returns the value of Send\(\left( A^{i},mr\right) \); otherwise, \(\beta \) returns a random string to \(\mathscr {A}\). The adversary has to distinguish the random string from a legal measurement result. In order to do that, if the quantum could be cloned, \(\mathscr {A}\) can measure the qubits from \(\hat{S_{1}}\) by using the positions and bases obtained from the query Send \( \left( TP1^{j},pos \& bases\right) \). Then, the adversary can successfully get the legal measurement results; hence, the random string and the legal measurement results can be distinguished. Hence, the adversary’s advantage, \(Adv_{Alice}^{Forge}\left( Tm\right) =Adv{}_{Qubit}^{Clone}\left( Tm\right) \).

1.2 The second public discussion

In the following analyses, the public discussion between Alice, Bob and TP2 is analyzed.

1.2.1 Formal security model

Let A denotes Alice, B denotes Bob, TP2 denotes TP2, and P2 is the public discussion they participate. To describe the multiple instances of the participants, let \(A^{i}\) denote the instance i of A, \(B^{j}\) denote the instance j of Bob, and \(TP2^{k}\) is the instance k of TP2.

Execute (\(A^{i},B^{j},TP2^{k}\)) : The query models the passive attack. An adversary can obtain all messages exchanged between \(A^{i}\), \(B^{j}\) and \(TP2^{k}\).

Reveal (\(A^{i},B^{j}\)): In this query model, if the oracle has accepted, it returns the secret quantum state between \(A^{i}\) and \(B^{j}\) to the adversary; otherwise, it returns the null value to the adversary.

Send (\(A^{i}/B^{j}/TP2^{k},m\)) : This query models an active attack. It returns the information corresponded to an input m that \(A^{i}\), \(B^{j}\), or \(TP2^{k}\) would send to each others.

Corrupt (\(A^{i},B^{j},a\)) : This query models corruption capability of the adversary. If \(a=0\), it returns a null value; otherwise, it returns the secret quantum states between \(A^{i}\) and \(Bs{}^{j}\).

Test (\(TP2^{k}\)) : This query measures whether the public discussion is secure or not. By throwing an unbiased coin, b, if \(b=1\), it returns a random bit sequence with the same length as \(A^{i}\) and \(B^{j}\)’s measurement results. The query can only be called once.

Similar as the previous model, we consider two kinds of adversaries. A passive adversary is allowed to issue the Execute and Test queries and an active adversary is additionally allowed for sending the Send query.

1.2.2 Definitions of security

To demonstrate the security of the first public discussion, we will give the security definition as follows.

Definition 1

(Partnering) \(A^{i}\), \(B^{j}\) and \(TP2^{k}\) are partnered, if they mutually authenticate each other.

Definition 2

(Freshness) The entities \(A^{i}\) and \(B^{j}\) with the partner \(TP2^{k}\) is freshness if the following two conditions hold:

1. (1)

   If it has accepted an measurement result \(MR\ne null\) and both the entity and its partner have not been sent a Reveal query.

2. (2)

   There is no Corrupt query has been asked before the query Send has been asked.

The advantage of the adversary \(\mathscr {A}\) is also measured by the ability of distinguish a legal measurement result from a random value. Hence, the advantage of \(\mathscr {A}\) in the attacked scheme P2 is defined as: \(Adv_{P2}\left( \mathscr {A}\right) =\left| 2\times Pr\left[ Succ\right] -1\right| \). We argue that the public discussion P1 is secure, as \(Adv_{P2}\left( \mathscr {A}\right) \) is negligible. Precisely, the adversary \(\mathscr {A}\) does not have any advantage to obtain the correct measurement result between the participants.

1.2.3 Security analysis

In the following description, we show that the public discussion, P2, holds several security properties, which are required for a secure quantum cryptographic public discussion.

\(Adv_{FakeState}^{Gen}\left( Tm\right) \): The advantage for generating a fake entangled state without being detected in the second public discussion.

\(Adv_{P2}^{Attack}\left( Tm\right) \): The advantage for attacking P2 successfully.

Lemma 3

The advantage for generating a fake entangled state \(\left| \psi \right\rangle \) that can be written as \(\left| \phi \right\rangle \left| \Phi ^{+}\right\rangle \), \(Adv_{FakeState}^{Gen}\left( Tm\right) \) is negligible.

Proof

Let \(\left| \phi \right\rangle \) be an special entangled state that an adversary can generate. The adversary will try share this state with the legal users, Alice and Bob, before the second public discussion. During the second public discussion, because Alice, Bob, and TP2 will check whether the state shared by Alice and Bob is \(\left| \Phi ^{+}\right\rangle \). In this case, the adversary should make \(\left| \phi \right\rangle =\left| \Phi ^{+}\right\rangle \left| \psi \right\rangle \), where \(\left| \psi \right\rangle \) is the state held by the adversary, and \(\left| \Phi ^{+}\right\rangle \) is shared among Alice and Bob.

However, \(\left| \phi \right\rangle =\left| \Phi ^{+}\right\rangle \left| \psi \right\rangle \) implies that \(\left| \phi \right\rangle \) is a product state (i.e., it is the product of \(\left| \psi \right\rangle \) and \(\left| \Phi ^{+}\right\rangle \)), which is not entangled. The contradiction shows that the advantage to generate such special quantum state, \(Adv_{FakeState}^{Gen}\left( Tm\right) \) is negligible. \(\square \)

Lemma 4

Suppose that there exists an attacker \(\mathscr {A}\), who wants to successfully attack P2 with running time Tm in the public discussion. Then \(Adv_{P2}^{Attack}\left( Tm\right) =2\times Adv{}_{Qubit}^{Clone}\left( Tm\right) +Adv_{FakeState}^{Gen}\left( Tm\right) \).

Proof

Suppose that \(\mathscr {A}\) wants to attack P2 procedure. The adversary hopes that he/she could share an entangled state with Alice, Bob, and himself/herself. \(\mathscr {A}\) constructs an attack \(\gamma \) to help him/her. \(\gamma \) will generate a special quantum state and distribute them to Alice, Bob, and the adversary. To send fake qubits to Alice and Bob without being detected, \(\gamma \) has to pass the first public discussions between Alice and TP1 (Bob and TP1.) Then, when the second public discussion is started, the fake qubits held by Alice and Bob can be converted to \(\left| \Phi ^{+}\right\rangle \), then the second public discussion will be success.

Here, \(\gamma \)’s goal is to successfully generate a fake entangled state and pass the first public discussions. \(\gamma \) runs a subroutine and simulates its attack environment and gives all the required public parameters to \(\mathscr {A}\). Without losing the generality, assume that \(\mathscr {A}\) does not ask queries on the same message more than once. \(\gamma \) maintains a list \(L_{GenFakeState}\) to ensure identical responding and avoid collision of the queries. \(\gamma \) simulates the oracle queries of \(\mathscr {A}\) as follows:

Send-query: the send query is defined as follows:

• Send\(\left( TP1^{k},S_{1}/S_{2}\right) \): when \(TP1^{k}\) sends \(S_{1}\) (\(S_{2}\)) to \(A^{i}\) (\(B^{j}\)), \(\gamma \) generates a sequence of a n-qubit fake state \(\left| \phi \right\rangle _{123 \ldots n}\), sends all the first qubits \(q_{1}\) to Alice and all the second qubit \(q_{2}\) to Bob. The remained qubits \(q_{3 \ldots n}\) of all the fake states are denoted as \(\hat{S_{3 \ldots n}}\) to \(\mathscr {A}\).

• Send\(\left( A^{i}/B^{j},ok\right) \): Alice and Bob will notify TP2 the first public discussion has been success. \(\gamma \) direct pass the collected information to \(\mathscr {A}\).

• Send\( \left( TP2^{k},pos \& bases\right) \): TP2 announces the positions and bases to Alice and Bob. \(\gamma \) direct pass the collected information to \(\mathscr {A}\).

• Send\(\left( A^{i}/B^{j},mr\right) \): Alice and Bob sends the measurement results to TP1. \(\gamma \) stores these results for the test query.

Execute-query: When \(\mathscr {A}\) asks for an Execute(\(A^{i},B^{j}TP2^{k}\)) query, \(\gamma \) returns the transcript \( \left\langle \hat{S_{3 \ldots n}},\text{ Send }\left( A^{i}/B^{j},ok\right) ,\text{ Send }\left( TP2^{k},pos \& bases\right) \right\rangle \) to \(\mathscr {A}\) by using the simulation of send query.

Test-query: When \(\mathscr {A}\) makes the test query, if the query is not asked in the first session, then \(\gamma \) will abort it; otherwise, \(\gamma \) randomly chooses a bit b. If \(b=0\), \(\gamma \) returns the value of Send\(\left( A^{i}/B^{j},mr\right) \); otherwise, \(\beta \) returns a random string to \(\mathscr {A}\). The adversary has to distinguish the random string from the legal measurement results. In order to do that, if the special entangled state \(\left| \phi \right\rangle _{123 \ldots n}\) can be converted to \(\left| \phi \right\rangle _{123 \ldots n}=\left| \Phi ^{+}\right\rangle _{12}\left| \psi \right\rangle _{3 \ldots n}\), Alice and Bob can generate a legal pair of measurement results, and \(\mathscr {A}\) can obtain their measurement result from \(\left| \psi \right\rangle _{3 \ldots n}\). To success such attack, \(\gamma \) has to impersonate as Alice and Bob to, respectively, pass the two public discussions (i.e., the first public discussion between Alice and TP1 and between Bob and TP1.) Hence, the adversary’s advantage can be derived as \(Adv_{P2}^{Attack}\left( Tm\right) =Adv{}_{Alice}^{Forge}\left( Tm\right) +Adv{}_{Bob}^{Forge}\left( Tm\right) +Adv_{FakeState}^{Gen}\left( Tm\right) \). According to Lemma 2, \(Adv_{P2}^{Attack}\left( Tm\right) =2\times Adv{}_{Qubit}^{Clone}\left( Tm\right) +Adv_{FakeState}^{Gen}\left( Tm\right) \).

Reprints and permissions