# Decentralized Identity Authentication with Auditability and Privacy
## 2 Background and Related Works
### Cryptographic Primitives  
**Hash function**. A cryptographic hash function is defined as \(H:\mathcal{X}\rightarrow\mathcal{Y}\), where \(\mathcal{X}\) is called the domain, and \(\mathcal{Y}\) is called the range. The function is collision-resistant, meaning that it is hard to find two different inputs producing the same output. Additionally, it is pre-image-resistant, i.e., given an element in the range, it should be computationally infeasible to find an input that maps to that element.  
**Unforgeable signatures**. A signature scheme is defined with the three following algorithms.  
1. \(KeyGen(1^{\lambda})\) is a key generation algorithm that takes a security parameter \(\lambda\) as input and outputs the (signing) secret key \(sk\) and the verification key \(vk\).  
2. \(Sig_{sk}(msg)\) is a signing algorithm that takes the secret key \(sk\) and a message \(msg\) as inputs, and it outputs a signature \(\sigma\). 3. \(vrfyg_{sk}(msg,\sigma)\) is a signature verification algorithm that takes a verification key \(vk\), a message \(msg\), and a signature \(\sigma\) as input, and it outputs \"True\" if the signature matches the key and the message, or \"False\" otherwise.  
We assume that the digital scheme used is existentially unforgeable under chosen message attacks, i.e., it is EUF-CMA (existential unforgeability under chosen message attack) secure.  
**Verifiable random function** (VRF). A VRF [18] is the following tuple of algorithms.  
1. \(KeyGen(1^{\lambda})\) is a key generation algorithm that takes a security parameter \(\lambda\) as input and outputs a keypair, i.e., the secret key and the verification key (\(sk\) and \(vk\), respectively).
2. \(VRF_{sk}(X)\) is an algorithm that takes the secret key \(sk\) and \(X\) as inputs and outputs a pseudorandom hash \(h\) and a proof \(\gamma\) (the value \(h\) is unique for the inputs \(sk\) and \(X\)).
3. \(vrfyVRF_{vk}(X,h,\gamma)\) is a verification algorithm that takes the verification key \(vk\) with the values \(X\), \(h\), and \(\gamma\); it returns \"True\" if \(\gamma\) proves that \(h\) was created for \(X\) with the corresponding key \(sk\), and \"False\" otherwise. In practice, VRFs can be implemented with unique signatures.  
**zk-SNARK**. zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) [19] is a non-interactive zero-knowledge proving system that allows one to prove and verify the integrity of an arbitrary computation (represented as an arithmetic circuit). zk-SNARK consists of the following algorithms.  
1. \(zkGen(C,\lambda)\) is a key generation algorithm that takes an arbitrary circuit \(C\) and secret parameter \(\lambda\) as inputs, and it generates a proving key \(z_{pk}\) and a verification key \(z_{vk}\). The generation of these keys constitutes a setup phase and is trusted.
2. \(zkProve_{z_{pk}}(in,w)\) is a function that takes public inputs \(in\) and the private witness \(w\) as inputs, and it outputs a succinct-integrity proof of computation \(\pi\).
3. \(zkVrfy_{z_{vk}}(\pi,in)\) is a function that takes as input a verification key \(z_{vk}\), a proof \(\pi\), and public inputs \(in\), and it returns \"True\" if the proof is valid, and \"False\" otherwise.  
Although we describe one of our protocols by using zk-SNARKs, it can be combined with any proving system with the same capabilities--in particular, with systems that offer better performance or do not require a trusted setup [20].