International Association
for Cryptologic Research

The increasing availability and use of biometric data for authentication and

other purposes leads to situations when sensitive biometric data is to be

handled or used in computation by entities who may not be fully trusted or

otherwise authorized to have full access to such data. This calls for

mechanisms of provably protecting biometric data while still allowing the

computation to take place. In this work, we treat the problem of

privacy-preserving matching of two fingerprints, which can be used for

secure fingerprint authentication and identification. We utilize traditional

minutia-based representation of fingerprints that leads to the most

discriminative (i.e., accurate) fingerprint comparisons. Unlike prior work,

we design a data-oblivious algorithm that results in the most accurate

outcome of fingerprint matching through a more complex minutia pairing

approach based on maximum flow in bipartite graphs. This algorithm then

leads to secure fingerprint matching solutions of high security standards.

The complexity of our solution is higher than those of some other available

protocols, but nevertheless we show that our techniques still efficiently

compare two fingerprints with provable security guarantees. That is, they

run in a similar amount of time to those with simpler matching mechanisms

which are not guaranteed to find the best matching.