# An Improved Fuzzy Vector Signature with Reusability
## 4 Fuzzy Vector Signature
### Security  
**Theorem 1**. : _If \(\mathcal{W}\) is a family of sources over \(Z^{n}\) with \(\alpha\)-entropy \(\ell\)-samples, then the FVS scheme is VK-private for such a \(\mathcal{W}\)._  
Proof. : Before proving the VK-privacy, we first prove that a family \(\mathcal{H}\) of functions \(\{f_{\mathsf{SP}}:\mathcal{Z}^{\ell}\to\mathbb{G}_{2}\}\) generating the partial verification key is a \(1/p\)-universal hash function for a fixed \(\mathsf{SP}\). In our FVS scheme, given a vector \(\overrightarrow{v_{j}}=\{w[i]|i\in I_{j}\}\) as input, the function \(f_{\mathsf{SP}}(\overrightarrow{v_{j}})\) is defined as follows:  
\[f_{\mathsf{SP}}(\overrightarrow{v_{j}})=\Big{(}\prod_{i\in I_{j}}{n^{x_{i}+w [i]y_{i}}}^{r_{j}},\]  
where \(r_{j}\) is a randomly chosen exponent \(\in\mathbb{Z}_{p}\). Since \(r_{j}\) is raised for each input, it is easy to see that two outputs of the function could be equal with probability \(1/p\). Thus, it holds that for two distinct inputs \(\overrightarrow{v_{i}}\) and \(\overrightarrow{v_{j}}\), \(\Pr\big{[}f_{\mathsf{SP}}(\overrightarrow{v_{i}})=f_{\mathsf{SP}}( \overrightarrow{v_{j}})\big{]}=\frac{1}{p}=\frac{1}{|\mathbb{G}_{2}|}\); thus, \(\mathcal{H}=\{f_{\mathsf{SP}}\}\) is \(1/p\)-universal. Next, we prove that a verification key \(\mathsf{VK}_{w}\) corresponding with \(w\in W\) is almost close to uniform distribution based on Lemma 3. After that, we extend the result to the case of a polynomial number of verification keys. Let \(W=(W[1],...,W[n])\) be a random variable of a source with \(\alpha\)-entropy \(\ell\)-samples. If \(V_{j}=\{W[i]|i\in\mathcal{I}_{j}\}\), we see that \((V_{1},...,V_{d})\) is a joint distribution of \(d\) subsets of \(W\in\mathcal{W}\) such that \(\tilde{\mathbf{H}}_{\infty}[V_{j}|\mathcal{I}_{j}]\geq\alpha\) for random sets of indices \((\mathcal{I}_{1},...,\mathcal{I}_{d})\). In addition, as mentioned above, each function \(f_{\mathsf{SP}}\) is a \(1/p\)-universal hash function with respect to a distinct \(j\in[1,d]\). By Lemma 2(a), if a random set of indices \(\mathcal{I}_{j}\) is set to be \(I_{i}\), then \(\mathbf{H}_{\infty}[V_{j}|\mathcal{I}_{j}=I_{j}]\geq\tilde{\mathbf{H}}_{ \infty}[V_{j}|\mathcal{I}_{j}]-\log(1/\xi)\) with a probability of at least \(1-\xi\). Let \(f_{\mathsf{SP}}(V_{j})\) be a random variable for a set \(V_{j}\) of indices for \(j\in[1,d]\) and let \((y_{j+1},\ldots,y_{d})\) be a sample of \((f_{\mathsf{SP}}(V_{j+1}),\ldots,f_{\mathsf{SP}}(V_{d}))\). By a similar proof A1 (proof of Lemma 3), we obtain the following result:  
\[\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}]\] \[\geq\tilde{\mathbf{H}}_{\infty}[V_{j}|\mathcal{I}_{j},f_{\mathsf{ SP}},\ldots,f_{\mathsf{SP}}]-(d-j)\log|\mathbb{G}_{2}|-\log(1/\epsilon)\] \[=\tilde{\mathbf{H}}_{\infty}[V_{j}|\mathcal{I}_{j}]-(d-j)\log| \mathbb{G}_{2}|-\log(1/\epsilon)\] \[\geq\alpha-(d-j)\log|\mathbb{G}_{2}|-\log(1/\epsilon),\]  
where \(\epsilon\) shows negligible probability determined by a security parameter. As a result, if \(\alpha\geq d\cdot\log|\mathbb{G}_{2}|+3\log(1/\epsilon)+\log(1/\xi)+\Theta(1)\), we have  
\[\mathbf{H}_{\infty}[V_{j}|\mathcal{I}_{j}=I_{j}]\] \[\geq\alpha-(d-j)\log|\mathbb{G}_{2}|-\log(1/\epsilon)-\log(1/\xi)\] \[=j\log|\mathbb{G}_{2}|+2\log(1/\epsilon)+\Theta(1)\] \[\geq\log|\mathbb{G}_{2}|+2\log(1/\epsilon)+\Theta(1).\]For \(j\in[1,d]\), we can show that \(\mathbf{H}_{\infty}[V_{j}|\mathcal{I}_{j}=I_{j}]\geq\log|\mathbb{G}_{2}|+2\log(1/ \epsilon)+\Theta(1)\), similarly as in the above process. Let \(EXP.real=(f_{\mathsf{SP}}(\overrightarrow{v_{1}}),\ldots,f_{\mathsf{SP}}( \overrightarrow{v_{d}}))\) for some samples \((V_{1}=\overrightarrow{v_{1}},\ldots,V_{d}=\overrightarrow{v_{d}})\), and let \(EXP.rand=(u_{1},\ldots,u_{d})\) be random samples chosen from \(\mathbb{G}_{2}^{d}\).