# Privacy-Preserving Solution for European Union Digital Vaccine Certificates
## 4 Cryptographic Preliminaries
### Notation and the Security Assumptions  
From now on, the symbol \":\" states for \"such that\", \"\(|x|\)\" the bitlength of \(x\), and \"\(||\)\" the concatenation of two binary strings. We write \(a\in_{R}A\) when \(a\) is sampled uniformly at random from \(A\). A secure hash function is denoted as \(\mathcal{H}:\{0,1\}^{*}\to\{0,1\}^{\kappa}\), where \(\kappa\) is the given security parameter. Let \(\mathbb{G}_{1}\), \(\mathbb{G}_{2}\), and \(\mathbb{G}_{T}\) be cyclic groups of the same prime order \(q\), where \(\mathbb{G}_{1}\) and \(\mathbb{G}_{2}\) are additive groups and \(\mathbb{G}_{T}\) is a multiplicative group. Let \(g_{1}\in\mathbb{G}_{1}\) and \(g_{2}\in\mathbb{G}_{2}\) be points of the respective group, and \(\mathcal{O}\) be the point at infinity.  
**Definition 1** (Bilinear pairing).: _A bilinear pairing is a map \(\mathbf{e}:\mathbb{G}_{1}\times\mathbb{G}_{2}\to\mathbb{G}_{T}\) which satisfies the following properties:_  
* _Bilinearity:_ \(\forall x,y\in\mathbb{Z}_{q},g_{1}\in\mathbb{G}_{1},g_{2}\in\mathbb{G}_{2}: \mathbf{e}(g_{1}^{\ast},g_{2}^{y})=\mathbf{e}(g_{1},g_{2})^{xy}\)_._
* _Non-degeneracy:_ \(\forall g_{1}\
eq\mathcal{O}\ \exists g_{2}\in\mathbb{G}_{2}:\mathbf{e}(g_{1},g_{2}) \
eq 1\in\mathbb{G}_{T}\) _and_ \(\forall g_{2}\
eq\mathcal{O}\ \exists g_{1}\in\mathbb{G}_{1}:\mathbf{e}(g_{1},g_{2}) \
eq 1\in\mathbb{G}_{T}\)_._
* _Computability: There exists an efficient algorithm_ \(\mathcal{G}(1^{\kappa})\) _to compute_ \(\mathbf{e}(g_{1},g_{2})\)_._  
By definition, \((q,\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},\mathbf{e},g_{1},g_{2})\) is a bilinear group if it satisfies all above properties.  
Let \(\mathbb{G}\) be a cyclic group of order \(q\) and \(g\in\mathbb{G}\) be its generator. The security of the proposed protocol relies on the \(n\)-Strong Computational Diffie-Hellman Inversion (\(n\)-SCDHI) assumption [21]:  
**Definition 2** (\(n\)-SCDHI Problem).: _Let \(\mathcal{O}(\cdot)\) be the oracle that on input \((m_{1},\ldots,m_{n})\in(\mathbb{Z}_{q}^{\ast})^{n}\) adds \((m_{1},\ldots,m_{n})\) to \(Q\) and outputs \(\{0,1\}\). Let \(O^{i}(\cdot)\) be the oracle that on input \(h\) outputs \(h^{x^{i}}\). Then for all probabilistic polynomial time adversary \(B\), the advantage is defined as follows:_  
\[Adv_{B}^{n-SCDHI}=\mathbf{Pr}[(x_{0},\ldots,x_{n})\leftarrow\{0, \ldots,q-1\};(y,m_{1}^{\ast},\ldots,m_{n}^{\ast})\gets B^{\mathcal{O}( \cdot),\mathcal{O}^{\mathcal{O}}(\cdot),\ldots,\mathcal{O}^{n}(\cdot)}:y=\] \[g^{\frac{1}{\mathbb{G}_{1}+\sum_{i=1}^{n}m_{i}^{\ast}x_{i}}}\wedge (m_{1}^{\ast},\ldots,m_{n}^{\ast})\
otin\mathcal{Q}]\]  
_SCDHI is \((t,\mathbf{\epsilon})\)-hard if no \(t\)-time adversary has the advantage at least \(\mathbf{\epsilon}\)._  
**Theorem 1**.: _The \(n\)-SCDHI problem is hard in the generic group model. More precisely, an adversary working in a generic group of order \(q\) with advantage \(\mathbf{\epsilon}\) requires time \(\Omega(3\sqrt{\mathbf{\epsilon}q})\)._  
In this article, we consider the case \(\mathbb{G}_{1}\
eq\mathbb{G}_{2}\); that is, when \(\mathbf{\epsilon}\) is an asymmetric bilinear map and the SCDHI assumption holds. Moreover, having \(\mathbb{G}_{1}\
eq\mathbb{G}_{2}\) permits obtaining the shortest possible signature; see [23] for more details.