Übung 11 - TU Chemnitz

Fakultät für Informatik
Professur Theoretische Informatik
und Informationssicherheit
Sommersemester 2007
Prof. Dr. Hanno Lefmann
Datensicherheit und Kryptographie II
11. Übung
Aufgabe 1 Wir betrachten den Körper der Polynome vom Grad maximal 7 über
Z2 modulo m(x) = x8 + x4 + x3 + x + 1. Zeigen Sie, dass das Quadrieren eines
Polynoms modulo m(x) eine injektive Abbildung q ist (und damit umkehrbar ist).
Hinweis: Verwenden Sie die Linearität q(a(x) + b(x)) = q(a(x)) + q(b(x)) vom letzten Übungsblatt und zerlegen Sie das zu quadrierende Polynom in seine einzelnen
Komponenten, d. h. Teilpolynome. Berechnen Sie die Koeffizienten des Quadrats.
Aufgabe 2 Angenommen, wir haben eine Funktion f : {0, 1} × X → Y für
Mengen X, Y , die in Polynomialzeit berechenbar ist, und die folgenden Eigenschaften
aufweist:
1. Es ist nicht in Polynomialzeit möglich, für b ∈ {0, 1} und x ∈ X aus dem Wert
f (b, x) zu bestimmen, welchen Wert b hat.
2. Die Funktion f ist injektiv.
Betrachten Sie folgendes Szenario (ein Bit-Commitment-Schema): Bob möchte ein
Bit effizient so codieren, dass er die Codierung Alice schicken kann, ohne dass Alice
daraus effizient berechnen kann, welchen Wert das codierte Bit hat. Andererseits soll
Bob sich festgelegt haben, d.h. auf Anfrage muss er offenlegen, welchen Wert das
codierte Bit hatte, und Alice soll effizient verifizieren können, dass der offengelegte
Wert der tatsächliche Wert des Bits war.
Wie kann man dieses Szenario mit der Funktion f von oben als Protokoll formulieren,
so dass die geforderten Eigenschaften gelten? Zeigen Sie, dass Ihr Protokoll die
geforderten Eigenschaften hat.
Aufgabe 3 Betrachten Sie folgendes Protokoll für das Problem Hamilton Cycle, das
darin besteht, zu einem gegebenen ungerichteten Graphen G einen Hamiltonkreis
zu finden, d.h. einen Kreis, der jeden Knoten aus V genau ein mal enthält. Das
Problem ist NP-hart. Es sei ein Graph G fest, und Bob möchte Alice überzeugen,
dass er einen Hamiltonkreis C in G kennt, wobei G öffentlich ist. Betrachten Sie
folgendes Interaktive Beweissystem mit Zero-Knowledge-Eigenschaft:
1. Bob wählt eine zufällige Permutation π der Knoten des Graphen und berechnet
H = π(G). Aus dem Hamiltonkreis C und der Permutation π berechnet er
den Hamiltonkreis C 0 = π(C) in H. Dann berechnet er mittels eines BitCommitment-Schemas wie in Aufgabe 2 eine Codierung H 0 von H, und schickt
H 0 an Alice.
2. Alice verlangt zufällig von Bob, entweder zu beweisen dass H 0 die Codierung
einer isomorphen Kopie von G ist, oder einen Hamiltonkreis in H 0 zu zeigen.
3. Bob kommt der Aufforderung nach, indem er entweder die komplette Codierung H 0 von H sowie die Permutation π offenlegt, oder nur die Kanten in der
Codierung H 0 offenlegt, die zum Hamiltonkreis C 0 gehören, sowie den Kreis
C 0 angibt.
4. Alice akzeptiert, wenn Bob ihrer Aufforderung korrekt nachgekommen ist. Im
ersten Fall bedeutet dies, dass sie überprüft, ob H 0 wirklich die Codierung
eines Graphen H ist und ob π(G) = H ist. Im zweiten Fall bedeutet dies, dass
sie überprüft, ob der angegebene Kreis C 0 tatsächlich ein Hamiltonkreis auf
den offengelegten Kanten in H bildet.
Zeigen Sie, dass Folgendes gilt:
1. Wenn Bob wirklich einen Hamiltonkreis in G kennt, kann er Alice immer
überzeugen, und das Protokoll arbeitet in Polynomialzeit.
2. Falls Bob keinen Hamiltonkreis in G kennt, wird Alice mit Wahrscheinlichkeit
mindestens 1/2 dies feststellen, wenn Bob nur Polynomialzeit zur Verfügung
hat.
3. Zeigen Sie, dass Alice aus den erhaltenen Informationen keine Informationen
über den Hamiltonkreis in G erhält.

Download Report