Secure and Efficient Protocols for Iris Identification

Today large amount of biometric data is being collected by all the countries like USA, UAE, UK, India, etc for the authentication process of their citizens and foreigners entering their country.  Though these data are extremely efficient in authentication, but it has some problems. The data must be securely stored without any leakage as this biometric data of a person can be easily used to replicate him for authentication and thus imposter that person to perform malicious deeds. So the computation, for authentication, on the biometric data requires the data to remain private and reveal only the outcome of the computation.

Feature Vector:

The biometric data we are going to work on is collected in the form of a feature vector X from the iris of a person. Iris code, X is an m-bit string, where each X_i   gives information about some particular feature.

X = X₁ X₂ X₃ X₄ …. X_m

But not all X_i have correct data as there is always some amount of noise which gets captured during the feature extraction from the iris. So we have another vector M(X) of m bits which says

M(X) = M(X₁)M(X₂) M( X₃) M( X₄)  ….M(X_m )

M(X_i) = 0, X_i is noise and should not be considered for computation

M(X_i) = 1, X_i is correctly captured and should be considered for computation

So we use only those X_i for which M(X_i) is 1. Now for authentication we need to match two biometric data X and Y and check whether they have a threshold amount of matching or not.

Hamming Distance:

Definition:

The hamming distance of two vectors X and Y can be computed as follows:

HD(X, Y) = (∑^m_i=1 (X_i ⊕ Y_i ))/m

Modification:

But here since the X and Y vectors have some unreliable bits we skip them by multiplying the term by both M(X_i) and M(Y_i).  D(X, Y) is the distance between the two vectors and M(X, Y) is the number of bits on which the computation is done. So our HD(X, Y) becomes:

HD(X, Y) = (∑^m_i=1 (X_i ⊕ Y_i )M(X_i)M(Y_i))/( ∑^m_i=1(M(X_i)M(Y_i))

                 = D(X, Y)/ M(X ,Y)

Our HD(X, Y) must be lesser than a threshold value T in order to authenticate the person, as this T value will define the maximum number of reliable bits the two feature vectors can differ in. If the two feature vectors have a HD more than T then they are considered to be from different persons.

HD(X, Y) = D(X, Y)/ M(X ,Y) ≤ T

Additive Homomorphic Encryption:

We need additive homomorphic encryption for this scheme. In additive homomorphic scheme, if a₁ = Enc(m₁) and  a₂ = Enc(m₂)  then a₁.a₂ = Enc(m₁+ m₂).

Main  Protocol:

Y is the feature vector that has been captured previously and stored in the database and X is the feature vector that has been captured to authenticate the person later. When the person comes for authentication, X is presented to the authenticator and he tries to find an Y from his database which has HD(X, Y) ≤ T. If he finds such a Y then the person is authenticated else the authentication fails. Here the authenticator is the server and the person who wants to be authenticated is the client. Client C does not share its X_i value and server S does not share its Y_i. Using the protocol, C and S securely compute whether the feature vector X has a threshold matching with any of the Y’s or not. The vector X and Y may be misaligned. So the Y vector is shifted 2c+1 times, for j= -c to c. This can be seen in the protocol. We use the following computations in our protocol. 

X_i ⊕ Y_{i =} (1- X_i)Y_i ⊕ (1-Y_i)X_i

D(X, Y) = ∑^m_i=1 ((1- X_i)Y_i ⊕ (1-Y_i)X_i )M(X_i)M(Y_i)

M(X, Y) = ∑^m_i=1(M(X_i)M(Y_i) 

The main protocol is as follows:

Input: C has biometric X, M(X) and key pair (pk, sk); S has a database D composed of Y, M(Y ) biometrics.

Output: C learns what records in D resulted in match with X if any, i.e., it learns a bit as a result of comparison of X with each Y ∈ D.

Protocol:

1. For each i = 1, . . ., m, C computes encryptions <a_i1, a_i2> = <Enc(X_iM(X_i)), Enc((1− X_i)M(X_i))> and sends them to S.
2. For each i = 1, . . ., m, S computes encryption of M(X_i) by setting a_i3 = a_i1 · a_i2 = Enc(X_iM(X_i)) · Enc((1 − X_i)M(X_i)) = Enc(M(X_i)).
3. For each record Y in the database, S and C perform the following steps in parallel:

       a. For each amount of shift j = −c, . . ., 0, . . ., c, S rotates the bits of Y by the appropriate number of positions to obtain Y^j and proceeds with all Y^j ’s in parallel.

          i. To compute (X_i ⊕ Y^j_i )M(X_i)M(Y^j_i) = (X_i(1 − Y^j_i ) + (1 − X_i) Y^j_i )M(X_i)M(Y^j_i) in encrypted form, S computes
b^j_i = a^{(1− Yji )M(Yji )} _i1 · a^{Yji M(Yji)}_i2
    = Enc(X_iM(X_i)(1 − Y^j_i )M(Y^j_i) + (1 − X_i)M(X_i) Y^j_i M(Y^j_i)).

    ii. S adds the values contained in b^j_i’s to obtain b^j =  π^m _i=1 b^j_i = Enc( ∑^m _i=1(X_i ⊕ Y^j_i )M(X_i)M(Y^j_i )) = Enc(||(X ⊕ Y^j ) ∩ M(X) ∩ M(Y ^j)||). S then “lifts up” the result, blinds, and randomizes it as c^j = (b^j ) ^{2^ℓ} · Enc(r ^j_S ), where r ^j_S  {0, 1} ^{⌈log m⌉+ℓ+κ} , and sends the resulting c^j to C.

          iii. To obtain T(||M(X) ∩ M(Y ^j)||), S computes d^j _i = a ^{M(Yji )} _i3 = Enc(M(X_i) · M(Y ^j _i )) and d^j = ( π^m _i=1 d^j_i)^T = Enc(T(∑^m _i=1 M(X_i)M(Y ^j _i ))). S blinds and randomizes the result as e^j = d^j · Enc(t ^j _S ), where t^j _S   {0, 1} ^{⌈log m⌉+ℓ+κ} , and sends e^j to C.

          iv. C decrypts the received values and sets r ^j _C = Dec(c ^j ) and t ^j_C = Dec(e ^j ).

     b. C and S perform 2c + 1 comparisons and OR of the results of the comparisons using garbled circuit. C enters r^j_C’s and t^j_C’s, S enters − r^j_S ’s and −t^j_S ’s, and C learns bit b computed as V^c_j=−c ((r ^j _C − r^j _S ) ?< (t ^j _C − t ^j _S )). To achieve this, S creates the garbled circuit and sends it to C. C obtains keys corresponding to its inputs using OT, evaluates the circuit, and S sends to C the key-value mapping for the output gate.

After the protocol C learns a bit whether Y was a matching of X or not and then he conveys the message to S. Since this is a semi honest protocol, C will not manipulate the output bit to get himself authenticated. So both S and C will know whether C was authenticated successfully or not. The Client needs to compute 2m bit encryptions for step 1 in the protocol. These encryptions are expensive, so they can be done offline. Client only needs to know the number of 0s and 1s it needed to encrypt.

Optimizations:

1.   Let p₀ and p₁ (q₀ and q₁) denote the fraction of 0’s and 1’s in an iris code (resp., its mask), where p₀ + p₁ = q₀ + q₁ = 1. Therefore, to have a sufficient supply of ciphertexts to form tuples <a_i1, ai2>, the client needs to precompute (2q₀ + q₁(p₁ + ε) + q₁(p₀ + ε))m = (1 + q₀ + 2q₁ε)m encryptions of 0 and (q₁(p₁ + ε) + q₁(p₀ + ε))m = q₁(1 + 2ε)m encryptions of 1, where ε is used as a cushion since the number of 0’s and 1’s in X might not be exactly p₀ and p₁, respectively. Then at the time of the protocol the client simply uses the appropriate ciphertexts to form its transmission. Similarly, the server can precomputes  r ^j_S ’s and t^j_S ’s for all records. He produce 2(2c + 1)|D| encryptions of different random values of length ⌈log m⌉ + ℓ + κ, where |D| denotes the size of the database D. The server generates one garbled circuit for each record Y in its database (for step 3(b) of the protocol) and communicates the circuits to the client.

2.   S computes b^j_i = a^{(1− Yji )M(Yji )} _i1 · a^{Yji M(Yji)}_i2 during the protocol but the number of modular multiplications in calculation of  b^j_i can be significantly reduced as follows:

    a.   Y^j_i = (0 or 1)and M(Y^j_i ) = 0: both M(Y^j_i )(Y^j_i ) and M(Y^j_i ) (1-Y^j_i ) are 0 so b^j_i  = Enc(0)

    b.   Y^j_i = 0 and M(Y^j_i ) = 1: M(Y^j_i )(Y^j_i ) = 0 and M(Y^j_i ) (1-Y^j_i ) =1, and so b^j_i = a_i1

    c.   Y^j_i = 1 and M(Y^j_i ) = 1: M(Y^j_i )(Y^j_i ) = 1 and M(Y^j_i ) (1-Y^j_i ) =0, and so b^j_i = a_i2

3.   To reduce online communication client randomly choose 2m bits - u₁ u_2.. u_2m, encrypt it and send it to the server during the offline phase. So that in the online phase, client just need to send v_i=x_i⊕u_i = (x_i)(1- u_i) ⊕ (1-x_i)( u_i). Then when the protocol begins, the server sets either Enc(x_i) = Enc(u_i), if v_i  =0 or Enc(x_i) = Enc(1 − u_i) , if v_i  =0.