**Post: #1**

Seminar Report On

QUANTUM CRYPTOGRAPHY

Submitted by

SANTHIMOL A. K.

In the partial fulfillment of requirements in degree of

Master of Technology in Computer and Information Science

DEPARTMENT OF COMPUTER SCIENCE

COCHIN UNIVERSITY OF SCIENCE AND TECHNOLOGY

KOCHI-682022

2008 Page 2

ACKNOWLEDGEMENT

I thank GOD almighty for guiding me throughout the seminar. I would like to

thank all those who have contributed to the completion of the seminar and helped me

with valuable suggestions for improvement.

I am extremely grateful to Prof. Dr. K Poulose Jacob, Director, Department of

Computer Science, for providing me with best facilities and atmosphere for the creative

work guidance and encouragement. I would like to thank my coordinator,

Mr.G.Santhosh Kumar, Lecturer, Department of Computer Science, for all help and

support extend to me. I thank all staff members of my college and friends for extending

their cooperation during my seminar.

Above all I would like to thank my parents without whose blessings, I would not

have been able to accomplish my goal.

SANTHIMOL AK Page 3

ABSTRACT

Quantum cryptography uses quantum mechanics to guarantee secure

communication. It enables two parties to produce a shared random bit string known only

to them, which can be used as a key to encrypt and decrypt messages.

An important and unique property of quantum cryptography is the ability of the

two communicating users to detect the presence of any third party trying to gain

knowledge of the key. This results from a fundamental part of quantum mechanics: the

process of measuring a quantum system in general disturbs the system. A third party

trying to eavesdrop on the key must in some way measure it, thus introducing detectable

anomalies. By using quantum superpositions or quantum entanglement and transmitting

information in quantum states, a communication system can be implemented which

detects eavesdropping. If the level of eavesdropping is below a certain threshold a key

can be produced which is guaranteed as secure, otherwise no secure key is possible and

communication is aborted.

The security of quantum cryptography relies on the foundations of quantum

mechanics, in contrast to traditional public key cryptography which relies on the

computational difficulty of certain mathematical functions, and cannot provide any

indication of eavesdropping or guarantee of key security.

Quantum cryptography is only used to produce and distribute a key, not to

transmit any message data. This key can then be used with any chosen encryption

algorithm to encrypt and decrypt a message, which can then be transmitted over a

standard communication channel. The algorithm most commonly associated with QKD is

the one-time pad, as it is provably secure when used with a secret, random key.

KEY WORDS:

qubit, uncertainty, entanglement, bit commitment, BB84 protocol, Ekert

protocol, key distribution, one-time-padPage 4

CONTENTS

1. INTRODUCTIONÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦..1

2. CLASSICAL CRYPTOGRAPHYÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦2

2.1. DEFINITIONÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦2

2.2. ONE-TIME-PAD Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦..Â¦Â¦3

2.3. LIMITATIONSÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦...4

3. QUBITÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦...4

3.1. QUBIT REPRESENTATIONÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦.5

4. QUATUM CRYPTOGRAPHYÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦6

4.1. UNCERTAINITYÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦...Â¦7

4.2. ENTANGLEMENTÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦.Â¦...7

4.3. BB84 PROTOCOLÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦.Â¦..8

4.4. EKERT PROTOCOLÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦...10

5. QUANTUM BIT COMMITMENT PROTOCOLÂ¦Â¦Â¦...11

5.1. BB84 QUANTUM BIT COMMITMENT PROTOCOLÂ¦Â¦Â¦Â¦Â¦Â¦Â¦.Â¦12

5.1.1.

THE COMMIT PROCEDUREÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦.Â¦Â¦..12

5.1.2.

THE UNVEIL PROCEDUREÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦.Â¦Â¦13

6. OUTLOOKSÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦.Â¦.13

6.1. OTHER QUANTUM KEY DISTRIBUTION PROTOCOLS..Â¦Â¦Â¦.Â¦Â¦..14

6.2. EXPERIMENTAL STATUSÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦.Â¦Â¦..14

6.3. CURRENT CHALLENGESÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦.Â¦...15

7. CONCLUSION & FUTURE SCOPEÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦..Â¦17

8.

REFERENCESÂ¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦Â¦...18Page 5

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

1

1. INTRODUCTION

Cryptography is the science of keeping private information from unauthorized

access, of ensuring data integrity and authentication, and other tasks. In this survey, we

will focus on quantum-cryptographic key distribution and bit commitment protocols and

we in particular will discuss their security. Before turning to quantum cryptography, let

me give a brief review of classical cryptography, its current challenges and its historical

development.

Two parties, Alice and Bob, wish to exchange messages via some insecure

channel in a way that protects their messages from eavesdropping. An algorithm, which

is called a cipher in this context, scrambles Aliceâ„¢s message via some rule such that

restoring the original message is hardâ€if not impossibleâ€without knowledge of the

secret key. This scrambled message is called the ciphertext. On the other hand, Bob

(who possesses the secret key) can easily decipher Aliceâ„¢s ciphertext and obtains her

original plaintext. Figure 1 in this section presents this basic cryptographic scenario.

Fig. 1. Communication between Alice and Bob, with Eve listening. Page 6

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

2

2. CLASSICAL CRYPTOGRAPHY

Overviews of classical cryptography can be found in various text books (see, e.g.,

Rothe [2005] and Stinson [2005]). Here, we present just the basic definition of a

cryptosystem and give one example of a classical encryption method, the one-time pad.

Definition 2.1. A (deterministic, symmetric) cryptosystem is a five-tuple (P, C, K, E, D)

satisfying the following conditions:

1. P is a finite set of possible plaintexts.

2. C is a finite set of possible ciphertexts.

3. K is a finite set of possible keys.

4. For each k ? K, there are an encryption rule e

k

? E and a corresponding decryption

rule d

k

? D, where e

k

: P? C and d

k

: C? P are functions satisfying d

k

(e

k

(x)) = x

for each plaintext element x ? P.

In the basic scenario in cryptography, we have two parties who wish to communicate

over an insecure channel, such as a phone line or a computer network. Usually, these

parties are referred to as Alice and Bob. Since the communication channel is insecure, an

eavesdropper, called Eve, may intercept the messages that are sent over this channel. By

agreeing on a secret key k via a secure communication method, Alice and Bob can make

use of a cryptosystem to keep their information secret, even when sent over the insecure

channel. This situation is illustrated in Figure 1.

The method of encryption works as follows. For her secret message m, Alice uses

the key k and the encryption rule e

k

to obtain the ciphertext c = e

k

(m). She sends Bob the

ciphertext c over the insecure channel. Knowing the key k, Bob can easily decrypt the

ciphertext by the decryption rule d

k

:

d

k

© = d

k

(e

k

(m)) = m.

Knowing the ciphertext c but missing the key k, there is no easy way for Eve to determine

the original message m.Page 7

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

3

There exist many cryptosystems in modern cryptography to transmit secret

messages. An early well-known system is the one-time pad, which is also known as the

Vernam cipher. The one-time pad is a substitution cipher. Despite its advantageous

properties, which we will discuss later on, the one-time padâ„¢s drawback is the costly

effort needed to transmit and store the secret keys.

Fig.2. Letters and punctuation marks encoded by numbers from 0 to 29.

Fig. 3. Encryption and decryption example for the one-time pad.

Example 2.2 (One-Time Pad). For plaintext elements in P , we use capital letters and

some punctuation marks, which we encode as numbers ranging from 0 to 29, see Figure2.

As is the case with most cryptosystems, the ciphertext space equals the plaintext space.

Furthermore, the key space K also equals P , and we have P =C= K={0, 1, . . . , 29}.

Next, we describe how Alice and Bob use the one-time pad to transmit their

messages. A concrete example is shown in Figure 3. Suppose Alice and Bob share a joint

secret key k of length n = 12, where each key symbol k

i

? {0, 1, . . . , 29} is chosen

uniformly at random. Let m = m

1

m

2

. . . m

n

be a given message of length n, which Alice

wishes to encrypt. For each plaintext letter m

i

, where 1 = i = n, Alice adds the plaintext

numbers to the key numbers. The result is taken modulo 30. For example, the last letter

of the plaintext from Figure 3, D, is encoded by m

12

=03. The corresponding key is

m

12

= 28, so we have c

12

= 3 + 28 = 31. Since 31 = 1 mod 30, our plaintext letter D is

encrypted as B. Decryption works similarly by subtracting, character by character, the

key letters from the corresponding ciphertext letters. So the encryption and decryption

can be written as respectively c

i

= (m

i

+ k

i

) mod 30 and m

i

=(c

i

- k

i

) mod 30, 1 = i = n. Page 8

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

4

2.3. Limitations

Cryptographic technology in use today relies on the hardness of certain

mathematical problems. Classical cryptography faces the following two problems. First,

the security of many classical cryptosystems is based on the hardness of problems such as

integer factoring or the discrete logarithm problem. But since these problems typically

are not provably hard, the corresponding cryptosystems are potentially insecure. For

example, the famous and widely used RSA public-key cryptosystem [Rivest et al. 1978]

could easily be broken if large integers were easy to factor. The hardness of integer

factoring, however, is not a proven fact but rather a hypothesis.1.We mention in passing

that computing the RSA secret key from the corresponding public key is polynomial-time

equivalent to integer factoring [May 2004].

Second, the theory of quantum computation has yielded new methods to tackle

these mathematical problems in a much more efficient way. Although there are still

numerous challenges to overcome before a working quantum computer of sufficient

power can be built, in theory many classical ciphers (in particular public-key

cryptosystems such as RSA) might be broken by such a powerful machine. However,

while quantum computation seems to be a severe challenge to classical cryptography in a

possibly not so distant future, at the same time it offers new possibilities to build

encryption methods that are safe even against attacks performed by means of a quantum

computer. Quantum cryptography extends the power of classical cryptography by

protecting the secrecy of messages using the physical laws of quantum mechanics.

3. QUBITS

The most important unit of information in computer science is the bit. There are

two possible values that can be stored by a bit: the bit is either equal to 0 or equal to

1. These two different states can be represented in various ways, for example by a

simple switch or by a capacitor: if not charged, the capacitor holds the value zero; if

charged, it holds the value one. Page 9

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

5

There exist many possibilities to physically represent a qubit in practice, as every

quantum system with at least two states can serve as a qubit. For example, the spin of an

atom or the polarization5 of a light particle can represent the state of a qubit. Even a cat

with its two basic states dead and alive, introduced by SchrÃƒÂ¶dinger [1935] to

visualize fundamental concepts of quantum mechanics, might serve as a representation.

The catâ„¢s problemâ€or fortune from the animalâ„¢s point of viewâ€when being used as a

quantum system is its sheer size compared to that of an atom or light particle. There is no

way to protect such a big quantum instance from interaction with its environment, which

in turn will result in decoherence of the superposition of the cat.

3.1. Qubit Representation

In general, a quantum state |?) is an element of a finite-dimensional complex

vector space (or Hilbert space) H. We denote the scalar product of two states |?) and |f)

by (?|f), where (?| = |?)

T

is the conjugate transpose of |?). It is convenient to deal with

normalized states, so we require (?|?) = 1 for all states |?) that have a physical meaning.

The quantum analog of the bit is called qubit, which is derived from quantum bit.

A qubit |?) is an element of a two-dimensional Hilbert space, in which we can introduce

an orthonormal basis, consisting of the two states |0) and |1). Unlike its classical

counterpart, the quantum state can be in any coherent superposition of the basis states:

|?) = a|0) + ÃƒÅ¸|1),

(1)

where a and ÃƒÅ¸ are, in general, complex coefficients. This is due to the fact that the

quantum mechanical equation of motion, the SchrÃƒÂ¶dinger equation, is linear: Any linear

superposition of its solutions (the quantum states) is also a solution. Since we require

quantum states to be normalized, we find that the coefficients in (1) have to fulfill

|a|

2

+ |ÃƒÅ¸|

2

= 1, where | Ã‚Â· | denotes the absolute value. Page 10

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

6

4. QUANTUM CRYPTOGRAPHY

Quantum Cryptography, or Quantum Key Distribution (QKD), uses quantum

mechanics to guarantee secure communication. It enables two parties to produce a shared

random bit string known only to them, which can be used as a key to encrypt and decrypt

messages. An important and unique property of quantum cryptography is the ability of

the two communicating users to detect the presence of any third party trying to gain

knowledge of the key. This results from a fundamental part of quantum mechanics: the

process of measuring a quantum system in general disturbs the system. A third party

trying to eavesdrop on the key must in some way measure it, thus introducing detectable

anomalies. By using quantum superpositions or quantum entanglement and transmitting

information in quantum states, a communication system can be implemented which

detects eavesdropping. If the level of eavesdropping is below a certain threshold a key

can be produced which is guaranteed as secure (i.e. the eavesdropper has no information

about), otherwise no secure key is possible and communication is aborted.

The security of quantum cryptography relies on the foundations of quantum

mechanics, in contrast to traditional public key cryptography which relies on the

computational difficulty of certain mathematical functions, and cannot provide any

indication of eavesdropping or guarantee of key security.

Quantum cryptography is only used to produce and distribute a key, not to

transmit any message data. This key can then be used with any chosen encryption

algorithm to encrypt (and decrypt) a message, which can then be transmitted over a

standard communication channel. The algorithm most commonly associated with QKD is

the one-time pad, as it is provably secure when used with a secret, random key.

Quantum cryptography exploits the quantum mechanical property that a qubit

cannot be copied or amplified without disturbing its original state. This is the statement

of the No-Cloning Theorem [Wootters and Zurek 1982], which is easily proven: Assume

there exists a unitary transformation U that can copy two states |?

1

) and |?

2

): Page 11

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

7

where |0) is an arbitrary input state. If we equate the scalar products of the left-hand and

right-hand sides, it follows by the unitarity of U that (?

1

|?

2

) = (?

1

|?

2

)

2

, which implies that

(?

1

|?

2

) equals 0 or 1. This means that we can copy only orthogonal or identical states. In

contrast, arbitrary unknown states cannot be perfectly cloned. (Note that orthogonal or

identical states are not viewed as unknown states, since we do know they are

orthogonal, for example.)

The essence of this theorem is the main ingredient of quantum key distribution,

where Alice and Bob use a quantum channel to exchange a sequence of qubits, which

will then be used to create a key for the one-time pad in order to communicate over an

insecure channel. Any disturbance of the qubits, for example caused by Eve trying to

measure the qubitsâ„¢ state, can be detected with high probability.

Quantum cryptographic devices typically employ individual photons of light and

take advantage of either the Heisenberg Uncertainity principle or Quantum

Entanglement.

4.1. Uncertainity

Unlike in classical physics, the act of measurement is an integral part of quantum

mechanics. So it is possible to encode information into quantum properties of a photon in

such a way that any effort to monitor them disturbs them in some detectable way. The

effect arises because in quantum theory, certain pairs of physical properties are

complementary in the sense that measuring one property necessarily disturbs the other.

This statement is known as the Heisenberg uncertainty principle. The two complementary

properties that are often used in quantum cryptography, are two types of photon's

polarization, e.g. rectilinear (vertical and horizontal) and diagonal (at 45Ã‚Â° and 135Ã‚Â°).

4.2. Entanglement

It is a state of two or more quantum particles, e.g. photons, in which many of their

physical properties are strongly correlated. The entangled particles cannot be described

by specifying the states of individual particles and they may together share information in

a form which cannot be accessed in any experiment performed on either of the particles

alone. This happens no matter how far apart the particles may be at the time. Page 12

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

8

4.3. BB84 Protocol

The BB84 protocol was proposed by Charles H.Bennett and Gilles Brassard

[1984]. This is the first protocol designed to employ quantum mechanics for two parties

to agree on a joint secret key. In this protocol, Alice and Bob use a quantum channel to

send qubits. They are also connected by a classical channel, which is insecure against an

eavesdropper but unjammable. Alice and Bob use four possible quantum states in two

conjugate bases (say, the rectilinear basis+and the diagonal basisÃƒâ€”).We use |0)

+

and |0)

Ãƒâ€”

=

(|0)

+

+|1)

+

)/v2 for the classical signal 0, and we use |1)

+

and |1)

Ãƒâ€”

= (|0)

+

- |1)

+

)/v2 for

the classical signal 1. Note that the two bases are connected by the so-called Hadamard

transformation

in the following way: We have H|0)

+

= |0)

Ãƒâ€”

and H|1)

+

= |1)

Ãƒâ€”

, and vice-versa, since

H

2

= 1.

The protocol works as follows (see also Table I for illustration):

(1) Alice randomly prepares 2n qubits, each in one of the four states |0)

+

, |0)

Ãƒâ€”

, |1)

+

, or|1)

Ãƒâ€”

,

and sends them to Bob.

(2) For each qubit that Bob receives, he chooses at random one of the two bases (+ or Ãƒâ€”)

and measures the qubit with respect to that basis. In the case of a perfectly noiseless

channel, if Bob chooses the same basis as Alice, his measurement result is the same

as the classical bit that Alice prepared. If the bases differ, Bobâ„¢s result is completely

random. Page 13

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

9

(3) Alice tells Bob via the classical channel which basis she used for each qubit. They

keep the bits where Bob has used the same basis for his measurement as Alice. This

happens in about half the cases, so they will have approximately n bits left. These are

forming the so-called sifted key.

(4) Alice and Bob choose a subset of the sifted key to estimate the error-rate. They do so

by announcing publicly the bit values of the subset. If they differ in too many cases,

they abort the protocol, since its security cannot be guaranteed.

(5) Finally, Alice and Bob obtain a joint secret key from the remaining bits by performing

error correction and privacy amplification.

Eveâ„¢s goal is to learn at least some part of the key. Thus, an obvious strategy for her

is to intercept the qubits being transmitted from Alice to Bob. She cannot simply copy the

qubits, since this would contradict the No-Cloning Theorem. In order to extract some

information, she is forced to measure (and thus destroy) them. But since she does not

know the basis in which they were prepared (Alice announces this information only after

Bob received all signals), she can only guess or just flip a coin for the selection of the

measurement basis. In about half the cases, she will happen to choose the same basis as

Alice and get completely correlated bit values. In the other half, her results will be

random and uncorrelated. Bob certainly expects to receive something from Alice, so Eve

needs to send some qubits to him. However, she still has no idea which basis Alice used,

so she prepares each qubit in the same basis as she measured it (or she chooses a basis at

random). These newly created qubits again match Aliceâ„¢s bases in only half of the cases.

After Bob receives Eveâ„¢s qubits, he measures them, and Alice and Bob apply the sifting.

Because of Eveâ„¢s disturbance, about half of Bobâ„¢s key was measured in a different basis

than it was prepared by Alice. Since Bobâ„¢s result is random in those cases, his sifted key

will contain about 25% errors. In the error-estimation stage, if Alice and Bob obtain such

a high error rate, it would be wise for them to abort the protocol.

If the error rate is below an agreed threshold value, Alice and Bob can eliminate

errors with (classical) error correction. A simple method for error correction works as

follows: Alice chooses two bits at random and tells Bob the XOR-value of the two bits.

Bob tells Alice if he has the same value. In this case, they keep the first bit and discard Page 14

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

10

the second bit. If their values differ, they discard both bits. The remaining bits form the

key.

The last stage of the protocol is privacy amplification [Maurer 1993; Bennett et al.

1995]â€a procedure in which Alice and Bob eliminate (or, at least, drastically reduce)

Eveâ„¢s knowledge about the key. They do so by choosing random pairs of bits of the sifted

key and replacing them by their corresponding XOR-values. Thus, they halve the length

of the key, in order to amplify their privacy. Note that Eve has less knowledge about

the XOR-value, even if she knew the values of the single bits with high probability (but

not with certainty).

Note that these simple methods for error correction and privacy amplification do not

always work. For the general case, there exist more sophisticated strategies.

4.4. Ekert Protocol

In 1991 Artur Ekert proposed a new QKD protocol whose security relies on the

entangled pairs of photons. These can be created by Alice, by Bob, or by some source

separate from both of them, including eavesdropper Eve. The photons are distributed so

that Alice and Bob each end up with one photon from each pair.

The scheme relies on two properties of entanglement. First, the entangled states are

perfectly correlated in the sense that if Alice and Bob both measure whether their

particles have vertical or horizontal polarizations, they will always get the same answer

with 100% probability. The same is true if they both measure any other pair of

complementary (orthogonal) polarizations. However, the particular results are completely

random; it is impossible for Alice to predict if she (and thus Bob) will get vertical

polarization or horizontal polarization.

Second, any attempt at eavesdropping by Eve will destroy these correlations in a way

that Alice and Bob can detect. Page 15

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

11

5. QUANTUM BIT COMMITMENT PROTOCOL

When talking about quantum cryptography, everyone is thinking about key

distribution. There are, however, other cryptographic applications as well, such as bit

commitment. A bit commitment protocol based on quantum mechanics was introduced

by Brassard et al. [1993]. The unconditional security of the protocol (which means that

the security of the protocol is independent of the computational resources, such as

computing time, amount of memory used, and computer technology of the cheater) has

been accepted without proof [Yao 1995]. Two years after it had been proposed, the

protocol turned out to be insecure [Mayers 1995].

A commitment protocol is a procedure in which one party, say Alice, deposits a

message such that no one (and in particular not Alice) can read it nor change it. At some

point in the future, Alice can announce her message, and with high certainty it can be

proven that the revealed message is the same as the one Alice had deposited originally.

To illustrate this situation, suppose Bob wants to auction off a diamond ring, subject to

the condition that each person wishing to participate in the auction can bid only one

single amount of money. After each person has chosen a specific amount, the highest

bidder gets the ring. So everyone writes their own bid on a piece of paper, puts it into a

personal safe, which is then locked and given to Bob. Until all bids have been submitted

to Bob, each bidder keeps the key matching the lock of his or her safe. In this way Bob

cannot see any of the bids, which in turn cannot be changed once they have been

submitted, since only Bob has access to the committed safes. All keys are handed over to

Bob after he has received all safes from the people participating in the auction. The

different offers are compared in public, so that everybody can be sure that only the

highest bidder walks away with the diamond and an empty wallet.

We can describe this commitment protocol mathematically as follows: The

protocol has two stages, the commit phase and the unveil phase. Alice commits herself to

the data m by computing c = f (m), and she sends c to Bob. Alice unveils the commitment

by showing Bob the preimage m of c. In classical cryptography, and in particular in

public-key cryptography, one-way functions are used for commitment. In quantum

cryptography, we want to make use of the laws of quantum mechanics to create a fair Page 16

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

12

protocol for both sides. Bit commitment is a special case of a commitment protocol,

where the data m consists of only one single bit.

It is widely believed that it is impossible to create a perfectly secure classical bit

commitment protocol. Regarding the extension to the quantum world, it was shown that

unconditionally secure quantum bit commitment is also impossible [Mayers 1997; Lo and

Chau 1997]. However, when relaxing the security constraints, quantum bit commitment

becomes possible in slightly modified frameworks. One example is Kentâ„¢s quantum bit

commitment protocol, which is based on special relativity theory [Kent 1999]. Another

example is due to Damgard et al. [2005] who proposed a quantum bit commitment

protocol that is secure in the bounded storage model.

5.1. BB84 Quantum bit commitment protocol

A quantum bit commitment protocol can be created from the BB84 quantum key

distribution protocol with a few minor changes in the BB84 protocol[Bennett and

Brassard 1984]. Just as in the classical bit commitment protocol, the quantum protocol

starts with the commit phase and ends with the unveil phase.

5.1.1. The commit procedure:

(1) Alice chooses a bit b ? {0, 1}.

(2) Alice creates a random binary string w = w

1

Ã‚Â· Ã‚Â· Ã‚Â·w

n

with n bits.

(3) If Alice wants to commit to 0, she does a quantum encoding of each bit w

i

in the two

basis states of the rectilinear basis +. If she wants to commit to 1, she encodes the bits

in the two basis states of the diagonal basis Ãƒâ€”. Let ?

i

denote the basis chosen for w

i

.

(4) Alice sends the sequence of n encoded quantum states to Bob.

(5) Bob chooses a random measurement basis (rectilinear or diagonal) for each of the

received quantum states, i.e., he chooses a string of random bases =

1

Ã‚Â· Ã‚Â·

n

? {+,

Ãƒâ€”}

n

. He measures the i

th

state in the basis

i

, and denotes the outcome by .

If we take a look at the two density matrices for the n states corresponding to b = 0

and b = 1, respectively, it is easy to see that they are the same, and equal to the identity

matrix. Thus, Bob has no chance to get any information about the bit b. Page 17

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

13

5.1.2. The unveil procedure:

(1) Alice publishes b (i.e., the basis that she used for encoding) and the string w.

(2) For about half of the n states, Bob used the same basis for his measurement as Alice

used for encoding. In these cases Bob can verify that Aliceâ„¢s revealed bits are

matching his measurement results.

How could a dishonest party cheat in this protocol? For example, Alice could choose

the bit b = 1 for the commit phase, so she encodes the states with the diagonal basis Ãƒâ€”.

Later during the unveil phase, she changes her mind and tells Bob that she committed to

the bit b = 0, so Bob assumes that Alice has used the rectilinear basis +. In approximately

n/2 cases, Bob measures the states with the rectilinear basis +, and in these cases Alice

has to guess the bits Bob measured. Since Aliceâ„¢s success to make a right guess for one

bit is 1/2, her overall cheating will not be detected with a probability of (1/2)

n/2

. Once n is

chosen large enough, Alice has practically no chance to manipulate the protocol by this

probabilistic method.

But what if Alice uses specially entangled states? Alice could create n pairs of

entangled states and send one part of each pair to Bob. She doesnâ„¢t have to commit to a

bit in the beginning, because she can perform a measurement right before the unveil

phase. If, for example, she chooses bit b = 0, she measures the states that she has kept in

the rectilinear basis +. Bobâ„¢s measurement results will be perfectly correlated, due to the

shape of the entangled state. If Alice wants to choose bit b = 1 instead, she measures the

states that she has kept in the diagonal basis Ãƒâ€”. The state is form-invariant under a basis

rotation by 45

?

, Aliceâ„¢s announced encoded states will again match Bobâ„¢s measurement

results. Thus, Bob has no chance to notice the attack.

6. OUTLOOKS

The security of quantum key distribution relies on the inviolable laws of quantum

mechanics: nonorthogonal quantum states are used as signal states in the BB84 protocol.

The impossibility of perfect cloning of nonorthogonal states implies the security of this

protocol. Page 18

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

14

In the security proof for the BB84 protocol, we have employed an equivalent

entanglement-based protocol. The main idea is that local measurements on a maximally

entangled state, shared by Alice and Bob, have perfectly correlated outcomes that can be

used as the key. A maximally entangled state is necessarily pure, and a pure state cannot

be entangled with an eavesdropperâ„¢s stateâ€thus Eve cannot learn anything about the key.

The idea for quantum cryptography with entangled states goes back to Ekert [1991], who

suggested to confirm the existence of quantum correlations in the state of Alice and Bob

by a Bell inequality test.

6.1. Other quantum key distribution protocols

A variety of quantum key distribution protocols can be found in the literature. All

known prepare-and-measure schemes can be seen as variations of the BB84 protocol,

which are obtained by changing the number and/or dimension of the quantum states.

Bennett [1992] proposed a protocolâ€which now is named after him the B92 protocolâ€

in which only two nonorthogonal states are used. In the so-called six-state protocol [BruÃƒÅ¸

1998; Bechmann-Pasquinucci and Gisin 1999], the six eigenstates of the three Pauli

operators are used. In this protocol, it is more difficult for Eve to retrieve any

information, thus the security is enhanced.

A recently suggested protocol [Scarani et al. 2004] introduces a new sifting

method: rather than announcing the basis, Alice gives Bob a list of two nonorthogonal

states from which the signal state was taken. This protocol has certain security

advantages that are connected with experimental implementations of quantum

cryptography.

6.2. Experimental status

In recent years, much effort has been devoted to experiments on quantum

cryptography, and much progress has been made. In most experiments, polarized photons

are representing the qubits: photons are polarized if their electromagnetic field oscillates

in a fixed direction of space.

Polarization-based encoding works best for free-space communication systems

rather than fiber-optic lines. Data are transmitted faster in free-space systems, but theyPage 19

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

15

cannot traverse the longer distances of fiber-optic links. In March 2004, NEC scientists in

Japan sent a single photon over a 150-km fiber-optic link, breaking the transmission

distance record for quantum cryptography.

The most commercially viable QKD systems rely on fiber-optic links limited to

100 to 120 km. At longer distances, random noise degrades the photon stream. Quantum

keys cannot travel far over fiber optic lines, and, thus, they can work only between

computers directly connected to each other.

As of March 2007 the longest distance over which quantum key distribution has

been demonstrated using optic fiber is 148.7 km, achieved by Los Alamos/NIST using

the BB84 protocol. Significantly, this distance is long enough for almost all the spans

found in today's fiber networks. The distance record for free space QKD is 144km

between two of the Canary Islands, achieved by a European collaboration using

entangled photons (the Ekert scheme) in 2006, and using BB84 enhanced with decoy

states[8] in 2007. The experiments suggest transmission to satellites is possible, due to

the lower atmospheric density at higher altitudes. For example although the minimum

distance from the International Space Station to the ESA Space Debris Telescope is about

400 km, the atmospheric thickness is about an order of magnitude less than in the

European experiment, thus yielding less attenuation compared to this experiment.

6.3. Current Challenges

Like everything in the world of information security, quantum cryptography is not

panacea. The main drawbacks of quantum cryptography are due to the following two

reasons:

Man in the middle attack

Quantum cryptography is vulnerable to a man-in-the-middle attack when used

without authentication to the same extent as any classical protocol, since no principle of

quantum mechanics can distinguish friend from foe. As in the classical case, Alice and

Bob cannot authenticate each other and establish a secure connection without some

means of verifying each other's identities (such as an initial shared secret). If Alice andPage 20

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

16

Bob have an initial shared secret then they can use an unconditionally secure

authentication scheme (such as Carter-Wegman,) along with quantum key distribution to

exponentially expand this key, using a small amount of the new key to authenticate the

next session. Several methods to create this initial shared secret have been proposed, for

example using a 3rd party or chaos theory.

Photon number splitting attack

In the BB84 protocol Alice sends quantum states to Bob using single photons. In

practice many implementations use laser pulses attenuated to a very low level to send the

quantum states. These laser pulses contain a very small amount of photons, for example

0.2 photons per pulse, which are distributed according to a Poissonian distribution. This

means most pulses actually contain no photons (no pulse is sent), some pulses contain 1

photon (which is desired) and a few pulses contain 2 or more photons. If the pulse

contains more than one photon, then Eve can split of the extra photons and transmit the

remaining single photon to Bob. This is the basis of the photon number splitting attack,

where Eve stores these extra photons in a quantum memory until Bob detects the

remaining single photon and Alice reveals the encoding basis. Eve can then measure her

photons in the correct basis and obtain information on the key without introducing

detectable errors.

There are several solutions to this problem. The most obvious is to use a true

single photon source instead of an attenuated laser. While such sources are still at a

developmental stage QKD has been carried out successfully with them. However as

current sources operate at a low efficiency and frequency key rates and transmission

distances are limited. Another solution is to modify the BB84 protocol, as is done for

example in the SARG04 protocol, in which the secure key rate scales as t3 / 2. The most

promising solution is the decoy state idea, in which Alice randomly sends some of her

laser pulses with a lower average photon number. These decoy states can be used to

detect a PNS attack, as Eve has no way to tell which pulses are signal and which decoy.

Using this idea the secure key rate scales as t, the same as for a single photon source. This

idea has been implemented successfully in several QKD experiments, allowing for high

key rates secure against all known attacks.Page 21

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

17

7. CONCLUSION AND FUTURE SCOPE

Quantum cryptography promises to revolutionize secure communication by

providing security based on the fundamental laws of physics, instead of the current state

of mathematical algorithms or computing technology. The devices for implementing such

methods exist and the performance of demonstration systems is being continuously

improved. Within the next few years, if not months, such systems could start encrypting

some of the most valuable secrets of government and industry.

Future developments will focus on faster photon detectors, a major factor limiting

the development of practical systems for widespread commercial use. Chip Elliott, BBN's

principal engineer, says the company is working with the University of Rochester and

NIST's Boulder Laboratories in Colorado to develop practical superconducting photon

detectors based on niobium nitride, which would operate at 4 K and 10 GHz.

The ultimate goal is to make QKD more reliable, integrate it with today's

telecommunications infrastructure, and increase the transmission distance and rate of key

generation. Thus the Long-term goals of quantum key distribution are the realistic

implementation via fibers, for example, for different buildings of a bank or company ,

and free space key exchange via satellites. Quantum cryptography already provides the

most advanced technology of quantum information science, and is on the way to achieve

the (quantum) jump from university laboratories to the real world. Page 22

QUANTUM CRYPTOGRAPHY

DEPARTMENT OF COMPUTER SCIENCE, CUSAT

18

8. REFERENCES

1. Quantum Cryptography: A Survey

DAGMAR BRUSS, GÃƒÂBOR ERDÃƒâ€° LYI, TIM MEYER, TOBIAS RIEGE, and JÃƒâ€“ RG ROTHE

ACM Computing Surveys, Vol. 39, No.2, Article 6, Publication date: June 2007

2. http://en.wikipediawiki/Quantum_cryptography

3. http://www.aiptip/INPHFA/vol-10/iss-6/p22.html

4. http://www.perimeterinstitute.ca/persona...n/QKD.html

5. http://www.cs.brandeis.edu/pablo/qbc/node4.htm