Public-Key Cryptosystems Based on Composite Degree Residuosity Classes

URL: https://link.springer.com/chapter/10.1007/3-540-48910-X_16 Authors: Pascal Paillier

Abstract

This paper investigates a novel computational problem, namely the Composite Residuosity Class Problem, and its applications to public-key cryptography. We propose a new trapdoor mechanism and derive from this technique three encryption schemes: a trapdoor permutation and two homomorphic probabilistic encryption schemes computationally comparable to RSA. Our cryptosystems, based on usual modular arithmetic, are provably secure under appropriate assumptions in the standard model. Of particular interest is the additive homomorphic property: given the encryptions of $m_1$ and $m_2$, one can compute the encryption of $m_1+m_2$ without decryption.