Abstract: A novel pairing-based optimistic Mix-net scheme was proposed. The key management is made easier by employing bilinear paring primitives and there is no need for the participating mix servers to re-generate keys jointly between mix-sessions to avoid providing decryption oracle service to other mix-sessions. Integrity of messages during mixing is partially guaranteed by using “dummy messages tracing” technology resulting in a simpler construction for proofs of correctness. An optimization method for the joint ElGamal decryption involved in the protocol was also proposed, which can reduce the number of exponentiations computed by each mix server. The Mix-net will shuffle and decrypt input ciphertexts much faster than all previous Mix-nets with public verifiability when all mix servers execute the mixing protocol honestly.