Experiments to see if iris codes can be matched in MPC with acceptable privacy and performance.
Specification
For present purposes an iriscode consists of $\mathtt{data}$ bits and $\mathtt{mask}$, two $12\ 800$-bit bitvectors. When a mask bit is set the corresponding data bit should be ignored.
Fractional hamming distance
A fraction hamming distance between two such iriscodes $\mathtt a$ and $\mathtt b$ is computed as
where $d$ is a vector of data bits that are different, $\overline{m}$ is a vector of bits that are unmasked in $\mathtt a$ and $\mathtt b$ and $\mathtt{fhd}$ is the fractional hamming distance.
Rotations
The $12\ 800$ bitvectors can be interpreted as $64 × 200$ bit matrices. We can then define a rotation as a permutation on the columns:
When applied to an iriscode this applies to $\mathtt{data}$ and $\mathtt{mask}$ equaly.
Distance
The distance between two iriscodes $\mathtt a$ and $\mathtt b$ is defined as the minimum distance over rotations from $-15$ to $15$:
$$
\mathrm{dist}(\mathtt a, \mathtt b) = \min_{r∈[-15,15]}\ \mathrm{fhd}(\mathrm{rot}(\mathtt a, r), \mathtt b)
$$
Uniqueness
To verify uniqueness we require that an iriscode $\mathtt a$ is a certain minimum distance from all previous iriscodes:
$$
\mathop{\Large ∀}\limits_{\mathtt b ∈ \mathtt{DB}}\\
\mathrm{dist}(\mathtt a, \mathtt b) > \mathrm{threshold}
$$
where $\mathtt{DB}$ is the set of already registered iriscodes (currently 3 million entries).
When there is a match, we are also interested in finding the location of the best match. Both can be addressed by implementing a method that returns the index of the minimum distance entry.
MPC specific notes
Minimal proposal
Keep the query $\mathtt{a}$ and the $\mathtt{mask}$ s cleartext, but $\mathtt{DB}$ entries ciphertext.
In cleartext compute a rotation of $\mathtt{a}$ and
Given bitvector $\mathbf a$ and $\mathbf b$. Observe that if the bits are lifted to a large enough group $ℤ_{2^k}$ we can compute a popcount as a dot product
$$
\mathtt{popcount}(\mathbf a ∧ \mathbf b) = \sum_i a_i ⋅ b_i
$$
For this to work we need $2^k$ larger than the number of bits in the vector. We can also lift the $⊕$ operation to one in $ℤ_{2^k}$:
Note that $\mathbf a$ and $\mathbf c$ are cleartext, so we can compute $\mathbf d = \mathbf a ∧ \mathbf c$ and $e = \mathtt{popcount}(\mathbf d)$ in advance