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.

FAST GARBLING OF CIRCUITS UNDER STANDARD ASSUMPTIONS

Yao’s Garbled circuits provide a method to compute circuits based on double decryption where keys for double decryption are the random values assigned to the input of the gates. The output of double decryption is once again a random value assigned to one of the two possible outputs (0, 1) which may be further used as input to next gate. Many optimizations of Yao’s garbled circuits have then come up one of which is free XOR. Free XOR enables the computation of XOR gates for free and it involves no necessity of any cipher text corresponding to output.

Implementation of XOR gate [free XOR]

Lct W_i⁰ be a random value associated with input i

W_a⁰, W_b⁰∈_R{0,1}ⁿ  W_c⁰ = W_a⁰ ⊕W_b⁰

Choose R∈_R {0,1}ⁿ

W_a¹= W_a⁰⊕R, W_b¹= W_b⁰⊕R and  W_c¹ = W_c⁰⊕R

Correctness of “FREE XOR” by example

Let W_c¹=W_a⁰⊕W_b¹

W_c¹ = W_a⁰⊕W_b⁰⊕R

W_c¹=W_c⁰⊕R

Implementation of AND gates (Free - XOR)

We need a hash function to analyse the gates securely. Also we have to assign permutation bits P_a,P_b ∈{0,1} for the inputs (a,b) associated with respect to AND gate.

W_a⁰ = <K_a⁰, P_a⁰> ∈_R {0,1} ⁿ⁺¹

W_b⁰ = <K_b⁰, P_b⁰>∈_R {0,1} ⁿ⁺¹

W_c⁰ = <K_c⁰, P_c⁰> ∈_R {0,1} ⁿ⁺¹

Choose R ∈_R {0,1}ⁿ

W_a¹ = <K_a⁰⊕R, P_a⁰⊕1>

W_b¹ = <K_b⁰⊕R, P_b⁰⊕1>

W_c¹ = <K_c⁰⊕R, P_c⁰⊕1>

The corresponding table entries T_⊼(i,j)  Permutated over  P_aⁱ, P_b^j,  i,j∈{0,1} will be

T_⊼ij   = H <K_a⁰ || K_b⁰ || g) ⊕ W_c⁰

T_⊼ij   = H <K_a⁰ || K_b⁰ || g) ⊕ W_c⁰

T_⊼ij   = H <K_a¹ || K_b⁰ || g) ⊕ W_c⁰

T_⊼ij   = H <K_a¹ || K_b¹ || g) ⊕ W_c¹

The above four entries pertain to garbled circuit K. The evaluator obtains W_c^g(a,b) by   XORing the hash of the input keys given to him with corresponding  tuple in table  obtained by combination of P_aⁱ, P_b^j .

This hash function is secure under circular secure correlation robustness or related key assumption

Garbled XOR with a single cipher text

The method is built using 4 PRF calls for garbling the circuit. Let the four inputs be K_i⁰, K_i¹, K_j⁰, K_j¹. Note that K_i¹=K_i⁰+△_l  

Step 1 : Compute  k_i⁰ = F_Ki(0,i)(g) and  k_c¹ = F_K(1,i) (g)

Step 2 : Compute △_l=  k_i⁰ ⊕ k_i¹

Step 3 : Compute  k_j^⊼j = F_K(⊼j,j)(g) and k_j^!⊼j =  k_j^⊼j + △_l

Step 4 : Compute output K_l⁰ =  k_i⁰ ⊕ k_j⁰ and K_l¹ = K_l⁰ ⊕△_l

Step 5 : Consider if the input in K_i⁰ and K_j¹. In such a case we cannot compute k_j¹ as it is function of K⁰_j . This can be solved by providing a cipher text T= F_K(!⊼j,j)(g) ⊕ k_j^!⊼j . Now given K_j^!⊼j it is possible to compute k_j^!⊼j as well. Not that (!⊼j )is complement of   (⊼j).

Reducing the number of PRF calls to Step 3

The output k_j⁰ can be simply taken as K_j⁰ and the pseudo random function to compute  k_j⁰ from K_j⁰ can be skipped. This reduces PRF calls from 4 to 3. Since  k_j⁰= K_j⁰ , T₀ entry of table T will be 0.

Algorithm to Implement XOR gates

1..  Set the output wire permutation bit for the ‘0’: ^⊼_l := ^⊼_i⊕^⊼_j

2.  Compute translate keys for wire  i : Compute  k_i⁰ = F_Ki(0,i)(g) and  k_c¹ = F_K(1,i) (g)

3.  Compute new offset for the output wire △_l=   k_i⁰ ⊕ k_i¹

4 .  Compute translated keys for wire j and the ciphertext for this gate

          a.      If  ⊼_j =0 , set  k_j⁰ = F_K(0,j)(g||0), k_j^{1 =} k_j^{0 +}△_l and T= F_K(1,j)(g) ⊕ k_j¹

           b.      If  ⊼_j =1 , set  k_j¹ = F_K(1,j)(g||0), k_j^{0 =} k_j^{1 +}△_l and T= F_K(0,j)(g) ⊕ k_j⁰

      5.  Compute the keys for output wire l : K_l⁰ =  k_i⁰ ⊕ k_j⁰ and K_l¹ = K_l⁰ ⊕△_l

      6.  Return (K_l⁰, K_l¹, ⊼_l,T)

Simple and Fast 4-2 garbled row reduction of non XOR gates

In previous section we removed one row of T representing garbled circuits, by setting one of the keys on the output wire to be actually K_0, than using K₀ to mask the output key. Here we improve by performing 4-2 reduction on cipher text for non-XOR gates. For case of understanding we explain the evaluation of gate first.

The gate evaluated, receives as input to gate, a table with two entries [T₁, T₂] and index I ∈ {0,1,2,3} and a value of K_i computed from the two garbled values of the input wire.

We compute K_out as follows

If i = 0 then K_out = K₀

If i = 1 then   K_out = K₁⊕T₁

If i = 2 then   K_out = K₂⊕T₂

If i = 3 then   K_out =  K₃⊕T₁⊕T₂

Let K[T_i] denote the output key with respect to i^th row of table T. We have K[T₀] = K₀ because K₀= K₀⊕T = K₀⊕0. An AND gate has two possible outputs. If K₀ is one output then we can consider K₁⊕K₂⊕K₃ to be another possible output or vice versa.

Now we need to define K[T₁], K[T₂]  and K[T₃]  and values of  T₁, T₂ and T₃ correspondingly

If K[T₁] = K₀ then T₁ = K₀⊕K₁

                  else

If K[T₁] = K₁⊕K₂⊕K₃ then T₁ = K₂⊕K₃

If K[T₂] = K₀ then T₂ = K₀⊕K₂

                   else

If K[T₂] = K₁⊕K₂⊕K₃ then T₂ = K₁⊕K₃

K[T₃] follow from values of T₁ and T₂ because T₃ = T₁⊕T₂ and K[T₃] = K₃⊕T₁⊕T₂

Since the evaluation can always compute T₃ given T₁ and T_2, the table T can be reduced to two rows.

Following is the table for garbled circuit

S	Truth table	T1	T2	K0out	K1out
3	0001	K0 ⊕ K1	K0 ⊕ K2	K0	K1⊕ K2⊕ K3
2	0010	K0 ⊕ K1	K1⊕ K3	K0	K1⊕ K2⊕ K3
1	0100	K2⊕ K3	K0 ⊕ K2	K0	K1⊕ K2⊕ K3
0	1000	K2⊕ K3	K1⊕ K3	K1⊕K2⊕ K3	K0

Correctness

K[T₃] = K₃⊕T₁⊕T₂

               = K₃⊕(K₁⊕K[T₁]) ⊕ (K₂⊕K[T₂])

               = K₁⊕K₂⊕K₃ ⊕ (K[T₁]) ⊕ (K[T₂])

If  K[T₁] = K[T₀] = K₀  or  K₁⊕ K₂⊕ K₃  then  K[T₃] is K₁⊕ K₂⊕ K₃

If  K[T₁] ≠ K[T₀]  then surely K[T₁] ⊕ K[T₂]  = K₀ ⊕ K₁⊕ K₂⊕ K₃  in which case            

K[T₃]=K₀