Identity-based mix: Anonymous communications without public key certificates

A mix is a cryptographic construction for anonymizing communications. Existing mixes require that the public key certificates of mix servers have been distributed among users. In this paper, we propose a new mix that uses techniques from identity-based cryptography. Our mix does not require any public certificates; as long as the users know the identities of mix servers, the mix can anonymize messages. We give proofs of correctness and privacy, as well as analysis of efficiency.