On 15 December 2023, Amina Bassit successfully defended her PhD thesis with the title „Fast and Accurate Biometric Search under Encryption”.
The supervisors of the thesis were Prof. Dr. Raymond Veldhuis (University of Twente, The Netherlands), Prof. Dr. Andreas Peter (Carl von Ossietzky Universität Oldenburg, Germany), and Dr. Florian hahn (University of Twente, The Netherlands).
Moreover, the following committee members were involved in the assessment of the thesis:
- Prof. Dr. Geert Heijenk, University of Twente, The Netherlands (chair of committee)
- Prof. Dr. Roland van Rijswijk-Deij, University of Twente, The Netherlands
- Prof. Dr. Willem Jonker, University of Twente, The Netherlands
- Prof. Dr. Colin Boyd, Norwegian University of Science and Technology, Norwey
- Prof. Dr. Marta Gomez-Barrero, Universität der Bundeswehr München, Germany
Here’s a short summary of the PhD thesis:
Modern biometric recognition (a.k.a. biometrics) is ubiquitous for digitally verifying the physical presence of individuals. Its core component is the biometric comparator that measures similarities between biometric samples via their distinctive representations called biometric feature vectors, quantifying their similarities as comparison scores. Analyzing biometric data leads to privacy violations by inferring personal information and reconstructing raw biometric samples, highlighting its inherent sensitivity due to its immutability. This necessitates protecting biometric data during its entire lifecycle - in transit, at rest, and in use - on top of maintaining recognition accuracy, regardless of the biometric recognition task, verification (one-to-one comparison), or search (one-to-many comparison). Prior research indicates that homomorphic encryption (HE) schemes hold great biometrics potential despite their computational and space complexities added to the cleartext biometrics by enabling arithmetic operations on encrypted data without decryption. Particularly, fully homomorphic encryption (FHE) schemes can perform those operations on ciphertext-packed vectors, spreading homomorphic operations over vector elements simultaneously (a.k.a., single-instruction multiple-data (SIMD)). Thus, HE ensures biometric data confidentiality and maintains recognition accuracy, but its efficiency is constrained by configuration parameters and multiplicative depth, impacting its runtime.
In this dissertation, our goal is to construct fast and accurate biometric recognition solutions in the encrypted domain for the verification and search tasks secure against semi-honest attackers. Given that the biometric comparator serves as the central component for both recognition tasks, our initial research focus is on constructing an efficient and accurate comparator for the verification task under encryption, and then we integrate our construction to handle the search task under encryption. In order to achieve our objectives, we follow a systematic approach where we initially begin by investigating existing biometric data protection methods upon which we validate the use of the HE-based approach. Then, we analyze further the architecture of this approach in both verification and search settings to identify sensitive entities involved in the recognition process. Our analysis emphasized the importance of hiding not only the biometric feature vectors but also the comparison scores since we showed through a recovery attack that the exposure of those scores leads to the recovery of the original biometric feature vector. After gathering the design requirements for our solutions, we tackle the construction of biometric comparators that easily integrate with HE without losing their accuracy. To this end, we target biometric comparators based on score functions that can be expressed as the sum of local functions on pairs of vector elements. A local function takes the i-th element of a pair of vectors and outputs a local score for which its sum yields a final score quantifying the vectors' similarities. There are two local function families: identical local functions and different local functions. For instance, multiplication represents the family of identical local functions in the case of the inner product-based score functions. Hence, we construct a biometric comparator for each local function type. Our construction for both comparators consists of approximating the score function by a set of pre-computed lookup tables, each approximating a local function. Thus, this construction transforms the evaluation of a biometric comparator into straightforward selections of individual scores from those lookup tables and their summation. The evaluation of this type of lookup table-based comparators under HE results in multiplication-free computations of low complexity dominated by homomorphic additions, which are the cheapest homomorphic operations. Compared to their baseline comparators, our lookup table-based comparators reach an identical accuracy for a fast evaluation under encryption. Specifically, we show that biometric verification protocols based on our lookup table-based comparators achieve significantly fast runtimes under encryption - in the order of milliseconds - even for the encrypted decision mode where the recognition process under encryption outputs the decision (match/no match) encrypted. Despite their demonstrated efficiency for the verification task under encryption, the direct integration of our comparators with the search task under encryption does not scale with the database size, resulting in runtimes in the order of hours. Therefore, we orient our research focus on establishing a fast and accurate biometric search solution under encryption. By organizing the biometric database vertically and using our lookup table-based comparators, we leverage the use of FHE with SIMD as a speeding-up tool for searching large-scale encrypted biometric databases, allowing comparators to handle multiple evaluations at the cost of one. Our approach is based on partitioning the database into manageable chunks, unlocking the potential for the simultaneous processing of each chunk separately. Our design not only brings parallelizability to our search solution but also enhances its dynamic management capabilities, including single/multiple additions/deletions and cleartext/encrypted search decisions. Our proposed solution demonstrates a significant improvement in the runtime performance compared to the current state-of-the-art solutions for biometric search. Specifically, our solution demonstrates remarkably fast runtimes - in the order of seconds - for an exhaustive search over a database comprising one million encrypted biometric references, considering both the cleartext and encrypted search decision modes.
The dissertation concludes with open research questions and concrete proposals. Most importantly, while our solutions are secure against semi-honest attackers, we show how to design an efficient biometric verification protocol secure against malicious attackers in response to our awareness of the risks malicious attackers can cause when considering protocols secure against semi-honest ones. Further studies in this direction are required but go beyond the scope of this dissertation.
Link to PhD thesis:
