# An Improved Fuzzy Vector Signature with Reusability
## 5 Performance Analysis  
Our FVS scheme is constructed using the subset-based sampling method of the re-usable fuzzy extractor [17], which does not require fuzzy (biometric) input data to have sufficiently high min-entropy and can still tolerate a sub-linear fraction of errors. Generally, biometric data sources are non-uniformly and uniquely distributed from person to person; thus, it is not easy to expect that such biometric data will have high min-entropy. Nevertheless, most reusable fuzzy extractors [8; 13; 14; 15] based on secure sketches require source data with high min-entropy because a secure sketch is known to cause an entropy loss of a biometric input data. For comparison, we focus on fuzzy extractors [17; 18] that do not rely on secure sketches, and therefore not require a high min-entropy source. A reusable fuzzy extractor suggested by Reference [12] is not based on a secure sketch and tolerates a linear fraction of errors, but it uses a so-called pseudoentropic isometry that requires each biometric input data component to have high min-entropy. This requirement is also far from realistic biometric information. A reusable fuzzy extractor suggested by [PERSON] et al. [16] is constructed based on the hardness of Learning with Errors (LWE) problems, where biometric data is injected into the part with LWE errors. In that case, such biometric data must follow a certain error distribution (e.g., Gaussian) in order to ensure the security of LWE problems. This reveals a limitation in its real-world application potential. Furthermore, the LWE-based fuzzy extractor [16] requires a time-consuming reproducing algorithm, where another sample of biometric data is subtracted from an LWE instance that was previously created per each component, and then a randomly chosen linear system is expected to be solved. A problem arises if any error components in the chosen linear system are not 0, at which point a new linear system must be randomly reselected until achieving success. The same problem is found in the reusable fuzzy signature [19] that follows the LWE-based fuzzy extractor technique. To mitigate the reproducing problem, [16; 19] should be limited to dealing with only a logarithmic size of errors.  
Eventually, we compare our FVS scheme with previous fuzzy extractors [17; 18] and the original FVS scheme [20], which all follow the subset-based sampling technique [17]. We specifically consider authentication protocols where a fuzzy extractor or an FVS scheme is instantiated to authenticate a user using biometric data. During protocol executions, we compare our proposed scheme with existing schemes in terms of storage or transmission costs and computational costs on the part of the user. In regards to the fuzzy extractor, we assume that a digital signature scheme \(\mathcal{S}=(\textbf{KeyGen},\)**Sign**, **Verify**) is additionally provided. As usual, an authentication protocol consists of two phases; enrollment and authentication. In the enrollment phase, a user is registered with an authentication server by sending an identity \(ID\), a verification key \(vk_{ID}\), and helper data \(P_{ID}\). In each authentication phase, a user receives helper data \(P_{ID}\) from the server, recovers a secret key for signature generation using their biometric data, and returns a signature \(\sigma_{ID}\) in response to a challenge message \(R\) sent by the server. Figures 1 and 2 present two authentication protocols in more detail.