Part XIII Quantum cryptography Quantum cryptography Quantum cryptography has a potential to be cryptography of 21st century. An important new feature of quantum cryptography is that security of quantum cryptographic protocols is based on the laws of nature - of quantum physics, and not on the unproven assumptions of computational complexity. Quantum cryptography is the first area of information processing and communication in which quantum particle physics laws are directly exploited to bring an essential advantage in information processing. prof. Jozef Gruska 2/62 MAIN OUTCOMES - so far ■ It has been shown that would we have quantum computer, we could design absolutely secure quantum generation of shared and secret random classical keys. ■ It has been proven that even without quantum computers unconditionally secure quantum generation of classical secret and shared keys is possible (in the sense that any eavesdropping is detectable). ■ Unconditionally secure basic quantum cryptographic primitives, such as bit commitment and oblivious transfer, are impossible. ■ Quantum zero-knowledge proofs exist for all NP-complete languages ■ Quantum teleportation and pseudo-telepathy are possible. ■ Quantum cryptography and quantum networks are already in advanced experimental stage. prof. Jozef Gruska 3/62 BASICS of QUANTUM INFORMATION PROCESSING As an introduction to quantum cryptography the very basic motivations, experiments, principles, concepts and results of quantum information processing and communication will be presented in the next few slides. prof. Jozef Gruska 4/62 BASIC MOTIVATION In quantum information processing we witness an interaction between the two most important areas of science and technology of 20-th century, between quantum physics and informatics. This is very likely to have important consequences for 21th century. prof. Jozef Gruska 5/62 QUANTUM PHYSICS Quantum physics deals with fundamental entities of physics - particles (waves?) like ■ protons, electrons and neutrons (from which matter is built); ■ photons (which carry electromagnetic radiation) ■ various "elementary particles" which mediate other interactions in physics. ■ We call them particles in spite of the fact that some of their properties are totally unlike the properties of what we call particles in our ordinary classical world. For example, a quantum particle can go through two places at the same time and can interact with itself. Because of that quantum physics is full of counterintuitive, weird, mysterious and even paradoxical events. prof. Jozef Gruska 6/62 FEYNMAN's VIEW I am going to tell you what Nature behaves like ... However, do not keep saying to yourself, if you can possibly avoid it, BUT HOW CAN IT BE LIKE THAT? Because you will get "down the drain" into a blind alley from which nobody has yet escaped NOBODY KNOWS HOW IT CAN BE LIKE THAT Richard Feynman (1965): The character of physical law. prof. Jozef Gruska 7/62 CLASSICAL versus QUANTUM INFORMATION Main properties of classical information: q It is easy to store, transmit and process classical information in time and space. B It is easy to make (unlimited number of) copies of classical information B One can measure classical information without disturbing it. Main properties of quantum information: □ It is difficult to store, transmit and process quantum information B There is no way to copy unknown quantum information B Measurement of quantum information destroys it, in general. prof. Jozef Gruska 8/62 Classical versus quantum computing The essense of the difference between classical computers and quantum computers is in the way information is stored and processed. In classical computers, information is represented on macroscopic level by bits, which can take one of the two values 0 or 1 In quantum computers, information is represented on microscopic level using qubits, (quantum bits) which can take on any from the following uncountable many values a\0)+/3\l) where a,j3 are arbitrary complex numbers such that H2 + \p\2 = 1. prof. Jozef Gruska 9/62 CLASSICAL versus QUANTUM REGISTERS An n bit classical register can store at any moment exactly one n-bit string. An n-qubit quantum register can store at any moment a superposition of all 2" n-bit strings. Consequently, on a quantum computer one can compute in a single step with 2" values. This enormous massive parallelism is one reason why quantum computing can be so powerful. prof. Jozef Gruska IV054 13. Quantum cryptography 10/62 CLASSICAL EXPERIMENTS prof. Jozef Gruska IV054 13. Quantum cryptography 11/62 QUANTUM EXPERIMENTS detector source ^ of electrons wall H2 >Pl2(z) , . wall ... (a) (b) Figure 3: Two-slit experiment detector light source source v of electrons wall Hi\ i'i-ľ wall P2(x) -P12W (a) (b) (c) Figure 4: Two-slit experiment with an observation prof. Jozef Gruska 12/62 THREE BASIC PRINCIPLES PI To each transfer from a quantum state 0 to a state if) a complex number < is associated. This number is called the probability amplitude of the transfer and Kl2 is then the probability of the transfer. P2 If a transfer from a quantum state 0 to a quantum state if) can be decomposed into two subsequent transfers tp <- ' <- (j> then the resulting amplitude of the transfer is the product of amplitudes of subtransfers: P3 If a transfer from a state

) = ;^*of vectors|) 0i 4>i 02 M) = 0n This allows to define the norm of vectors as 11011 = V\W7\- Two vectors } and are called orthogonal if { C. If V, 4> £ H, then (ip\4>) - scalar product of tp and 4> (an amplitude of going from 4> to tp). \4>) - ket-vector (a column vector) - an equivalent to 4> (tp\ - bra-vector (a row vector) a linear functional on H such that (ip\{\)) = (ip\) prof. Jozef Gruska IV054 13. Quantum cryptography 15/62 QUANTUM EVOLUTION / COMPUTATION EVOLUTION COMPUTATION in in QUANTUM SYSTEM HUBERT SPACE is described by Schrodinger linear equation ihd\%p_ = w(t)|0(t)> where h is Planck constant, H(t) is a Hamiltonian (total energy) of the system that can be represented by a Hermitian matrix and (t) is the state of the system in time t. If the Hamiltonian is time independent then the above Shrodinger equation has solution |0(t)> = U(t)\*(0)) where iHt U(t) = e h is the evolution operator that can be represented by a unitary matrix. A step of such an evolution is therefore a multiplication of a unitary matrix A with a vector \ifj), i.e. A A matrix A is unitary if A ■ A* = A* ■ A = I prof. Jozef Gruska IV054 13. Quantum cryptography 16/62 PAULI MATRICES Very important one-qubit unary operators are the following Pauli operators, expressed in the standard basis as follows; a*=(°i o)'^=(l ~o)'az=(<[) -l) Observe that Pauli matrices transform a qubit state \4>) = a\0) + ß\l) as follows ax(a\0) + ß\l)) =ß\0)+a\l) a2{a\0) + ß\l)) = a\0) - ß\l) ay{a\0) + ß\l)) = ß\0) - a\l) Operators ax,az and ay represent therefore a bit error, a sign error and a bit-sign error. prof. Jozef Gruska IV054 13. Quantum cryptography 17/62 QUANTUM (PROJECTION) MEASUREMENTS A quantum state is always observed (measured) with respect to an observable 0 - a decomposition of a given Hilbert space into orthogonal subspaces (where each vector can be uniquely represented as a sum of vectors of these subspaces). There are two outcomes of a projection measurement of a state } with respect to 0: Q Classical information into which subspace projection of } was made. B Resulting quantum projection (as a new state) '} in one of the above subspaces. The subspace into which projection is made is chosen randomly and the corresponding probability is uniquely determined by the amplitudes at the representation of } as a sum of states of the subspaces. prof. Jozef Gruska IV054 13. Quantum cryptography 18/62 QUANTUM STATES and PROJECTION MEASUREMENT In case an orthonormal basis {j3,}"=1 is chosen in Hn, any state } g Hn can be expressed in the form n n |0) = ^a,-|A),^a,f = l i=i i=i where a; = (Pi\4>) are called probability amplitudes and their squares provide probabilities that if the state } is measured with respect to the basis {j3,}"=1, then the state } collapses into the state \j3i) with probability |a,|2. The classical "outcome" of a measurement of the state \,|1» we can obtain only classical information and only in the following random way: 0 with probability \a\2 1 with probability |/?|2 measurement wrt.{|0 >, |1 >} Classical world measurement wrt. {|0'">,|1'">} Quantum world prof. Jozef Gruska \ >=a\0>+P\l> = í'ŕ'V-Sŕi'i" >measurement wrt-il°" >■ I1" = a'"|0'">+i9'"|l'"> IV054 13. Quantum cryptography >} MIXED STATES - DENSITY MATRICES A probability distribution {(p/, on pure states is called a mixed state to which it is assigned a density operator n p = ^2pi\)(i\- i=l One interpretation of a mixed state {(p/, |/))}/Li is that a source X produces the state with probability p,-. Any matrix representing a density operator is called density matrix. Density matrices are exactly Hermitian, positive matrices with trace 1. To two different mixed states can correspond the same density matrix. Two mixes states with the same density matrix are physically undistinguishable. prof. Jozef Gruska IV054 13. Quantum cryptography 23/62 MAXIMALLY MIXED STATES To the maximally mixed state which represents a random bit corresponds the density matrix i(;)(1,o,+i(j)(o,^i(j Surprisingly, many other mixed states have density matrix that is the same as that of the maximally mixed state. prof. Jozef Gruska 24/62 QUANTUM ONE-TIME PAD CRYPTOSYSTEM CLASSICAL ONE-TIME PAD cryptosystem plaintext an n-bit string c shared key an n-bit string c cryptotext an n-bit string c encoding c = p © k decoding p = c © k QUANTUM ONE-TIT plaintext: shared key: cryptotext: encoding: decoding: an n-qubit string |p) two n-bit strings k,k an n-qubit string c) E PAD cryptosystem Pn) IPl). ki>. k: k; ax oz lp/> \ k: k, i \ \Pi) = ax'az' \q) \c„) where |p,} = (^' J and |c,} = (^ J are qubits and ax = (^ with tjz = \ \ ^ are Pauli matrices. prof. Jozef Gruska IV054 13. Quantum cryptography UNCONDITIONAL SECURITY of QUANTUM ONE-TIME PAD In the case of encryption of a qubit {<(>)= a\0) + ß\l) by QUANTUM ONE-TIME PAD cryptosystem, what is being transmitted is the mixed state whose density matrix is This density matrix is identical to the density matrix corresponding to that of a random bit, that is to the mixed state prof. Jozef Gruska IV054 13. Quantum cryptography 26/62 SHANNON'S THEOREMS Shannon classical encryption theorem says that n bits are necessary and sufficient to encrypt securely n bits. Quantum version of Shannon encryption theorem says that 2n classical bits are necessary and sufficient to encrypt securely n qubits. prof. Jozef Gruska IV054 13. Quantum cryptography 27/62 COMPOSED QUANTUM SYSTEMS (1) Tensor product of vectors (xi,.. . , x„) ® (yi,... ,ym) = (xiyi,..., xiym,x2yi,... ,x2ym,. .. ,x2ym,... , x„yi,... ,x„ym /a\\B ... a\nB\ Tensor product of matrices A® B = \aniB . annB ) where A - Example /an • • • 3ln\ \3fjl • • • 3nn J 1 0\ / an ai2^ 0 1/ la2i a22. ( an 312 1 6 5Í1 °) \a2i 322 / Ho 1 / an ai2 0 ai2\ a2i a22 0 0 a22 y 0 0 an 312 \o 0 a2i 322/ / an 0 o\ 0 an 0 312 a2i 0 a22 0 1° a2i 0 322/ prof. Jozef Gruska IV054 13. Quantum cryptography COMPOSED QUANTUM SYSTEMS (2) Tensor product of Hilbert spaces Hi (g> H2 is the complex vector space spanned by tensor products of vectors from Hi and H2 . That corresponds to the quantum system composed of the quantum systems corresponding to Hilbert spaces Hi and H2. An important difference between classical and quantum systems A state of a compound classical (quantum) system can be (cannot be) always composed from the states of the subsystem. prof. Jozef Gruska IV054 13. Quantum cryptography 29/62 QUANTUM REGISTERS A general state of a 2-qubit register is: |0) = a0o|00) +a0i|01) +aio|10) +an|ll) where «00 2 + «01 2 + aio 2 + an 2 = i 00), |01), |10), |11) are vectors of the ' standard' basis of H4, i.e. (°\ f°\ |00) = 0 0 W |01) = 1 0 w |10) = 0 1 W |n) = 0 0 vJ An important unitary matrix of degree 4, to transform states of 2-qubit registers: CNOT=XOR /I 0 0 0 1 0 0 0 0 1 0 \° 0 0 V It holds: CNOT : \x,y) =>• |x,x0y) prof. Jozef Gruska IV054 13. Quantum cryptography 30/62 QUANTUM MEASUREMENT of the states of 2-qubit registers |0) = a00|00) +a0i|01) +ai0|10) +an|ll) Measurement with respect to the basis {100), |01), |10), |11)} RESULTS: 00) and 00 with probability aoo|2 01) and 01 with probability aoi|2 10) and 10 with probability |aio|2 11) and 11 with probability |an|2 Measurement of particular qubits: By measuring the first qubit we get 0 with probability |aoo|2 + laoi|2 aoo 100) +a0i 101) and |0) is reduced to the vector 1 with probability |«io|2 + an|2 and |0) is reduced to the vector \/\otio\2 + an I2 + an I2 aid 110) + an V|aio|2 + |an|2 prof. Jozef Gruska IV054 13. Quantum cryptography NO-CLONING THEOREM INFORMAL VERSION: Unknown quantum state cannot be cloned. FORMAL VERSION: There is no unitary transformation U such that for any qubit state PROOF: Assume U exists and for two different states \a) and \j3) U(\a)\0)) = \a)\a) U(|/3)|0» = \fl\0) Let |7> = -L(|a> + |/?» Then t/(|7>|0» = ^(|a)|a) + / |7>|7> = ^(lQ>lQ> + + + l^>l«>) However, CNOT can make copies of basis states |0), |1): CNOT(\x)\0)) = \x)\x) prof. Jozef Gruska 32/62 BELL STATES States | + |11)), = -L(|00> _ |11)) = -J=(|01> + |10)), = -J=(|01> - |10)) form an orthogonal (Bell) basis in H4 and play an important role in quantum computing. Theoretically, there is an observable for this basis. However, no one has been able to construct a measuring device for Bell measurement using linear elements only. prof. Jozef Gruska IV054 13. Quantum cryptography 33/62 QUANTUM n-qubit REGISTER A general state of an n-qubit register has the form: 2"-l 2"-l } = ai\i) = Q!;|'}, where |a,-|2 = 1 i=o ;e{o,i}" i=0 and |0} is a vector in H2". Operators on n-qubits registers are unitary matrices of degree 2". Is it difficult to create a state of an n-qubit register? In general yes, in some important special cases not. For example, if n-qubit Hadamard transformation H, is used then Hn|0("») = ®?=iH|0> = ®?=i|0'> 1 xe{o,i}' and, in general, for x g {0,1}' 1The dot product is defined as follows: x ■ y — ®"=1x,y,. prof. Jozef Gruska IV054 13. Quantum cryptography 34/62 QUANTUM PARALLELISM If f :{0,1,...,2"-1}^{0,1,...,2"-1} then the mapping f : (x,0)=S>(x, f(x)) is one-to-one and therefore there is a unitary transformation Uf such that. i/f(|x>|o»=Hx>|f(x)> Let us have the state 2"-l w = -7= y i')io) With a single application of the mapping Uf we then get 2"-l OBSERVE THAT IN A SINGLE COMPUTATIONAL STEP 2" VALUES OF fARE COMPUTED! IN WHAT LIES POWER OF QUANTUM COMPUTING? In quantum superposition or in quantum parallelism? NOT, in QUANTUM ENTANGLEMENT! Let |^> = -^(|00> + |11» be a state of two very distant particles, for example on two planets Measurement of one of the particles, with respect to the standard basis, makes the above state to collapse to one of the states 100} or |11}. This means that subsequent measurement of other particle (on another planet) provides the same result as the measurement of the first particle. This indicate that in quantum world non-local influences, correlations, exist. prof. Jozef Gruska IV054 13. Quantum cryptography 36/62 POWER of ENTANGLEMENT Quantum state |v|/) of a composed bipartite quantum system A (g> B is called entangled if it cannot be decomposed into tensor product of the states from A and B. Quantum entanglement is an important quantum resource that allows ■ To create phenomena that are impossible in the classical world (for example teleportation) ■ To create quantum algorithms that are asymptotically more efficient than any classical algorithm known for the same problem. ■ To create communication protocols that are asymptotically more efficient than classical communication protocols for the same task ■ To create, for two parties, shared secret binary keys ■ To increase capacity of quantum channels prof. Jozef Gruska IV054 13. Quantum cryptography 37/62 CLASSICAL versus QUANTUM CRYPTOGRAPHY ■ Security of classical cryptography is based on unproven assumptions of computational complexity (and it can be jeopardize by progress in algorithms and/or technology). Security of quantum cryptography is based on laws of quantum physics that allow to build systems where undetectable eavesdropping is impossible. ■ Since classical cryptography is vulnerable to technological improvements it has to be designed in such a way that a secret is secure with respect to future technology, during the whole period in which the secrecy is required. Quantum key generation, on the other hand, needs to be designed only to be secure against technology available at the moment of key generation. prof. Jozef Gruska IV054 13. Quantum cryptography 38/62 QUANTUM KEY GENERATION Quantum protocols for using quantum systems to achieve unconditionally secure generation of secret (classical) keys by two parties are one of the main theoretical achievements of quantum information processing and communication research. Moreover, experimental systems for implementing such protocols are one of the main achievements of experimental quantum information processing research. It is believed and hoped that it will be quantum key generation (QKG) another term is quantum key distribution (QKD) where one can expect the first transfer from the experimental to the development stage. prof. Jozef Gruska IV054 13. Quantum cryptography 39/62 QUANTUM KEY GENERATION - EPR METHOD Let Alice and Bob share n pairs of particles in the entangled EPR-state. ^(|00)+ |11)). n pairs of particles in EPR state If both of them measure their particles in the standard basis, then they get, as the classical outcome of their measurements the same random, shared and secret binary key of length n. prof. Jozef Gruska IV054 13. Quantum cryptography 40/62 POLARIZATION of PHOTONS Polarized photons are currently mainly used for experimental quantum key generation. Photon, or light quantum, is a particle composing light and other forms of electromagnetic radiation. Photons are electromagnetic waves and their electric and magnetic fields are perpendicular to the direction of propagation and also to each other. An important property of photons is polarization - it refers to the bias of the electric field in the electromagnetic field of the photon. Figure 6: Electric and magnetic fields of a linearly polarized photon prof. Jozef Gruska IV054 13. Quantum cryptography 41/62 POLARIZATION of PHOTONS Figure 6: Electric and magnetic fields of a linearly polarized photon If the electric field vector is always parallel to a fixed line we have linear polarization (see Figure). prof. Jozef Gruska IV054 13. Quantum cryptography POLARIZATION of PHOTONS There is no way to determine exactly polarization of a single photon. However, for any angle 8 there are ^-polarizers - "filters" - that produce 0-polarized photons from an incoming stream of photons and they let #i-polarized photons to get through with probability cos2(8 — 9\). Figure 6: Photon polarizers and measuring devices-80% Photons whose electronic fields oscillate in a plane at either 0° or 90° to some reference line are called usually rectilinearly polarized and those whose electric field oscillates in a plane at 45° or 135° as diagonally polarized. Polarizers that produce only vertically or horizontally polarized photons are depicted in Figure 6 a, b. prof. Jozef Gruska IV054 13. Quantum cryptography 43/62 POLARIZATION of PHOTONS Generation of orthogonally polarized photons. -m- (0 (b) (d) Figure 6: Photon polarizers and measuring devices-80% For any two orthogonal polarizations there are generators that produce photons of two given orthogonal polarizations. For example, a calcite crystal, properly oriented, can do the job. Fig. c - a calcite crystal that makes ^-polarized photons to be horizontally (vertically) polarized with probability cos28(sin28). Fig. d - a calcite crystal can be used to separate horizontally and vertically polarized photons. prof. Jozef Gruska IV054 13. Quantum cryptography 44/62 7 QUANTUM KEY GENERATION - PROLOGUE Very basic setting Alice tries to send a quantum system to Bob and an eavesdropper tries to learn, or to change, as much as possible, without being detected. Eavesdroppers have this time especially hard time, because quantum states cannot be copied and cannot be measured without causing, in general, a disturbance. Key problem: Alice prepares a quantum system in a specific way, unknown to the eavesdropper, Eve, and sends it to Bob. The question is how much information can Eve extract of that quantum system and how much it costs in terms of the disturbance of the system. Three special cases q Eve has no information about the state Alice sends. B Eve knows that is one of the states of an orthonormal basis {|n) that are not mutually orthonormal and that p, is the probability that = ,-}. prof. Jozef Gruska IV054 13. Quantum cryptography 45/62 TRANSMISSION ERRORS If Alice sends randomly chosen bit 0 encoded randomly as |0) or |0'} or 1 encoded as randomly as |1) or |l'} and Bob measures the encoded bit by choosing randomly the standard or the dual basis, then the probability of error is | = | If Eve measures the encoded bit, sent by Alice, according to the randomly chosen basis, standard or dual, then she can learn the bit sent with the probability 75% . If she then sends the state obtained after the measurement to Bob and he measures it with respect to the standard or dual basis, randomly chosen, then the probability of error for his measurement is | - a 50% increase with respect to the case there was no eavesdropping. Indeed the error is 11 1/11 1 3\_3 2'4 + 2V2'4 + 2'4/8 prof. Jozef Gruska IV054 13. Quantum cryptography 46/62 BB84 QUANTUM KEY GENERATION PROTOCOL Quantum key generation protocol BB84 (due to Bennett and Brassard), for generation of a key of length n, has several phases: Preparation phase Alice is assumed to have four transmitters of photons in one of the following four polarizations 0, 45, 90 and 135 degrees Figure 8: Polarizations of photons for BB84 and B92 protocols Expressed in a more general form, Alice uses for encoding states from the set {|0),|1),|0'),|1')}. Bob has a detector that can be set up to distinguish between rectilinear polarizations (0 and 90 degrees) or can be quickly reset to distinguish between diagonal polarizations (45 and 135 degrees). prof. Jozef Gruska IV054 13. Quantum cryptography 47/62 BB84 QUANTUM KEY GENERATION PROTOCOL (In accordance with the laws of quantum physics, there is no detector that could distinguish between unorthogonal polarizations.) (In a more formal setting, Bob can measure the incomming photons either in the standard basis B = {|0>, |1)} or in the dual basis D = {|0'>, |1')}. To send a bit 0 (1) of her first random sequence through a quantum channel Alice chooses, on the basis of her second random sequence, one of the encodings |0) or |0') (|1) or |1')), i.e., in the standard or dual basis, Bob chooses, each time on the base of his private random sequence, one of the bases B or D to measure the photon he is to receive and he records the results of his measurements and keeps them secret. Alice's Bob's Alice's state The result Correctness encodings observables relative to Bob and its probability 0 -> B |o> 0 (prob. 1) correct 1 -> D ^(|0'> + |1'» 0/1 (prob, i) random o - |0'> 0 -> B ^(|0> + |1» 0/1 (prob, i) random 1 —> D |o'> 0 (prob. 1) correct 1^11) 0 -> B ll> 1 (prob. 1) correct 1 -> D ^(|o'>-|i'» 0/1 (prob, i) random 1^11') 0 -> B ^(|0> + |1» 0/1 (prob, i) random 1 -> D ll'> 1 (prob. 1) correct Figure 9: Quantum cryptography with BB84 protocol Figure 9 shows the possible results of the measurements and their probabilities. prof. Jozef Gruska IV054 13. Quantum cryptography 48/62 BB84 QUANTUM KEY GENERATION PROTOCOL An example of an encoding - decoding process is in the Figure 10. Raw key extraction Bob makes public the sequence of bases he used to measure the photons he received -but not the results of the measurements - and Alice tells Bob, through a classical channel, in which cases he has chosen the same basis for measurement as she did for encoding. The corresponding bits then form the basic raw key. 1 0 0 0 1 1 0 0 0 1 1 Alice's random sequence ll> |0'> |0> |0'> |1> |ľ> |0'> |0> |0> |1> |ľ> Alice's polarizations 0 1 1 1 0 0 1 0 0 1 0 Bob's random sequence B D D D B B D B B D B Bob's observable 1 0 R 0 1 R 0 0 0 R R outcomes Figure 10: Quantum transmissions in the BB84 protocol — R stands for the case that the result of the measurement is random. prof. Jozef Gruska IV054 13. Quantum cryptography 49/62 BB84 QUANTUM KEY GENERATION PROTOCOL Test for eavesdropping Alice and Bob agree on a sequence of indices of the raw key and make the corresponding bits of their raw keys public. Case 1. Noiseless channel. If the subsequences chosen by Alice and Bob are not completely identical eavesdropping is detected. Otherwise, the remaining bits are taken as creating the final key. Case 2. Noisy channel. If the subsequences chosen by Alice and Bob contains more errors than the admitable error of the channel (that has to be determined from channel characteristics), then eavesdropping is assumed. Otherwise, the remaining bits are taken as the next result of the raw key generation process. Error correction phase In the case of a noisy channel for transmission it may happen that Alice and Bob have different raw keys after the key generation phase. A way out is to use qa special error correction techniques and at the end of this stage both Alice and Bob share identical keys. prof. Jozef Gruska IV054 13. Quantum cryptography 50/62 BB84 QUANTUM KEY GENERATION PROTOCOL Privacy amplification phase One problem remains. Eve can still have quite a bit of information about the key both Alice and Bob share. Privacy amplification is a tool to deal with such a case. Privacy amplification is a method how to select a short and very secret binary string s from a longer but less secret string s'. The main idea is simple. If \s\ = n, then one picks up n random subsets Si,. .., S„ of bits of s' and let s,-, the i-th bit of S, be the parity of Si. One way to do it is to take a random binary matrix of size \s\ x \s'\ and to perform multiplication Ms'T, where s'T is the binary column vector corresponding to s'. The point is that even in the case where an eavesdropper knows quite a few bits of s', she will have almost no information about s. More exactly, if Eve knows parity bits of k subsets of s', then if a random subset of bits of s' is chosen, then the probability that Eve has any information about its parity bit is 2-(n-k-l) less than -■-. In 2 prof. Jozef Gruska 51/62 EXPERIMENTAL CRYPTOGRAPHY Successes □ Transmissions using optical fibers to the distance of 120 km. Open air transmissions to the distance 144 km at day time (from one pick of Canary Islands to another). B Next goal: earth to satellite transmissions. All current systems use optical means for quantum state transmissions Problems and tasks □ No single photon sources are available. Weak laser pulses currently used contains in average 0.1 - 0.2 photons. B Loss of signals in the fiber. (Current error rates: 0,5 - 4%) B To move from the experimental to the developmental stage. prof. Jozef Gruska IV054 13. Quantum cryptography 52/62 QUANTUM TELEPORTATION Quantum teleportation allows to transmit unknown quantum information to a very distant place in spite of impossibility to measure or to broadcast information to be transmitted. 2 classical bits gets destroyei by measurement measurement Bob unitary t ransformation I* > \1>) = a\0) + 0\1) \ip)\EPR - pair) -- (100)+ |11» V2 EPR-pair \EPR - pair) -Total state (a|000) + a|011) + /3|100) + /3|111)) Measurement of the first two qubits is done with respect to the "Bell basis": |*+> = -^(|00> + |ll» = -^(|01> + |10» |*-> = -^(|00>-|ll» |V-> = -^(|01> - |10» prof. Jozef Gruska IV054 13. Quantum cryptography QUANTUM TELEPORTATION I Total state of three particles: \i/j)\EPR - pair) = -^(a|000) + a|011) + /?|100) + v2 can be expressed as follows: \*/>)\EPR - pair) = |+)_L(Q|0) + + |v|/+)-j=(P\0) + a\l)) + |0->-L(a|O> - P\l)) + \^-)^=(-P\0)+a\l)) and therefore Bell measurement of the first two particles projects the state of Bob's particle into a "small modification" \ipi) of the state \ip) = a\0) + |v|/i) = either |v|/} or crx|W) or crz|^) or crxcrz|^) The unknown state \ip) can therefore be obtained from \ipi) by applying one of the four operations ax, Uy, crz, / and the result of the Bell measurement provides two bits specifying which of the above four operations should be applied. These four bits Alice needs to send to Bob using a classical channel (by email, for example). prof. Jozef Gruska IV054 13. Quantum cryptography 54/62 QUANTUM TELEPORTATION II If the first two particles of the state \*/>)\EPR - pair) = |+)-L(a|0> + + |i|/+>-L(/J|0> + a|l» + |0->-L(a|O> -/?|l>) + |V->-^(-/?|0)+a|l>) are measured with respect to the Bell basis then Bob's particle gets into the mixed state (\,a\0) +/?|1>) © (i,a|0> -/?|1>) © (\,P\0) + a|l)) © (\,P\0) - a|l>) to which corresponds the density matrix The resulting density matrix is identical to the density matrix for the mixed state J,|o>)efi |i> Indeed, the density matrix for the last mixed state has the form iQ(i,o) + iO(o,i) = i/ prof. Jozef Gruska IV054 13. Quantum cryptography 55/62 QUANTUM TELEPORTATION - COMMENTS ■ Alice can be seen as dividing information contained in into ■ quantum information — transmitted through EPR channel ■ classical information — transmitted through a classical cahnnel ■ In a quantum teleportation an unknown quantum state } can be disassembled into, and later reconstructed from, two classical bit-states and an maximally entangled pure quantum state. ■ Using quantum teleportation an unknown quantum state can be teleported from one place to another by a sender who does need to know - for teleportation itself -neither the state to be teleported nor the location of the intended receiver. ■ The teleportation procedure can not be used to transmit information faster than light but it can be argued that quantum information presented in unknown state is transmitted instanteneously (except two random bits to be transmitted at the speed of light at most). ■ EPR channel is irreversibly destroyed during the teleportation process. prof. Jozef Gruska IV054 13. Quantum cryptography 56/62 DAR PA Network ■ In Cambridge connecting Harward, Boston Uni, and BBN Technology (10,19 and 29 km). ■ Currently 6 nodes, in near future 10 nodes. ■ Continuously operating since March 2004 ■ Three technologies: lasers through optic fibers, entanglement through fiber and free-space QKD (in future two versions of it). ■ Implementation of BB84 with authentication, sifting error correction and privacy amplification. ■ One 2x2 switch to make sender-receiver connections ■ Capability to overcome several limitations of stand-alone QKD systems. prof. Jozef Gruska IV054 13. Quantum cryptography 57/62 WHY IS QUANTUM INFORMATION PROCESSING SO IMPORTANT ■ QIPC is believed to lead to new Quantum Information Processing Technology that could have broad impacts. ■ Several areas of science and technology are approaching such points in their development where they badly need expertise with storing, transmision and processing of particles. ■ It is increasingly believed that new, quantum information processing based, understanding of (complex) quantum phenomena and systems can be developed. ■ Quantum cryptography seems to offer new level of security and be soon feasible. ■ QIPC has been shown to be more efficient in interesting/important cases. prof. Jozef Gruska IV054 13. Quantum cryptography 58/62 UNIVERSAL SETS of QUANTUM GATES The main task at quantum computation is to express solution of a given problem P as a unitary matrix U and then to construct a circuit Qy with elementary quantum gates from a universal sets of quantum gates to realize U. A simple universal set of quantum gates consists of gates. CNOT /l 0 0 0\ 0 10 0 0 0 10 \0 0 0 1/ prof. Jozef Gruska IV054 13. Quantum cryptography 59/62 FUNDAMENTAL RESULTS The first really satisfactory results, concerning universality of gates, have been due to Barenco et al. (1995) Theorem 0.1 CNOT gate and all one-qubit gates form a universal set of gates. The proof is in principle a simple modification of the RQ-decomposition from linear algebra. Theorem 0.1 can be easily improved: Theorem 0.2 CNOT gate and elementary rotation gates 6 6 Ra{@) = cos -/ — / sin —aa for a £ {x, y, z} form a universal set of gates. prof. Jozef Gruska IV054 13. Quantum cryptography 60/62 QUANTUM ALGORITHMS Quantum algorithms are methods of using quantum circuits and processors to solve algorithmic problems. On a more technical level, a design of a quantum algorithm can be seen as a process of an efficient decomposition of a complex unitary transformation into products of elementary unitary operations (or gates), performing simple local changes. The four main features of quantum mechanics that are exploited in quantum computation: ■ Superposition; ■ Interference; ■ Entanglement; ■ Measurement. prof. Jozef Gruska IV054 13. Quantum cryptography 61/62 EXAMPLES of QUANTUM ALGORITHMS Deutsch problem: Given is a black-box function f: {0,1} —> {0,1}, how many queries are needed to find out whether f is constant or balanced: Classically: 2 Quantumly: 1 Deutsch-Jozsa Problem: Given is a black-box function f : {0,1}" —> {0,1} and a promise that f is either constant or balanced, how many querries are needed to find out whether f is constant or balanced. Classically: n Quantumly 1 Factorization of integers: all classical algorithms are exponential. Peter Shor developed polynomial time quantum algorithm Search of an element in an unordered database of n elements: Clasically n queries are needed in the worst case Lov Grover showen that quantumly ^/n queries are enough prof. Jozef Gruska IV054 13. Quantum cryptography 62/62