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

作     者：Peng, Kun 

作者机构：Inst Infocomm Res Singapore Singapore 

出 版 物：《INTERNATIONAL JOURNAL OF INFORMATION SECURITY》 (国际信息安全杂志)

年 卷 期：2013年第12卷第4期

页      面：337-345页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Shuffle Pre-computation 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.