# On the Unlinkability of Fingerprint Shell

Authors: Sanghoon Lee; Ik Rae Jeong
Journal: Security and Communication Networks
 (2020)

---

## Abstract

To prevent the leakage of original biometric information of a user, it may be transformed into a cancelable form. A cancelable biometric transformation should satisfy four requirements: unlinkability, revocability, noninvertibility, and performance. In 2014, Moujahdi et al. proposed a new cancelable fingerprint transformation called fingerprint shell, which was also later discussed by Ali et al. In this paper, we show that all of the shell fingerprint schemes presented by Moujahdi et al. and Ali et al. do not satisfy the condition of unlinkability.


---

## Body

## 1. Introduction

The development of sensor technology has made it easier to use biometric recognition systems, and as a result, the demand for biometric authentication has increased sharply in devices such as smart phones and tablets. Biometric authentication is simpler and more convenient than other authentication methods using the secret user information.However, biometric information cannot be replaced if it is compromised or exposed, meaning that it must be protected [1, 2]. In feature transformation schemes, biometric information is transformed into a protected biometric template using the transformation function stored on a server. During the verification process, queried biometric information is also transformed using the same function and a matching score is calculated between the stored transformed template on the server and the queried transformed template to determine the validity of the information.According to the property of transformation functions, feature transformation can be classified two ways: noninvertible transformation [3, 4] and salting [5, 6]. The noninvertible transformation applies a one-way function such as a hash function to the original biometric information. It should be computationally difficult to reconstruct the original biometric information from the transformed template even if the parameters of the functions are revealed. Salting is an invertible transformation that uses a user-specific key. That is, if an adversary obtained both the user key and the transformed template, they could recover the original biometric information.The noninvertible feature transformation methods must meet the following properties [7]:(i)
Revocability: it should be possible to revoke and replace the transformed template. This is necessary because if the transformed biometric template were to become compromised, it should be revoked and replaced with a new one based on the biometric information of the same user.(ii)
Unlinkability: it should be impossible to link transformed templates derived from the same user. This is necessary because if the user were to make a new transformed template after the user’s old transformed template is revoked, it is desirable for the two transformed templates to look independent.(iii)
Noninvertibility: it must be computationally difficult to discern the original template from the transformed template. Consequently, template matching must be done between the transformed templates.(iv)
Performance: the performance of biometric recognition using template transformation should be plausibly efficient compared to the performance of biometric recognition without transformation.The unlinkability is often called diversity [8, 9]. Diversity means that it is necessary to be able to generate diverse templates in one fingerprint, and there should be no relation between them. In addition, cross-matching should not be possible between templates in different applications. In other words, it is called unlinkability. We use unlinkability, which is more intuitive than diversity.Recently, as various biometric traits such as ECG (electrocardiogram) and speech are widely used, concern about security has increased. Chee et al. proposed the speech template protection technique using the cancelable transform, called Random Binary Orthogonal Matrices Projection (RBOMP) hashing [10]. Wu et al. generated cancelable ECG templates with a subspace-based approach, MUSIC algorithm [11]. Some attacks have also been studied for cancelable biometric templates such as zero effort attack, inversion attack, ARM (attacks via record multiplicity), and similarity-based attack [8, 12]. Dong et al. proposed a similarity-based attack framework that can be applied to any cancelable biometric templates [13].In 2014, Moujahdi et al. proposed a new noninvertible feature transformation scheme for minutiae-based fingerprint recognition called fingerprint shell [9]. Ali and Prakash proposed new fingerprint shell schemes [14, 15]. We propose a method to extract the original distance that should be protected from the fingerprint shell and use the framework to quantify how unsafe the shells are in this method. As a result, we show that the shells do not satisfy the condition of unlinkability.


## 2. Review of Fingerprint Shell

The basic idea of the fingerprint shell is to make a spiral curve using the information extracted from minutiae and singular points of a user. The process of making a fingerprint shell is as follows:(1)
Minutiae and singular points are extracted from the fingerprint of a user.(2)
For each singular point, the distance between each minutiae and singular point is calculated. We note that the distances are not changed by shifting or rotating a fingerprint image. We also note that the number of curves will be equal to the number of singular points.(3)
Suppose there aren minutiae points. Then, d1,d2,…,dn are n distances from a singular point to the minutiae. The distances are sorted in an ascending order.(4)
The sorted distances and user keyd0 are used to construct the hypotenuse of a number of adjacent right triangles (Figures 1 and 2). It should be noted that user key d0 is added to all extracted distances di before triangle construction. hi represents the length of the height of the triangle, which is calculated with the Pythagorean theorem. The hypotenuse of the previous triangle becomes the base of the proceeding triangle. As a result, except the initial triangle, all subsequent triangles rotate by the accumulated angle.(5)
Finally, the fingerprint shell template consists of the top vertices of the triangles, which are stored as transformed templates.Figure 1
Simple example of fingerprint shell construction.Figure 2
Fingerprint shell construction algorithm.For example, suppose that a fingerprint has two minutiae with3,2 and 5,7 and singular point with 5,5 coordinates. The sorted distances, d1 and d2, between the minutiae and the singular point are 2 and 13. Suppose also that a fingerprint shell is made using user key d0=1.5. Then, DIS1,DIS2,DIS3,h1,h2, and θ1,θ2 are 1.5,3.5,1.5+13,10,3+313, and 0,1.1279, respectively. Therefore, each point of the fingerprint shell to be stored is 1.5,10 and −1.8585,4.7533.In the verification, the fingerprint shell template is created from a query fingerprint and it is compared with the enrolled fingerprint shell using theHausdorff distance. The Hausdorff distance between two sets A and B is defined as HDA,B=maxhA,B,hB,A, where hA,B=maxa∈Aminb∈Ba−b and ⋅ is an Euclidean distance.


## 3. Analysis of Unlinkability of Fingerprint Shell

In this section, we show that the fingerprint shell does not satisfy unlinkability. We first show that we can extract a user’s secret key from the fingerprint shell of the user, if the fingerprint shell is revealed. And we show that the fingerprint shell does not satisfy the condition of unlinkability either.


### 3.1. Extraction of User Key

In [9], the authors proposed a new template representation for fingerprint feature protection. Due to design problems, however, the user private key used to create the fingerprint shell is easily exposed. The fingerprint shell used di+d0 to protect di, the features of user fingerprint. It is not difficult to reconstruct di using an exposed user private key d0 because it uses simple addition operations. It can be done without any additional information besides the fingerprint shell. The fingerprint shell is stored on the server without any additional cryptographic operations because of the cancelable template property. Thus, if an attacker gets a fingerprint shell from the server, it causes key exposure and template linkable.The first pointx1,y1 in Figure 3) in the fingerprint shell is the top vertex of the first triangle. In the first triangle, the length of the base is d0 (as same as x1 in Figure 3), the length of the hypotenuse is d1+d0, and the length of the height is d1+d02−d02 (as same as y1 in Figure 3). Therefore, the coordinates of the first point are x1,y1=d0,d1+d02+d02 (Figure 3). As a result, we can easily obtain the user key d0=x1 from the first point of the fingerprint shell. Furthermore, since the distances between each point in the fingerprint shell and origin point are in the form of d0+di, we can reconstruct di from the given fingerprint shell by extracting d0 as described above (Figure 4).Figure 3
Example of fingerprint shell.Figure 4
Distance extraction algorithm.


### 3.2. Linkability of the Fingerprint Shell

Unlinkability is defined by ISO/IEC 24745 : 2011 as “a property of two or more biometric references that cannot be linked to each other or to the subject(s) from which they were derived” [16].In [17], the authors proposed a framework to evaluate linkability. This framework defines mated and nonmated samples as two types of score distributions. The mated sample distribution is a set of scores computed between two templates from the same user. The nonmated sample distribution is made using scores computed between two templates from two different users. As shown in Figure 5, the sample distributions can be used to distinguish three different levels of linkability: fully unlinkable, fully linkable, and semilinkable. Figure 5(a) shows that the mated sample distribution with different keys (cross-matching) is identical to the nonmated sample distribution. It means that similarity scores between templates from the same finger using different keys are indistinguishable from similarity scores between different fingers. This is referred to as fully unlinkable. Under a fully linkable scenario, the mated sample and nonmated sample distributions are completely separable (Figure 5(c)). Thus, given the two templates, we can distinguish templates whether they originated from the same finger or different fingers. Semilinkable means that they were linked only for a subset of the templates. In the overlapping part of the mate sample and nonmated sample distributions (Figure 5(b)), it is impossible to differentiate which templates are from the same or different fingers.Figure 5
Sample distributions for different levels of linkability. (a) Fully unlinkable. (b) Semilinkable. (c) Fully linkable.
(a)
(b)
(c)We measured the unlinkability of the fingerprint shell using the framework in [17]. The experiments were executed on four FVC2002 databases (DB1, DB2, DB3, and DB4) [18]. Each database contains 100 fingers with 8 impressions each. A linkage score calculated for two fingerprint shells, FS1 and FS2, is HDD1′,D2′, where HD⋅ is the Hausdorff distance and D1′ and D2′ are the extracted distance sets from FS1 and FS2 using Figure 4, respectively. If the given fingerprint shell FS1 and FS2 are the mated samples, the Hausdorff distance is small. Otherwise, the Hausdorff distance is large.For the linkability test, we generated51 fingerprint shells from the first impression of each finger using different user keys. Then, one of them is selected as a reference and compared against the remaining fingerprint shells of the same finger (i.e., 5000 attempts). Figure 6 represents the sample distributions for each FVC2002 database. It can be seen that the mated and nonmated distributions are clearly separated in all of the databases. In other words, the fingerprint shell is fully linkable on these four FVC2002 databases.Figure 6
Sample distributions of the fingerprint shell on (a) FVC2002 DB1. (b) FVC2002 DB2. (c) FVC2002 DB3. (d) FVC2002 DB4.
(a)
(b)
(c)
(d)


### 3.3. Linkability of Enhanced Fingerprint Shell

Ali and Prakash proposed the enhanced fingerprint shell scheme in [14]. Their method is a two-step process of fingerprint shell construction and shell translation that uses two keys. The first step uses one of the key pairs to create a fingerprint shell that essentially replicates the original fingerprint shell construction. The next step is to add k0×sink0,k0×cosk0, which is generated by the second key k0 of the key pair, to all points in the created fingerprint shell.For example, suppose that a fingerprint shell which is created in Section2 is used to construct an enhanced fingerprint shell and a second user key k0 used to shift the fingerprint shell is 1.2. For translation k0×sink0,k0×cosk0=1.1184,0.4348 is added to all points of the fingerprint shell. Then, each point of the enhanced fingerprint shell to be stored is 1.5+1.1184,10+0.4348=2.6184,3.5971 and −1.8585+1.1184,3.7533+0.4348=−0.7401,4.1881.They wanted to enhance the security of the original fingerprint shell scheme with the additional key. However, it is not difficult to reconstruct the original fingerprint shell from a shell of the Ali and Prakash scheme [14]. The shell of Ali and Prakash’s scheme consists of right angle triangles [14]. Therefore, we can calculate the origin of the shell by finding intersection of perpendicular lines to connecting lines of neighboring shell points (Figure 7). The lines can be expressed as follows:(1)li=aix+bi,(2)li⊥=−1aix+ki.Figure 7
Shell origin calculation.Theli in (1) is an equation connecting Pi and Pi+1, and the li⊥ in (2) is an equation perpendicular to li passing through Pi (Figure 7). The shifted origin is an intersection of the perpendicular lines li⊥.Even if we do not know the second key of the key pair, we can recover the original fingerprint shell with only one key if the origin of the shell from Ali and Prakash’s scheme is moved to the coordinate origin [14]. The translated shell is exactly the same as the original fingerprint shell [9]. Therefore, Ali and Prakash’s scheme in [14] also shows that it does not provide unlinkability in the same method as the previous section.


### 3.4. Linkability of 3D Secured Fingerprint Shell

Ali and Prakash also proposed a new 3D fingerprint shell scheme based on the fingerprint shell [15]. They used an angle in addition to the distance between singular and minutia. It is used to generate a new secured distance, li. The set of li and user key l0 are used to generate a new one. The generated shell is rotated in the xy plane and xz plane using the user key s0 and l0, respectively, and translated using the user key k0 (see Figure 8). However, this algorithm is also vulnerable.Figure 8
The 3D transformation of [11]. (a) Initial spiral curve. (b) Spiral curve translation using user key s0,l0, and k0.
(a)
(b)Translate the transformed 3D curve so that the first point of the curve is the origin and project each point on the curve to thexy plane such that the distance to the origin is maintained. Then, using the origin calculation of the previous chapter, we can get the shell before the translation, as shown in Figure 9(b). As mentioned earlier, we can easily recover the li from the shell. The li is as follows:(3)li=di2+s02+2di×s0×cosθi.Figure 9
Basic components of [11]. (a) Computation of secured distance. (b) Computation of spiral curve.
(a)
(b)Suppose that the attacker has three different databases,DBA,DBB, and DBC. Let li extracted from the template of each database be li,A, li,B, and li,C. If li,A, li,B, and li,C are made from the same di and θi, then two equations can be obtained as follows:(4)li,A2−li,B2=di2+s0,A2+2di×s0,A×cosθi−di2−s0,B2−2di×s0,B×cosθi,li,A2−li,C2=di2+s0,A2+2di×s0,A×cosθi−di2−s0,C2−2di×s0,C×cosθi.We know thes0,A, s0,B, and s0,C through the inverse operation of the rotation in calculating li from the new 3D shell. Equation (4) can be transformed as follows:(5)li,A2−li,B2−s0,A2−s0,B22s0,A−s0,B=di×cosθi,li,A2−li,C2−s0,A2−s0,C22s0,A−s0,C=di×cosθi.The left side of equation (5) consists of the known values. So, the values obtained from the template of each database are calculated by using the left side of equation (5) and compared to determine whether the user is the same user.


## 3.1. Extraction of User Key

In [9], the authors proposed a new template representation for fingerprint feature protection. Due to design problems, however, the user private key used to create the fingerprint shell is easily exposed. The fingerprint shell used di+d0 to protect di, the features of user fingerprint. It is not difficult to reconstruct di using an exposed user private key d0 because it uses simple addition operations. It can be done without any additional information besides the fingerprint shell. The fingerprint shell is stored on the server without any additional cryptographic operations because of the cancelable template property. Thus, if an attacker gets a fingerprint shell from the server, it causes key exposure and template linkable.The first pointx1,y1 in Figure 3) in the fingerprint shell is the top vertex of the first triangle. In the first triangle, the length of the base is d0 (as same as x1 in Figure 3), the length of the hypotenuse is d1+d0, and the length of the height is d1+d02−d02 (as same as y1 in Figure 3). Therefore, the coordinates of the first point are x1,y1=d0,d1+d02+d02 (Figure 3). As a result, we can easily obtain the user key d0=x1 from the first point of the fingerprint shell. Furthermore, since the distances between each point in the fingerprint shell and origin point are in the form of d0+di, we can reconstruct di from the given fingerprint shell by extracting d0 as described above (Figure 4).Figure 3
Example of fingerprint shell.Figure 4
Distance extraction algorithm.


## 3.2. Linkability of the Fingerprint Shell

Unlinkability is defined by ISO/IEC 24745 : 2011 as “a property of two or more biometric references that cannot be linked to each other or to the subject(s) from which they were derived” [16].In [17], the authors proposed a framework to evaluate linkability. This framework defines mated and nonmated samples as two types of score distributions. The mated sample distribution is a set of scores computed between two templates from the same user. The nonmated sample distribution is made using scores computed between two templates from two different users. As shown in Figure 5, the sample distributions can be used to distinguish three different levels of linkability: fully unlinkable, fully linkable, and semilinkable. Figure 5(a) shows that the mated sample distribution with different keys (cross-matching) is identical to the nonmated sample distribution. It means that similarity scores between templates from the same finger using different keys are indistinguishable from similarity scores between different fingers. This is referred to as fully unlinkable. Under a fully linkable scenario, the mated sample and nonmated sample distributions are completely separable (Figure 5(c)). Thus, given the two templates, we can distinguish templates whether they originated from the same finger or different fingers. Semilinkable means that they were linked only for a subset of the templates. In the overlapping part of the mate sample and nonmated sample distributions (Figure 5(b)), it is impossible to differentiate which templates are from the same or different fingers.Figure 5
Sample distributions for different levels of linkability. (a) Fully unlinkable. (b) Semilinkable. (c) Fully linkable.
(a)
(b)
(c)We measured the unlinkability of the fingerprint shell using the framework in [17]. The experiments were executed on four FVC2002 databases (DB1, DB2, DB3, and DB4) [18]. Each database contains 100 fingers with 8 impressions each. A linkage score calculated for two fingerprint shells, FS1 and FS2, is HDD1′,D2′, where HD⋅ is the Hausdorff distance and D1′ and D2′ are the extracted distance sets from FS1 and FS2 using Figure 4, respectively. If the given fingerprint shell FS1 and FS2 are the mated samples, the Hausdorff distance is small. Otherwise, the Hausdorff distance is large.For the linkability test, we generated51 fingerprint shells from the first impression of each finger using different user keys. Then, one of them is selected as a reference and compared against the remaining fingerprint shells of the same finger (i.e., 5000 attempts). Figure 6 represents the sample distributions for each FVC2002 database. It can be seen that the mated and nonmated distributions are clearly separated in all of the databases. In other words, the fingerprint shell is fully linkable on these four FVC2002 databases.Figure 6
Sample distributions of the fingerprint shell on (a) FVC2002 DB1. (b) FVC2002 DB2. (c) FVC2002 DB3. (d) FVC2002 DB4.
(a)
(b)
(c)
(d)


## 3.3. Linkability of Enhanced Fingerprint Shell

Ali and Prakash proposed the enhanced fingerprint shell scheme in [14]. Their method is a two-step process of fingerprint shell construction and shell translation that uses two keys. The first step uses one of the key pairs to create a fingerprint shell that essentially replicates the original fingerprint shell construction. The next step is to add k0×sink0,k0×cosk0, which is generated by the second key k0 of the key pair, to all points in the created fingerprint shell.For example, suppose that a fingerprint shell which is created in Section2 is used to construct an enhanced fingerprint shell and a second user key k0 used to shift the fingerprint shell is 1.2. For translation k0×sink0,k0×cosk0=1.1184,0.4348 is added to all points of the fingerprint shell. Then, each point of the enhanced fingerprint shell to be stored is 1.5+1.1184,10+0.4348=2.6184,3.5971 and −1.8585+1.1184,3.7533+0.4348=−0.7401,4.1881.They wanted to enhance the security of the original fingerprint shell scheme with the additional key. However, it is not difficult to reconstruct the original fingerprint shell from a shell of the Ali and Prakash scheme [14]. The shell of Ali and Prakash’s scheme consists of right angle triangles [14]. Therefore, we can calculate the origin of the shell by finding intersection of perpendicular lines to connecting lines of neighboring shell points (Figure 7). The lines can be expressed as follows:(1)li=aix+bi,(2)li⊥=−1aix+ki.Figure 7
Shell origin calculation.Theli in (1) is an equation connecting Pi and Pi+1, and the li⊥ in (2) is an equation perpendicular to li passing through Pi (Figure 7). The shifted origin is an intersection of the perpendicular lines li⊥.Even if we do not know the second key of the key pair, we can recover the original fingerprint shell with only one key if the origin of the shell from Ali and Prakash’s scheme is moved to the coordinate origin [14]. The translated shell is exactly the same as the original fingerprint shell [9]. Therefore, Ali and Prakash’s scheme in [14] also shows that it does not provide unlinkability in the same method as the previous section.


## 3.4. Linkability of 3D Secured Fingerprint Shell

Ali and Prakash also proposed a new 3D fingerprint shell scheme based on the fingerprint shell [15]. They used an angle in addition to the distance between singular and minutia. It is used to generate a new secured distance, li. The set of li and user key l0 are used to generate a new one. The generated shell is rotated in the xy plane and xz plane using the user key s0 and l0, respectively, and translated using the user key k0 (see Figure 8). However, this algorithm is also vulnerable.Figure 8
The 3D transformation of [11]. (a) Initial spiral curve. (b) Spiral curve translation using user key s0,l0, and k0.
(a)
(b)Translate the transformed 3D curve so that the first point of the curve is the origin and project each point on the curve to thexy plane such that the distance to the origin is maintained. Then, using the origin calculation of the previous chapter, we can get the shell before the translation, as shown in Figure 9(b). As mentioned earlier, we can easily recover the li from the shell. The li is as follows:(3)li=di2+s02+2di×s0×cosθi.Figure 9
Basic components of [11]. (a) Computation of secured distance. (b) Computation of spiral curve.
(a)
(b)Suppose that the attacker has three different databases,DBA,DBB, and DBC. Let li extracted from the template of each database be li,A, li,B, and li,C. If li,A, li,B, and li,C are made from the same di and θi, then two equations can be obtained as follows:(4)li,A2−li,B2=di2+s0,A2+2di×s0,A×cosθi−di2−s0,B2−2di×s0,B×cosθi,li,A2−li,C2=di2+s0,A2+2di×s0,A×cosθi−di2−s0,C2−2di×s0,C×cosθi.We know thes0,A, s0,B, and s0,C through the inverse operation of the rotation in calculating li from the new 3D shell. Equation (4) can be transformed as follows:(5)li,A2−li,B2−s0,A2−s0,B22s0,A−s0,B=di×cosθi,li,A2−li,C2−s0,A2−s0,C22s0,A−s0,C=di×cosθi.The left side of equation (5) consists of the known values. So, the values obtained from the template of each database are calculated by using the left side of equation (5) and compared to determine whether the user is the same user.


## 4. Conclusions

Moujahdi et al. proposed a new noninvertible fingerprint transformation method called the fingerprint shell in [9] and Ali and Prakash proposed an enhanced fingerprint shell scheme in [14] and a new 3D fingerprint shell scheme in [15]. All the schemes present low computational cost and high levels of accuracy and are less sensitive to rotating fingerprint images.However, the accuracy of these three schemes depends on a technique of singular point extraction. The singular point extraction is challenged with low quality images [19]. Table 1 shows the number of images used for experiments in [15]. For FVC2002 DB3 and FVC2004 DB2, only about 750 of 800 were used. The authors in [15] observed that the singular point extraction had filed for about 50 images due to the low image quality and excluded those low-quality images in the experiments. Therefore, the fingerprint shell schemes might not be adequate for the low-quality images. Besides, we showed that all the fingerprint shell schemes of [9, 14, 15] do not provide unlinkability. That is, we have shown that we can construct a distinguisher which can tell whether the two fingerprint shells are from the same user or different users with a high degree of success.Table 1
The number of images used for experiments.
FVC2002 DB1
FVC2002 DB2
FVC2002 DB3
FVC2004 DB2
[11]
799
797
757
750These problems come from using invertible operations such as translation, addition, and linear geometric transformation in making cancelable templates. To make secure and unlinkable templates, the cancelable template generation algorithms must use the nonlinear and noninvertible operations such as the many-to-one mapping and functional transformation in [20].As a future work, it would be interesting to construct a new fingerprint shell scheme providing unlinkability.



---

*Source: 8256929-2020-03-04.xml*