A Length-Flexible Threshold Cryptosystem with Applications
Ivan B. Damgård
March 2003 |

## Abstract:
We propose a public-key cryptosystem which is derived from the
Paillier cryptosystem. The scheme inherits the attractive homomorphic
properties of Paillier encryption. In addition, we achieve two new
properties: First, all users can use the same modulus when generating key
pairs, this allows more efficient proofs of relations between different
encryptions. Second, we can construct a threshold decryption protocol for our
scheme that is length flexible, i.e., it can handle efficiently messages of
arbitrary length, even though the public key and the secret key shares held
by decryption servers are of fixed size. We show how to apply this
cryptosystem to build:
1) a self-tallying election scheme with perfect ballot secrecy. This is a small voting system where the result can be computed from the submitted votes without the need for decryption servers. The votes are kept secret unless the cryptosystem can be broken, regardless of the number of cheating parties. This is in contrast to other known schemes that usually require a number of decryption servers, the majority of which must be honest. 2) a length-flexible mix-net which is universally verifiable, where the size of keys and ciphertexts do not depend on the number of mix servers, and is robust against a corrupt minority. Mix-nets can provide anonymity by shuffling messages to provide a random permutation of input ciphertexts to the output plaintexts such that no one knows which plaintexts relate to which ciphertexts. The mix-net inherits several nice properties from the underlying cryptosystem, thus making it useful for a setting with small messages or high computational power, low-band width and that anyone can verify that the mix have been done correctly
Available as |

Last modified: 2003-06-11 by webmaster.