# An Improved Fuzzy Vector Signature with Reusability
## 1 Introduction
[17] relaxed these conditions, only requiring a subset of samples to have sufficient average min-entropy for given subset indices, and proposed a reusable fuzzy extractor that would tolerate a sub-linear fraction of errors. The construction is contingent on the existence of a powerful tool called _digital locker_, which is a non-standard assumption. Other reusable biometric cryptosystems [16; 19] did not require either unrealistic requirements on the biometric distribution or contain non-standard assumptions, but they only tolerated a logarithmic fraction of errors. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Schemes**} & **Secure** & **High** & **Security** & **Error** & **Reusability** & **Source** \\  & **Sketch** & **Min-Entropy** & **Assumption** & **Tolerance Rate** & **Rusability** & **Distribution** \\ \hline \multirow{8}{*}{FE} & [8] & O & Y & + & linear & weak & \(w_{i}=w+\delta_{i}\) \\  & [16] & X & N & LWE & log & Strong & \(w_{i}=w+\delta_{i}\) \\  & [13] & O & Y & LWE & linear & Strong & \(w_{i}=w+\delta_{i}\) \\  & [15] & O & Y & DDH & linear & Strong & \(w_{i}=w+\delta_{i}\) \\  & [14] & O & Y & DDH & linear & Strong & \(\mathbf{H}_{\infty}[w_{i}|w_{i}-w_{i}]>m\) \\  & [17] & X & N & X & sub-lin & Strong & \((w_{i},w_{i})\) \\  & [18] & X & N & X & sub-lin & Strong & \((w,w_{i})\) \\  & [12] & X & Y & X & linear & Strong & \((w,w_{i})\) \\ \hline FS & [19] & X & N & LWE & log & Strong & \(w_{i}=w+\delta_{i}\) \\ \hline \multirow{2}{*}{FVS} & [20] & X & N & XDH & sub-lin & \(\triangle\) & \((T,k)\) \\  & Ours & X & N & XDH & sub-lin & Strong & \((w,w_{i})\) \\ \hline \hline \end{tabular}  
* In Secure Sketch, If the scheme used the secure sketch, “O”. Otherwise, “X”.
* In Reusability, “weak” means that the scheme does not provide a formal proof;
* In Source Distribution, “\(w_{i}=w+\delta_{i}\)” means that, for a fuzzy (biometric) source \(w\), the error \(\delta_{i}\) is controlled by an adversary;
* \((w,w_{i})^{*}\) means that the biometric readings \(w\) and \(w_{i}\) are arbitrary correlated;
* \((T,k)\)” means the \((T,k)\)-block source in Reference [21].
* High Min-entropy means that min-entropy is higher than some value secure against brute-force attack. In High Min-entropy, “Y” is indicated if the scheme requires sufficiently high min-entropy of the input (biometric) data, and “N” otherwise;
* In Security Assumption, “+” means that the scheme is information-theoretically secure.  
\end{table} 
Table 1: Comparison with reusable biometric cryptosystems. Recently, a new primitive called fuzzy vector signature (FVS) [20] was proposed based on bilinear maps (i.e., pairings), which improved the error tolerance rate without any additional requirements on the distribution of biometric information. This scheme tolerates a sub-linear fraction of errors and also is based on standard assumptions, like the external Diffie-Hellman (XDH). It is also claimed to be reusable, but no formal proof for reusability was provided in Reference [20]. In this paper, we introduce the formal security model for reusability of fuzzy vector signature (FVS) and prove that our proposed scheme is reusable in the reusability model. By more strictly applying the subset-based sampling method [17], our scheme is also more efficient than Reference [20] from the perspective of the user and the authentication server. Specifically, it reduces not only the size of the signature and verification key but also the number of pairing operations required for verification. Section 5 outlines a detailed performance comparison.