# Paillier

## Alter Ablauf
Unser Protokoll beginnt mit dem Arzt, dieser betrachtet alle Variablen $v_x \in V$ ($x\in \mathbb{Z}_n$) des Patienten und bringt diese auf einheitliche Werte $v_x' \in V'$, sodass gilt:
$\forall v_x' \in V' :v_x'\in [0:100]$. Näheres zu dem Umformen der Werte in Kapitel 5.3.\\
Diese angepassten Werte verschlüsselt der Arzt mit dem öffentlichem Schlüssel des Verarbeitungsservers zu $cV'$ und schickt sie daraufhin an die Krankheitsdatenbank. \\
Die Krankheitsdatenbank formt nach gleichem Schema wie der Arzt die Variablen
$k_{y,x} \in K_y$ ($y\in \mathbb{Z}_m$) der $y$-ten Krankheit um, sodass diese wieder einheitliche Werten
$k_{y,x}' \in K_y'$ entsprechen, für welche gilt: $\forall k_{y,x}' \in K' :k_{y,x}'\in [0:100]$.\\
Folglich fertigt die Krankheitsdatenbank eine temporäre Kopie von $cV'$ an und subtrahiert von jedem Wert der verschlüsselten Patientenakte $cV'$ den entsprechenden Wert der zu vergleichenden Krankheit $y$, sodass: $cv_x' - k_{y,x} = ca_{y,x} \in [-100:100]$. Wobei $ca_{y,x}$ der verschlüsselten Differenz der $x$-ten Variable der Patientenakte und der Krankheit $y$ entspricht.\\
Diese verschlüsselten Werte sagen über die Abweichung verglichener Variablen aus, das heißt desto weiter der Wert $ca_{y,x}$ von $0$ entfernt ist, desto größer ist der Unterschied zwischen den $x$-ten Variablen der verglichenen Akten, desto weniger stimmen die den Variablen zu Grunde liegenden Symptome überein.\\
Nachdem alle $ca_{y,x} \in cA_{y}$ berechnet wurden, wird für jeden dieser Werte eine Zufallszahl $r_{y,x}$ generiert und auf diesen aufaddiert, womit sich $ca_{y,x} + r_{y,x} = car_{y,x} \in cAR_y$ ergibt. Dies wird getan da im nächsten Schritt $cAR_y$ an den Verarbeitungsserver weitergeleitet wird, welcher nicht in der Lage sein soll Informationen über die korrekten Werte von $cA_y$ zu erhalten, obwohl er sich im Besitz des privaten Schlüssels befindet.\\
Nachdem der Verarbeitungsserver die Daten empfangen hat, kann er sie mit dem privatem Schlüssel entschlüsseln und erhält somit $AR_y$. Für jedes $ar_{y,x} \in AR_y$ berechnet der Verarbeitungsserver $ar_{y,x}^2$ und verschlüsselt diese quadrierten Werte danach wieder mit dem öffentlichem Schlüssel zu $cAR_y^2$. Durch das quadrieren der Werte stellen wir sicher das sich keiner der Werte mehr im negativen Bereich befindet, was dabei hilft die Abweichungen zwischen Patientenakte und den Krankheiten zu ermitteln, da wir jetzt nur noch positive Abweichungen von Variablen betrachten müssen. \\
Der Verarbeitungsserver leitet diese neu berechneten Werte anschließend wieder zurück zur Krankheitsdatenbank mit wessen Hilfe die Werte nun wieder unabhängig von den Zufallsgenerierten Zahlen dargestellt werden sollen. Dafür berechnet die Datenbank den Term: $(2ca_{y,x}r_x+r^2)$ für jedes $x \in \mathbb{Z}_n$ und subtrahiert diesen von $car_{y,x}^2$. Damit ergibt sich: \[car_{y,x}^2-(2ca_{y,x}r_x+r^2)=(ca_{y,x}^2+2ca_{y,x}r_x+r^2)-(2ca_{y,x}r_x+r^2)=ca_{y,x}^2 \in cA_y^2\]
Durch diese Rechnung isolieren wir den quadrierten Abweichungswert der Variablen von den vorhin aufaddierten Zufallszahlen.
Nachdem wir alle $n$ Elemente von $cA_y^2$ mit dem obigen Rechenweg berechnet haben, summiert die Krankheitsdatenbank diese neu berechneten Werte auf, was den gesamt Abweichungswert $\alpha$ der $y$-ten Krankheit beschreibt:
\[ \sum_1^n ca_{y,x} = c\alpha_y\]
Dieser Abweichungswert wird dann an den Verarbeitungsserver gesendet, wo dieser dann das $c\alpha_y$ zu $\alpha_y$ mit dem privaten Schlüssel entschlüsseln kann. Ist dies getan vergleicht er den entschlüsselten Abweichungswert mit einem Wert $\beta$ für welchen gilt:
\[\beta= \begin{cases}
\alpha_y & \text{für } \beta = NULL \\
\alpha_y & \text{für } \beta > \alpha_y \\
\beta & \text{für } \beta \leq \alpha_y
\end{cases}\]
Nachdem alle diese Schritte für jede der $m$ Krankheiten durchgeführt wurden, enthält $\beta$ den kleinsten Abweichungswert aller Krankheiten. \\
Dieser wird zusammen mit der Zahl der Krankheit $i$ um dessen Abweichungswert es sich handelt an den Arzt übermittelt. Da es sich um die geringst abweichende Krankheit handelt kann er Arzt dann mit Hilfe von Oblivious Transfer den $i$-ten Eintrag der Krankheitsdatenbank abfragen und erhält so Informationen über die best übereinstimmende Krankheit wie dessen Name und Richtwerte der verglichenen Variablen. Dadurch sieht der Arzt welche Symptome einstimmig sind, sowie welche nicht und kann den betroffenen Patienten entsprechend beraten oder behandeln.

## Alte Sicherheit des Protokolls
\section{Sicherheit des Protokolls}
In diesem Kapitel gehen wir auf die Sicherheit des Paillier basierten Protokolls ein und betrachten, wo diese gut abgesichert ist und wo sich potenzielle Schwachstellen befinden. Dafür betrachten wir, inwiefern die Schutzziele von unserem Protokoll erfüllt werden.
\begin{itemize}
\item \textbf{Vertaulichkeit:} Das Schutzziel der Vertraulichkeit ist in unserem Protokoll erfüllt, vorausgesetzt das nicht die Krankheitsdatenbank und der Hilfsserver beide böswillige Instanzen sind und untereinander kommunizieren. Dies ist der einzige Fall in welchem der Hilfssserver an die verschlüsselten Werte gelangen könnte, ohne das auf diesen eine Zufallszahl addiert ist und so die Werte der Patientenakte mit seinem privaten Schlüssel auslesen könnte.
Da wir uns allerdings in dem semi-honest Vertrauensmodell befinden, kann dieser Fall nur eintreten, wenn sowohl die Krankheitsdatenbank und der Hilfsserver von der gleichen böswilligen Entität kompromittiert wurden. Bei dem dazu benötigten Aufwand ist es je nach vorliegenden Schutzmaßnahmen einfacher die Daten des Arztes direkt zu kompromittieren, weshalb dieser Fall mit genügenden Schutzmaßnahmen als zu vernachlässigen gilt. \\
Ein realistischeres Szenario was die Vertraulichkeit vereinzelter Werte gefährden kann, entsteht wenn der Hilfsserver über den minimal und maximal Wert des Zufallsgenerators der Krankheitsdatenbank Bescheid weiß. Ist dies der Fall, kann passieren, dass ein von dem Verarbeitungsserver entschlüsselter Wert größer als das Maximum oder analog kleiner als das Minimum des Zufallsgenerators ist. Wenn dies eintritt, weiß der Verarbeitungsserver mit Sicherheit, dass der zugehörige Wert ohne die addierte Zufallszahl ungleich $0$ ist, was bedeutet dass die verglichenen Werte nicht übereinstimmen. Dies kann besonders im Falle eines verglichenen $boolean$ einen großen Unterschied ausmachen, da dies aussagt, dass das Symptom des Patienten mit dem entsprechenden Richtwert nicht übereinstimmt. Dies verletzt direkt die Vertraulichkeit, da der Verarbeitungsserver sensible Informationen interpretieren kann. Allerdings kann man diesem Fall entgegenwirken, indem man die Vorzeichen der Werte zufällig ändert, sodass das der Hilfsserver nicht weiß ob die Krankheit oder der Patient einen $true$ Wert hatte und umgekehrt. Zusätzlich gilt, dass je größer die minimal und maximal Werte des Zufallsgenerators gewählt werden, desto kleiner die Wahrscheinlichkeit für das Eintreten dieses Problems ist.

\item \textbf{Integrität:} Das Schutzziel der Integrität ist in unserem Protokoll gefährdet. Es können zwar nur der Arzt, die Krankheitsdatenbank und der Hilfsserver die Werte verändern, allerdings reicht es für eine böswillige Entität nur eine der drei Instanzen zu kompromittieren. Ist dies der Fall kann sie Berechnungen auf den Werten ausführen um falsche Ergebnisse zu produzieren und weiterzuleiten, was die Integrität der Werte verletzen würde.

\item \textbf{Authentizität:} Das Schutzziel der Authentizität ist in unserem Protokoll nicht erfüllt. Um dies zu erfüllen müssten wir die Kommunikation unter den Instanzen erweitern, sodass sie die Identität ihres Kommunikationspartners verifizieren können, mit etwa einer digitalen Signatur. Man könnte unser Protokoll um eine solche Funktionalität erweitern, wir hielten dies allerdings als Rahmen sprengend und nicht zu relevant im direkten Bezug auf unserem Anwendungsfall.
\end{itemize}