# An Improved Fuzzy Vector Signature with Reusability
## 4 Fuzzy Vector Signature
### Security
In particular, for a sample \(w^{*}=(w^{*}[1],\ldots,w^{*}[n])\) corresponding to \(W^{*}\), \(\mathcal{C}\) sets \(w^{*}[1]=R_{1},\ldots,w^{*}[\alpha-1]=R_{\alpha-1}\) for randomly chosen values \(R_{1},\ldots,R_{\alpha-1}\in\mathbb{Z}_{p}\). For each \(w_{j}\), \(\mathcal{C}\) generates \((\mathsf{VK}_{w_{j}},\mathsf{SP}_{j})\) for \(j=1,\ldots,q\) as follows:Choose random values \(\phi\) and \(\{x_{ji},y_{ji}\}_{i=1}^{n}\) in \(\mathbb{Z}_{q}\). Set \(\mathsf{SP}_{j}=\{g,g^{\phi},g^{x_{ji}},g^{y_{ji}}\}_{i=1}^{n}\). Select \(d\) sets of random indices \(I_{m}\) such that \(|I_{m}|=\ell\). Set a subset \(\overrightarrow{v_{jm}}=\{w_{j}[i]|i\in I_{m}\}\) for \(m\in[1,d]\). Choose \(\{r_{jm}\}_{m=1}^{d}\) at random in \  
now selected by an adversary. The important point is that the adversary still cannot know the exact discrete logarithm \(s\cdot s^{\prime}\), which is then the witness necessary for generating the other signature elements \((\sigma_{4},\sigma_{5})\) as an NIZK proof as it relates to \(s\cdot s^{\prime}\). However, generating such an NIZK proof equates to breaking the statistical soundness of proving the equality of discrete logarithms [28] in regard to the unknown witness. Thus, the probability that the adversary would succeed is at most \(q_{h}/p\), where \(q_{h}\) is the number of \(H\)-oracle queries, which is also negligible. Now, the remaining case is to reuse the previous signature as it is and simply reconstruct a new proof \((\sigma_{4},\sigma_{5})\). Fortunately, this case can be reduced to the forgery of a one-time multi-user Schnorr signature [29], which is provably secure under the DL assumption. In our proof, a slight variant of the one-time multi-user Schnorr signature proves the equality of discrete logarithms rather than proving knowledge. In line with this, the variant is also provably unforgeable [30; 31] against chosen-message attacks in a multi-user setting (MU-SUF-CMA). Based on the variant we use, we show that, under the DL assumption, it is difficult for the adversary to succeed in the remaining case. Proof. : A simulator \(\mathcal{B}\) uses an adversary \(\mathcal{A}\) (which breaks the reusability of the FVS scheme) as a subroutine to forge a signature in the one-time multi-user Schnorr signature scheme. Let \(q_{s}\leq\rho\) for the number \(q_{s}\) of signature queries. Given \(\rho\) independent public keys \(\big{(}g,g_{1},\{(g^{s_{1}},g_{1}^{s_{1}}),\ldots,(g^{s_{\rho}},g_{1}^{s_{ \rho}})\}\big{)}\) of the one-time multi-user Schnorr signature scheme, \(\mathcal{B}\) interacts with \(\mathcal{A}\) as follows:  
* **Setup. **\(\mathcal{A}\) gives correlated random variables \((W_{1},\ldots,W_{q})\in\mathcal{W}^{q}\), of which each is in \(\mathcal{Z}^{n}\). \(\mathcal{B}\) samples \((w_{1},\ldots,w_{q})\leftarrow(W_{1},\ldots,W_{q})\) and runs \(\mathbf{Setup}(1^{\lambda},n,d,\ell,w_{j},t)\) to obtain a signing parameter \(\mathsf{SP}_{j}\) and a verification key \(\mathsf{VK}_{w_{j}}\) for \(j=1,\ldots,q\). In the setup algorithm, \((x_{j1},\ldots,x_{jn})\) and \((y_{j1},\ldots,y_{jn})\) are selected uniformly at random in \(\mathbb{Z}_{p}\). \(\mathcal{B}\) gives \(\{(\mathsf{SP}_{j},\mathsf{VK}_{w_{j}})\}_{j=1}^{q}\) to \(\mathcal{A}\). * **Signing queries. *
* For \(j\in[1,q]\), \(\mathcal{A}\) issues signing queries with input, namely a random variable \(W^{\prime}\) correlated with \((W_{1},\ldots,W_{q})\), an index of signing parameter \(\mathsf{SP}_{j}\), and a message \(m_{k}\). \(\mathcal{B}\) responds to the query as follows:
* Choose a sample \(w^{\prime}=(w^{\prime}[1],\ldots,w^{\prime}[n])\) correlated with \((w_{1},\ldots,w_{q})\) from \(W^{\prime}\). * Generate \(\sigma_{1,i}=(g^{s_{k}})^{x_{ji}+y_{ji}w^{\prime}[i]}\) for \(i\in[1,n]\), and set \(M_{k}=\big{(}g^{s_{k}},g_{1}^{s_{k}},\{\sigma_{1,i}\}_{i\in[1,n]},m_{k}\big{)}\). * Query \((j,M_{k})\) to the signing oracle of the one-time multi-user Schnorr signature scheme, meaning a signing query on a message \(M_{k}\) under the \(j\)-th public key, and receive \((h_{k},c_{k})\).