{'fraction_non_alphanumeric': 0.03099619998509798, 'fraction_numerical': 0.008494150957454736, 'mean_word_length': 4.83416648554662, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Random Hash Code Generation for Cancelable Fingerprint Templates using Vector Permutation and Shift-order Process

Cancelable biometric techniques have been used to prevent the compromise of biometric data by generating and using their corresponding cancelable templates for user authentication. However, the non-invertible distance preserving transformation methods employed in various schemes are often vulnerable to information leakage since matching is performed in the transformed domain. In this paper, we propose a non-invertible distance preserving scheme based on vector permutation and shift-order process. First, the dimension of feature vectors is reduced using kernelized principle component analysis (KPCA) prior to randomly permuting the extracted vector features. A shift-order process is then applied to the generated features in order to achieve non-invertibility and combat similarity-based attacks. The generated hash codes are resilient to different security and privacy attacks whilst fulfilling the major revocability and unlinkability requirements. Experimental evaluation conducted on 6 datasets of FVC2002 and FVC2004 reveals a high-performance accuracy of the proposed scheme better than other existing state-of-the-art schemes.


Introduction
Fingerprint authentication systems have witnessed a progressive deployment in various areas of our daily endeavors, stretching from a simple task of verifying ourselves on our smartphones to a broader area of identity management such as visa application and cross boarder checking procedures. Such huge reliant on fingerprints amongst other modalities has to do with its permanence, uniqueness, proven stability, assurance, individuality and cost-effectiveness [13] [24] [25] [14]. However, the stored fingerprint templates are vulnerable to attacks, and once compromised, there would be a permanent loss of vital data since it is irrevocable and irreplaceable. As such, the devastating consequence that comes with the loss is immeasurable. To overcome these draw-backs, cancelable templates are used to efficiently preserve the security and privacy concerns of fingerprint biometric data by permitting compromised templates to be replaced by a new one. They are built on the idea that they can be revoked and a new instance of the corresponding templates can be re-generated if the original data is tampered with. This is often achieved through non-invertible transformation, i.e., an intentional (but crafted) distortion of the biometric data by means of transformation function and userpredefined parameters. The transformation function can be applied either in a form of blending mechanism (salting) or a many-to-one transformation (non-invertibility). The essential properties of cancelable biometric schemes are as follows: a) Diversity: Different cancelable templates should be generated from same biometric data. In other words, same biometric data should not correlate in different applications. b) Non-invertibility: It should be impossible to reconstruct the original biometric data from its corresponding transformed version even if the transformed templates and the transformation methods are known. c) Revocability: It should be possible to revoke a compromised template and replace it with a new one based on the original data. d) Performance: The accuracy performance should not be degraded after the template transformation. In other words, the incorporation of security mechanism should not reduce the systems' recognition accuracy.
Generally, the accuracy performance of a cancelable biometric system is known to be directly impacted by the feature extraction and representation of the biometric data. Minutiae descriptors provides us with the efficient means of representing their discriminative features for effective construction of fingerprint templates. An example of such descriptor is the state-of-the-art minutiae cylinder code (MCC) [3] which is known for its superior matching performance. However, this descriptor exhibits some security and privacy shortcomings as they are prone to inversion. On the other hand, the incorporation of security mechanism such as in the protected version of MCC, known as 2PMCC [8]. The method is able to avert the inversion but still prone to revocability. Besides non-invertibility and revocability, the accuracy performance is often degraded after transformation due to modification of the minutiae descriptor, coupled with information leakage in the matching procedure which raise concerns over the systems' full non-invertibility.

Review works
In the section, several works that focus on the noninvertibility of fingerprint templates including the recent distance preserving drawbacks in most of these approaches are discussed. Readers can as well refer to these papers [27] [22] [25] for a more in-depth survey on cancelable biometrics. The earlier works of [8] [21] [29], and [17] are all designed with notion of achieving non-invertibility. However, even though it is not fully achieved due to the fact that the distance between features is not attained, their accuracy is also degraded considering that the security mechanisms are directly applied on the descriptors or incorporated in the mapping approach, except for [8]. Even so, it also suffers accuracy degradation depending on the parameter tuning. Wang et al [36] designed a cancelable fingerprint templates using zoned minutiae pairs. Local minutiae structures are leveraged to construct the minutiae pairs with the incorporation of partial discrete Fourier transform in order to generate discriminating features for matching. The scheme however, only shows good accuracy performance on DB1 of FVC2002, while achieving a relatively low accuracy in other datasets. In another different work [35], the authors used a partial Hadamard transform approach for the design of cancelable templates. The stochastic distance between binary vectors is theoretically proven to be preserved after transformation. Even though the achieved accuracy is better than the previous scheme, it still lacks a profound distance preservation analysis.
Recently, Trivedi et al. [33] proposed a non-invertible approach based on information extracted from the Delaunay triangulation of the minutiae points. A random binary sting is utilized with a user specific key for cancelability. However, the scheme is evaluated on a single dataset only, which of course is insufficient for effective validation of the accuracy performance and other cancelable properties of the scheme. Another novel design of cancelable templates using randomized non-negative least squares is performed by Kho et al. [19]. The authors formulated a unique PR-NNLS descriptor for non-invertible transformation but instead of applying it directly on the minutiae descriptor, they chose to apply it on the PLS descriptor dictionary in order to retain the accuracy. However, its full non-invertibility still cannot be ascertained because there is no analysis conducted on the distance preservation. In a rather similar approach by Shahzad et al [32], authors explored the concept of window-shift-XOR and discrete wavelet transform to avert ARM. Some similarity-based attacks are evaluated on their dual protection mechanism to validate the non-invertibility of the scheme but without an analysis.
The new prevailing problem applicable to most cancelable biometric systems is their inability to achieve full noninvertibility due to the fact that the transformation techniques often used are not preserving the distance space between original features and their transformed versions. However, the best possible ways of overcoming these issues are 1) to avoid matching in the transformed domain, instead perform matching in an encrypted domain (which of course requires the integration of an encryption mechanism); 2) perform matching in an entirely different dataset that does not require a lot of attempts for same user verification; 3) develop schemes that take full cognizance of the non-invertibility of the system, e.g., by incorporating additional protection mechanisms to secure the parameters [23]. Gomez et al. [10] gave a comprehensive survey on the inversion of biometric templates with possible ways of surmounting the weakness associated with the related attacks. One of such attacks is launched through perceptron learning [7]. A deep secure quantization approach [5], genetic algorithm [28], and constraint optimization approach [34] are some of the recent works aimed at preventing such attacks. Another survey by Dong et al. [6] analyzes the distance preserving properties in cancelable biometrics. They also digressed into the security risks in relation to pre-image attacks, and proposed a framework for countering such attacks. Their previous works on random projection [15] [2], index-of-max hashing [16], and kernalized hashing [20] are however, susceptible to similarity-based attacks. A cryptanalysis conducted by Ghamman et al. [9] also proves the vulnerability of [16].

Proposed scheme
First, the minutiae feature descriptor, popularly known as Minutiae Cylinder Code (MCC) [3] is employed to extract fingerprint vector features, and a fixed length representation technique using Kernel Principle Component Analysis (KPCA) [18] to convert the extracted feature descriptors into fixed-length vectors is applied. We choose to use MCC feature descriptor due to its invariance property and its capability of local minutiae matching, which leads to high performance accuracy during authentication. The accuracy is also retained after feature transformation using KPCA, which has also proven better performance and accuracy preservation than other descriptors [12] [1].

Feature Extraction with MCC
This is done by capturing the directional and spatial relationship between the reference minutiae m r = {p r , q r , θ r }. For p r and q r denotes the minutiae point location, while θ r represents the minutiae orientation. Their corresponding aligned neighbor minutiae m t = {p t i , q i t, θ ′ i t|i = 1, ..., N − 1} is within the selected pre-defined radius R. The extraction technique mainly relies on a robust discretization of the neighborhood of each minutia into a 3D cell-based structure known as the cylinder, as each cylinder is discretized into a number of cells. Hence, a numerical value is computed from each cell based on the likelihood of finding minutiae that are closer to the cell with respect to location and direction. MCC is a prominent fingerprint recognition technique based on minutiae template. Due to its cylinder invariance, fixedlength binary string, and bit-oriented coding, it provides us with the perfect suitability for achieving non-invertibility, cancelability and unlinkability of our proposed template protection technique.
Generate the feature vector: In order to reduce the dimension of the binary strings derived from MCC, KPCA is employed for such purpose. To achieve this, MCC descriptor variable size is converted into a fixed-length vector representation. Given Φ = Φ l (i)|i = 1, ...N l as the set of MCC training samples, where N l is the total number of Φ l , the kernel matrix of the fixed features F k ∈ Q v l ×v l is computed with its resultant function as given in Eq. 1 below.
where D sMCC denotes the MCC dissimilarity measure, given σ 2 as the speed factor. The eigenvectors of KPCA projection matrix P r ∈ Q v l ×d is derived as in [31], where d represents the output dimension of a considerate desired projection. Then, a query instance of the MCC given as Φ q is used to match with all the training samples Φ l (i), in order to generate a vector v ∈ Q v l . v can then be transformed using the initial kernel function to have

Feature vector permutation
The generated fixed-length vectors from KPCA are used as the input to our protection mechanism. For each of the derived vectors v ∈ Q N l and T ∈ Q N l ×d , we utilized an instance of LSH [4] from the function h(.) to generate h i together with a permutation set [P θ ]. Lets assume the parent fingerprint feature vector ω = v ′ T ∈ Q d and an n independent LSH family hash function denoted by h i (ω) ∈ [1, b]|i = 1, ..., n, where each hash function consti-tutes a product function. Therefore, for each h i (ω), p independent random permutation seeds are generated to make up the permutation set [P θ ]. Consequently, ω is permuted so as to get the permuted vectorsω k = Q d |k = 1, ..., p. Next, a hash sample h (ω k i) is formed by performing n times permutation of randomly independent enrolled vectors. Hence, h (ω k i) yields n number of permuted feature vector h (ω k i) ∈ Q v l |i = 1, ..., n.
Sampling bit location: The hash generation procedure can be denoted by the function F which constitutes of the randomly sampled bit location ξ of each permuted hash vector h (ω k i) . Thus, each hash sample can be denoted by Eq. 2 below.
We extract the bits θ bits corresponding to each marked po-

Non-invertible hash component
Even though the randomized permutation of the enrolled vectors in the previous step can provide us with sufficient security, we still consider storing C (i,n) in the plain as insecure because an attacker can make use of the vector components to effectively infer to the feature vectors in each of the components available in the marked position. To avoid such scenario from occurring, a security parameter S k is introduced such that S k : L ow ≤ S k ≤ H igh for all permuted vector components. L ow and H igh represent the predefined lowest and highest values of the given threshold, respectively. This threshold is also tied to the accuracy preservation of the scheme. Hence, eliminating or limiting the tradeoff impact between accuracy and non-invertibility. Consequently, S k can be incorporated into each vector component with respect to their bit location using Eq. 3 below.
Next, we perform a random search via a shift-max order process on the entire hash component H C (i,n) by taking the index of the maximum value from the 1st two elements (in which one of them must be the highest in the entire hash component). We term this as the shift-max value order scenario. Each component H C (i,n) consists of m number of elements with a fixed window size k. Thus, H C (i,n) can be ,n) , ..., H C m (i,n) and m = l/k, where l denotes the length of the vector component. In the first order shifting, each H C 1 (i,n) is shifted in a sequentially cyclical order in each of the hash component H C (i,n) , until the last element H C m (i,n) . The entire shifting procedure can be represented by the matrix in Eq. 4. . . . . where are the first and last components constituting the entire elements of a given k − size window, while m × k denote the size of the entire M shif t matrix.
After selecting the highest value from the 1st two elements , it is then passed on to the second component H C 2 (i,n) , until the entire component is searched whilst preserving the bits position of the selected elements (i.e., shifting bits corresponding to each element in the vector components according to the matrix order). From the second component, the highest value of h ′ i from each component is thus passed to the hash bin H bin for final hash construction. As such, the randomized permutation, security parameter S k , coupled with the shift-max value procedure, all contribute to the non-invertibility of the templates. Fig. 1 illustrate the entire hash generation procedure at both enrollment and querying stages. Final hash construction: In order to construct the final hash code, we take the index of the highest value from the bin such that for each h ′ i ∈ H bin , we have; for h ′ i ∈ H bin and y ′ i ∈ H bin , where H bin denotes the hash bin, and y ′ i denote the index of the highest value in the bin. The highest value is then recorded in the first k − size window and its index value is stored. Therefore, we will have θ h ′ Similarity score: A similarity score is used to evaluate the comparison between the reference (enrolled) and probe (queried) hash codes of the proposed scheme. Since LSH instance is used to ascertain the similarity of permuted vector features within the inherent set of ordered elements, whereby their hash is directly dependent on their relative distances, we therefore cannot opt for traditional similarity measures that does not support such ordering. Instead, the global similarity is estimated between the enrolled and queried hash codes by computing the number of elements within each component that matches with the two sets. Each set here correspond to the correlation order of each index of the maximum value over k − size window. In order to enhance security, matching between the enrolled and queried vectors is still conducted in the transformed domain, but by taking into cognizance the similarity between feature vectors with respect to the shifting process, which might be argued of being prone to similarity-based attacks (Our future work will give an in-depth analysis on this). ,2) , ..., h ′′ C (j,n) be the enrolled and queried instances of the non-invertible hash components, respectively. Thus, the two sets of hash components from h ′′ C (i,n) and h ′′ C (j,n) can be given as: . Therefore, Hence, the similarity between E h ′′ C (i,n) and Q h ′′ C (j,n) indicates a high probability, while their dissimilarity indicates a less collision probability. Consequently, a normalized similarity correlation score is derived by dividing the number of matches between the two components with their set cardinality. The similarity correlation between the two hash codes can be given as: where V ′ l = V l /k for each V l denoting a single vector element from the vector component, r is the correlation order of each index, and b is the index of maximum value over k − size window. This b can be selected via a k − 1 entries that are less than b in both the enrolled and queried hash codes, which helps determine the exact similarity between two hash codes and consequently assist with the selection of the maximum element within a hash component.

Experiments
In this section, we performed an extensive evaluation of the proposed template protection scheme over all six public fingerprint datasets which includes, FVC2002 (DB1, DB2, and DB3), as well as FVC2004 (DB1, DB2, and DB3). Each dataset contains 800 fingerprints of varying quality collected from 100 users with 8 impressions per user. Verifinger SDK is utilized for the extraction of ISOcompliant minutiae information which was further feed to MCC. Four major parameters including security threshold S key , window size k, Hashvecs H C (i,n) , and number of elements in each vector N um perm are assigned specific values with respect to analyzing the accuracy of the proposed scheme. Also, the security and privacy analysis including non-invertibility, cancelability/revocability, and unlinkability, were all carried out in order to evaluate the efficacy of the proposed scheme.
Different performance measures are used for the evaluation. These are the False Match Rate (FMR), False Non-Match Rate (FNMR), and Equal Error Rate (EER). FMR results from the decision threshold of a biometric system to misinterpret the probability of two different impressions from two fingers as an impression of one finger, while FNMR results from the decision of the system to misinterpret the probability of two different impressions from one finger as an impression of two fingers. The common value between FMR and FNMR is the ERR, which determines the accuracy of the scheme. (i.e., the error rate when FMR = FNMR). Likewise, the Genuine Match Rate (GMR) is akin to the FMR when GMR + FMR = 1. We employed the original FVC protocol for all evaluations and analysis.

Effect of security threshold S key and window size k
In this analysis, the number of hash vector H C (i,n) in each component C (i,n) (component size) is set at 10, while the number of vector elements is set at 500. The affected parameters i.e., window size k and security threshold S key are set within the specified range of k = 75, 100, 125, 150, and S key = 2, 6, 10, 14, 18, 22, 26, 30, respectively. Fig. 2. shows the overall plots analysis against FMR and FNMR with the initials m and n as depicted on their distributions (K, S), respectively. All six datasets of FVC2002 and FVC2004 are utilized for the evaluation. It can be seen that lower S key and higher k generally exhibits better accuracy as compared to higher S key and lower k. This proves the sensitivity of the generated hash codes w.r.t the defined security threshold. Also, DB1 & DB2 of FVC2002, and DB1 of FVC2004 depicts a better performance than the other datasets.

Performance Accuracy and Comparison with other state-of-the-arts
In addition to the evaluations with respect to the effect of different parameters, we also analyze the matching performance of the scheme under lost-key scenario using the FVC protocol, in relation to the GMR and FMR. All six datasets are used for the experiment by keeping the window size k at 100, N um perm at 500. The security threshold S key is however adjusted from 2 to 30 according to the previous experimentation while keeping the hash vector at 5. A detailed description of the evaluation is given in Table 1 Table 2 shows the performance comparison between the proposed method and other state-of-the-art existing cancelable templates schemes with protection and their corresponding transformed version before the incorpo-ration of protection mechanism. It can be seen from   The EER of all 3 approaches from same features is depicted in Fig. 3, with MCC as unprotected, fixed-length vector as transformed, and the proposed scheme as protected. It can be seen that the protected scheme generally outperforms both unprotected and transformed version in BD1 of FVC2004, whilst being outperformed by its counterparts in DB2 and DB3 of same database. This certainly has to do with the low identifiable correlation within different el-ements in the components of these datasets, which in same vain emanates from the distorted or low-quality images in the datasets. In FVC2002 however, the protected version performs better than its unprotected counterpart in DB1 and DB2. But is slightly outperformed by the transformed version, which of course has to do with the incorporation of security mechanisms. Let's also not forget that the rigorous search for a maximum value between the 1st two elements of each components has a role to play in reducing the accuracy performance of the protected templates. Overall, 2PMCC 16,16 shows the worst performance on schemes incorporated with a template protection mechanism, TKPCA-DQ depicts the worse performance on schemes without a template protection mechanism, while the fixed length (transformed) version performs best among the three techniques from same features. Also, it is worth mentioning that due to the randomness (caused by random vector permutation) and iterative reshuffling (caused by shifting procedure) of the mechanism, a difference of 0.1 to 0.5 is noticed at each specific feature reconstruction of the protected template when a loop iteration without pre-allocation is allowed. This certainly confirms the sensitivity of the hash code and the entire security mechanism of the scheme.

Revocability
Revocability is an important property of cancelable biometrics which pertains to the security of a biometric system. When the original stored biometric template is compromised, it is expected by the cancelable system to re-generate uncorrelated templates from same fingerprint. Thus, further ensuring that the reissued templates from same fingerprint are not correlated despite being generated from the same biometric data. To test the revocability of the proposed scheme, transformed templates are generated from first impression of each finger using different randomly generated keys. Same process is repeatedly applied to DB1 of FVC2002 by matching the pseudo-imposter templates against its imposter and genuine counterparts. The mean for both pseudo-impostor and impostor distributions are set at 0.35. Fig. 4 shows the distributions of pseudo-impostor, impostor, and genuine scores of the dataset. We can see from the figure that the distributions of pseudo-impostor and impostor overlap, while being completely unrelated to the genuine distributions. This signifies that the reissued version of the fingerprint templates are uncorrelated despite coming from same source.

Unlinkability
Unlinkability is another important property of cancelable biometrics which relates to the privacy of the biometric data. To measure the unlinkability of a cancelable biometric system, it is required that the protected template should not cross-match with the same corresponding unprotected fingerprint on different platforms and/or applications. Two major indicators are used for the evaluation of unlinkability. These are mated and non-mated score distributions. According to the framework [11], mated and non-mated sample score distributions measure the system's unlinkability at both local and global level. Calculating the mated sample scores is mainly performed by comparing the templates that are extracted from fingers with same impression using different keys, while non-mated scores are computed by comparing templates that are extracted from fingers with different impressions using different keys. Unlinkability analysis of the scheme is conducted on DB1 of FVC2002 dataset. The same mean value used in revocability is also maintained here. The score distributions between mated and non-mated samples can be seen in Fig.  5, which revealed a significant overlap. Thus, indicating the unlinkability of the scheme.

Conclusions and Future work
We have introduced a novel approach for the construction of cancelable and non-invertible fingerprint hash codes using vector permutation and a shift-order process. Particularly, the security mechanism of the scheme against non-invertibility and similarity-based attacks is improved through the integration of shift-order process. Performance accuracy of the scheme outperforms other state-of-the-art recognition systems that comes with, and without the incorporation of security mechanisms. The scheme also satisfy other properties of cancelable biometrics.
Future work will cover security analysis of the scheme against similarity-based attacks, non-invertiblity, and other important security threats. We will also prove that the scheme is able to alleviate the similarity preservation drawback between hash spaces. Consequently, we shall further build upon the shift-ordering procedure by incorporating homomorphic encryption to avert all shortcomings associated with matching in the transformed domain. Instead, matching will be performed in the encrypted domain.