Paper 2014/596

Secure and Oblivious Maximum Bipartite Matching Size Algorithm with Applications to Secure Fingerprint Identification

Marina Blanton and Siddharth Saraph


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 are not 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. This work is motivated by the problem of privacy-preserving matching of two fingerprints (used for secure fingerprint authentication or identification) using traditional minutia-based representation of fingerprints that leads to the most discriminative (i.e., accurate) fingerprint comparisons. Unlike previous work in the security literature, we would like to focus on algorithms that are guaranteed to find the maximum number of minutiae that can be paired together between two fingerprints leading to more accurate comparisons. To address this problem, we formulate it as a flow network problem and reduce it to finding maximum matching size in bipartite graphs. The resulting problem is in turn reduced to computing the rank of a (non-invertible) matrix, formed as a randomized adjacency matrix of the bipartite graph. We then provide data-oblivious algorithms for matrix rank computation and consecutively finding maximum matching size in a bipartite graph and also extend the algorithms to solve the problem of accurate fingerprint matching. These algorithms lead to their secure counterparts using standard secure two-party or multi-party techniques as we show later in this work. Lastly, we implement secure fingerprint matching in the secure two-party computation setting using garbled circuit evaluation techniques. Our experimental results demonstrate that the techniques are very efficient, leading to performance similar to that of other fastest secure fingerprint matching techniques, despite higher complexity of our solution that higher accuracy demands.

Note: This version contains additional results compared to the conference version.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.ESORICS 2015
private fingerprint authenticationoblivious algorithmmaximum flowgarbled circuits
Contact author(s)
mblanton @ nd edu
2016-02-01: last of 3 revisions
2014-08-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marina Blanton and Siddharth Saraph},
      title = {Secure and Oblivious Maximum Bipartite Matching Size Algorithm with Applications to Secure Fingerprint Identification},
      howpublished = {Cryptology ePrint Archive, Paper 2014/596},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.