Extensions to the Paillier Cryptosystem with Applications to
Mads J. Jurik
The main contribution of this thesis is a simplification, a generalization and some modifications of the homomorphic cryptosystem proposed by Paillier in 1999, and several cryptological protocols that follow from these changes.
The Paillier cryptosystem is an additive homomorphic cryptosystem, meaning that one can combine ciphertexts into a new ciphertext that is the encryption of the sum of the messages of the original ciphertexts. The cryptosystem uses arithmetic over the group and the cryptosystem can encrypt messages from the group . In this thesis the cryptosystem is generalized to work over the group for any integer with plaintexts from the group . This has the advantage that the ciphertext is only a factor of longer than the plaintext, which is an improvement to the factor of 2 in the Paillier cryptosystem. The generalized cryptosystem is also simplified in some ways, which results in a threshold decryption that is conceptually simpler than other proposals. Another cryptosystem is also proposed that is length-flexible, i.e. given a fixed public key, the sender can choose the when the message is encrypted and use the message space of . This new system is modified using some El Gamal elements to create a cryptosystem that is both length-flexible and has an efficient threshold decryption. This new system has the added feature, that with a globally setup RSA modulus , provers can efficiently prove various relations on plaintexts inside ciphertexts made using different public keys. Using these cryptosystems several multi-party protocols are proposed: