Cryptology ePrint Archive: Report 2020/1498

EPID with Malicious Revocation

Olivier Sanders and Jacques Traoré

Abstract: EPID systems are anonymous authentication protocols where a device can be revoked by including one of its signatures in a revocation list. Such protocols are today included in the ISO/IEC 20008-2 standard and are embedded in billions of chips, which make them a flagship of advanced cryptographic tools. Yet, their security analysis is based on a model that suffers from several important limitations, which either questions the security assurances EPID can provide in the real world or prevents such systems from achieving their full impact. The most prominent example is the one of revocation lists. Although they could be managed locally by verifiers, which would be natural in most use-cases, the security model assumes that they are managed by a trusted entity, a requirement that is not easily met in practice and that is thus tempting to ignore, as illustrated in the corresponding standard.

In this paper, we propose to revisit the security model of EPID, by removing some limitations of previous works but mostly by answering the following question: what can we achieve when revocation lists are generated by a malicious entity?

Surprisingly, even in this disadvantageous context, we show that it is possible to retain strong properties that we believe to better capture the spirit of EPID systems. Moreover, we show that we can construct very efficient schemes resisting such powerful adversaries by essentially tweaking previous approaches. In particular, our constructions do not require to perform any significant test on the revocation lists during the signature generation process. These constructions constitute the second contribution of this paper.

Category / Keywords: cryptographic protocols /

Original Publication (with minor differences): CT-RSA 2021

Date: received 30 Nov 2020, last revised 2 Mar 2021

Contact author: olivier sanders at orange com, jacques traore@orange com

Available format(s): PDF | BibTeX Citation

Version: 20210302:130143 (All versions of this report)

Short URL: ia.cr/2020/1498