Transcript
Fakult¨ at f¨ ur Informatik Professur Theoretische Informatik und Informationssicherheit
Sommersemester 2007
Prof. Dr. Hanno Lefmann
Datensicherheit und Kryptographie II ¨ 11. Ubung
Aufgabe 1 Wir betrachten den K¨orper der Polynome vom Grad maximal 7 u ¨ber 8 4 3 Z2 modulo m(x) = x + x + x + 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 Linearit¨at q(a(x) + b(x)) = q(a(x)) + q(b(x)) vom letz¨ ten Ubungsblatt 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 f¨ ur Mengen X, Y , die in Polynomialzeit berechenbar ist, und die folgenden Eigenschaften aufweist: 1. Es ist nicht in Polynomialzeit m¨oglich, f¨ ur 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 m¨ochte 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 k¨onnen, dass der offengelegte Wert der tats¨achliche 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 f¨ ur 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 enth¨alt. Das Problem ist NP-hart. Es sei ein Graph G fest, und Bob m¨ochte Alice u ¨berzeugen, dass er einen Hamiltonkreis C in G kennt, wobei G ¨offentlich ist. Betrachten Sie folgendes Interaktive Beweissystem mit Zero-Knowledge-Eigenschaft: 1. Bob w¨ahlt eine zuf¨allige 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 zuf¨allig 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 geh¨oren, sowie den Kreis C 0 angibt. 4. Alice akzeptiert, wenn Bob ihrer Aufforderung korrekt nachgekommen ist. Im ersten Fall bedeutet dies, dass sie u uft, ob H 0 wirklich die Codierung ¨berpr¨ eines Graphen H ist und ob π(G) = H ist. Im zweiten Fall bedeutet dies, dass sie u uft, ob der angegebene Kreis C 0 tats¨achlich ein Hamiltonkreis auf ¨berpr¨ 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 Verf¨ ugung hat. 3. Zeigen Sie, dass Alice aus den erhaltenen Informationen keine Informationen u ¨ber den Hamiltonkreis in G erh¨alt.
