A Generalisation, a Simplification and some Applications of Paillier's
Probabilistic Public-Key System
Ivan B. Damgård
December 2000 |
Abstract:
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 loosing 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 Available as PostScript, PDF, DVI. |