A verifiable secret shuffle and its application to e-voting

We present a mathematical construct which provides a cryptographic protocol to verifiably shue,a sequence of k modular integers, and discuss its application to secure, universally verifiable, multi-authority election schemes. The output of the shue,operation is another sequence of k modular integers, each of which is the same secret power of a corresponding input element, but the order of elements in the output is kept secret. Though it is a trivial matter for the “shuer”,(who chooses the permutation of the elements to be applied) to compute the output from the input, the construction is important because it provides a linear size proof of correctness for the output sequence (i.e. a proof that it is of the form claimed) that can be checked by an arbitrary verifiers. The complexity of the protocol improves on that of Furukawa-Sako[16] both measured by number,of exponentiations and by overall size. The protocol is shown to be honest-verifier zeroknowledge in a special case, and is computational zeroknowledge in general. On the way to the final result, we also construct a generalization of the well known,Chaum-Pedersen protocol for knowledge of discrete logarithm equality ([10], [7]). In fact, the generalization specializes exactly to the ChaumPedersen protocol in the case k = 2. This result may,be of interest on its own. An application to electronic voting is given that matches the features of the best current protocols with significant eciency,improvements. An alternative application to electronic voting is also given that introduces an entirely new