How to Break, Fix, and Optimize "Optimistic Mix for Exit-Polls"

Wikström, Douglas (2002) How to Break, Fix, and Optimize "Optimistic Mix for Exit-Polls". [SICS Report]



First we present two attacks for the mix-net proposed by Golle et al., and also propose modifications that counter our attacks. The first attack breaks the privacy of the protocol completely. Our attacks are adaptations of the "relation attack", discussed by Jakobsson, Pfitzmann, and Wikström, but we introduce a novel way of exploiting intermediate values of different mix-sessions. Then we propose two optimizations of the protocol that reduce the number of exponentiations computed by each mix-server from 4(k+1)N to 4N, where k is the number of mix-servers, and N is the (large) number of senders (we improve the analysis of the original protocol from (5+10k)N to 4(k+1)N). Thus the modified protocol outperforms the original by a factor k+1, with complexity essentially independent of k.

Item Type:SICS Report
Uncontrolled Keywords:mix-net, anonymous channel, electronic voting
ID Code:2273
Deposited By:Vicki Carleson
Deposited On:29 Oct 2007
Last Modified:18 Nov 2009 16:04

Repository Staff Only: item control page