# An Improved Fuzzy Vector Signature with Reusability
## 4 Fuzzy Vector Signature  
### Construction  
Let \(\mathcal{G}=(p,g,h,\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},e)\) be a bilinear group, where \(g\in\mathbb{G}_{1}\) and \(h\in\mathbb{G}_{2}\) are generators. Let \(\mathcal{W}\) be a (biometric) space with the Hamming distance metric, and let \(\mathcal{W}\in\mathcal{W}\) be a random variable that is the user source. Given \(W\), we consider two fuzzy (biometric) samples such that \(w,w^{\prime}\in W\). In this section, we present our FVS scheme that consists of the following three algorithms: \(\mathbf{Setup}\), \(\mathbf{Sign}\), and \(\mathbf{Verify}\).  
* \(\mathbf{Setup}(1^{\lambda},w,n,d,\ell,t)\) For a security parameter \(\lambda\), the setup algorithm generates a bilinear group \(\mathcal{G}\), and picks a hash function \(H:\{0,1\}^{*}\rightarrow\mathbb{Z}_{p}\). The setup algorithm generates a signing parameter (\(\mathsf{SP}\)) as follows: 1. Pick random elements \(x_{i},y_{i}\in\mathbb{Z}_{p}\) for \(i\in[1,n]\) and set \(X_{i}=g^{x_{i}},Y_{i}=g^{y_{i}}\in\mathbb{G}_{1}\) for \(i\in[1,n]\). 2. Generate a random element \(g_{1}\in\mathbb{G}_{1}\). 3. Output \(\mathsf{SP}=\big{(}g,g_{1},H,\{X_{i},Y_{i}\}_{i\in[1,n]}\big{)}\). Let \(n\) be the length of a fuzzy (biometric) data \(w\), and \(d\) be the number of entire subsets, \(\ell\) be the number of elements included in each subset, and \(t\) be the maximum number of errors among \(n\) elements, indicating an error tolerance rate. Given a fuzzy (biometric) data \(w=(w[1],\ldots,w[n])\gets W\), the setup algorithm generates a verification key \(\mathsf{VK}_{w}\) as follows: 1. Randomly select a set \(I_{j}\subset\{1,\ldots,n\}\) where \(|I_{j}|=\ell\) for \(j\in[1,d]\). 2. Set a subset \(\overline{v_{j}}=\{w[i]|i\in I_{j}\}\) of a vector \(w\) for \(j\in[1,d]\).  
Select random elements \(r_{j}\in\mathbb{Z}_{p}\) for \(j\in[1,d]\).
4. Set \(vk_{j}=\left(\big{(}\prod_{i\in I_{j}}h^{x_{i}+w[j]y_{i}}\big{)}^{\gamma_{j}},h^{ \prime}\big{)}\in\mathbb{G}_{2}^{2}\) for \(j\in[1,d]\).  
The verification key \(\mathsf{VK}_{w}\) is given by  
\[\mathsf{VK}_{w}=\big{(}\{vk_{1},\ldots,vk_{d}\},\{1_{1},\ldots,I_{d}\}\big{)}.\]  
* \(\mathbf{Sign}\big{(}\mathsf{SP},w^{\prime},m\big{)}\). To sign a message \(m\) under fuzzy (biometric) data \(w^{\prime}=(w^{\prime}[1],\ldots,w^{\prime}[n])\gets W\), the signing algorithm generates a signature \(\sigma_{w^{\prime}}\) as follows: 1. Choose random elements \(s,k\in\mathbb{Z}_{p}^{*}\). 2. Set \(\sigma_{(1,i)}=\big{(}X_{i}\Gamma_{i}^{w^{\prime}[i]}\big{)}^{s}\) for \(i\in[1,n]\). 3. Set \(\sigma_{2}=g^{s}\in\mathbb{G}_{1}\). 4. Set \(\sigma_{3}=g_{1}^{s}\in\mathbb{G}_{1}\). 5. Set \(\sigma_{4}=H(g^{k},g_{1}^{k},\sigma_{2},\sigma_{3},\{\sigma_{(1,i)}\}_{i\in[1, n]},m)\) 6. Set \(\sigma_{5}=k+\sigma_{4}\cdot s\in\mathbb{Z}_{p}\). 7. Output \(\sigma_{w^{\prime}}=\big{(}\{\sigma_{(1,i)}\}_{i\in[1,n]},\sigma_{2},\sigma_{3 },\sigma_{4},\sigma_{5}\big{)}\).
* \(\mathbf{Verify}\big{(}\mathsf{VK}_{w},\sigma_{w^{\prime}},m\big{)}\). To verify a signature \(\sigma_{w^{\prime}}=\big{(}\{\sigma_{(1,i)}\}_{i\in[1,n]},\sigma_{2},\sigma_{3 },\sigma_{4},\sigma_{5}\big{)}\) on a message \(m\) under the verification key \(\mathsf{VK}_{w}=\big{(}\{vk_{1},\ldots,vk_{d}\},\{1_{1},\ldots,I_{d}\}\big{)}\), the verification algorithm proceeds as follows: 1. Set \(vk_{j}=(vk_{1,j},vk_{2,j})\) for \(j\in[1,d]\). 2. Set \(cnt=0\). 3. While \(cnt=0\) for \(j=1,\ldots,d\): 1. Compute \(A=\prod_{i\in I_{j}}\sigma_{(1,i)}\). 2. If \(e(\sigma_{2},vk_{1,j})=e(A,vk_{2,j})\), \(cnt=1\). If \(cnt=0\), output 0. 4. Otherwise, set \(B=g^{\sigma_{5}}\sigma_{2}^{-\sigma_{4}}\) and \(B_{1}=g_{1}^{\sigma_{5}}\sigma_{3}^{-\sigma_{4}}\). 5. If \(\sigma_{4}=H\big{(}B,B_{1},\sigma_{2},\sigma_{3},\{\sigma_{(1,i)}\}_{i\in[1,n] },m\big{)}\), output 1; otherwise 0.