Pass-As-You-Go: Widespread Deployment of Direct Anonymous Attestation

Direct Anonymous Attestation (DAA) is an anonymous signature scheme which has been standardized by the Trusted Computing Group and ISO/IEC. DAA schemes were originally designed to allow an external party to anonymously attest that a platform (PC or mobile phone) embeds a Trusted Platform Module (TPM). The authentication step requires the TPM to compute anonymous signatures using its DAA signing key. Due to the limited computational capabilities of TPMs, part of the computation is delegated to the more powerful (and potentially compromised) host  embedding the TPM, thus introducing a number of privacy concerns.
We introduce a new DAA scheme (also known as a pre-DAA scheme), where all computations required to either verify the validity of a DAA signing key or to generate a DAA can be carried out solely by the TPM. Our scheme is in particular suitable for resource constrained devices such as SIM cards as it requires no heavy computations on the TPM’s side. In addition, the most efficient DAA schemes to date base their security on interactive assumptions (namely the LRSW assumption), which raises concerns in the cryptographic community. This led to the developpement of alternative DAA schemes based on the q—SDH assumption (schemes that compromise on the efficiency, but that are proven secure under a non-interactive assumption). We achieve the best of both worlds by providing a pre-DAA scheme based on the q—SDH assumption, in addition to being more efficient than current constructions based on both LRSW and q—SDH.
We then illustrate the relevance of our scheme in the context of anonymous transit passes for public transport systems. Our Pass-As-You-Go protocol, based on the pre-DAA construction, allows commuters to anonymously validate their passes, while remaining untraceable.