A reductionist proof for sender anonymity of an asymmetric bilinear pairing based mixnet (BILMIX) is presented. We give an experiment-based definition for anonymity and show that BILMIX possesses anonymity in the semi-honest model against static adversaries assuming that the co-Bilinear Diffie-Hellman Problem, the Matching Find-Guess Problem and the Matching Diffie-Hellman Problem are hard. A new problem called Divisible Decisional Factorized Diffie-Hellman Problem (DDF- DHP) is introduced and showed that finding connection between data stored by the Registration Authority and the receiver is at least as hard as breaking DDF-DHP, with the assumption that secret keys of the Registration Authority and the special bulletin board are kept secret.

mixnet, anonymity, asymmetric bilinear pairings, co-Bilinear Diffie-Hellman Problem, Matching Find-Guess Problem, Matching Diffie-Hellman Problem, Divisible Decisional Factorized Diffie-Hellman Problem