# Private Information Retrieval & Oblivious Transfer

### Private Information Retrieval
[14]
**Ziel**: Schuzt der Privatsphäre des Klienten

Ermöglicht dem Klienten ein Element aus einer Datenbank abzurufen, ohne dass der Datenbankbesitzer erfährt, welches Element der Klient ausgewählt hat.

Eine naive Implementation von PIR ist das Kopieren der gesammten Datenbank. Dies erfordert jedoch einen großen Kommunikationsaufwand und es enstehen viele Replikas der selben Datenbank. Diese Implementation ist die einzige single-database PIR Implementation mit information-theoretic privacy. [3]

Alle PIR Protokolle haben den Anspruch einen geringeren Kommunikationsaufwand als diese triviale Implementation zu haben: $o(n)$ [13]
Diese Protokolle werden als nicht-triviale PIR bezeichnet.

### Symmetrical Private Information Retrieval
Eingeführt in [12]
[14]
**Ziel**: Schuzt der Privatsphäre des Klienten und der Datenbank

Private Information Retrieval mit der zusätzlichen Anforderung, dass der Klient nur von dem Element erfahren darf, welches er ausgewählt hat.

Daher ähnlich zu $\binom{n}{1}$-OT, wobei SPIR jedoch der zusätzlichen Anforderung $o(n)$ genügen muss. Daher SPIR auch als als kommunikationseffizienter $\binom{n}{1}$-OT bezeichnet werden [15]

Jedes PIR Protokoll kann in ein SPIR umgewandelt werden, ohne die Anzahl an Datenbanke zu erhöhen. [10][7]

### Computationally Private Information Retrieval
**Ziel:** Schutz gegen polynomiell begrentzten Sender [2]

### Lösunganstätze von PIR Problem
$\qquad$**single-database:** keine Datenbank Replikas (Computational privacy)
$\qquad$$\qquad$ 1997 durch Kushilevitz, Ostrovsky [5]
$\qquad$$\qquad$ Diese Arten von PIR können lediglich Computational privacy erreichen
$\qquad$$\qquad$ Alle nicht-trivialen single-database PIR können Kommunikationseffizient zu einem $\binom{n}{1}$-OT Protokoll umgewandelt werden. [15]

$\qquad$**multi-database:** Datenbank Replikas auf k-Servern (Information-theoretic privacy)
$\qquad$$\qquad$ 1995 durch Chor, Goldreich, Kushilevitz, Sudan [1] (fortsetzung)
$\qquad\qquad$**One-round schemes:** Alle Server werden gleichzeitig abgefragt
$\qquad\qquad$**Multi-round schemes:**

**Allgemeine Eigenschaften von multi-database Schemata** [1]
Datenbank wird als binärer String $x=x_1...x_n$ mit der Länge $n$ gesehen.
Identische Kopien dieses Strings sind auf $k\geq2$ Servern gespeichert, die nicht kooperieren.
Der Klient hat ein Index $i$ und möchte $x_i$ erfahren.
Dazu fragt der Klient alle Server ab und berechnet $x_i$ aus deren Antworten. Die Server-Anfragen sind dabei unabhängig von $i$, sodass keiner der Server auf $i$ schließen kann.

**Two-Server PIR Schema**
Der Klient möchte den Eintrag $x_i$ erfahren.
Dazu wählt er $j, l$ sodass $j+l=i mod n$ und sendet $j$ zu dem 1. und $l$ zu dem 2. Server.
Alle drei führen das Protokol von Pudlàk and Rödl [1993] aus

**Beispiele von PIR**
* two-database (one-round) Schema mit Kommunikationsaufwand $O(n^{\frac{1}{3}})$ [1]
* two-database cPIR mit Kommunikationsaufwand $O(n^\epsilon)$ mit $\epsilon > 0$ wobei $n$ der Länge des Daten-String enstpricht [6]
* single-database cPIR mit Kommunikationsaufwand $O(n^\epsilon)$ mit $\epsilon > 0$ wobei $n$ der Länge des Daten-String enstpricht [5]
* two-round cPIR mit polylogarithmischem Kommunikationsaufwand in n wobei $n$ der Länge des Daten-String enstpricht [3]

**Beispiele von SPIR**
* two-database SPIR implementation [3] mit [12]
* **Oblivious Transfer with Adaptive Queries [7] (Implementation von cSPIR in Java siehe [2])**

* Implementation als effizienter und anpassungsfähiger k-out-of-n-Oblivious-Transfer (in [7] weiterentwickelung aus [8]) oder kommunikationseffizienter cSPIR (in [2])
* k hat dabei keine Auswirkung auf die Komplexität
* anpassungsfähig: man muss nicht zu Beginn k Elemente auswählen, die dann gleichzeitig übertragen werden, sondern kann bis zu k Elemente nacheinander auswählen
* 2 Phasen:
* **Initialisierungsphase**: Sender berechnet "Commitment" zu jedem der n Elemente und sendet diese an den Klienten
* **Übertragungsphase**: Übertragung eines Elements $x_i$ zum Input $i$ des Klienten. In dieser Phase werden mehrere 1-out-of-m-OT durchgeführt, wobei m entweder konstant ist oder $\sqrt{n}$ entspricht, die dem Klienten die nötigen Schlüssel geben, um das "Commitment" zu $x_i$ zu öffnen.
* "On a more practical level, we believe that it is preferable to use the computation efficient OT(...) protocols rather than the communication efficient PIR protocols."
* Vorgestellte Protokolle:
* **Protocols Based on the Decisional Diffie-Hellman Assumption**
* einfacher als die allgemeine Konstruktion
* Commit-Schlüssel ist die Ausgabe einer DDH-basierten Pseudo-Zufallsfunktion
* **Protocols Based on Any Sum Consistent Synthesizer**
* Implementation und leichte Modifikation dieses Protokols in [2]
* Anstelle einer einzigen Initialisierungs-Phase am Anfang, welche das Senden aller Commitments in $\Omega(n)$ beinhaltet, werden hier pro Runde alle Commitments berechnet und der Klient erhält nur das entsprechende Commitment. Dies erhöht die lokale Berechnungskomplexität auf $O(n)$, ist jedoch insegsammt effizienter.
* commit Funktion: symmetric cryptosystem AES ($committ_{K_{ij}}(x_{ij} = AES - ENC_{K_{ij}}$)
* sum-consistent synthesizer: hash function sha156 ($S(A,B)=sha256(A + B$)

**Cryptographic Commitment**
[17]
* stellt sicher, das Werte auf richtige Weise ausgewählt werden
* Vertraulichkeit: der Empfänger erfärt nichts über das Geheimnis g oder die zufällige Zahl z aus dem commit(g, z) erfährt
* Verbindlichkeit: der Sender kann das secret im Nachhinein nicht mehr verändern

* Implementierungen:
* Hash-based commitment
* ElGamal commitment
* Pederson commitment

* in [7]:
* Stellt sicher, dass der Sender die Elemente zwischen den $k$ Übertragungen nicht verändert
* Commit Phase: abbilden von einem zufälligen Schlüssel $k$ und einem Geheimnis $x$ auf einen String $commit_k(x)$
* Reveal Phase: presigabe des Schlüssels $k$ damit $x$ berechent werden kann

**Decisional Diffie-Hellman Assumption**
[7]
* viele kryptografische Protokolle haben die DDH-assumption als grundliegenden Sicherheitsannahmen
* kein effizienter Algorithmus kann brechnete von zufälligen Werten in zyklischen Gruppen unterscheiden
* **zyklische Gruppen**: Gruppen, die von einem Element erzeugt werden [18]

**Sum Consistent Synthesizer**
[7]
* ist ein Pseudo-random Synthesizer (eingeführt in [18])
* effiziente Funktion S mit $l$ Variablen $x_1,...,x_l$ mit der Eigenschaft: "bei polynomiell vielen gleichmäßig verteilten Zuweisungen zu jeder seiner Eingangsvariablen ist die Ausgabe von S für alle Kombinationen dieser Eingaben pseudozufällig."
* mit der zusätzlichen Eigenschaft:
* Wenn für $x_1,...,x_l$ und $y_1,...,y_l$ $\qquad \sum_{1}^{l}x_i = \sum_{1}^{l}y_i \qquad$ dann gilt $S(x_1,...,x_l)=S(y_1,...,y_l)$

### Private Information Storage
[4]
Zeigt, dass privatspäreerhaltende lese-schreib-Schemata genauso Kommunikationseffizient implementierbar sind wie read-only Schemata.

**Privatsphäreerhaltende lese-schreib-Schemata:**
$\qquad$**single-database:**
* Verschlüsselung der eingefügten Daten
* Um jedoch auch den Ort, wo die Daten eingefügt wurden, geheimzuhalten, muss die gesamte Datenbank pro lese-schreib-Zugriff entschlüsselt und wieder verschlüsselt werden.
* hohe Kommunikationskomplexität
* der Nutzer muss einen Private Key verwalten
* nur Computational Security

$\qquad$**multi-database:**
* der Nutzer muss keine Informationen verwalten
* Information-theoretic security

## Oblivious Transfer Protokolle
Ermöglichen die Übertragung einer Teilmenge von Informationen vom Sender zu Empfänger, bei welcher der Sender nicht erfährt, welche Informationen der Empfänger erhält, und der Empfänger keine weiteren Informationen außer der Angeforderten bekommt. [13]

### $\frac{1}{2}$-OT
Michael O. Rabin
Die erste Form von Oblivious Transfer, 1981

Ziel: Simulation von zufälligem Informationsverlust durch Rauschen

Eine Information wird dabei zu einer Wahrscheinlichkeit von 50% korrekt übermittelt. Der Sender weiß somit nicht, ob der Empfänger die korrekte Information erhalten hat, oder nicht.

### $\binom{2}{1}$-OT
Even, Goldreich, Lempel

Der Sender kennt 2 Geheimnisse ($g_0,g_1$). Der Empfänger sucht sich ein $i \in {0,1}$ aus und erhält das entsprechende Geheimnis ($g_i$). Der Sender weiß somit nicht, welches der beiden Geheimnisse der Empfänger bekommen hat.

### $\binom{n}{1}$-OT
Brassard, Crepau, Lempel

Der Sender kennt n Geheimnisse ($g_0,...,g_n$). Der Empfänger sucht sich ein $i \leq n$ aus und erhält das entsprechende Geheimnis ($g_i$). Der Sender weiß somit nicht, welches der n Geheimnisse der Empfänger bekommen hat.

### $\binom{n}{k}$-OT
Naor, Pinkas [8]

Der Sender kennt n Geheimnisse ($g_0,...,g_n$). Der Empfänger kann nun bis zu k-mal hintereinander ein Geheimniss erfahren ohne dass der Sender weiß, welche k Geheimnisse der Empfänger ehalten hat.

$\binom{n}{k}$-OT ist ein SPIR Protokoll [2]

### Adaptiver $\binom{n}{k}$-OT
Naor, Pinkas [7][9]

Der Sender kennt n Geheimnisse ($g_0,...,g_n$). Der Empfänger entscheidet sich zu Beginn, welche k Elemente er bekommen möchte.

(Quelle: „https://www.ctfnote.com/crypto/research/oblivious-transfer-ot“, „https://www.cs.jhu.edu/~susan/600.641/scribes/lecture13.pdf“, stand: 22.10.2022)

## Oblivious Sampling
[11]
**"Private Sampling-based Query Framework"**

Entwurf von effiziente und sichere Algorithmen für zwei bekannte Sampling techniques: "sampling without replacement" und "poisson" sodass kein Muster oder die Indizes identifiziert werden können.

Rahmenbedingungen für sichere Datenabfragen gegen zwei **Angreiferszenarien**:
1. Der Eigentümer der Infrastruktur auf die die Datenbank läuft
2. Datenwissenschaftler, die auf den Daten arbeiten wollen

**Warum Sampling?**
* Effizient - Berechnungen auf Stichproben ist günstiger als auf gesamten Datensatz
* Apprximation großer Datensätze
* Privatspähreerhaltend

## Quellen Paper
[1] Chor, Goldreich, Kushilevitz, Sudan. Private Information Retrieval. Journal of the ACM (JACM), Band 45, Ausgabe 6, 1998.

[2] Saint-Jean. A Java Implementation of a Single-Database Computationally Symmetric Private Information Retrieval (cSPIR) protocol. Yale University, 2005.

[3] Cahcin, Micali, Stadler. Computationally Private Information Retrieval With Polylogarithmic Communication. 1999.

[4] Ostrovsky, Shoup. Private Information Storage. In 38. FOCS, S. 294-303, 1997.

[5] Kushilevitz, Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval. Proc. 38. Symp. on Foundations of Computer Science, 1997: 364-373

[6] Chor, Gilboa. Computationally Private Information Retrieval. Proc. 29. ACM symp. on Theory of Computing, 1997:304-313

[7] Naor, Pinkas, “Oblivious Transfer with Adaptive Queries,” Advances in
Cryptology-Crypto’99, Lecture Notes In Computer Science; Vol. 1666 , 1999: 573 -
590

[8] Naor, Pinkas, “Oblivious Transfer and Polynomial Evaluation,” Proc. 31st ACM Symp. on Theory of Computing, 1999: 245 - 254

[9] Naor, Pinkas, “Efficient Oblivious Transfer Protocols,” Proc. 12th ACM-SIAM Symp. on Discrete Algorithms, 2001: 448 - 457

[10] Lipmaa. An oblivious transfer protocol with log-squared total communication.

[11] Sasy, Ohrimenko. Oblivious Sampling Algorithms for Private Data Analysis. 33rd Conference on Neural Information Processing Systems, 2019

[12] Gertner, Ishai, E. Kushilevitz, and T. Malkin, Protecting data privacy in private information retrieval schemes, Proc. 30th Annual ACM Symposium on Theory of Computing (STOC), 1998

[13] „https://www.cs.princeton.edu/courses/archive/fall07/cos433/lec19.pdf“, stand: 22.10.2022

[14] „https://crypto.stanford.edu/pir-library/“, stand: 22.10.2022

[15] Crescenzo, Malkin, Ostrovsky. Single Database Private Information Retrieval Implies Oblivious Transfer. Massachusetts Institute of Technology

[16] Kolesnikov, Kumaresan†, Rosulek, Trieu. Efficient Batched Oblivious PRF with Applications to Private Set Intersection. 2016

[17] "https://kyle-crypto.medium.com/cryptographic-commitments-55ccc4f297c9", stand: 06.11.2022

[18] "https://link.springer.com/chapter/10.1007/978-3-662-61952-0_5", stand: 06.11.2022

[19] Naor, Reingold. “Synthesizers and their application to the parallel construction of pseudo-random function,”. Proc. 36th IEEE Symp. on Foundations of Computer Science, 1995:170-181