Paillier-Kryptosystem
Das Paillier-Kryptosystem wurde 1999 von Pascal Paillier an der Eurocrypt vorgestellt. Es handelt sich dabei um ein asymmetrisches Kryptosystem, dessen Sicherheit darauf beruht, dass für einen zusammengesetzten Modul  nicht effizient geprüft werden kann, ob ein Element in  eine -te Wurzel modulo  besitzt oder nicht. Eine besondere Eigenschaft des Paillier-Kryptosystems ist, dass zwei verschlüsselte Nachrichten addiert werden können, ohne die Nachrichten vorher zu entschlüsseln.

Das Verfahren wird oft als Nachfolger des Okamoto-Uchiyama-Kryptosystems bezeichnet. Des Weiteren ist es ein Spezialfall des Damgård-Jurik-Kryptosystems.

Verfahren 
Im Folgenden werden die Schlüsselerzeugung und die Algorithmen zur Ver- und Entschlüsselung von Nachrichten beschrieben.

Erzeugung des öffentlichen und privaten Schlüssels 
Das Schlüsselpaar wird folgendermaßen generiert:
 Man generiert zwei zufällige Primzahlen , sodass  gilt. In der Praxis sollte n zumindest 1024, besser jedoch 1536 oder 2048 Binärstellen haben. Man setzt dann  sowie .
 Man wählt  zufällig in , sodass  die Ordnung von  teilt.

Der öffentliche Schlüssel besteht aus , der private Schlüssel aus .

Vereinfachung:
Die Schlüsselerzeugung kann auch folgendermaßen vereinfacht werden:
 Man wählt einen Sicherheitsparameter , und die beiden Primzahlen  zufällig in , also mit gleicher Bitlänge.
 Man definiert , sowie .

Verschlüsseln von Nachrichten 

Um eine Nachricht  zu verschlüsseln, verfährt man wie folgt:
 Zuerst wählt man ein zufälliges .
 Die verschlüsselte Nachricht ist dann gegeben durch .

Entschlüsseln von Nachrichten (Decodierung) 
Zum Entschlüsseln definiert man zuerst die Funktion . Für einen Schlüsseltext  verfährt man dann wie folgt:
 Man setzt , wobei  die logarithmische Funktion von oben ist.
In diesem Schritt ist zu beachten, dass die Division modulo  durchgeführt werden muss, d. h., durch Multiplikation mit dem multiplikativ Inversen. Die Division in der Berechnung der logarithmischen Funktion  wird über den ganzen Zahlen ausgeführt.

Vereinfachung:
Hat man die vereinfachte Variante der Schlüsselgenerierung gewählt, ergibt sich die Entschlüsselung zu:
 Man setzt , wobei die Division wieder modulo  zu verstehen ist.

Sicherheit 
Unter der Decisional Composite Residuosity-Annahme kann gezeigt werden, dass das Verfahren semantisch sicher gegen gewählte-Klartext Angriffe ist. Diese Annahme besagt, dass für einen zusammengesetzten Modul  nicht effizient geprüft werden kann, ob ein Element in  eine -te Wurzel modulo  besitzt oder nicht.

Homomorphieeigenschaften 
Das Paillier-Kryptosystem ist additiv-homomorph, wodurch durch Operationen auf Schlüsseltexte unbekannte Klartexte addiert werden können:

 Durch Multiplikation von zwei Schlüsseltexten  werden die verschlüsselten Klartexte  addiert:
 .
Dabei sind manchmal zwei Sonderfälle von besonderem Interesse:
 Durch Multiplikation eines Schlüsseltextes  mit  kann ein beliebiger Wert  zum verschlüsselten Klartext  addiert werden:
 
 Durch Multiplikation eines Schlüsseltextes  mit , d. h. der Addition des verschlüsselten Wertes "0", kann eine Verschlüsselung von  erneut randomisiert werden, ohne die Nachricht  zu ändern:
 

 Durch Exponentiation eines Schlüsseltexts  mit einer natürlichen Zahl  kann die verschlüsselte Nachricht  ver-w-facht werden
 .

Allerdings gibt es keine bekannte Möglichkeit, mittels Operationen auf zwei Schlüsseltexten die enthaltenen Nachrichten miteinander zu multiplizieren.

Vorteile 
Die homomorphen Eigenschaften werden u. a. im Zusammenhang mit den folgenden Anwendungen ausgenützt.
 E-Voting: Nachdem alle Wahlberechtigten ihre Stimmen (im einfachsten Fall eine 1 für ja, eine 0 für nein) verschlüsselt und an die Wahlbehörde übermittelt haben, werden alle Schlüsseltexte multipliziert; der resultierende Schlüsseltext enthält die Summe der Ja-Stimmen (in verschlüsselter Form). Durch Entschlüsseln erhält man nun das Wahlergebnis. Wichtig ist, dass die den ersten Schritt ausführende Partei keine Kenntnis des geheimen Schlüssels benötigt, wodurch keine einzelnen Stimmen entschlüsselt werden können.
 eCash
 Zero-Knowledge-Beweise im Universal Composability Modell

Nachteile 
Aufgrund der angeführten Homomorphieeigenschaften ist das Verfahren allerdings nicht IND-CCA sicher, d. h. nicht sicher unter gewählten Schlüsseltext-Angriffen. Jedes Verschlüsselungssystem, das diese Sicherheit besitzt, müsste nämlich auch nicht-verformbar sein, eine Eigenschaft, die zur Homomorphie im Widerspruch steht. In der Literatur findet man auch Transformationen, das Paillier-Kryptosystem in eine IND-CCA-sichere Variante zu transformieren. Ob diese Transformationen angebracht sind oder nicht, ist von der jeweiligen Anwendung abhängig.

Vollständiges Beispiel 
Die oben angeführten Schritte sollen hier an einem kleinen Beispiel veranschaulicht werden.

Schlüsselerzeugung 
Zunächst wählen wir den Sicherheitsparameter , und wählen  und . Dies erlaubt uns nun, die vereinfachte Variante der Schlüsselerzeugung zu wählen. Damit erhalten wir:

Der öffentliche Schlüssel ist damit gegeben durch: 

Der geheime Schlüssel lautet .

Vorarbeiten 
In einem ersten Schritt muss der zu verschlüsselnde Text in Zahlen kleiner als  übersetzt werden. Wir ersetzen dazu einfach jeden Buchstaben durch seine Position im Alphabet:
 A=01 B=02 C=03 usw. (00 = Leerzeichen)
Wir verschlüsseln nun je drei Zeichen auf einmal, da vier aufeinanderfolgende Buchstaben unter Umständen einen zu großen Wert liefern könnten.
 Klartext:  P  A  I  L  L  I  E  R
 Kodierung: 16 01 09 12 12 09 05 18 00

Verschlüsselung 
Wir haben drei zu verschlüsselnde Klartexte (,  und ), für die wir jeweils ein  benötigen.
 r1 =  12312
 r2 = 623543
 r3 = 215688
Die Verschlüsselungen  ergeben sich damit zu:
 ci = gmirin mod n2
 c1 = 899778160109 12312899777 mod 809598649729 = 594091908920
 c2 = 508000332395
 c3 = 783129227180

Entschlüsselung 
Da wir zur Schlüsselgenerierung die vereinfachte Variante gewählt hatten, können wir die Nachrichten entschlüsseln durch:
 mi = L(ci mod n2) /  mod n
Wichtig ist hier, dass die Division  ausgeführt wird. Wir berechnen daher mittels des erweiterten Euklidischen Algorithmus das multiplikative Inverse von  modulo  und erhalten damit . Damit ergibt sich die Entschlüsselung zu:
 m1 = L(594091908920897876 mod 809598649729) * 141522 mod 899777 = 160109
 m2 = 121209
 m3 = 051800
Durch Invertierung der Substitutionsvorschrift kann man diese Werte nun wieder in Buchstaben übersetzen.

Referenzen 

Asymmetrisches Verschlüsselungsverfahren