# Private Set Intersection

**Ziel**: Die Schnittmenge von Elementen mehrerer Parteien erfahren, ohne Informationen über die anderen Elemente preiszugeben [2]

[5]
Entity $E_1$ hat einen Datensatz $P_1$ mit den Elementen $a,b,c,d$, während Entity $E_2$ einen Datensatz $P_2$ mit den Elementen $a,c,e,f,g,h$ hat.
$E_1$ stellt nun eine Anfrage an $E_2$ ohne Informationen über $P_1$ preizugeben.
$E_2$ antwortet ohne Informationen über $P_2$ preiszugeben. $E_1$ kann die Antwort von $E_2$ dekodieren und erhält $P_1 \cap P_2={a,c}$

[6]

**PSI für ...**
| kleinere Mengen | große Mengen| asymmetrische Mengen | Berechnung auf der Schnittmenge |
| -------- | -------- | -------- | -------- |
|mit hunderten Elementen | mit millionen Elementen | (100:milliarden) | z.B. Statistiken|
| Schlüsselübereinkommenstechniken (key agreement techniques)| OT -Weiterführung / SPIR Weiterführung | ||
| [HubermanFranklinHogg99] | [PinkasSchneiderZohner14], [KolesnikovKumaresanRosulekTrieu16]| [KalesRechbergerSChneiderSenkerWeinert19], [LiPalAilSulivanChatterjeeRistenpart19] | [PinkasSchneiderTkachenkoYanai] |

### PSI für kleinere Mengen
Frage: Was ist $X\cap Y$?

Alice hat $x_1,x_2,...$ $\qquad\qquad\qquad\qquad\qquad\qquad$ Bob hat $y_1,y_2,...$

$H(x_1)^{a},H(x_2)^{a},... \qquad\qquad\qquad\qquad \longrightarrow$

$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad \longleftarrow \qquad H(y_1)^{b},H(y_2)^{b},...(H(x_1)^{a})^{b},(H(x_2)^{a})^{b},...$

$(H(y_1)^{b})^{a},(H(y_2)^{b})^{a},...$
$(H(x_1)^{a})^{b},(H(x_2)^{a})^{b},...$

Falls $(H(y_1)^{b})^{a} = (H(x_1)^{a})^{b} \Rightarrow y_1=x_1$

**Laufzeit:** für 256 Werte
0.1 Sekunden; 10KB (mit malicious security)
[RosulekTrieu21] [7]

#### Zusätze
* Malicious security via ZK [DeCristofaroKimTsudik10, JareckiLiu09]
* Authenticate items [DeCristofaroKimTsudik10]
* From generic key agreement [RosulekTrieu21] [7]

## Anwendung

**Volles System:**

* PSI kann verwendet werden um (die Strings und Boolean) auf Gleichheit zu überprüfen
* Da wir nur mit kleinen Mengen arbeiten, reicht die Implementierung des PSI mithilfe von Schlüsselübereinkommenstechniken aus
* PSI kann auch für größere Mengen verwendet werden, benötigt allerding eine andere, komplexere Implementation auf Basis von OT oder SPIR (siehe unten)
* In unserem Anwendungsfall wären es möglich die folgenden Daten mithilfe von PSI zu vergleichen:

| Brustschmerzen | Anstrengungsbedingte Angina pectoris/ Brustenge |
| -------- | -------- |
| Enum (String) |boolean |

*Brustschmerzen Kriterien: Brennen, Druckgefühl, Ziehen, Stechen

**Schema - Übersicht**

**Details**
* Die Falldatenbank sendet die Werte des Patienten, $BS$ (Brustschmerzen), $BE \in {0,1}$ (Brustschmerzen) und $AV \in {0,1,2,3,4,5}$, mit Hasfunktion H und Schlüssel a verschlüsselt an die Krankheitendatenbank:
* $H(BS_p)^{a},H(BE_p)^{a}$
* Die Krankheitendatenbank verschlüsselt diese Werte, und alle Werte jeder Krankheit, mit ihrem Schlüssel b und sendet diese and den Arzt
* $(H(BS_p)^{a})^{b},(H(BE_p)^{a})^{b}$
* $H(BS_1)^{b},H(BS_2)^{b},...,H(BS_n)^{b}$
* $H(BE_1)^{b},H(BE_2)^{b},..,H(BE_n)^{b}$
* Die Falldatenbank verschlüsselt die Werte der Krankheiten mit dem Schlüssel a
* $(H(BS_1)^{b})^{a},(H(BS_2)^{b})^{a},...,(H(BS_n)^{b})^{a}$
* $(H(BE_1)^{b})^{a},(H(BE_2)^{b})^{a},...,(H(BE_n)^{b})^{a}$

* In der Falldatenbank werden die Werte dann pro Krankheit verglichen und die Warhscheinlichkeit pro Krankheit bewertet:
* $(H(BS_p)^{a})^{b}==(H(BS_1)^{b})^{a},...,H(BS_p)^{a}==(H(BS_n)^{b})^{a}$
* $(H(BE_p)^{a})^{b}==(H(BE_1)^{b})^{a},...,H(BE_p)^{a}==(H(BE_n)^{b})^{a}$

* Da die Werte der Krankheitendatenbank sich eigentlich nie ändern, kann die Kommunikationskomplexität verringert werden, indem die verschlüsselten Werte der Krankheiten nur bei der ersten Anfrage und bei eventuellen Änderungen verschickt werden. Die Werte können lokal zwischengespeichert und bei neuen Anfragen immer wieder mit den Patientendaten verglichen werden. Nur die Werte der Patienten müssen einmal an die Datenbank geschickt werden, um mit dem Schlüssel b verschlüsselt zu werden
* In der Falldatenbank werden dann die Werte des Patienten dann mit den Werten der Krankheiten verglichen
* Evtl. nur Krankheiten vergleichen, die durch die anderen Werte schon am Wahrscheinlichsten sind. Könne bei vielen Krankheiten effizienter sein

**Anforderungen an die Funktion H:**
* sollte keine Kollisionen erzeugen, ist bei höchstens 11 verscheidenen Werten allerdings sehr unwahrscheinlich
* es muss $(H(x)^{b})^{a} = (H(x)^{a})^{b}$ gelten

**TBD:**
* Verschlüsselte Krankheitendatenbank zwischenspeichern und nicht jedes Mal übertragen?
* Nur bereits wahrscheinlicheren Krankheiten vergleichen?
* Wer bekommt Daten? Wer vergleicht? (Secure Multiparty Computation)
* PSI mit Public, private Key/ symmetrisch?
* Konzept für Datenbanken mit verscheidenen Ärzten (Secure Multiparty COmputation - Public Key)
* PSI für gesamte Datenbank..

## Compact and Malicious Private Set Intersection for Small Sets [7]
* two-party private set intersection basierend auf dem Diffie-Hellman key agreement
* **Semi-honest security**
* Der passive Angreifer folgt dem Protokoll, versucht aber zusätzliche Informationen zu erfahren
* Daher muss das Preisgeben von Informationen verhindert werden
* oder **malicious security**
* Der aktive Angreifer kann von dem Protokoll abweichen
* geringster Zeit und Kommunikationaufwand aller bekannten PSI Protokolle für $n \neq 512$
* PSI basierend auf FHE, RSA, generic MPC sinf um einiges langamer als Protokolle die auf Diffie-Hellman oder Oblivious Transfer basieren
* Im Generellen gilt: OT-PSI ist um einiges schneller als DH-PSI, hat aber eine größeren Kommunikationskosten (Evaluation of Communication vs. Computation costs), allerdings ist das vorgestellte Protokoll für kleinere Sets unter 500-1000 Einträge effektiver
* OT-PSI mit malicious security ist fast genauso performant wie semi-honest security
* Diese Arbeit erreicht das für DH-PSI
* Verbesserung des semi-honest Protokols von Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing privacy and trust in electronic communities. In ACM CONFERENCE ON ELECTRONIC COMMERCE. ACM, 1999.
* Zeigt, wie ein beliebiges Key-Agreement Protokoll in ein PSI Protokoll umgewandelt werden kann
* Geringere Berechnungs und Kommunikationskomplexität als alle anderen Protokolle:

**Funtkionsweise:**
* Nachrichten einen Plain key agreement (KA) Protokoll in ein Polynom einbetten - zur Sicherstellung, dass $x_i$ mit $y_i$ verglichen wird:
* Polynom $P(x_i)$ entspricht der Nächsten Nachricht für den iten Durchlauf
* Oracle Diffie-Hellman (ODH) Vermutung wird für malicious security
* Computational Diffie-Hellman Vermutung für semi-honest security
* Polynomiale Interpolation durch divide-and-conquer Algorithmus mit einer Berechnungskomplexität von $O(nlog²n)$:
* Der Algorithmus findet für zwei Mengen der Größe n, die beide Teilmengen der gleichen Menge sind, ein Polynom $P$ des Grades (n-1), welches für alle $i \in [n]$ $P(x_i)=y_i$ erfüllt
* 2-round key agreement protocol
* 2-round: die zweite Nachricht $m_2$ abhängig von der ersten Nachricht $m_1$ is
* 1-round: beide Nachrichten $m_1, m_2$ können gleichzeitig verschickt werden
* non-malleable
* $g^{b},g^{a},H(g^{ab})$ sind nicht von zufälligen Werten zu unterscheiden
* dies gilt für ODH sowie hashed DHKA

**Implementierung:**
https://github.com/osu-crypto/MiniPSI
* in C++
* DH-Key Agreement mit elliptic curve groups (non malleable)
* SHA2 Hash
*

____________________________________________
## Vorgehensweisen:
* keine Dritte Partei soll Informationen über die Elemente bekommen, daher keine keine trusted third party (TTP) Server oder andere trusted execution environments (TEE) genutzt [2]
* **Server aided PSI** [2] (untrusted third party)
* Privatsphäreerhaltend?
* Der Server erfährt nur die die Anzahl der Elemente der Parteien, sowie die Größe der Schnittmenge
* Sicher?
* Hängt von der Vertrauenswürdigkeit des Serves ab
* Betrug kann durch verschiedene Methoden erkannt werden

### Verschiedene Private Set Intersection Protokolle [1]

| Paper | Parties | Security | Building Blogs |
| -------- | -------- | -------- | -------- |
| [PSZ14] | 2 | Semi-Honest |OT(OPRF) |
| [HEK12] | 2 | Semi-Honest |GC,GMW |
| [CHLR18] | 2 | Hybrid |(leveled-)FHE |
| [RR17] | 2 | Malicious |OT(ORPF) |
| [KMP+17] | n | Semi-Honest |OT(ORPPF) |

* **Private record linkage** [4]
* Privatsphäreerhaltendes teilen von Datensätzen
* 2 Parties, Semi-Honest
* **PSI durch SPIR** [5]
* 2 Parties
* PSI kann als ein multi-message symmetric private information retrieval (MM-SPIR) mit zusätzlichen Einschränkungen aufgefasst werden
* eine alternative für single-message SPIR (SM-SPIR) von Sun-Jafar
* dazu müssen die Datensätze als Inzidenz-Vektoren vorliegen:
* Umwandlung von PSI zu MM-SPIR Problem durch Inzidenz-Vektoren:

## Quellen:

[1] https://crypto.sjtu.edu.cn/~hongrui/SpOT-Slides/PSI_Survey_Slides.pdf, stand: 13.11.2022

[2] https://decentralizedthoughts.github.io/2020-03-29-private-set-intersection-a-soft-introduction/, stand 13.11.2022

[3] Brickell, Porter, Shmatikov, Witchel. Privacy-Preserving Remote Diagnostics. University of Texas, 2007.

[4] He, Machanavajjhala, Flynn, Srivastava. Composing Differential Privacy and Secure Computation: A case study on scaling private record linkage. September 2017.

[5] Wang, Banawan, Ulukus. Private Set Intersection: A Multi-Message Symmetric Private Information Retrieval Perspective. IEEE 2021

[6] https://csrc.nist.gov/presentations/2021/a-brief-overview-of-private-set-intersection, stand:13.11.2022

[7] Rosulek, Trieu. Compact and Malicious Private Set Intersection for Small Sets. 2021