Quantum Computing

Hartmut KlauckUniversität FrankfurtWS 04/05

2.2.

Andere Krypto-Probleme

Bit-Commitment [BC]: Alice möchte ein Bit verschliessen, an Bob geben, so

dass• Bob keine Information über das Bit erhält• Alice trotzdem festgelegt ist

Packe Zettel mit Bit in einem Safe, behalte Schlüssel Coin-Flipping [CF]:

Alice und Bob möchten über einen Kommunikationskanal ein faires Zufallsbit ziehen

1,2-Oblivious-Transfer [OT]: Alice hat 2 Bits, Bob soll genau ein Bit lernen, Alice

nicht, welches

Anwendungen

BC: Z.B. Auktionen OT: Private Berechnung von

Funktionen CF: On-line Spiele

BC und CF

Wenn BC möglich, dann auch CF:Alice wirft eine Münze, Wert x,

Commitment an BobBob wirft eine Münze, Wert y, sendet

zu AliceAlice öffnet CommitmentZufallsbit x©y

Klassische Unmöglichkeit

OT: Bob kann immer Information über beide Eingaben erhalten

BC: Wenn Alice Bob Nachricht ohne Information sendet, kann Alice immer ihr Bit wechseln

CF: Entweder: Für alle Nachrichten von Alice gibt es jeweils eine Nachricht von Bob, .... , so dass Bob gewinnt, dann kann Bob perfekt betrügenOder: umgekehrt, Alice kann perfekt betrügen

BB84 Bit Commitment

Commit: Alice wählt Basis |0i, |1i ODER

(|0i+|1i)/21/2, (|0i-|1i)/21/2

Alice sendet 100 zufällige Elemente der Basis, entspr. Bits x1,...,x100

Bob misst die erhaltenen Zustände, jeweils zufällig in einer der Basen

Reveal: Alice sagt Basis, sendet x1,...,x100

Bob testet, ob seine Messergebnisse korrekt auf den Qubits, wo er in der richtigen Basis gemessen hat, und Messergebnisse sonst unkorelliert

Ist das Protokoll korrekt?

Bekommt Bob Information? Kann Alice mogeln?

Bob erhält 100 Qubits, jedes ist zufällig aus |0i, |1i ODER selbe Situation mit (|0i+|1i)/21/2, (|0i-|1i)/21/2

Behauptung: Beide Fälle ununterscheidbar!

Dichtematrizen

Sei ein Zustand |i=i=1...n i |ii gegeben “purer Zustand”

h| transponierter und komplex konjugierter Vektor

Dichtematrix: |i h| Matrix hat Rang 1 Eigenwert 1 mit Eigenvektor |i Spur 1 Hermitesch und positiv semidefinit

Gemischte Zustände

Ensemble: Menge von Zuständen mit Wahrscheinlichkeiten, {|ii,pi}; pi=1

Dichtematrix dazu: pi |ii hi| Klar:

Matrix ist HermiteschSpur ist 1 (ist linear)Ist positiv semidefinit

Dichtematrizen

Dichtematrix: Matrix ist Hermitesch Spur ist 1 (ist linear) Ist positiv semidefinit

Definiere Quantenzustände als Dichtematrizen

Anwendung einer unitären Operation: U U* Messung: per Linearität definiert

Dichtematrizen

Für jedes : es gibt eine Basis, in der diagonal ist, EW auf Diagonale, EW reell, zwischen 0 und 1

In dieser Basis ist eine Wahrscheinlichkeitsverteilung

Wenn purer Zustand ist, dann ist Diagonale (00010000)

Dichtematrizen und Ensembles Zu jedem Ensemble gibt es genau eine Dichtematrix Umgekehrt? Bob erhält 100 Qubits, jedes ist zufällig aus |0i, |1i

ODER selbe Situation mit (|0i+|1i)/21/2, (|0i-|1i)/21/2

Behauptung: Beide Fälle ununterscheidbar! Dichtematrizen:

Ist BB84 BC sicher?

Bob erhält keine Information in der Commit Phase Aber kann Alice mogeln?

Alice präpariert 100 EPR-Paare, schickt je eines der Qubits zu Bob

Für Bob kein Unterschied erkennbar Bob misst EPR-Paare (in zuf. Basis) Alice behauptet gewünschte Basis, misst ihre Qubits

in dieser Basis, und nennt Bob Messergebnisse Behauptung: Übereinstimmung auf gewählter Basis,

keine Korrelation auf anderer:

Gibt es andere Protokolle?

Theorem: [Mayers 96] Bit-Commitment ist nicht möglich (basiert allein auf Quantenmechanik)

Idee: Annahme Alice und Bob enden nach Commit mit Zustand |ABi, der teilweise bei Alice liegt, teilweise bei Bob. Bob’s Teil hat keine Information über das versteckte Bit: Alice kann immer mogeln.

Beschreibung von Teilsytemen Sei also |ABi gegeben Im normalen Formalismus Teilsysteme nicht

beschreibbar, z.B. EPR-Paare Dichtematrix AB auf Zuständen im Hilbertraum H­ G ist

Matrix mit |H| |G| Zeilen und Spalten Operation partielle Spur: traceB (|ai hb|­|cihd| = |ai hb| ¢ trace |ci hd|

Beschreibung von Teilsytemen Eigenschaften:

A ist Dichtematrix A­B AB im allgemeinen A ist der Zustand des A-Teilsystems traceB(A­ B)=A

Beispiel: EPR-Paar

Purifikation

Sei eine Dichtematrix eines gemischten Zustands im Raum H

Dann gibt es einen Zustand |ABi in H­H mittraceB |ABi hAB|=

Warum? Bringe in Diagonalform, mit Diagonale p1,...,pm und EV |v1i,..,|vii

Setze |i=pi)1/2 |vii |ii

Purifikation

Weiterhin: Alle Purifikationen sind unitär äquivalent, d.h. es gibt unitäre Transformationen, die zwei gegebene Purifikationen ineinander überführen Jeder Zustand kann als

i i |eii|dii geschrieben werden [Schmidt Dekomposition], wegen Singularwertdekomposition

Dabei sind i immer gleich Purifikationen sind i i |eii|dii­i i |eii|fii Verwende unitäre Transformation, die e-Basis zu f-

Basis wechselt

Unmöglichkeit von BC

Am Ende der Commit Phase sind (im ehrlichen Protokoll) Zustände AB oder AB gegeben mit B=B

O.b.d.A. sind AB und AB pur, da Messungen simulierbar durch Hinzunehmen von Qubits und unitären Transformationen

Dann sind es Purifikationen, und Alice kann später ihr Bit wechseln

Entspricht verallgemeinertem EPR Angriff: gemessene Zustände durch Purifikation ersetzen

Quantitatives Argument möglich: Bob hat Information , dann kann Alice mit Ws 1-1/2 mogeln

Coin Flipping

Geht Coin Flipping? Nicht, wenn unehrlicher Spieler

keinen Vorteil erhalten kann Möglich mit bias 1/4:

Beide ehrlich) Fairer MünzwurfBeide unehrlich: Verhalten egalEiner unehrlich: Erhält gewünschtes

Ergebnis mit Ws. 3/4

Protokoll

[Ambainis 2001] Alice macht schwaches Commitment:

Verwende Qutrits: Alice zieht a und sendet zweites Qutrit von (|aai+|22i)/21/2

Bob sendet Zufallsbit b zu Alice Alice sendet zweites Qutrit und a Bob testet ob Qutrits im korrekten Zustand Wenn ja, Ausgabe a©b

Niemand mogelt: 1 resp. 0 mit Ws. 1/2

Bob mogelt:

Bob kann Qutrit messen, kann mit Ws. 1/2 Wert a erfahren und b anpassen, Erfolg 3/4

Bob muss a raten um das Ergebnis festzulegen, wenn Alice erhlich

Man zeigt, dass a nur mit Ws. 3/4 geraten werden kann: Betrachte Distanz zwischen den Dichtematrizen der Zustände für a=0 und a=1 und deren Zusammenhang zur Vorhersagbarkeit

Alice mogelt:

Alice startet mit (|00i+|11i+2|22i) /61/2

Alice sendet in Runde 3 a=b um Münze 0 zu erhalten

Ws. Entdeckung:

Alice mogelt

3/4 ist auch optimal.

OT

Alice kodiert Bits x,y als: 00: |0i+ ( |0i+|1i)/21/2 norm. 01: |0i­- (-|0i+|1i)/21/2 norm. 10: |1i+ ( |0i+|1i)/21/2 norm. 11: |1i+ (-|0i+|1i)/21/2 norm.

Bob entscheidet zu messen in Standard oder rotierter Basis. Erhält x bzw. y mit Ws. cos2 /8 ¼0.853

Bob kann Wert von beiden Bits nur mit Ws. ·1/2 vorhersagen