Paper 2000/008

Efficient Protocols based on Probabilistic Encryption using Composite Degree Residue Classes

Ivan Damgård and Mads Jurik

Abstract

We study various applications and variants of Paillier's probabilistic encryption scheme. First, we propose a threshold variant of the scheme, and also zero-knowledge protocols for proving that a given ciphertext encodes a given plaintext, and for verifying multiplication of encrypted values. 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. Finally, we propose a variant of the encryption scheme, that allows reducing the expansion factor of Paillier's scheme from 2 to almost 1.

Metadata
Available format(s)
PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Probabilistic EncryptionElectronic Voting
Contact author(s)
ivan @ daimi au dk
History
2000-03-23: received
Short URL
https://ia.cr/2000/008
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2000/008,
      author = {Ivan Damgård and Mads Jurik},
      title = {Efficient Protocols based on Probabilistic Encryption using Composite Degree Residue Classes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2000/008},
      year = {2000},
      url = {https://eprint.iacr.org/2000/008}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.