# Privacy preserving pattern matching

## Why privacy preserving pattern matching?
- Most of the web traffic is encrypted.
- Standard encryption protcols do not allow processing.
- Therefore its hard to do quality checks on data
- Parental control
- Encrypted flow can be used to hide malware

## What is privacy preserving pattern matching?
Privacy preserving pattern matching erlaubt das vergleichen von Mustern in verschlüsselten Daten, wobei die gesuchten Muster und die durchsuchten Daten geschützt bleiben, mit Ausnahme des Pattern-Providers, welcher einsicht in die genutzten Muster hat.

Mit pattern matching nach Bkakria, A. et al [1], gilt das nichts über die Muster bekannt sein soll außer ihrer Länge (nur für Pattern-Provider) und diese Muster nur nützlich sein sollen um den Datenverkehr zum Empfänger zu analysieren und nicht vom Empfänger.
Zusätzlich soll nichts über den Datenverkehr freigegeben werden, mit Ausnahme der Information ob Muster auf diesem entdeckt wurden.

## Which solution works best?
Es gibt eine sehr große Anzahl an möglichen Wegen um privacy preserving pattern matching zu ermöglichen, die Lösung nach Bkakria, A. et al [1], teilt ein minimum an Daten, während es in den meisten Situationen noch im mer anwendbar ist und eine konservative menge an Rechenkraft im vergleich zu Alternativen benötigt.

Alle Bilder aus Video von Asiacrypt 2020 [2]:

## How does it work? [1]

##### Modell
Der Datenverkehr wird in Segmente fester Länge aufgeteilt, welche danach seperat verschlüsselt werden, so benötigt man nur Schlüssel und Trapdoors, welche in ihrer Größe gleich zu der Größe eines Data fragments sind. Zusätlich nimmt man von den Zwischenpunkten der Segmente nach rechts und links einen Teil der größe l, wobei l die größe des größten Musters ist nach dem gesucht werden kann und erschafft weitere Segmente, sodass auch Segment übergreifende Muster erkennt werden können.


##### Scalar generation

##### Key Generation
Wird vom Empfänger ausgeführt, welcher große Skalarwerte auswählt, im Falle eines bitstrings zwei. Diese Skalar werte, bilden den Geheimschlüssel.
Randomisierung von Kt (Schlüssel zur generirung der Trapdoor) wird verwendet um zu verhindern das Pattern Provider Informationen über Datenverkehr gewinnt.

##### Traffic Encryption
Für jedes Segment wird ein zufälliger großer Skalarwert generiert, welche die verschlüsselung des Segments randomisiert.
Danach wird jedes Symbol in den Daten seperat verschlüsselt, wobei die Symbole die zwei Fragementen angehörig sind, zweifach verschlüsselt werden.

##### Trapdoor Generation (By Pattern provider)
$\sigma$ entspricht des Wertes des Bits
$i$ ist der offset des Bits im durchsuchten Pattern-Fragments
$j$ ist der offset des Pattern-Fragments im Data-Fragment
$v$ ist ein zufälliger Skalar.

Das hinzufügen zur Trapdoor, erlaubt das suchen nach dem Patter an der $i$-Stelle im Data-Fragment
##### Pattern Matching

Wenn die Gleichungen übereinstimmen, ist dem Service provider bewusst, das ein Pattern gefunden wurde, an gegebenem offset.
Allerdings sehen beide Seiten der Gleichung zufällig aus, sodass der Service Provider keine Informationen über das Pattern oder den Plaintext erhalten kann.

##### Results
- Detection correctness
- Keine falsch negativen, vernachlässige Anzahl an falsch positiven
- Traffic indistinguishability
- Für Service und Pattern provider
- Pattern indistinguishability
- Brute force kann nicht verhindert werden.

##### Datei Größen


Noch immer sehr langsam.
- 128-mal größer als Plaintext
- 4* schneller als nächst effiziente vergleichbare Lösung
- Noch nicht für real-time Benutzung nutzbar

[1] Bkakria, A., Cuppens, N., Cuppens, F. (2020). Privacy-Preserving Pattern Matching on Encrypted Data. In: Moriai, S., Wang, H. (eds) Advances in Cryptology – ASIACRYPT 2020. ASIACRYPT 2020. Lecture Notes in Computer Science(), vol 12492. Springer, Cham. https://doi.org/10.1007/978-3-030-64834-3_7

[2] https://youtube.com/watch?v=6Iw_AtrY1A4&feature=share&si=EMSIkaIECMiOmarE6JChQQ