that discourage their use in the present setting: some schemes are closely tied to particular countries (i.e., the German Identity Card[@cryptoeprint:2012:558; @bsitr03110; @cryptoeprint:2018:1148]), thus non-general purpose enough to include any country in the world, or flexible to adapt to future changes; they require interaction with an issuer during card initialization; they feature protocols for deanonymisation and revocation, not desired in the setting considered in this paper; the initial German scheme[@bsitr03110] could easily be subverted[@10.1007/978-3-319-40367-0_31] because the formalization of pseudo-anonymous signatures is still incipient[@10.1007/978-3-319-49151-6_17], and improvements are being worked out[@cryptoeprint:2014:067; @cryptoeprint:2016:070; @cryptoeprint:2018:1148].

Anonymous credentials, first envisioned by David Chaum[@10.1007/978-1-4757-0602-4_18], and first fully realised by Camenisch and Lysyanskaya[@cryptoeprint:2001:019] with follow-up work improving its security/performance[@cryptoeprint:2009:107; @cryptoeprint:2005:060; @cryptoeprint:2010:496; @10.1007/978-3-540-28628-8_4; @cryptoeprint:2012:298], are a centrally important building block in e-cash. The use of anonymous credentials to protect against Sybil attacks[@the-sybil-attack] has already been proposed in previous works[@DBLP:conf/wistp/AnderssonKMP08; @cryptoeprint:2007:384] although with different cryptographic techniques and for different goals. The main problem with anonymous credentials is that they require a first identification step to an issuing party[@indyAnonCreds] and that would compromise anonymity. This problem is shared with other schemes for pseudoanymization: for example, Bitnym[@sybilPseudonym] requires that a Trusted Third Party must check the real identity of a user 