PHYSICAL REVIEW A 76, 062316 共2007兲

Multiparty quantum-key-distribution protocol without use of entanglement
Ryutaroh Matsumoto*Department of Communications and Integrated Systems, Tokyo Institute of Technology, Tokyo 152-8550, Japan
共Received 7 August 2007; published 20 December 2007兲
We propose a quantum-key-distribution protocol that enables three parties to agree at once on a sharedcommon random bit string in the presence of an eavesdropper without use of entanglement. We prove its
unconditional security and analyze the key rate.
DOI: 10.1103/PhysRevA.76.062316

PACS number共s兲: 03.67.Dd, 03.67.Pp

I. INTRODUCTION

This paper is organized as follows: Section II presents theproposed protocol. Section III shows an unconditional security proof and a lower bound on its key rate. Section IV gives
concluding remarks.

When a sender, Alice, wants to send a confidential message to single receiver, Bob, over a public communication
channel in an unconditionally secure way, they must share asecret common random bit string, which is usually called asecret key. Such a secret key can be shared by a quantumkey-distribution 共QKD兲 protocol, such as the BennettBrassard 1984 共BB84兲 protocol 关1,2兴 even when there is aneavesdropper, Eve, with unlimited computational power.
When Alice sends a confidential message by broadcast totwo receivers, Bob and Charlie, these three parties must
share a common secret key. We propose a protocol enablingthem to share such a secret key under the assumption that
there are point-to-point quantum channels from Alice to Boband Charlie whose message can be eavesdropped and modified by Eve and three point-to-point classical channels
among Alice, Bob, and Charlie whose message can be eavesdropped but cannot be modified by Eve. Eve is assumed to
do whatever manipulation on quantum systems transmitted
over the quantum channels allowed by the quantum mechanics. This assumption is the same as Ref. 关3兴 and is a multiparty generalization of that in Ref. 关2兴. This problem is called
the multiparty key distribution or conference key agreement.
Under this assumption we prove the unconditional security
and give a lower bound on the key rate.
As a prior relevant research, it was pointed out in Ref. 关4兴
that Alice can secretly send a key after two different secretkeys are shared between Alice and Bob and between Aliceand Charlie by a conventional two-party QKD protocol suchas Ref. 关1兴. The difference of our proposed protocol to Ref.
关4兴 is that our protocol allows three parties to share a secretkey at once.
As another prior relevant research, Chen and Lo 关3兴 proposed a protocol for the same goal as our proposed protocol.
In their protocol, Alice must prepare the Bell state while inour protocol she does not need an entangled quantum state,
which makes our protocol easier to implement with current
technology than theirs 关3兴. Our protocol is the first multiparty
QKD protocol that does not use entangled state. It is also
worth noting that the security proof for our protocol does notuse multipartite entanglement distillation 关5兴, while Chen
and Lo 关3兴 use it.

*ryutaroh@rmatsumoto.org; URL: http://www.rmatsumoto.org/research.html
1050-2947/2007/76共6兲/062316共3兲

II. PROTOCOLIn this section we describe our proposed protocol. Let 兩0典,
兩1典 be an orthonormal basis for the qubit state space, and兩 + 典 = 共兩0典 + 兩1典兲 / 冑2, 兩−典 = 共兩0典 + 兩1典兲 / 冑2. We also define thematrices X and Z representing the bit error and the phaseerror, respectively, asX兩0典 = 兩1典,

X兩1典 = 兩0典,

Z兩 + 典 = 兩− 典,

Z兩− 典 = 兩 + 典.

共1兲 Alice makes a random qubit sequence according to thei.i.d. uniform distribution on 兵兩0典 , 兩1典 , 兩 + 典 , 兩−典其 and sends it toBob. Alice also sends the same qubit sequence to Charlie.
共2兲 Bob chooses the 兵兩0典 , 兩1典其 basis or 兵兩 + 典 , 兩−典其 basis uniformly randomly for each received qubit and measure it by
the chosen basis.
共3兲 Charlie does the same thing as step 共2兲.
共4兲 Alice publicly announces which basis 兵兩0典 , 兩1典其 or
兵兩 + 典 , 兩−典其 each transmitted qubit belongs to. Bob and Charlie
also publicly announce which bases were used for measurement of each qubit. In the following steps they will only
consider qubits with which transmission basis and measuringbases coincide among all of them.
共5兲 Suppose that there are 2n qubits transmitted in the兵兩0典 , 兩1典其 basis and measured with the 兵兩0典 , 兩1典其 basis by bothBob and Charlie. Index those qubits by 1 , . . . , 2n. Define thebit ai = 0 if Alice’s ith qubit was 兩0典, and ai = 1 otherwise.
Define the bit bi = 0 if Bob’s measurement outcome for ithqubit was 兩0典, and bi = 1 otherwise. Define the bit ci = 0 if
Charlie’s measurement outcome for ith qubit was 兩0典, andci = 1 otherwise.
共6兲 Suppose also that there are 2n⬘ qubits transmitted inthe 兵兩 + 典 , 兩−典其 basis and measured with the 兵兩 + 典 , 兩−典其 basis byboth Bob and Charlie. Index those qubits by 1 , . . . , 2n⬘. Define the bit ␣i = 0 if Alice’s ith qubit was 兩 + 典, and ␣i = 1otherwise. Define the bit ␤i = 0 if Bob’s measurement outcome for ith qubit was 兩 + 典, and ␤i = 1 otherwise. Define thebit ␥i = 0 if Charlie’s measurement outcome for ith qubit was兩 + 典, and ␥i = 1 otherwise.
For the simplicity of the presentation, we shall describe
the procedure extracting the secret key from ai, bi, and ci.

062316-1©2007 The American Physical Society

PHYSICAL REVIEW A 76, 062316 共2007兲

RYUTAROH MATSUMOTO共7兲 Alice chooses a subset S 傺 兵1 , . . . , 2n其 with size 兩S兩= n uniformly randomly from subsets of 兵1 , . . . , 2n其, and publicly announces the choice of S. Alice, Bob, and Charlie publicly announce ai, bi, and ci for i 僆 S and compute the error
rate

再q1 = max冎兩兵兩i 僆 S兩ai ⫽ bi其兩 兩兵兩i 僆 S兩ai ⫽ ci其兩,.
兩S兩兩S兩

兩v + w典,冑兩C2兩 wជ兺僆C2ជជ

for all vជ 僆 C1. We also need parametrized CSS codes introduced in Ref. 关2兴. The parametrized CSS code for xជ , zជ 僆 Fn2 isdefined as the linear space spanned by
1

共8兲 Alice chooses a subset S⬘ 傺 兵1 , . . . , 2n⬘其 with size兩S⬘兩 = n⬘ uniformly randomly from subsets of 兵1 , . . . , 2n⬘其,and publicly announces the choice of S⬘. Alice, Bob, andCharlie publicly announce ␣i, ␤i, and ␥i for i 僆 S⬘ and compute the error rate兩兵兩i 僆 S⬘兩␣i = ␥i ⫽ ␤i or ␣i = ␤i ⫽ ␥i其兩.
q2 =兩S⬘兩1共− 1兲冑兩C2兩 wជ兺僆C2

ជ兲
共zជ,w
ជ

ជ 典,
兩x + vជ + w

for all vជ 僆 C1, where 共¯ , ¯兲 denotes the inner product.
For a linear code C of length n, define the linear code CCof length 2n and dimension dim C by兵cជ cជ 兩cជ 僆 C兩其,

共1兲

Observe the difference between the definitions for q1 and q2.
共9兲 Alice, Bob, and Charlie decide a linear code C1 oflength n such that its decoding error probability is sufficiently small over all of the binary symmetric channel whosecrossover probability is close to q1. Let H1 be a parity checkmatrix for C1, aជ be Alice’s remaining 共not announced兲 bits
among ai’s, bជ be Bob’s remaining bits among bi’s, and cជ beCharlie’s remaining bits among ci’s.
共10兲 Alice publicly announces the syndrome H1aជ .
共11兲 Bob computes the error vector ជf such that H1ជf
= H1bជ − H1aជ by the decoding algorithm for C1. With highprobability bជ − ជf = aជ .
共12兲 Charlie computes the error vector fជ⬘ such that H1 fជ⬘= H1cជ − H1aជ by the decoding algorithm for C1. With highprobability cជ − fជ⬘ = aជ .
共13兲 Alice chooses a subspace C2 傺 C1 with dim C2= nh共q2兲 uniformly randomly, where h denotes the binary
entropy function, and publicly announces her choice of C2.
The final shared secret key is the coset aជ + C2.

where cជ cជ is the concatenated vector of length 2n. In thesecurity proof of our protocol, we must consider the CSS
code defined by the pair of linear codes C1C1 傻 C2C2, whoseorthonormal basis is given by1

兩v + w典兩v + w典.
冑兩C2兩 wជ兺
僆C2

ជជ ជ

ជ

For vectors xជ and zជ 僆 Fn2 of length n, we define the parametrized CSS code as the complex linear space spanned by
1共− 1兲
冑兩C2兩 wជ兺
僆C2

ជ兲
共zជ,w
ជ

ជ 典兩xជ + vជ + w
ជ 典,
兩x + vជ + w

共2兲

for vជ 僆 C1. Using the parametrized CSS code defined in Eq.
共2兲, we shall show a security proof of our protocol.
B. Security proof and analysis of the key rate

We shall first show that our protocol is equivalent to sending a parametrized CSS codeword with the parameters xជ andzជ randomly chosen. If we fix vជ and xជ and choose zជ uniformly
randomly in Eq. 共2兲, then the resulting density operator is1兺
2 兩C2兩 ជ nIII. SECURITY PROOF AND A LOWER BOUND ON THE
KEY RATEnz僆F2⫻

We shall show the unconditional security of our proposed
protocol by directly relating it to the quantum error correction by the quantum CSS 共Calderbank-Shor-Steane兲 codes关6,7兴. To make this paper self-contained, we shall briefly review the CSS code.

=冉兺冉兺ជ 1僆C2w

ជ 2僆C2w

ជ 1典兩xជ + vជ + w
ជ 1典
共− 1兲共zជ,wជ 1兲兩xជ + vជ + w

ជ 2兩具xជ + vជ + w
ជ 2兩
共− 1兲共zជ,wជ 2兲具xជ + vជ + w

冊冊1兺 兩xជ + vជ + wជ 典兩xជ + vជ + wជ 典具xជ + vជ + wជ 兩具xជ + vជ + wជ 兩,
兩C2兩 wជ 僆C2共3兲

A. Review of the CSS code

For a binary vector vជ = 共v1 , . . . , vn兲 僆 Fn2, where F2 is theGalois field with two elements, we define the quantum statevector 兩vជ 典 byby the exact same argument as Ref. 关2兴.
Denote the right-hand side of Eq. 共3兲 by ␳共xជ , vជ 兲. By astraightforward computation we can see兩vជ 典 = 兩v1典 丢 兩v2典 丢 ¯ 丢 兩vn典.

11ជ ជជជ ជជn 兺 兺 ␳共x, v兲 = n 兺 兩aa典具aa兩.
4 ជ nជ n
2 ជ n

For two binary linear codes C2 傺 C1 傺 Fn2, the CSS code is
the complex linear space spanned by the vectors

The right-hand side of Eq. 共4兲 means sending 兩00典 or 兩11典 ntimes with equal probability, which is exactly what Alice isx僆F2 v僆F2062316-2

共4兲

a僆F2

PHYSICAL REVIEW A 76, 062316 共2007兲

MULTIPARTY QUANTUM-KEY-DISTRIBUTION PROTOCOL…

doing in our protocol. Announcing the syndrome H1aជ in step
共10兲 is equivalent to announcing which xជ is chosen.
We shall consider the decoding of the imaginary transmission of CSS code words. A good review of decoding of CSS
codes is provided in Ref. 关2兴. We regard Bob and Charlie asa single receiver. The bit error correction is actually performed in our protocol, therefore we must ensure that it canbe separately executed by Bob and Charlie. On the otherhand, the phase error correction is not actually performed, so
it does not need to be separately executable.
Observe that the bit error correction for the leftmost nqubits in the CSS code defined in Eq. 共2兲 can be done separately from the rightmost n qubits in Eq. 共2兲, which meansthat Bob and Charlie can correct their bit flip errors with
their local operations and that they do not need their cooperation for bit error correction.
We shall consider the phase error correction. Let Zi be thephase error that occurred at ith qubit in Eq. 共2兲. We can seethat Zi and Zn+i have the same effect on the quantum codeword in Eq. 共2兲, and that Zi 丢 Zn+i does not change the quantum codeword in Eq. 共2兲.
Let

H2 =

冢 冣hជ 1]hជ n−dim C2

be a parity check matrix for C⬜
2 , thenH2⬘ =冢hជ 1hជ 1]hជ n−dim C2hជ n−dim C2

冣

has the same effect on the state 共2兲 if zi + zn+i = zi⬘ + zn+i
⬘ for alli, where the addition is considered in F2. Thus, in order tocorrect phase errors, we must find the binary vectoreជ ⬘ = 共e1 + en+i, . . . ,en + e2n兲

共7兲

from the data given in Eq. 共6兲. Also observe that共hជ ihជ i,eជ 兲 = 共hជ i,eជ ⬘兲.
Finding eជ ⬘ from 共hជ i , eជ ⬘兲 is exactly the ordinary decoding process for the classical linear code C⬜
2 . Also observe that theprobability of ei + en+i = 1 is given by q2 in Eq. 共1兲 in oursituation.
It is proved in Ref. 关8兴 that random choice of关n − h共q2兲兴-dimensional subspace C2 in C1 almost always
gives the low phase error decoding probability. This fact isalso stated without proof in Ref. 关2兴. If the choice of C1 isappropriate, then the fidelity of quantum error correction in
the imaginary transmission of the CSS codeword 共2兲 is close
to 1, which implies that the eavesdropper Eve can obtain
little information by the same argument as Ref. 关9兴, whichshows the security of the BB84 protocol directly relating it to
the quantum error correction without use of entanglement
distillation argument.
It was shown in Corollary 2 of Ref. 关10兴 that there exists
a linear code C1 of information rate 1 − h共q1兲 satisfying thecondition in step 共9兲. Therefore, we can extract 1 − h共q1兲
− h共q2兲 bit of secret key from one bit of the raw bits aជ .
IV. CONCLUSION AND DISCUSSION

is a parity check matrix for 共C2C2兲⬜.
Suppose that a phase error
Zz1 丢 ¯ 丢 Zz2n

⬘Zz1⬘ 丢 ¯ 丢 Zz2n

共5兲occurred with the quantum state 共2兲, where zi 僆 F2 for i= 1 , . . . , 2n. Let eជ = 共z1 , . . . , z2n兲 僆 F2n
2 . From the measurement
outcomes in the phase error correction process, we can know

We have proposed a protocol that allows Alice, Bob, andCharlie to share a common secret key at once. This is thefirst such protocol without use of entangled states. However,
the amount of extracted common secret key per single photon transmission is lower than the repeated use of the BB84
protocol and the well-known post-processing described inRef. 关4兴. Finding a multiparty QKD protocol with higher
efficiency is a future research agenda.
ACKNOWLEDGMENTS

共6兲

The author would like to thank Shun Watanabe and Tomohiko Uyematsu for helpful discussions. This research waspartly supported by the Japan Society for the Promotion ofScience under Grants-in-Aid for Young Scientists Grant No.
18760266.

关1兴 C. H. Bennett and G. Brassard, Proceedings of the IEEE International Conference on Computers, Systems, and Signal
Processing, 1984, pp. 175–179.
关2兴 P. W. Shor and J. Preskill, Phys. Rev. Lett. 85, 441 共2000兲.
关3兴 K. Chen and H.-K. Lo, Proceedings of the 2005 IEEE International Symposium on Information Theory 共IEEE, Adelaide,Australia, 2005兲, pp. 1607–1611.
关4兴 S. K. Singh and R. Srikanth, e-print arXiv:quant-ph/0306118.
关5兴 M. Murao, M. B. Plenio, S. Popescu, V. Vedral, and P. L.

Knight, Phys. Rev. A 57, R4075 共1998兲.
关6兴 A. R. Calderbank and P. W. Shor, Phys. Rev. A 54, 1098
共1996兲.
关7兴 A. M. Steane, Proc. R. Soc. London, Ser. A 452, 2551 共1996兲.
关8兴 S. Watanabe, R. Matsumoto, and T. Uyematsu, Int. J. Quantum
Inf. 4, 935 共2006兲.
关9兴 M. Hamada, J. Phys. A 37, 8303 共2004兲.
关10兴 I. Csiszár, IEEE Trans. Inf. Theory 28, 585 共1982兲.

共hជ ihជ i,eជ 兲for i = 1 , . . . , n − dim C2. Observe that the error 共5兲 and062316-3