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.
Keywords mix - anonymity - distributed system
Partially supported by Polish Ministry of Science and Higher Education, grant N N206 1842 33.