A shuffle to achieve high efficiency through pre-computation and batch verification

Shuffle is an important anonymous routing protocol, in which a shuffling node (router) re-encrypts and reorders some encrypted messages. It is usually used to build anonymous communication networks. A new shuffle scheme is proposed in this paper. A shuffling node’s costly operations can be carried out offline in advance so that its online efficiency is very high. Moreover, any verifier can employ batch verification to efficiently verify validity of the shuffle. As in practical applications of shuffles like e-voting, there are many verifiers including some entities with weak computation capability, and offline pre-computation is a feasible solution for a shuffling node; our proposal is an effective efficiency optimisation mechanism. So our new shuffle design has an advantage in practical efficiency over the existing shuffle schemes. Moreover, its achievement of desired security properties is formally proved only on the base of the most basic computational assumption inevitable in any shuffle. Application of our new shuffle to e-voting is described in the end of this paper to show its importance and applicability in practice.