Abstract: An efficient hybrid-encryption-based Mix-net is presented that is much faster than all previous Mix-nets with public verifiability when all mix-servers execute the mixing protocol honestly (the usual case). The improvement by taking an “optimistic” and hash-based approach to verify the correctness of mixing is achieved without requiring complex and costly zero-knowledge proofs. Only two element-wise testing processes with low-cost computations of hash functions are involved to make certain messages are not manipulated by a cheating server. An efficient integration of public-key and symmetric-key operations also speeds up the mixing. As a result, the computational task of each mix-server is almost inde-pendent of the number of mix-servers except for some negligible tasks. Anyone can verify the correctness of a result rapidly by computing a few exponentiations. The scheme is robust, too. Those characteristics make it very suitable for large scale electronic voting.