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 ${\displaystyle n}$ nicht effizient geprüft werden kann, ob ein Element in ${\displaystyle (\mathbb {Z} /n^{2}\mathbb {Z} )}$ eine ${\displaystyle n}$-te Wurzel modulo ${\displaystyle n^{2}}$ 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.