Efficient Publicly Verifiable Mix-net for Long Inputs

Abstrakt:

A mix-net is a multi-party protocol that takes a list of cryptotexts and outputs the list of corresponding cleartexts in random order. No individual mix-server knows the secret key of the cryptosystem used or the resulting random permutation. The main application of mix-nets is to implement electronic elections.

We propose here the first efficient publicly verifiable hybrid mix-net. In order to achieve this goal, we have newly developed an IND-ME-CCA secure scheme of multiple encryption using hybrid encryption and a perfect zero-knowledge argument for shuffle-and-decryption of ElGamal ciphertexts. Although the resulting mix-net does not provide full public verifiability of the hybrid decryption in the case when a user and a mixer collude, the best adversary can do is to switch the input between a valid and an invalid one. The resulting scheme is efficient enough to treat large scale electronic questionnaires of long messages as well as voting with write-ins. The scheme is provably secure if we assume random oracles, semantic security of a one-time symmetric-key cryptosystem, and intractability of decision Diffie-Hellman problem.