Abstract: A new method for achieving revocable anonymity in re-encryption mix networks is presented. Each sender is required to append his identity information encrypted under the public key of an anonymity revocation authority to every ciphertext submitted by him. Then ciphertexts from different senders, as well as their encrypted identities, are re-encrypted and shuffled together by the mix net. The adjusted secret shuffle proof protocol can guarantee the bindings of these two types of ciphertexts in the mixing process. In the output phase, a quorum of mix servers jointly decrypts every normal ciphertext and generates a threshold signature to keep the correspondence between every output message and its sender’s re-encrypted identify. When tracing a vicious message, the anonymity revocation authority just needs to decrypt its corresponding encrypted identifies. Compared with the previous work, our method needs only 1 additional ElGamal pair and involves less exponential computation and communication.

Key words: anonymous communication, Mix Net, revocable anonymity, proof of secret shuffle