EPID systems are anonymous authentication mechanisms which are standardized by ISO/IEC and massively deployed in Intel processors. They are related to the large family of privacy-preserving signatures but differ in that they provide a very pragmatic way of revoking members. Concretely, a member P can be revoked by simply placing one of its signatures in a so-called signature revocation list SRL. Once this is done, every signer will have to include in its future signatures a proof that it has not generated any element of SRL, which implicitly revokes P. This proof of non-revocation generated by each signer is thus the core component of EPID systems and largely dominates the overall complexity. Yet, it appears that it has been a secondary concern for existing constructions that usually implement it using some costly modular zero-knowledge proofs. In this paper, we reconsider this problem by proposing a new EPID system with a much more efficient proof of non-revocation. The latter is no longer zero-knowledge but its combination with the other components of the EPID system still results in an anonymous signature. Proving the latter point is actually quite complex and requires to tweak these other components but in the end it leads to EPID signatures that are up to three times smaller than previous ones and that can be generated and verified with two times less.