Introduction to Quantum Cryptography Hoi-Kwong Lo
Department of Elect. & Computer Engineering (ECE); &
Department of Physics;&
University of Toronto
URL: http://www.comm.utoronto.ca/~hklo/
Email: hklo@comm.utoronto.ca

List of most frequently asked questions:

List of most frequently asked questions 1. What quantum code-breaking can do?
2. What quantum code-making can do?
3. What quantum code-making CANNOT do?
4. What is the future direction?

Outline:

Outline Motivation and Introduction: Why quantum crypto?
Quantum key distribution (QKD).
(a) Procedure of standard BB84 protocol
(b) Theory and Experiment
Unconditional security of QKD
Impossibility of Quantum bit commitment (QBC)
What is the Physics?
Concluding Remarks---Bridging the big gap between theory and practice.

CONVENTIONALCRYPTOGRAPHY:

CONVENTIONAL CRYPTOGRAPHY MILITARY AND
DIPLOMATIC
APPLICATIONS SECURE E-BUSINESS
AND E-COMMERCE CRYPTOGRAPHY COMPUTATIONAL ASSUMPTIONS
(e.g. “RSA” crypto assumes factoring is hard)

What is wrong with conventional cryptography?:

What is wrong with conventional cryptography? Unanticipated Advances in Hardware and Algorithms.
Quantum Code-breaking:
“Cryptographers do not sleep well.”
Cryptography is for the paranoid.

1. Unanticipated Advances in Hardware and Algorithms.:

1. Unanticipated Advances in Hardware and Algorithms. In history, every advance in code-making has been defeated
by advances in code-breaking with disastrous consequences to
users. German Enigma Machine
10 million billion possible combinations!
Looked unbreakable. Allied code-breaking machine “bombe”.
Enigma Broken! Code-breaking of Enigma led to fore-runners of computers!

Slide7:

2. Quantum Code-breaking
(Shor’s algorithm): Factoring is easy with a quantum computer! (Peter Shor) Quantum computing can efficiently break:
RSA
Discrete logarithm problem: Diffie-Hellman key exchange
Elliptic-curve cryptographic systems
“If a quantum computer is ever built, much of conventional
Cryptography will fall apart!” (Brassard)

Forward security?:

Forward security? Trade secrets and government secrets are kept as secrets for decades (say 75 years).
A Big Problem RIGHT NOW:
If adversary can factor in 2079, she can then decrypt all traffic sent in 2004. (She can save all communications in 2004.)
Was there any computer 75 years ago?
What will a computer look like 75 years from now?
It is ridiculous to think that we know the future 75 years from now.

Slide9:

ENIAC The world's first electronic digital computer
1946

Slide10:

LAPTOP
2004

Slide11:

COMPUTER
2079
? ? ?

CONVENTIONALCRYPTOGRAPHY:

CONVENTIONAL CRYPTOGRAPHY MILITARY AND
DIPLOMATIC
APPLICATIONS SECURE E-BUSINESS
AND E-COMMERCE CRYPTOGRAPHY COMPUTATIONAL
ASSUMPTIONS

QUANTUM CRYPTOGRAPHY:

QUANTUM CRYPTOGRAPHY MILITARY AND
DIPLOMATIC
APPLICATIONS SECURE E-BUSINESS
AND E-COMMERCE CRYPTOGRAPHY QUANTUM
MECHANICS

Quantum Cryptography:

Quantum Cryptography Two potential applications:
Quantum key distribution (QKD)
Quantum bit commitment

Outline:

Outline Motivation and Introduction: Why quantum crypto?
Quantum key distribution (QKD).
(a) Procedure of standard BB84 protocol
(b) Theory and Experiment
Unconditional security of QKD
Impossibility of Quantum bit commitment (QBC)
What is the Physics?
Concluding Remarks---Bridging the big gap between theory and practice.

Key Distribution Problem:

Key Distribution Problem Alice Bob encryption key decryption key

One-time pad:

One-time pad 011010 XOR 110010 XOR=
Exclusive-OR 101000 transmission 101000 XOR 110010 011010 If Alice and Bob share a common
long random string of secret, then
One-time-pad method is
perfectly secure. (Shannon 1949)
QUESTION: How to transfer
the key?
Alice Eve Bob

Classical Key Distribution:

Classical Key Distribution Eve’s copying
machine Bob Eve (representable as a string of
Number: 01101……. ) All CLASSICAL key distribution schemes are
fundamentally INSECURE.

Quantum key distribution:

Quantum key distribution Quantum No-Cloning Theorem: The polarization of a single photon cannot be cloned. Therefore, eavesdropper CANNOT have the same quantum information that Bob has.

Proof of quantum no-cloning theorem:

Proof of quantum no-cloning theorem Assume the contrary. Cloning implies that:
input , ancilla
| 0 >i | 0 >a | 0 >i | 0 >a Eq. (1)
| 1 >i | 0 >a | 1 >i | 1 >a Eq. (2)
Consider a general input ( a | 0 >i + b | 1 >i ).
QM is linear. Therefore, a x Eq. (1) + b x Eq. (2) gives
( a | 0 >i + b | 1 >i ) | 0 >a a | 0 >i | 0 >a+ b | 1 >i | 1 >a
≠ ( a | 0 >i + b | 1 >i) ( a | 0 >a + b | 1 >a )
Let = | 0 >i , = | 1 >I . Then
θ θ θ

Non-commuting observables:

Non-commuting observables 0 1 Rectilinear basis: eigenstates of σz 0 1 Diagonal basis: σx Heisenberg’s uncertainty principle:
Information gain by Eve implies disturbance.
Therefore, Alice and Bob can detect eavesdropping!
Pauli matrices σx and σz do NOT commute. A single photon can represent one bit of information:

Defeating counterfeiters with unclonable quantum checks (Wiesner) U. Of T. Quantum Check
Serial number: 1011010 Record for U. of T. Quantum Check
Serial number: 1011010 ( up, left, right, down, left, up )
Quantum checks are impossible to counterfeit without basis information.

Quantum key distribution:

Quantum key distribution Absolute security based on fundamental laws of quantum mechanics, rather than computational assumptions.
Allow two persons who share a small amount of authentication information to communicate in absolute security in the presence of an eavesdropper.
Any eavesdropping attack will essentially always be caught.
Alice Bob

Quantum key distribution (QKD):

Quantum key distribution (QKD) Absolute security based on fundamental laws of quantum mechanics, rather than computational assumptions.
Allow two persons who share a small amount of authentication information to communicate in absolute security in the presence of an eavesdropper.
Any eavesdropping attack will essentially always be caught.
Intrusion alert! Eve Intrusion alert!

Procedure of BB84 (Bennett-Brassard protocol):

Procedure of BB84 (Bennett-Brassard protocol)
Similar to uncloneable Quantum Checks discussed before.
In more detail…..…..

Procedure of standard BB84 QKD scheme (Sketch):

Procedure of standard BB84 QKD scheme (Sketch) Step 5: Test for tampering by random sampling and computing
quantum bit error rate. If error rate is OK, apply error correction
and ``privacy amplification’’.

Slide27:

Alice: Bob: Bob: Same
Basis? Bob: Raw key: 1 0 0 0 Schedule of BB84 scheme

Slide28:

Alice: Bob: Bob: Same
Basis? Bob: Raw key: 1 0 0 0 Test for tampering Broadcast and Compare a subset of signals.

Error Correction:

Error Correction Problem: Quantum Transmission may have errors.
Quantum Bit Error Rate (QBER) = wrong bits
total number of bits received
Solution: Error detection/correction
(a) Alice and Bob estimate QBER Alice: 0 1 0 1 1 0 1 1 1
by picking a random subset and Bob: 1 1 0 1 0 0 1 1 1
comparing their values in public.
(b) Classical error correction: Alice: 0 0 1 0 1 1
e.g. (B step) Alice and Bob randomly XOR 0 1 0
pair up bits and take their XOR. XOR 1 1 0
Bob says: Bob: 1 0 1 0 1 1
“Same” Keep first bit
“Different” Discard both bits
Shortened key: 1 0

Error Correction:

Error Correction Problem: Quantum Transmission may have errors.
Quantum Bit Error Rate (QBER) = wrong bits
total number of bits received
Solution: Error detection/correction
(a) Alice and Bob estimate QBER Alice: 0 1 0 1 1 0 1 1 1
by picking a random subset and Bob: 1 1 0 1 0 0 1 1 1
comparing their values in public.
(b) Classical error correction: Alice: 0 0 1 0 1 1
e.g. Alice and Bob randomly pair XOR 0 1 0
up bits and take their XOR. XOR 1 1 0
Bob says: Bob: 1 0 1 0 1 1
“Same” Keep first bit
“Different” Discard both bits
Shortened key: 0 1

Privacy Amplification:

Privacy Amplification Problem: There will be some errors in transmission. Eve may know a small number of bits. For perfect security, Eve must know exponentially small amount of information.
Solution: Alice and Bob use some “hash” function h and use the hashed value as the final key.
Example: (P step) Alice: 101110010
Bob: 101110010
Form random trios and take XOR: 0 1 0 Final key

Slide32:

What about experiments?

Experimental QKD:

Experimental QKD Unlike quantum computing, quantum key distribution is feasible with current technology.
Over Telecom fibers experiments:
Over 100km [Toshiba, LANL, BT (now Corning), Geneva,..]
Limitation: Need quantum repeaters.
Open air experiment (about 23km).
Proposal for ground to satellite experiments.

Commercial Quantum Crypto products available on the market Today!:

Commercial Quantum Crypto products available on the market Today! MagiQ Technologies (New York) and id Quantique (Geneva) are selling commercial quantum cryptographic products.
Distance over 100 km of
commercial Telecom fibers.
Long-term stability through
“auto-compensation”.
(“Plug and Play” set-up.) MAGIQ TECH. ID QUANTIQUE

Slide35:

Randomly selects Phase and Value Randomly chooses Phase Basis Measures Phase & Value Timing and Framing Quantum Crypto over Telecom fibers

DARPA Quantum Network:

DARPA Quantum Network

3. Proposed Ground to satellite QKD experiment:

3. Proposed Ground to satellite QKD experiment

Outline:

Outline Motivation and Introduction: Why quantum crypto?
Quantum key distribution (QKD).
(a) Procedure of standard BB84 protocol
(b) Theory and Experiment
Unconditional security of QKD
Impossibility of Quantum bit commitment (QBC)
What is the Physics?
Concluding Remarks---Bridging the big gap between theory and practice.

Security of Quantum key distribution (Intuition):

Security of Quantum key distribution (Intuition) Quantum No-Cloning Theorem: The polarization of a single photon cannot be cloned. Therefore, eavesdropper CANNOT have the same quantum information that Bob has. a a a IMPOSSIBLE

Is QKD secure?:

Is QKD secure? ``The most important question in quantum
cryptography is to determine how secure it
really is.’’
Gilles Brassard and Claude Crepeau Problems:
a) Real channels are all NOISY. Eve may try to disguise herself as noise.
b) Eve can perform ANY attack consistent with quantum mechanics.
c) A priori, classical probabilistic arguments do NOT work because of
the well-known Einstein-Podolsky-Rosen (EPR) paradox.

1. Proof of unconditional security of quantum key distribution (QKD):

1. Proof of unconditional security of quantum key distribution (QKD) Mayers, J. of ACM, vol. 48, no. 3, pp. 351-406; preliminary version Crypto’96.
Lo and Chau, Science 283, 2050 (1999).
Biham et al., in Proceedings of Symposium on the Theory of Computing, STOC 2000, p. 715.
Ben-Or, to appear.
Shor and Preskill, Phys. Rev. Lett. 85, 441 (2000).
Gottesman and Lo, IEEE Trans. IT, Vol. 49, No. 2, p. 457 (2003). http://xxx.lanl.gov/abs/quant-ph/0105121
With imperfect devices:
Inamori, Lutkenhaus and Mayers, quant-ph/0107017 Los Alamos preprint archive 2001.
D. Gottesman, H.-K. Lo, N. Lütkenhaus, and J. Preskill, http://xxx.lanl.gov/abs/quant-ph/0212066

Error Correction and Security in Quantum Cryptography:

Error Correction and Security in Quantum Cryptography Hoi-Kwong Lo
University of Toronto
in collaboration with
Daniel Gottesman,
Norbert Lutkenhaus
John Preskill
D. Gottesman and H.-K. Lo, IEEE Transactions on Information Theory, Vol. 49, No. 2, p. 457 (Feb., 2003).
Daniel Gottesman, Hoi-Kwong Lo, Norbert Lutkenhaus, John Preskill
http://xxx.lanl.gov/abs/quant-ph/0212066

Two big ideas:

Two big ideas Quantum Cryptography: quantum key distribution
Quantum Error Correction: entanglement distillation protocols.

1. Quantum key distribution (QKD):

1. Quantum key distribution (QKD) Alice Bob Distill a secret (encryption key) from imperfect quantum communications.

2. EDPs (Entanglement Distillation protocols):

2. EDPs (Entanglement Distillation protocols) Distill better singlets from imperfect ones by local operations and classical communications (LOCCs).
Singlet= (1/ √2) [ | 01> - |10> ].

Classification of errors acting on spin-1/2 system:

Classification of errors acting on spin-1/2 system A) Bit flip error: B) Phase error: C) Simultaneous Bit-flip and Phase error: Y= X Z For N spin-1/2 objects, consider the tensor product error operator.
Remark: If an entanglement distillation protocol can correct up to
t errors acting on N spin-1/2 objects of the tensor product form in
X, Y and Z types of errors, then it can correct a general error acting on up to t out of the N spin-1/2 objects. (This is because I, X, Y, and Z generate the most general 2 x 2 unitary matrix.) Two types of
truly independent
errors

Connecting the two big ideas:

Connecting the two big ideas Alice Bob Quantum
Key
Distribution
(QKD):
Entanglement
Distillation
Protocol (EDP):
[Distill better singlets from
imperfect ones by local operations
and classical communications.] Connection: Think of Eve as Environmental Noise. [Distill a secure key from
imperfect quantum
communications.] singlets Alice Bob Environmental
Noise

Overall Strategy of Shor-Preskill’s proof:

Overall Strategy of Shor-Preskill’s proof Use entanglement distillation idea to prove security of standard BB84:
entanglement-based
QKD

Overall Strategy of Shor-Preskill’s proof:

Overall Strategy of Shor-Preskill’s proof Use entanglement distillation idea to prove security of standard BB84:
entanglement-based
QKD Reduction

Overall Strategy of Shor-Preskill’s proof:

Overall Strategy of Shor-Preskill’s proof Use entanglement distillation idea to prove security of standard BB84:
entanglement-based
QKD Reduction Procedure:
Construct entanglement-based QKD scheme and prove its security.
Show that security of EPP-based QKD scheme implies
Security of BB84.
Result: A simple proof of unconditional security of BB84.
(Cf. Mayers’ proof, the first proof for BB84, is hard for many people.)
Remark: Unconditional security means security against the most
general type of attacks---``joint attacks’’. Holy Grail of Quantum Crypto.

Deutsch et al 96/Lo-Chau 98:

Deutsch et al 96/Lo-Chau 98 Entanglement-based QKD scheme:
Alice (or Eve) prepares EPR pairs ( | 01> - |10>)n and sends half of each pair to Bob.
Alice & Bob perform entanglement distillation
Measurement of almost perfect EPR pairs.

Question:

Question How to reduce an entanglement distillation based QKD protocol to standard BB84? Solution: Shor-Preskill’s proof….

Correspondence between quantum error corrrection and BB84 (Shor-Preskill’s proof):

Correspondence between quantum error corrrection and BB84 (Shor-Preskill’s proof) CSS codes BB84
bit flip error correction error correction
phase error correction privacy amplification
(to remove Eve’s info.)

Equivalence of circuits:

Equivalence of circuits
Phase error correction privacy amplification. Recall: Measure X (P step) Circuit that computes

Example: Three-qubit code:

Example: Three-qubit code Classical 3-bit repetition code (can correct one error):
0 000
111
Suppose there is one error in the second bit:
0 000 010
1 111 101

Example: Three-qubit phase code:

Example: Three-qubit phase code Classical 3-bit repetition code (can correct one error):
0 000
111
Suppose there is one error in the second bit:
0 000 010
1 111 101
Comparing first bit with second Z1 Z2: Get 1 Second bit
Comparing first bit with third Z1 Z3 : Get 0 is wrong.

Equivalence of circuits
Phase error correction privacy amplification. Recall: = Three-qubit phase code Measure X Classical circuit that computes:

Intuition of Shor-Preskill’s proof:

Intuition of Shor-Preskill’s proof To go from EDP-based QKD to standard BB84,
Just throw away phase error syndrome.
The value of the final key is not changed by phase errors.
What is important is not phase error correction is actually performed, but that it could have been successful, if it had been performed.

Tolerable Bit Error Rates:

Tolerable Bit Error Rates Question: Under what operating parameters will BB84 be secure? Proof (Quantum) Bit Error Rate Cf. Upper bound: 25%.
Significance of our result:
Practical: a) Extend distance of secure QKD.
b) Higher key generation rate.
c) Proved security of standard schemes: e.g. ``Cascade’’
2) Conceptual: a) Demonstrate the advantage of using two-way
classical communications in classical post-processing
of data generated in QKD.
b) Introduce a new class of quantum codes.

Correspondence between EDP and BB84 (Gottesman-Lo’s proof):

Correspondence between EDP and BB84 (Gottesman-Lo’s proof) EDP BB84/six-state
bit-flip error detection “advantage distillation”
bit-flip error correction error correction
phase error correction privacy amplification
We proved BB84 is secure up to 18.9 percent bit error rate.
“Security of quantum key distribution with two-way classical communications”,
D. Gottesman and H.-K. Lo, IEEE Transactions on Information Theory,
Vol. 49, No. 2, p. 457 (Feb., 2003). http://xxx.lanl.gov/abs/quant-ph/0105121

Classification of Entanglement Distillation Protocols:

Classification of Entanglement Distillation Protocols Alice A) EDP with ONE-WAY classical communications only. B) EDP with TWO-WAY classical communications. Alice Bob

Connecting EDP with BB84:

Connecting EDP with BB84 EDP with one-way
Communications BB84 Shor-Preskill Use CSS codes EDP with two-way
communications
BB84 Gottesman-Lo Two-way
CSS-like codes

Correspondence between quantum error correction and BB84:

Correspondence between quantum error correction and BB84
Quantum-computing BB84
Protocol
bit-flip error detection “advantage distillation”
(e.g B step)
bit-flip error correction error correction
phase error correction privacy amplification

Correspondence between quantum error correction and BB84:

Correspondence between quantum error correction and BB84
Quantum-computing BB84
Protocol
bit-flip error detection “advantage distillation”
(e.g B step)
bit-flip error correction error correction
phase error correction privacy amplification
Phase error detection STRICTLY FORBIDDEN!
(Phase error syndrome not available without QC.)

Outline:

Outline Motivation and Introduction: Why quantum crypto?
Quantum key distribution (QKD).
(a) Procedure of standard BB84 protocol
(b) Theory and Experiment
Unconditional security of QKD
Impossibility of Quantum bit commitment (QBC)
What is the Physics?
Concluding Remarks---Bridging the big gap between theory and practice.

Slide67:

Quantum Key Distribution Alice Bob Eve

Slide68:

Beyond Quantum Key Distribution Alice Bob 666 666

Slide69:

Age Problem Alice Bob I’m X years old. I’m Y years old. How to find out whether x > y without
disclosing the exact value of x and y to each other?

Impossibility of Quantum Bit Commitment (QBC):

Impossibility of Quantum Bit Commitment (QBC) Old belief: The Age Problem can be solved through a basic primitive called quantum ``bit commitment’’.
Surprising result: (Mayers 96, Lo and Chau 96) Unconditionally secure quantum bit commitment is IMPOSSIBLE.

Aside: What is bit commitment?:

Aside: What is bit commitment? 1. Commit Phase: Alice 0 1 or Bob 2. Opening Phase: Alice can prove to Bob that she has made up her mind during
the commit phase and she cannot change it. Yet, Bob does not
know her choice until the opening phase.

Example: Bennett and Brassard QBC scheme:

Example: Bennett and Brassard QBC scheme Alice picks a bit, b, to be 0 or 1.
If b= 0, Alice prepares a time sequence of photons in
either or polarization and sends them to Bob.
If b=1, Alice prepares a time sequence of photons in
either or polarization and sends them to Bob.
3. To open the bit, Alice announces the value of b and the polarizations of all photons sent to Bob. Bob checks Alice’s answers.
Remark: If Alice prepares a “0” and then opens as “1”, she has to guess the polarizations randomly. Thus, probability of passing the test is only (1/2)n, where n is the number of photons sent. Exponential security.

Entangled attack breaks Bennett and Brassard QBC scheme:

Entangled attack breaks Bennett and Brassard QBC scheme Alice picks a bit, b, to be 0 or 1.
If b= 0, Alice prepares a time sequence of photons in
either or polarization and send them to Bob.
If b=1, Alice prepares a time sequence of photons in
either or polarization and send them to Bob.
3. To open the bit, Alice announces the value of b and the polarizations of all photons sent to Bob. Bob checks Alice’s answers.
Quantum cheating: Suppose for each photon, Alice prepares a singlet state (1/ √2) [ | 01> - |10> ] and sends the second half to Bob, keeping the first half herself. She postpones her choice of b. In the opening phase, if she decides now that b=0, she measures her qubits along rectilinear basis. If she decides that b=1, she measures them along diagonal basis instead. She can always cheat successfully by Einstein-Poldolsky-Rosen effect. Bob’s polarization is always anti-parallel to Alice’s.

Entangled attack breaks Bennett and Brassard QBC scheme:

Entangled attack breaks Bennett and Brassard QBC scheme Quantum cheating: Suppose for each photon, Alice prepares a singlet state (1/ √2) [ | 01> - |10> ] and sends the second half to Bob, keeping the first half herself. She postpones her choice of b. In the opening phase, if she decides now that b=0, she measures her qubits along rectilinear basis. If she decides that b=1, she measures them along diagonal basis instead. She can always cheat successfully by Einstein-Poldolsky-Rosen effect. Bob’s polarization is always anti-parallel to Alice’s.
Essence: Use entanglement (Einstein-Podolsky-Rosen effect) and delay measurements.

Generality of the proof of impossibility of quantum bit commitment:

Generality of the proof of impossibility of quantum bit commitment Any quantum/classical hybrid protocol can be equivalently be
described by a purely quantum protocol. (Analogy: Any
expression involving both real numbers and complex numbers
can be evaluated by using complex analysis. There is no need
to switch back and forth between real and complex analyses.)

Aside: What is bit commitment?:

Aside: What is bit commitment? 1. Commit Phase: Alice 0 1 or Bob 2. Opening Phase: Alice can prove to Bob that she has made up her mind during
the commit phase and
she cannot change it.
Bob does not know her choice until the opening phase.
Will Show that (a) and (b) are incompatible: (b) implies not (a)!

Schmidt decomposition Theorem:

Schmidt decomposition Theorem Theorem: Any bi-partite pure state of a system consisting of subsystems A and B can be re-written as
| ψ > = Σ √ pi |ai >A | bi>B where |ai >A’s are orthonormal in A and |bi >A’s are orthonormal in B [i.e. No cross terms.]
where pi ‘s are eigenvalues of the reduced density matrix ρB.
N.B. Bob’s reduced density matrix is
ρB = TrA | ψ > < ψ | = Σ pi | bi>B < bi | B

Impossibility of QBC:

Impossibility of QBC Using a unitary description, one can write Alice and Bob’s combined system at the end of the commit phase as a pure state.
Requirement (b)----Bob does not know the bit of Alice---implies ρB0 ≈ ρB1
Case One: Ideal case: ρB0 = ρB1 . Suppose
ρB = TrA | ψ > < ψ | = Σ pi | bi>B < bi | B
From Schmidt decomposition theorem,
| ψ0 > = Σ √ pi |a i >A | bi >B and
| ψ1 > = Σ √ pi |a’ i >A | bi >B .
N.B. This implies that | ψ0 > and | ψ1 > are related by a local unitary transformation by Alice only. Consider UA : |a i >A |a’ i >A .
Indeed, UA | ψ0 > = | ψ1 > .
Note that Alice can change | ψ0 > to | ψ1 > without Bob’s help!!

Quantum cheating strategy: Ideal case.:

Quantum cheating strategy: Ideal case. Alice picks b =0 and executes the protocol by a quantum computer. At the end of the commit phase, the overall state is given by .
In the beginning of the opening phase, Alice decides on the value of the bit that she wants to open.
If b=0, she simply honestly executes the protocol.
If b=1, she applies a unitary transformation UA first and then executes the protocol corresponding to b=1.
Note that since UA | ψ0 > = | ψ1 > , Alice has successfully prepared the required state for b=1! Therefore, Alice will succeed with probability 1 in deceiving Bob.
In summary: Alice can always delay her measurements and cheat successfully in QBC! This is due to a fundamental effect---Einstein-Podolsky-Rosen effect---in QM. | ψ0 > = Σ √ pi |a i >A | bi >B

Non-ideal case:

Non-ideal case Case Two: Non-ideal case ρB0 ≈ ρB1 .
Fidelity: F (ρB0 , ρB1 ) = Max < φ0 | φ1 > = 1 – δ where
| φ0 > and | φ1 > are purifications of ρB0 and ρB1 respectively.
It turns out that we can consider a fixed purification, say
| ψ1 > of ρB1 and
F (ρB0 , ρB1 ) = Max < φ0 | ψ1 > = < φ0opt | ψ1 > = 1 – δ.
Any two purifications must be related by a unitary transformation. Therefore,
| ψ0 > = UA | φ0opt > for some UA .
Alice can make | ψ0 > looks like | ψ1 > by applying a local unitary transformation UA by herself.

Quantum cheating strategy: Non-ideal case.:

Quantum cheating strategy: Non-ideal case. Alice picks b =0 and executes the protocol by a quantum computer. At the end of the commit phase, the overall state is given by .
In the beginning of the opening phase, Alice decides on the value of the bit that she wants to open.
If b=0, she simply honestly executes the protocol.
If b=1, she applies a unitary transformation UA first and then executes the protocol corresponding to b=1.
Note that since UA | ψ0 > ≈ | ψ1 > , Alice has successfully prepared the required state for b=1! Therefore, Alice will succeed with high probability in deceiving Bob.
In summary: Alice can always delay her measurements and cheat almost always successfully in QBC! This is due to a fundamental effect---Einstein-Podolsky-Rosen effect---in QM. | ψ0 > = Σ √ pi |a i >A | bi >B

Foundation of security:

Foundation of security DOABLE Quantum Key Distribution
(No-cloning
Theorem)
Mayers
Lo and Chau
Biham et al.
Ben-Or
Shor and Preskill IMPOSSIBLE Quantum bit commitment
Quantum oblivious transfer
(Quantum cheating using
``Einstein-Podolsky-Rosen Effect’’)
Mayers
Lo and Chau
Lo

Slide83:

DOABLE Quantum Key Distribution
(No-cloning
Theorem)
Mayers
Lo and Chau
Biham et al.
Ben-Or
Shor and Preskill IMPOSSIBLE Quantum bit commitment
Quantum oblivious transfer
(Quantum cheating using
``Einstein-Podolsky-Rosen Effect’’)
Mayers
Lo and Chau
Lo WHAT IS THE BOUNDARY
WHY IS THERE SUCH A BOUNDARY? Quantum coin tossing Unclonable quantum
encryption

Outline:

Outline Motivation and Introduction: Why quantum crypto?
Quantum key distribution (QKD).
(a) Procedure of standard BB84 protocol
(b) Theory and Experiment
Unconditional security of QKD
Impossibility of Quantum bit commitment (QBC)
What is the Physics?
Concluding Remarks---Bridging the big gap between theory and practice.

What is the physics?:

What is the physics? Classical
Description
(Classical
Probability
Theory)
Simple Quantum/
Classical
Hybrid
Description
COMPLEX Quantum
Description
(Unitary
Description)
Simple Reduction? Reduction?

What is the physics?:

What is the physics? Classical
Description
(Classical
Probability
Theory)
Simple Quantum/
Classical
Hybrid
Description
COMPLEX Quantum
Description
(Unitary
Description)
Simple Reduction Reduction Construct
Commuting
Observables Always
Possible

Outline:

Outline Motivation and Introduction: Why quantum crypto?
Quantum key distribution (QKD).
(a) Procedure of standard BB84 protocol
(b) Theory and Experiment
Unconditional security of QKD
Impossibility of Quantum bit commitment (QBC)
What is the Physics?
Concluding Remarks---Bridging the big gap between theory and practice.

Theory and Practice:

Theory and Practice Theory

Theory and Practice:

Theory and Practice Theory Practice

Bridging the gap between theory and practice:

Bridging the gap between theory and practice Theory Practice There is a big gap
between theory and practice!

Bridging the gap between theory and practice:

Bridging the gap between theory and practice Theory Practice Phenomenology

QKD : Theory Bennett and Brassard’s scheme (BB84):

QKD : Theory Bennett and Brassard’s scheme (BB84) ASSSUMPTIONS:
Source: Emits perfect single photons. (No multi-photons)
Channel: Noisy but lossless. (No absorption in channel)
Detectors: a) Perfect detection efficiency. (100 %)
Basis Alignment: Perfect. (Angle between X and Z basis is exactly 45 degrees.)
Assumptions lead to security proofs:
Mayers (BB84), Lo and Chau (quantum-computing protocol), Biham et al. (BB84), Ben-Or (BB84), Shor-Preskill (BB84), …
Conclusion: QKD is secure in theory.
Alice Bob

QKD : Practicee.g., weak coherent state implementation of BB84:

QKD : Practice e.g., weak coherent state implementation of BB84 Reality:
Source: Weak coherent states of bosonic modes. (Double photons may be emitted.)
Channel: Absorption inevitable. (e.g. 0.25 dB/km)
Detectors: efficiency ~15% for Telecom wavelengths
Basis Alignment: Minor misalignment inevitable.
Question: Is QKD is secure in practice?
(Progress: i) Inamori, Lütkenhaus, and Mayers
and ii) Gottesman. Lo, Lütkenhaus, and Preskill.)

Applications of our results:

Applications of our results Tagging: A faulty source may “tag” some of the qubits with information, readable by the eavesdropper, that reveals the basis used in preparation. (Special case: Inamori, Lutkenhaus, and Mayers considered weak coherent states. Multi-photons reveal basis information).
Basis-dependent detector efficiency: The probability that a qubit is detected may depend on the basis used. An adversary may control whether the detector fires to disguise eavesdropping.
Basis-dependent misalignment in source/detector: Source and detector not perfectly aligned. Eavesdropper can exploit her freedom to rotate these devices to reduce the disturbance caused by her eavesdropping. fire ; pass. rectilinear basis diagonal basis Bob’s basis:

Error Rates of tested and untested pairs:

Error Rates of tested and untested pairs Tested Pairs: , X-basis error rate (of tested signals) , Z-basis error rate (of tested signals) Key generation Pairs: , bit-flip error rate. [Key generation rate: ] Question: How to relate to ? Answer: With imperfection =
(Biased Sample) = . Conclusion: Can reduce the whole question of dealing with imperfections to deriving constraints on from . . , phase error rate.

Future directions:

Future directions Model real-life QKD systems.
Study eavesdropping attacks.
Design practical protocols for classical post-processing of QKD.

Summary:

Summary 1. What quantum code-breaking can do?
2. What quantum code-making can do?
3. What quantum code-making CANNOT do?
4. What is the future direction?

Summary:

Summary 1. What quantum code-breaking can do?
Break standard encryption schemes including RSA.
2. What quantum code-making can do?
Secure communications using unbreakable quantum key distribution (QKD).
3. What quantum code-making CANNOT do?
Protect private information during discussions: Age problem.
4. What is the future direction?
Bridging the big gap between theory and practice.
Build single photon source, better single-photon detectors, better fibers. Build Quantum Repeaters.
Ground to satellite experiments. Commercialization.

Reference:

Reference A. Survey paper in “Physics Today”:
Gottesman and Lo, “From quantum cheating to quantum security’’,
Physics Today, Nov. 2000 p. 22.
www.physicstoday.org/pt/vol-53/iss-11/p22.html
B. Recent papers:
Simple proof of security of the BB84 QKD Protocol,
Shor and Preskill, PRL 85 (2000) 441-444
2. Security of quantum key distribution with two-way classical communications, Gottesman and Lo, IEEE Trans. IT, Vol. 49, No. 2, p. 457 (2003). http://xxx.lanl.gov/abs/quant-ph/0105121
3. Security of quantum key distribution with imperfect Devices,
Gottesman, Lo, Lütkenhaus & Preskill,
http://xxx.lanl.gov/abs/quant-ph/0212066

Slide100:

THE END

1.Design practical protocols for classical post-processing of QKD.:

1.Design practical protocols for classical post-processing of QKD. Remark: ``Privacy amplification’’ is the dual of error correction. (Cf. “Generalized Hamming Weights for linear codes”, Wei, IEEE IT, 91)
1. Finite size codes: (convolutional codes or block codes?)
Security proofs usually deal with an infinitely long key.
In practice, it is necessary to consider a final key of finite length.
Fluctuations become very important.
Need REAL-TIME (hardware?) implementation.
Limited REAL random number generator rate.
Limited computational power.
Limited memory space.
Limited classical communication bandwidth.
Cost

2. Model real-life QKD systems.:

2. Model real-life QKD systems. 1) All models of QKD are idealizations of real-life systems.
Real-life QKD system is a complex system with many degrees of freedom.
2) Imperfections:
Imperfect single-photon sources
Lossy channels
Imperfect single-photon detection efficiency
Detectors’ dark counts
Trojan Horse’s attacks
Denial-of-service attacks
How to quantify (experimentally) small imperfections and ensure security in the presence of those imperfections?

3. Study eavesdropping attacks. :

3. Study eavesdropping attacks. The best way to build a secure cryptographic system is to try hard to break it.
Need to study theoretically and experimentally the feasibility and power of various eavesdropping attacks: beam-splitting attacks, unambiguous state determination, Trojan Horse attacks, etc.

Experimental Implementations:

Experimental Implementations Current status: Small scale Implementations.
Entanglement of four atoms.
Factor 15=3 x 5 in nuclear magnetic resonance machines.
Proposals for scalable quantum computers: Ion Traps, Cavity Quantum Electrodynamics, Nuclear Magnetic Resonance (NMR), Optical Lattices, Super-conducting qubits, Silicon-based proposal, Electrons flowing on Helium, …

Towards scalablequantum computers:

Towards scalable quantum computers Proposals:
Ion Traps
Cavity Quantum Electrodynamics
Nuclear Magnetic Resonance (NMR)
Optical Lattices
Super-conducting qubits
Silicon-based proposals
Electrons flowing on Helium
8. …….
9. …….

Towards scalable quantum computers IV:

Towards scalable quantum computers IV Summary:
Primitive (small scale) quantum computing has successfully been performed in experiments.
Large scale experimental quantum computing is extremely challenging. But, this has not deterred researchers from working on the subject.
Success of quantum computing depends on efforts, not time. (Eli Yablonovitch UCLA)

Research activities in quantum information processing:

Research activities in quantum information processing Industries: MagiQ, AT&T, Bell Labs, IBM, Microsoft,…
Universities: Too many to list. (e.g. Caltech, MIT, Stanford, Princeton, UC Berkeley, UCLA, UC Santa Barbara,…)
National Labs: NIST, Los Alamos
Funding Agencies: DARPA, ARO, NSA, NIST, NASA,…
(In the US alone, public government funding is over $50 million per year.)
Motivation: Go beyond the demise of Moore’s law.
Quantum information processing as the Second Phase of the IT revolution.

What is bit commitment?:

What is bit commitment? 1. Commit Phase: Alice 0 1 or Bob 2. Opening Phase: Alice can prove to Bob that she has made up her mind during
the commit phase and she cannot change it. Yet, Bob does not
know her choice until the opening phase.

What is oblivious transfer?:

What is oblivious transfer? Alice sends two pieces of information to Bob. Bob can only
choose to learn one piece of the information, NOT both.
Alice does not know which piece of information Bob has learnt.
For example, Alice sends her age and height to Bob.
Bob can learn either Alice’s age or height, but not both….

Advances in quantum crypto:

Advances in quantum crypto

Quantum cheating using Einstein-Podolsky-Rosen effect:

Quantum cheating using Einstein-Podolsky-Rosen effect Quantum objects can exhibit correlations that are stronger than
what is allowed by any local classical model. Spin 0 When a spin-0 object decays into two spin-1/2 objects, from
conservation of momentum, the two resulting objects exhibit
perfect anti-correlations.
Individual measurement outcomes: RANDOM
Relative measurement outcomes: OPPOSITE
Appearance of faster-than-light transmission.
Does not violate causality because the outcomes are random.

What is the physics?:

What is the physics? Classical
Description
(Classical
Probability
Theory)
Simple Quantum/
Classical
Hybrid
Description
COMPLEX Quantum
Description
(Unitary
Description)
Simple Reduction Reduction Construct
Commuting
Observables Always
Possible

“Commuting observables” idea:

“Commuting observables” idea Question: Does classical estimation theory work for the estimation of error rates in quantum mechanics?
Answer (Lo-Chau): Yes, provided that we use only commuting observables.
e.g. For two qubits, σx . σx and σz . σz commute.
Therefore, they have simultaneous eigenvectors. One can
safely assign probabilities to them and use classical probability theory.

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.

By: raghav_29 (28 month(s) ago)

Plz send it to raghav1sharma@yahoo.co.in