Distributed Verification of Mixing -  Local Forking  Proofs Model

        Jacek Cichon,  Marek Klonowski, Miroslaw Kutylowski
 		Wroclaw University of Technology


One of generic techniques to achieve anonymity  is to process messages through a batch 
of cryptographic mixes. In order to  guarantee proper execution verifiable mixes are 
constructed:  each mix provides a proof of correctness together with its output. 
However, if a mix is working on a huge number of messages at a time,  the proof itself
is huge since it concerns processing all messages. So in practice only a few verifiers
would download the proofs and in turn we would have to trust what they are saying.  

We consider a different model in which there are many verifiers, but each of them 
is going to download only a limited number of bits in order to check the mixes. Distributed 
character of the process ensures effectiveness even if many verifiers are 
dishonest and do not report irregularities found. 

We concern a fully distributed and intuitive verification scheme  which we call  
local forking proofs. For each intermediate  ciphertext a verifier may ask for a proof 
that its re-encrypted version is in the output of the mix concerned. 
The proof shows that the re-encrypted version is within some subset of k ciphertexts
from the output of the mix, and it can be performed with strong zero-knowledge or 
algebraic methods. They  should work efficiently concerning communication complexity, 
if  k is a relatively small constant. 

There are many issues concerning stochastic properties of local forking proofs. 
In this paper we examine just one: we estimate quite precisely 
how many mixes are required so that if a local proof  is provided for each message, then 
a plaintext hidden in an input message can appear on any position of the final output set.

  paper accepted for Australasian Conference on Information Security and Privacy (ACISP 2008)