# Decentralized Identity Authentication with Auditability and Privacy
###### Abstract  
Decentralized identity (DID) systems aim to give users full control over their identities by using completely decentralized technologies, such as blockchain or distributed ledgers, as identity providers. However, when user credentials are compromised, it is impossible in existing DID systems for the users to detect credential misuse. In this paper, we propose new DID authentication protocols with two properties: auditability and privacy. The former enables the detection of malicious authentication events, while the latter prevents an adversary from linking an authentication event to the corresponding user and service provider. We present two protocols that achieve auditability with varying privacy and performance guarantees. The first protocol has high performance, but it reveals information about the user. The second protocol achieves full privacy, but it incurs a higher performance overhead. We present a formal security analysis of our privacy-preserving protocols by using the Tamarin prover. We implemented them and evaluated their performance with a permissioned blockchain deployed over the Amazon AWS and a local cloud infrastructure. The results demonstrate that the first protocol is able to support realistic authentication workloads, while the second is nearly practical. blockchain; decentralized identity; authentication; auditability; privacy +
Footnote †: journal:  
Our goal is to design DID authentication protocols that enable users to detect credential misuse. We define two security properties for such protocols: auditability, which allows users to detect unauthorized authentication events that use their credentials, and _privacy_, which prevents adversaries from linking an authentication to the corresponding user and service provider. The challenge here is to design protocols that have both properties and reasonable performance. One naive solution is to store the full content of all authentication events in distributed append-only storage (in our implementation, a blockchain). This achieves auditability because the user can see the complete history of their credential usage, but both the user and the service provider of every event are revealed, thus achieving no privacy. We propose two protocols that achieve auditability with varying privacy and performance guarantees. The first protocol has high performance, but limited privacy. It works as follows. For each authentication, the user increments a counter and signs it with a key associated with their DID. This signed counter is sent to the service provider, who tries to log it in the DLT or blockchain. If successful, the user is authenticated. The blockchain ensures that it only accepts consecutive counter values from the correct user. The user can detect malicious authentication by checking if a future counter value has been logged on the blockchain by keeping track of the latest counter value. However, because counter values are signed, each authentication event reveals who the user is by associating it with the DID. The second protocol achieves full privacy, but incurs a high performance overhead. The key challenge in designing this protocol is how to hide user information (such as the DID or keys associated with it) from the authentication event. To illustrate this, we describe a protocol using verifiable random functions (VRFs) and show that it only works under strong security assumptions. We address this challenge by using the Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK) primitive [10]. More specifically, the client generates a token \(tkn\) based on a counter value \(cnt\) and a zero-knowledge proof with which the blockchain can verify that some token \(tkn^{\prime}\) derived from the value \(cnt-1\) is already in the blockchain, but without revealing this token or the counter value. Our evaluation shows a performance that is three orders of magnitude lower than that of the first protocol. This overhead is due to the cost of the verification performed by the blockchain.