# How can I perform matching on an “encrypted- fingerprint feature matrix” using Fully Homomorphic Encryption?

I am doing a finger-print authentication process. The feature-extraction using minutiae has been done and I get an N x 6 matrix, where the 6 columns are {$x_i$ ,$y_i$, crossing number of the $i$th minutiae, orientation of $i_{th}$ minutiae, rest 2 columns are not used for matching}. The first two are (x,y) co-ordinates of the ith minutiae point detected. The crossing number detects the type of minutiae (ridge=1,bifurcation=3).

I want to encrypt this matrix. Perform matching in the encrypted domain and send the result back in encrypted form (like a ).

The following is an example of the simple matching program code in C (without any encryption)…

The feature matrices which are got as output after the feature extraction are t1 and t2. The values can be seen assigned to matrix t1 and t2 in the program. These are the feature vectors of 101_1.tif and 101_2.tif from FVC2002 Database. (images of same person). It gives output as similarity score of 0.7 (out of 1), which means the images match.

Another thing observed from the 80 images database is that on applying the feature extraction the maximum value for "N" (the number of features) is 82. That is, the row size is max. 82 and column size is always 6 (fixed). Here is the program (in C for matching):

#include stdio.h
#include math.h

float t1[26][6]= {216.0000,46.0000, 3.0000, 0.5030,0, 1.0000,190.0000,49.0000, 1.0000, 3.5827,0, 1.0000,146.0000,64.0000, 1.0000, 3.2684,0, 1.0000,247.0000,80.0000, 1.0000, 0.7002,0, 1.0000,173.0000,86.0000, 1.0000, 0.3666,0, 1.0000,302.0000,93.0000, 1.0000, 0.8372,0, 1.0000,176.0000,127.0000, 3.0000, 0.2761,0, 1.0000,227.0000,131.0000, 3.0000, 0.5634,0, 1.0000,164.0000,135.0000, 1.0000, 3.3159,0, 1.0000,117.0000,140.0000, 1.0000, 5.7642,0, 1.0000,216.0000,169.0000, 1.0000, 0.7320,0, 1.0000,256.0000,170.0000, 3.0000, 3.8934,0, 1.0000,196.0000,181.0000, 1.0000, 3.7386,0, 1.0000,176.0000,187.0000, 3.0000, 0.4613,0, 1.0000,151.0000,195.0000, 1.0000, 5.7175,0, 1.0000,285.0000,215.0000, 3.0000, 0.7886,0, 1.0000,227.0000,218.0000, 1.0000, 0.8161,0, 1.0000,152.0000,219.0000, 1.0000, 2.2884,0, 1.0000,169.0000,233.0000, 1.0000, 4.1407,0, 1.0000,147.0000,242.0000, 1.0000, 4.6064,0, 1.0000,186.0000,250.0000, 1.0000, 4.1676,0, 1.0000,240.0000,332.0000, 1.0000, 0.4986,0, 1.0000,165.0000,227.0000, 5.0000,0,0, 1.0000,72.0000,360.0000, 7.0000,0,1.0000,1.0000,324.0000,12.0000, 7.0000,0, 1.0000, 1.0000,120.0000,312.0000, 7.0000,0, 1.0000, 1.0000};

float t2[19][6]= {190.0000,45.0000,3.0000,0.5896,0,1.0000
,139.0000,46.0000,3.0000,0.1600,0,1.0000
,126.0000,54.0000,1.0000,3.3025,0,1.0000
,79.0000,64.0000,1.0000,5.7130,0,1.0000
,181.0000,83.0000,1.0000,0.6658,0,1.0000
,219.0000,84.0000,3.0000,3.9261,0,1.0000
,159.0000,98.0000,1.0000,3.7340,0,1.0000
,136.0000,110.0000,1.0000,0.2556,0,1.0000
,118.0000,115.0000,1.0000,5.8276,0,1.0000
,248.0000,130.0000,3.0000,0.8766,0,1.0000
,192.0000,134.0000,1.0000,0.8088,0,1.0000
,117.0000,137.0000,1.0000,2.3575,0,1.0000
,132.0000,150.0000,3.0000,2.4106,0,1.0000
,111.0000,164.0000,1.0000,4.6623,0,1.0000
,149.0000,169.0000,1.0000,4.1655,0,1.0000
,129.0000,148.0000,5.0000,0,0,1.0000
,60.0000,264.0000,7.0000,0,1.0000,1.0000
,276.0000,264.0000,7.0000,0,1.0000,1.0000
,84.0000,264.0000,7.0000,0,1.0000,1.0000
};

float t3[30][4],t4[20][4],tnew[30][4];
void transform(float t1[26][6],int i,int flag);
void transform2(float t4[20][4],float thref);
float score(float x1[22][4],float x2[15][4]);

main()
{
float sm=0,S=0;
int i,j,a,i1,j1;
printf("Matching Program\n\n");

for(i=0; i<22; i++)
{
transform(t1,i,1);
for(j=0; j<15; j++)
{
if(t1[i][2]==t2[j][2])
{
transform(t2,j,2);
for(a=-5; a<6; a++)
{
transform2(t4,(a*3.1416/180));
sm=score(t3,tnew);
if(S<sm)
{
S=sm;
}
}
}
}
}
if(S>0.4) printf("Match");
else printf("Mismatch");
}

//COORDINATION TRANSFORM FUNCTION
void transform(float t1[26][6],int i,int flag)
{
float xref,yref,thref;
int k,l,j,c,count,i1,j1;
float b[3][1],t[5][5];
xref=t1[i][0];
yref=t1[i][1];
thref=t1[i][3];
float r[3][3]= {cos(thref),sin(thref),0,-sin(thref),cos(thref),0,0,0,1};
if(flag==1)
count=22;
else if(flag==2)
count=15;
for(i=0; i<count; i++)
{
b[0][0]=t1[i][0]-xref;
b[1][0]=t1[i][1]-yref;
b[2][0]=t1[i][3]-thref;
for(j=0; j<3; j++)
{
for(k=0; k<3; k++)
{
t[j][k]=0;
for(c=0; c<3; c++)
t[j][k]=t[j][k]+(r[j][c]*b[c][k]);
}
}
if(flag==1)
{
for(c=0; c<3; c++)
{
t3[i][c]=t[c][0];
}
t3[i][3]=t1[i][2];
}
if(flag==2)
{
for(c=0; c<3; c++)
{
t4[i][c]=t[c][0];
}
t4[i][3]=t1[i][2];
}
}
}

//COORDINATION TRANSFORM FUNCTION2
void transform2(float t4[20][4],float thref)
{
float r[4][4]= {cos(thref),sin(thref),0,0,-sin(thref),cos(thref),0,0,0,0,1,0,0,0,0,1},b[4][1],t[5][5];
int k,l,i,j,c,i1,j1;
for(i=0; i<15; i++)
{
for(j=0; j<4; j++)
b[j][0]=t4[i][j];
b[2][0]=b[2][0]-thref;
for(j=0; j<4; j++)
{
for(k=0; k<4; k++)
{
t[j][k]=0;
for(c=0; c<4; c++)
t[j][k]=t[j][k]+(r[j][c]*b[c][k]);
}
}
for(j=0; j<4; j++)
{
tnew[i][j]=t[j][0];
}
}
}

//Transformed Minutiae Matching Score
float score(float x1[22][4],float x2[15][4])
{
int i,j,i1,j1;
float n,thres,thres_theta,found,dx,dy,sm;
float dtheta,d;
n=0;
thres=15;
thres_theta=14;
for(i=0; i<22; i++)
{
found=0;
j=0;
while((found==0)&&(j<15))
{
dx=x1[i][0]-x2[j][0];
dy=x1[i][1]-x2[j][1];
d=sqrt(pow(dx,2)+pow(dy,2));
if(d<thres)
{
dtheta=(abs(x1[i][2]-x2[j][2]))*180/3.1416;
if(dtheta>(360-dtheta))
dtheta=360-dtheta;
if(dtheta<thres_theta)
{
n=n+1;
found=1;
}
}
j=j+1;
}
}
sm=sqrt(pow(n,2)/(22*15));
return sm;
}

-

I haven't read over your code entirely, but a quick glance at it tells me you will have a hard time simply "porting"it to something like helib. First, I don't think helib has native support for floating point. Second, functions like sqrt, sin, cos, etc might take a fair amount of work to get going in something like helib even if you had floating point math.

That said, in theory you should be able to perform matching on encrypted fingerprint matrices using homomorphic encryption. The application of HE, however, is still not at a point where it will be super easy and practical to do so.

-
Thank you so much for the reply. . Well i also thought so.. but since I am not an expert i needed to confirm it.. I have just started with helib on github... but it is using c++ which i am not that fond of.. i have tested something like: multiplication, addition, subtraction on cipher texts.. which worked well.. now i am trying with matrices.. but, i couldn't find a way to input the matrix into to methods(encode, encrypt methods) in the "EncryptedArray" class.. can you help me out... – Ultra_Champ May 26 '14 at 12:49

Is there code or idea for doing this?

As you did not specify what research you have done, or what you already know, I can merely guess.

In case you haven’t done so yet, you could check on:

and last but not least

Depending on the research you have (or haven’t) already done, each of them might provide helpful pointers to you.

I hope you’ll understand that I won’t be throwing in code… the source you’re providing doesn’t show any effort of any encryption implementation yet, and I’m surely not planning to code it all up for you as that would be a bit too much and take it a bit too far for an answer. After all, this isn’t GitHub or something… (But, I definitely would like to echo @mikeazo, who already pointed you to potential portability issues.)

-
Thank you so much for the reply... I had read the research papers mentioned before starting the work. . but they use a different technique for feature extraction and matching.. whereas I am using another technique which I coded above (just aligning w.r.t the core point and calculating the euclidean distance). . i needed to know whether it is possible to covert the code into a homomorphic format.. – Ultra_Champ May 26 '14 at 12:41
@Tintumon007 I had a feeling you might have read them, I just wasn’t sure so I didn’t want to miss out on at least mentioning them. As for the practical (coding) side of things… it can be done, but it takes a whole lot of fiddling to make all parts fit (yet, diving into that would be more on-topic at StackOverflow). Anyway, I obviously wasn’t as helpful as I wished I could have been – so please don’t thank me for providing nothing usable to you. Oh well, at least I did throw in my good intentions and an upvote on your question. Erm… welcome to Crypto.SE btw.! ;) – e-sushi May 26 '14 at 13:11
@Tintumon007 Ugh, just noticed you’ve already been there. (A little hint related to that: watch out not to cross-post the same question to different sites of the StackExchange network because such cross-posts tend to get closed pretty quickly around here. Instead, moderators♦ can migrate questions to other sites if it makes sense.) – e-sushi May 26 '14 at 13:17
thank you again.. not for upvoting (seriously).. but for the the fact that "i am happy that i found a reply to my question". . and i am new to stackexchange.. so i appreciate that you are making me aware of some important facts i need to take care of.. just started my research.. and i hope to continue it and hopefully finish it.. your valuable help will be required.. – Ultra_Champ May 26 '14 at 13:55