# An Improved Fuzzy Vector Signature with Reusability
## 4 Fuzzy Vector Signature
### Security
Because of the above inequality, under the assumption that \(\alpha\geq d\cdot\log|\mathbb{G}_{2}|+3\log(1/\epsilon)+\log(1/\zeta)+\Theta(1)\), we see via Lemma 2.3 that, for any \((V_{1},\ldots,V_{d})\) and \((f_{\mathsf{SP}},\ldots,f_{\mathsf{SP}})\), the statistical distance between \(EXP.real\) and \(EXP.\ rand\) is less than \(2 ed\). We can extend the above result of a single verification key to correlated random variables \(W=(W_{1},\ldots,W_{q})\). Let \((V_{i1},\ldots,V_{id})\) be a joint distribution of \(d\) subsets \((I_{i1},\ldots,I_{id})\) for \(i\in[1,q]\). If \(\alpha\geq d\cdot q\cdot\log|\mathbb{G}_{2}|+3\log(1/\epsilon)+\log(1/\zeta)+ \Theta(1)\), the statistical distance between \(EXP.real=(\mathsf{VK}_{w_{1}},\ldots,\)\(\mathsf{VK}_{w_{k}},\ldots,\)\(\mathsf{VK}_{w_{q}})\) and \(EXP.rand=(\mathsf{VK}_{w_{1}},\ldots,R_{k},\ldots,\mathsf{VK}_{w_{q}})\) is less than \(2\epsilon(q\cdot d-(q\cdot d-d+1)+1)=2 ed\) for any \(k\in[1,q]\) where \(\mathsf{VK}_{w_{i}}=(f_{\mathsf{SP}_{i}}(\overrightarrow{v_{i1}}),\ldots,f_ {\mathsf{SP}_{i}}(\overrightarrow{v_{id}}))\) and \(R_{k}=(u_{1},\ldots,u_{d})\) for uniformly random \(u_{i}\in\mathbb{G}_{2}^{d}\). If the FVS scheme is VK-private and the XDH assumption holds in \(\mathbb{G}_{1}\), the FVS scheme is SIG-private in the random oracle model. In reality, if verification keys and signatures were to become revealed to an adversary, we would have to prove that it is infeasible for the adversary to glean any information on the fuzzy (biometric) data from the signatures. As mentioned above, however, we prove from Theorem 4.1 that the VK-privacy holds, meaning that it is difficult for the adversary to get some information on the fuzzy data from verification keys. In addition, the setup algorithm chooses a new signing parameter \(\mathsf{SP}\) each time a verification key is generated for each fuzzy data. Thus, it is sufficient to show that a signature generated under a fixed \(\mathsf{SP}\) does not reveal any information about a challenged fuzzy data. To do this, a simulator chooses a challenge sample \(w^{*}\) along with other correlated samples. For the length \(n\) of \(w^{*}\), we create the following sequence of games where \(w^{*}\) is used for generating a challenge signature:  
\[\text{Game }0:w^{*} =(w^{*}[1],w^{*}[2],\ldots,w^{*}[n])\] \[\tilde{\mathbf{H}}_{\infty}[V_{j}|\mathcal{I}_{j},f_{\mathsf{SP}},\ldots,f_{\mathsf{SP}},\{f_{\mathsf{SP}}(V_{k})=y_{k}\}_{k=j+1}^{d}]\]0 \[\tilde{\mathbf{H}}_{\infty}[V_{j}|\mathcal{I}_{j},f_{\mathsf{SP}},\ldots,f_{\mathsf{SP}},\{f_{\mathsf{SP}}(V_{k})=y_{k}\}_{k=j+1}^{d}]\]1 \[\tilde{\mathbf{H}}_{\infty}[V_{j}|\mathcal{I}_{j},f_{\mathsf{SP}},\ldots,f_{\mathsf{SP}},\{f_{\mathsf{SP}}(V_{k})=y_{k}\}_{k=j+1}^{d}]\]2 \[\tilde{\mathbf{H}}_{\infty}[V_{j}|\mathcal{I}_{j},f_{\mathsf{SP}},\ldots,f_{\mathsf{SP}},\{f_{\mathsf{SP}}(V_{k})=y_{k}\}_{k=j+1}^{d}]\]3 \[\tilde{\mathbf{H}}_{\infty}[V_{j}|\mathcal{I}_{j},f_{\mathsf{SP}},\ldots,f_{\mathsf{SP}},\{f_{\mathsf{SP}}(V_{k})=y_{k}\}_{k=j+1}^{d}]\]4  
In Game 0, the challenge signature is generated for the original \(w^{*}\) as in a real game, whereas in Game \(n\) the challenge signature is generated for a random vector and thus does not have any information on the original \(w^{*}\). For proving the SIG-privacy, it is sufficient to show that it is infeasible for the adversary to distinguish between Game \((\alpha-1)\) and Game \(\alpha\) under the DDH problem. Under the XDH assumption in \(\mathbb{G}_{1}\), it is infeasible to distinguish between Game \((\alpha\)-1) and Game \(\alpha\). Proof. : Given an XDH instance \((g,h,g^{a},g^{b},T)\in\mathbb{G}_{1}\times\mathbb{G}_{2}\times\mathbb{G}_{1}^ {3}\), a challenger \(\mathcal{C}\) interacts with an adversary \(\mathcal{A}\) who tries to break the the SIG-privacy of our FVS scheme. * **Setup. **\(\mathcal{C}\) chooses samples \((w^{*},w_{1},\ldots,w_{q})\leftarrow(W^{*},W_{1},\)\(\ldots,W_{q})\), where those \(q+1\) correlated distributions are from \(\mathcal{A}\).