Privacy-preserving PKIs with reduced server trust

Motivated by vehicular networking applications, we study a novel type of privacy-preserving public-key infrastructures where the server that distributes public and private keys to clients need not be trusted by clients to protect its secret data against intruders. We target three main requirements for these public-key infrastructures: privacy preservation of the client´s identity (or, anonymity), traceability of malicious messages to clients corrupted by an attacker rather than honest clients (or, traceability) and communication and computation time constant with respect to the number of users (or, efficiency). This combination of properties was not achieved in previously studied areas such as broadcast or multicast encryption, group signatures and ring signatures. This paper designs a public key infrastructure that achieves satisfactory performance on all three requirements, based on key pools and a novel probabilistic key revocation and update strategy. Perhaps surprisingly, we use a careful design of our revocation protocol to achieve a combination of properties for public-key infrastructures that was not previously achieved.