A Generalisation, a Simplification and some Applications of Paillier’s Probabilistic Public-Key System

By Ivan Bjerre Damgård, Mads Jurik. 2000

395 citations recorded by the source corpus.

We propose a generalisation of Paillier's probabilistic public key system, in which the expansion factor is reduced and which allows to adjust the block length of the scheme even after the public key has been fixed, without losing the homomorphic property. We show that the generalisation is as secure as Paillier's original system. We construct a threshold variant of the generalised scheme as well as zero-knowledge protocols to show that a given ciphertext encrypts one of a set of given plaintexts, and protocols to verify multiplicative relations on plaintexts. We then show how these building blocks can be used for applying the scheme to efficient electronic voting. This reduces dramatically the work needed to compute the final result of an election, compared to the previously best known schemes. We show how the basic scheme for a yes/no vote can be easily adapted to casting a vote for up to t out of L candidates. The same basic building blocks can also be adapted to provide receipt-free elections, under appropriate physical assumptions. The scheme for 1 out of L elections can be optimised such that for a certain range of parameter values, a ballot has size only O(log L) bits.

Subfields: Artificial Intelligence, Sociology and Political Science, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Sociology and Political Science

In Privacy & Security

Citations in the corpus

IBM Federated Learning: an Enterprise Framework White Paper V0.1 (2020, methodology): “Techniques such as local diﬀerential privacy [8], multi-party computation (SMC) [13, 33] and hybrid approaches have been proposed for this purpose [31].”
A Review of Homomorphic Encryption Libraries for Secure Computation (2018, background): “Partially Homomorphic Encryption (PHE) schemes such as [9,10,11,12,13,14,15,16,17,18,19] allow only one type of operation any number of times - either addition or multiplication on encrypted data as compared to Somewhat Homomorphic schemes that support both.”
A Comprehensive Comparison of Multiparty Secure Additions with Differential Privacy (2015, background): “Details of key generation, encryption and decryption algorithms can be found in [18], [33].”
A Survey on Homomorphic Encryption Schemes (2017, methodology): “Likewise, Damgard-Jurik (DJ) [Damgård and Jurik 2001] introduced another PHE scheme as a generalization of Paillier.”
Multiparty Computation Goes Live (2008, background): “A lot of research has gone into solving the efficiency problem, both for general protocols [11, 17, 9] and for special types of computations such as voting [4, 12].”
Secure Multiparty Computation Goes Live (2009, background): “A lot of research has gone into solving the efficiency problems, both for general protocols [11, 17, 9] and for special types of computations such as voting [4, 12].”
Performance Comparison of Secure Comparison Protocols (2009, background): “SMC protocols have widespread applications [4], [5] in various real-life problems, such as matchmaking, electronic voting, private bidding and auctions, etc.”
A Fast Single Server Private Information Retrieval Protocol with Low Communication Cost (2014, neutral): “Lipmaa uses the Damg˚ard-Jurik scheme [27].”
L1 - An Intermediate Language for Mixed-Protocol Secure Computation (2011, background): “It currently supports general SC protocols [34], [5], [11] and HE [12], [28], but it is also easily extensible to other protocols and encryption schemes.”
Optimal Rate Private Information Retrieval from Homomorphic Encryption (2015, methodology): “The Damgård-Jurik cryptosystem [11] allows to encrypt plaintexts for arbitrary ‘ ≥ 1, so that the ciphertext length is not more than ‘ + 2 k .”
Elliptic Curve Paillier Schemes (2001, background): “This scheme has found many applications in cryptography (such as [4]).”
Privacy-Preserving Face Recognition (2009, neutral): “Also let g = n + 1 [10].”