Fingerprinting Techniques

Christoph Bürger

Seite 2

Gliederung

1. Einführung

2. Matrix-Multiplikation

3. Identität von Polynomen

4. Perfekte Matchings in Graphen

5. Gleichheit von Strings

6. Pattern Matching

7. Zusammenfassung und Ausblick

1. Einführung Seite 3

Einführung

• komplexe Probleme z.T. durch gute, aber komplizierte Algorithmen gelöst

• Korrektheit dieser Algorithmen ist nicht einfach zu verifizieren

• Programmverifikation, etc. sehr schwierig

• Alternative: Überprüfung des Ergebnisses eines Algorithmus auf Korrektheit.

1. Einführung Seite 4

Einführung

• Ergebnis eines Programms aus einem sehr großen Universum U

• Problem besteht im Vergleich zweier Elemente x und y aus U

• Gleichheit ist in log(|U|) überprüfbar

• Verbesserung: Mapping vom Universum U in deutlich kleineres Universum V und Vergleich der Bilder von x und y

• in Zeit log(|V|) möglich• hohe Wahrscheinlichkeit dafür, dass

• die Bilder von x und y heißen Fingerprints von x bzw. y

)()( yBildxBildyx =⇔=

2. Matrix-Multiplikation Seite 5

Matrix-Multiplikation

Gegeben: -Matrizen A, B, CBehauptung: AB=C

naiver Algorithmus läuft in Zeit bester (bekannter) Algorithmus läuft in Zeit

einfachste Testmöglichkeit: mit naivem Algorithmus nachrechnenProblem: Verbesserung durch schnelleren Algorithmus würde verloren gehen

Vorstellung eines randomisierten -Zeit Algorithmus mit begrenzter Fehlerwahrscheinlichkeit

nn×

)( 3nO)( 376,2nO

)( 2nO

2. Matrix-Multiplikation Seite 6

Matrix-Multiplikation(Freivalds Technik)

Verfahren:Geg.: -Matrizen A, B, C

1. Wähle Zufallsvektor 2. berechne 3. berechne4. berechne 5. wenn y=z, dann Ausgabe „korrekt“, sonst Ausgabe „falsch“

nn×

nr }1,0{∈Brx =

ABrAxy ==Crz =

2. Matrix-Multiplikation Seite 7

Matrix-Multiplikation

Klar: Wenn AB=C, dann auch y=z

Theorem: Seien A, B, C -Matrizen, mit . Dann gilt für ein gleichverteilt zufällig gewähltes ,

k-fache Iteration des Tests verringert Fehlerwahrscheinlichkeit auf Wert

nn× CAB ≠nr }1,0{∈

21)Pr( ≤= CrABr

k21≤

3. Identität von Polynomen Seite 8

Produkte von Polynomen

• Geg.: • Beh.:

•

• Multiplikation ist in Zeit möglich

• Auswertung eines Polynoms in einem Punkt n in Zeit möglich• Verfahren:

wähle wähle zufällig falls : Ausgabe „korrekt“, ansonsten Ausgabe „falsch“

][)(),(),( 321 xFxPxPxP ∈)()()( 321 xPxPxP =×

nxPGradnxPGradxPGrad 2))(()))(()),((max( 321 ≤⇒≤

)log( nnO

)(nO

12, +≥⊆ nSFSSr∈

)()()( 321 rPrPrP =

3. Identität von Polynomen Seite 9

Produkte von Polynomen

• setze•• wenn , dann ist mit hoher Wahrscheinlichkeit• hat höchstens 2n Wurzeln • 2n verschiedene Wahlen von können verursachen

• passende Wahl von S bzw. Iterationen des Algorithmus führen zu kleinen Fehlerwahrscheinlichkeiten• det. Variante möglich, indem alle einmal ausprobiert werden• aber benötigt 2n+1 Berechnungen Gesamtlaufzeit• Multiplikation der symbolischen Polynome wäre einfacher

)()()()( 321 xPxPxPxQ −=nxQGrad 2))(( ≤

0)( ≠xQ 0)( ≠rQQ

Sr∈ 0)( =rQ

SnFehler 2)Pr( =⇒

Sr∈⇒ )log( 2 nnΘ

3. Identität von Polynomen Seite 10

Identität von Polynomen

• vorgestelltes Verfahren auch geeignet, um Polynome zu vergleichen• Vergleich explizit gegebener Polynome in O(n) möglich• ?• Verfahren vorteilhaft, wenn Polynome nur implizit gegeben

Bsp.: Determinante einer symbolischen Matrix als Identität multivariater Polynome lösbar

Vandermonde-Matrix M

Technik: wähle zufällige Werte für jedes und teste Q=0

0)()()( 21 =−= xPxPxQ

∏<

−=ij

ji xxM )()det(

∏<

−−=ij

jin xxMxxQ )()det(),,( 1 K

ix

3. Identität von Polynomen Seite 11

Schwartz-Zippel Theorem

• Formalisierung als Erweiterung von Freivalds Technik auf multivariate Polynome• der Grad eines Terms eines multivar. Polynoms ist die Summe der Exponenten der Variablen des Terms• Grad des Polynoms: Maximum der Grade der TermeTheorem (Schwartz-Zippel):

Sei ein multivariates Polynom mit absolutem Grad d. Sei und unabhängig, zufällig aus S gewählt. Dann gilt:

• Potentielles Problem: in der Berechnung sehr große Werte als Ergebnisse der Polynome• Lösung: Berechnungen modulo einer „kleinen“ Primzahl p

),,( 1 nxxQ K

],,[),,( 11 nn xxFxxQ KK ∈FS ⊆ nrr ,,1 K

SdxxQrrQ nn ≤≠= ]0),,(|0),,(Pr[ 11 KK

4. Perfekte Matchings in Graphen Seite 12

Perfekte Matchings in Graphen

• Geg.: bipartiter Graph G(U,V,E) mit unabhängigen Knotenmengen und

• Ein Matching ist eine Sammlung von Kanten so dass jeder Knoten höchstens einmal in M vorkommt• Ein perfektes Matching ist ein Matching der Größe n• Jedes perfekte Matching kann als Permutation von U in V gesehen werden

•Die perfekten Matchings in G können in eine 1-zu-1 Korrespondenz mit den Permuationen in gesetzt werden, wobei das Matching, das zu einer Permutation korrespondiert durch die Paare gegeben ist

EM ⊆},,{ 1 nuuU K= },,{ 1 nvvV K=

nSnS∈π ),( )(ii vu π

4. Perfekte Matchings in Graphen Seite 13

Perfekte Matchings in Graphen(Edmonds Theorem)

Theorem (Edmonds Theorem):Sei A die wie folgt aus G entstehende -Matrix:

Sei Dann hat G ein perfektes Matchings gdw.

Entsprechend Abschnitt 3 lässt sich nun ein einfaches Verfahren zum Test der Existenz eines perfekten Matchings konstruieren

• Laufzeit des Algorithmus von der Berechnung der Determinante dominiert• Da gute Algorithmen zu Matching-Berechnung existieren bringt Verfahren kaum Vorteile

⎩⎨⎧

∉∈

=EvuEvux

Aji

jiijij ),(0

),(

nn×

)det(),,,( 1211 AxxxQ nn =K

0≠Q

5. Gleichheit von Strings Seite 14

Gleichheit von Strings

• Alice & Bob besitzen Kopien derselben Daten(bank)• periodischer Abgleich notwendig, aber Kommunikation sehr teuer

• Alices Daten: Bitsequenz • Bobs Daten: Bitsequenz• deterministischer Konsistenz-Check mit weniger als n Bits wird scheitern

• Fingerprint-Verfahren:interpretiere Daten als n-Bit Integer a und b

Fingerprint-Funktion: für Primzahl pAnnahme:Anzahl der zu übertragenden Bits:

),,( 1 naa K),,( 1 nbb K

∑=

−=n

i

iiaa

1

12 ∑=

−=n

i

iibb

1

12

pxxFp mod)( =)()( bFaFba pp ≠⇒≠

)(log pO

5. Gleichheit von Strings Seite 15

Gleichheit von Strings

• Strategie ist für festes p leicht zu überlisten• Lösung: wähle p zufällig

• für jedes k sei die Anzahl der Primzahlen kleiner k

•• Verfahren versagt nur, wenn und „p teilt c“•

• Lemma: Die Anzahl der Primteiler einer beliebigen Zahl ist höchstens n

•Wähle Schwelle

kkk

ln)( ≈π

bac −=0≠c

n2<

( )Nn log=>τ

nN 2= Nc ≤

5. Gleichheit von Strings Seite 16

Gleichheit von Strings

•höchstens n Primzahlen kleiner können Teiler von c sein

• wähle um Fingerprint-Funktion zu definieren

• Anzahl der Kommunikationsbits:

• wähle für großes t

• Theorem:

• Fehlerwahrscheinlichkeit

• zu übertragende Bits:

τ

τ<p

)(logτO

tntn log=τ

⎟⎠⎞

⎜⎝⎛=≤≠=t

OnbabFaF pp1

)(]|)()(Pr[

τπ

⎟⎠⎞

⎜⎝⎛t

O 1

)log(log ntO +

6. Pattern Matching Seite 17

Pattern Matching

text := pattern :=o.B.d.A.

pattern kommt in text von, wenn ein j ex. mit so dass für ,

triviale Lösung inguter deterministischer Algorithmus in

Definiere sub-stringMatch liegt vor, wenn j ex. mit

kleinstes j, das Bedingung erfüllt, führt zu Eindeutigkeit der Lösung

nxxX K1=

myyY K1=über festem Alphabet Σ, nm ≤

}1,0{=Σ

}1,,2,1{ +−∈ mnj Kmi ≤≤1 iij yx =−+ 1

)(nmO)( mnO +

11)( −++= mjjj xxxjX K

)( jXY =

6. Pattern Matching Seite 18

Pattern Matching

• Brute-Force Verfahren: vergleiche Y mit jedem X(j)• Randomisiertes Verfahren: wähle Fingerprint F(Y) und vergleiche ihn mit jedem F(X(j))Fehler: F(Y)=F(X(j)) und wähle F so, dass Fehlerwahrscheinlichkeit klein ist

Wahl von F: für jeden String , interpretiere Z als m-bit Integer

interpretiere Y und X(j) als Integer und vergleiche und

Fehlerwahrscheinlichkeit für eine der max. n Werte von j ist

)( jXY ≠

mZ }1,0{∈pZZFp mod)( =⇒

)(YFp ))(( jXFp

⎟⎠⎞

⎜⎝⎛=≤≠=

ττ

τπlog

)()](|))(()(Pr[ mOmjXYjXFYF pp

⎟⎠⎞

⎜⎝⎛

ττlognmO

6. Pattern Matching Seite 19

Pattern Matching

• wähle

• Monte Carlo Algorithmus: vergleiche Fingerprints aller X(j) mit dem von Y und gebe erstes j aus, für das Match eintritt

• Theorem: Der Monte Carlo Algorithmus hat eine Laufzeit von und eine Fehlerwahrscheinlichkeit von

• Las Vegas Algorithmus:wenn Match zwischen den Fingerprints von Y und X(j) vorliegt, vergleiche Y und X(j) in Zeit O(m). Wenn dabei false-match auftritt, Algorithmus abbrechen und brute-force Methode anwenden

• Algorithmus ist fehlerfrei mit erwarteter Laufzeit

⎟⎠⎞

⎜⎝⎛=⇒=

nOmnmn 1match] falsePr[log 22τ

)( mnO +

⎟⎠⎞

⎜⎝⎛

nO 1

)( mnO +

7. Zusammenfassung und Ausblick Seite 20

Fingerprinting Techniken

• Im wesentlichen 2 verschiedene Techniken

• Geg.: Strings bzw. Vektoren

• Alphabet kodierbar mit Zahlenmenge

• Polynome:

• Ziel:

),,( und ),,( 11 nn bbbaaa KK ==

endlich ,, ΣΣ∈ii baΣ∈−=Γ kk mit }1,,1,0{ K

∑ ∑−

=

−

=

≤==1

0

1

0n Grad undten Koeffizien-Integermit )( ,)(

n

i

n

i

ii

ii zbzBzazA

)()( zBzAba =⇔=

7. Zusammenfassung und Ausblick Seite 21

Fingerprinting Techniken I

• Wähle feste Primzahl

•

• Fingerprint: wähle zufälliges und berechne

•

•

Feld fixieren und zufälligen Berechnungspunkt wählen

kpnp >> und 2

pp ZzZzBzA ⊆Γ∈ ,][)( ),(

pZr∈ )( ),( rBrA

)()()()( rBrAzBzAba =⇒=⇒=

p gewähltesfür 21]|)()(Pr[ ≤≤≠=

pnbarBrA

7. Zusammenfassung und Ausblick Seite 22

Fingerprinting Techniken II

• Wähle festes z=2

• Wähle zufällige Primzahl q genügend klein

• Fingerprints: berechne A(2) und B(2) über

Evaluierungspunkt fixieren und zufällig Feld wählen

qZ

7. Zusammenfassung und Ausblick Seite 23

Fingerprinting Techniken III

• Annahme: k=2

• Fixiere Primzahl

• wähle zufälliges Polynom P(z) über

• Fingerprints: bestimme P(a), P(b) über

• dann Reduktion modulo einer Zahl nahe

np 2>

pZ

pZ

functions)hash (universal log n

7. Zusammenfassung und Ausblick Seite 24

Zusammenfassung

• Vorstellung von Fingerprinting-Techniken fürMatrix-Multiplikation

Identitäten von Polynomen

Perfekte Matchings in Graphen

Gleichheit von Strings

Pattern Matching