Direct Anonymous Attestation with Efficient Verifier-Local Revocation for Subscription System

Vireshwar Kumar, He Li, Noah Luther, Pranav Asokan, Jung-Min "Jerry" Park, Kaigui Bian, Martin B. H. Weiss, Taieb Znati

TL;DR

This paper introduces LASER, a novel cryptographic scheme for anonymous subscription systems that significantly improves the efficiency of user revocation. By shifting computational costs from online signature generation to an offline credential acquisition phase, LASER drastically reduces the burden on users, making anonymous subscriptions more practical for large-scale deployments.

What Problem Does This Paper Address?

In online subscription services, users often want to access content anonymously without revealing their identity to service providers (SPs). Direct Anonymous Attestation (DAA) is a cryptographic protocol that enables privacy-preserving authentication of a user's platform. However, existing DAA schemes suffer from a critical drawback: the computational and communication costs for users increase linearly with the number of revoked users. This makes them impractical for systems with large user bases and frequent revocations, hindering widespread adoption.

Methods

LASER proposes a new approach to DAA that addresses the revocation scalability issue. The core innovation lies in shifting the computational and communication burden associated with revocation checks from the online signature generation phase to an offline credential acquisition phase. This is achieved by:

  • Multiple Credentials: Users acquire multiple "login credentials" during an offline phase.
  • Adaptable Unlinkability: LASER introduces a novel concept of "adaptable unlinkability," allowing users to choose between absolute unlinkability (where signatures are unlinkable by both issuer and verifier) and conditional unlinkability (where signatures are unlinkable by the verifier but potentially linkable by the issuer). This flexibility allows for a trade-off between privacy and efficiency.
  • Leveraging TPMs: The scheme is designed to work with Trusted Platform Modules (TPMs), a hardware security component found in many computers, specifically adhering to the TPM 2.0 specification.

Datasets

Not discussed in the paper. The paper focuses on theoretical design and analytical evaluation, with an implementation on a laptop platform.

Key Insights and Ideas

  • Revocation is the Bottleneck: The paper clearly identifies that the efficiency of revocation is the primary performance bottleneck in existing DAA schemes for subscription systems.
  • Offline vs. Online Trade-off: By strategically moving computation from the online (user-facing, latency-sensitive) phase to the offline (less time-critical) phase, LASER achieves significant performance gains for users.
  • Adaptable Unlinkability: The introduction of adaptable unlinkability is a key conceptual contribution. It recognizes that absolute anonymity isn't always necessary and allows for a more practical balance between privacy and system efficiency.
  • Practical TPM Integration: The paper emphasizes the importance of implementing DAA schemes on actual TPM hardware, highlighting the challenges and benefits of working with real-world security modules.

Key Results

  • Reduced Online Costs: LASER achieves computational and communication costs for online operations that are orders of magnitude lower than prior art, especially as the revocation list grows. Specifically, online computational costs are O(1) in LASER, compared to O(mr) in CDL-EPID (where mr is the number of revoked platforms).
  • Scalability: The scheme is designed to be scalable for large subscription systems with potentially long revocation lists.
  • Implementation on TPM 2.0: The paper presents the first implementation and analysis of an anonymous authentication scheme using an actual TPM 2.0 compliant cryptoprocessor.
  • Performance Trade-off: While online costs are significantly reduced, offline costs are higher in LASER compared to CDL-EPID. This trade-off is deemed advantageous because online operations are more frequent and latency-sensitive.

Limitations and Future Work

  • Offline Cost: The offline computational costs in LASER-A and LASER-B are significantly higher than in CDL-EPID.
  • TPM Security Vulnerability: The implementation uses the TPM2_Sign algorithm, which can be vulnerable to a Diffie-Hellman oracle attack, reducing the effective security to 85 bits. The authors note that LASER's construction aims for 128 bits of security, but this implementation detail limits it.
  • Backward Linkability: After revocation of a login credential, previous signatures associated with that credential can be linked by the verifier. The authors suggest that this can be mitigated using time-stamped parameters or accumulators, but this is beyond the scope of the current paper.
  • Future Work: The authors suggest that the concept of adaptable unlinkability could pave the way for designing more practical and scalable DAA schemes. Further research into mitigating the TPM2_Sign vulnerability and exploring countermeasures for backward linkability would be valuable.

Summary updated

BibTeX
@article{kumar2018direct,
  author = {Vireshwar Kumar and He Li and Noah Luther and Pranav Asokan and Jung-Min "Jerry" Park and Kaigui Bian and Martin B. H. Weiss and Taieb Znati},
  title = {{Direct Anonymous Attestation with Efficient Verifier-Local Revocation for Subscription System}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2018},
}
Figure