Device-Bound Anonymous Credentials With(out) Trusted Hardware

Anonymous Credentials enable privacy-preserving authentication. To ensure non-transferability of credentials among corrupt users, they can additionally be device-bound. Therein, a credential is tied to a key protected by a secure element (SE), usually a hardware component, and any presentation of the credential requires a fresh contribution of the SE. Despite being a fundamental concern of user credentials, device binding for Anonymous Credentials is relatively unstudied. Existing constructions either require multiple calls to the SE, or need the SE to keep state -violating the design principles of resource-limited SEs. Further, constructions that are compatible with the most mature credential scheme BBS rely on the honesty of the SE for privacy, which is hard to vet given that SEs are black-box components. In this work, we thoroughly study Device-Bound Anonymous Credentials (DBACs). We model DBACs to ensure not only unforgeability and non-transferability of credentials, but also user privacy, even when the SE is subverted or fully corrupted. We also define blind DBACs, in which the SE learns nothing about the credential presentations it helped compute. This targets the design of a remote, cloud-based SE which is a deployment model considered for the EU Digital Identity wallet. Finally, we present three simple and round-optimal constructions for device binding of BBS credentials, prove their security in the AGM+ROM, and privacy unconditionally. The SE remains extremely lightweight, computing only a single BLS or Schnorr signature. A blind variant of the BLS-based construction yields the first protocol to enable privacy-preserving device binding for Anonymous Credentials when used with a remote SE.