# An Improved Fuzzy Vector Signature with Reusability
## 1 Introduction  
Biometric information (e.g., fingerprint, iris, face, vein) has been used for user authentication [1; 2; 3; 4; 5] because of its uniqueness and immutability. Due to these properties, such biometric information can be used in place of a user secret key in an authentication system. When using biometric information as a security key, the user is not required to memorize or securely store anything to authenticate, which makes the process much more convenient and user-friendly. However, since biometric information is _noisy_ and _non-uniformly_ distributed, it differs greatly from what is known about cryptographic secret keys. In general, a secret key of an authentication system is largely set to be a uniformly random string of fixed length. Until now, a large body of research has been conducted to bridge this gap and enable biometric information to be used as a secret key in a cryptographic way. To overcome the problem of noisy secret keys, researchers proposed the fuzzy extractor and fuzzy signature as two types of biometric cryptosystems. Comprised of two algorithms, **Gen** and **Rep**, a fuzzy extractor [6] is able to generate a uniformly random string of fixed length (i.e., a secret key) from fuzzy (biometric) data. The generation algorithm **Gen** takes as input sample f fuzzy (biometric) data \(w\) to generate a secret key \(r\) together with helper data \(p\). The reproduction algorithm **Rep** takes as inputanother sample of fuzzy (biometric) data \(w^{\prime}\) close to \(w\) and \(p\) to reproduce \(r\). If the difference between \(w\) and \(w^{\prime}\) is less than a minimal threshold value, **Rep** can generate the same secret key \(r\). On the other hand, consisting of three algorithms, **KG**, **Sign**, and **Vrfy**, the fuzzy signature [7] generates a signature by using fuzzy (biometric) data itself as a signing key. The key generation algorithm **KG** takes as input sample of fuzzy (biometric) data \(w\) to generate a verification key \(vk\). The signing algorithm **Sign** takes as input another sample of biometric information \(w^{\prime}\) to generate a signature \(\sigma\). The verification algorithm **Vrfy** takes as input \(vk\) and \(\sigma\) and succeeds in verification if \(w\) and \(w^{\prime}\) are close to within a fixed threshold. Biometric cryptosystems are generally considered secure when each sample of fuzzy (biometric) data is used only once. However, in reality, a user may use the same biometric source (e.g., right index fingerprint) to authenticate their accounts for several applications as a matter of expediency. Since similar biometric information is used multiple times, a new security notion is required to guarantee both the privacy of the fuzzy (biometric) data at hand and the reusable security of biometric cryptosystems in this situation. In 2004, [PERSON] [8] introduced the _reusability_ of a fuzzy extractor, which ensures no entropy loss to the secret key or biometric source even when relevant pairs of helper data or keys from similar forms of biometric information are revealed. Since then, many researchers have focused on studying this fuzzy extractor with reusability (a.k.a. reusable fuzzy extractor). In order for a reusable fuzzy extractor to be widely used in practice, it should be able to tolerate more than a certain level of errors inherent in fuzzy (biometric) data. For example, iris readings have the average error rate of 20-30% [9; 10; 11]. A number of studies have proposed constructions that tolerate linear fraction of errors [8; 12; 13; 14; 15], but these schemes impose a strong requirement on the distribution of fuzzy (biometric) data, namely: (1) the distribution must have sufficiently high min-entropy (\"Y\" in High min-entropy in Table 1), or (2) any difference between two distinct biometric readings cannot significantly decrease the min-entropy of the fuzzy (biometric) data (\"\(\mathbf{H}_{\infty}[w_{i}|w_{i}-w_{j}]>m\)\" in Source Distribution in Table 1). Unfortunately, both of these expectations are somewhat unrealistic. [PERSON] et al.