An Ecient Scheme for Proving a Shue

Abstract

In this paper, we propose a novel and ecient protocol for proving the correctness of a shue, without leaking how the shue was performed. Using this protocol, we can prove the correctness of a shue of n data with roughly 18n exponentiations, where as the protocol of Sako-Kilian(SK95) required 642n and that of Abe(Ab99) required 22nlogn. The length of proof will be only 2 11 n bits in our protocol, opposed to 2 18 n bits and 2 14 nlogn bits required by Sako-Kilian and Abe, respectively. The proposed protocol will be a building block of an ecient, universally veriable mix-net, whose application to voting system is prominent.