Multi-device anonymous authentication

Recently, a few pragmatic and privacy protecting systems for authentication in multiple systems have been designed. The most prominent examples include Pseudonymous Signatures for German personal identity cards and Anonymous Attestation. The main properties are that a user can authenticate himself with a single private key (stored on a smart card), but nevertheless the user’s IDs in different systems are unlinkable. We develop a solution which enables a user to achieve the above-mentioned goals while using more than one personal device, each holding a single secret key, but different for each device. Our solution is privacy preserving: it will remain hidden for the service system which device is used. Nevertheless, if a device gets stolen, lost or compromised, the user can revoke it (leaving his other devices intact). In particular, in this way we create a strong authentication framework for cloud users, where the cloud does not learn indirectly personal data. Our solution is based on a novel cryptographic primitive, called Pseudonymous Public Key Group Signature.