Doctoral Dissertation Proposal Oral Presentation, Maryam Rezapour

Title: Efficient Secure Computation via Error Correcting Codes
Ph.D. Candidate: Maryam Rezapour
Major Advisor: Dr. Benjamin Fuller
Committee Members: Dr. Alexander Russell, Dr. Walter Krawec
Date/Time: Monday, April 1st, 2024, 10:00am
Location: HBL 1102
Webex Link: https://uconn-cmr.webex.com/meet/mar19058

Abstract
Country-scale biometric databases are deployed with few privacy or security protections. This work builds approximate proximity searchable encryption, the required tool for secure biometric databases. Prior work (starting with Kuzu, Islam, and Kantarcioglu, ICDE 2012) combines locality-sensitive hashes, or LSHs, (Indyk, STOC ’98), and oblivious multimaps. The multimap associates LSH outputs as keywords to biometrics as values. The underlying biometric noise means:

1. Oblivious multimaps are required because multiple biometrics can be associated with each keyword. Designing multimaps is more difficult than designing maps. Current volume hiding multimaps have query equality leakage (Amjad et al., PoPETS 2023). Zero-leakage maps are known (George, Kamara, and Moataz, Eurocrypt 2021).
2. A large number of selective LSHs are required, harming system efficiency.

When the desired result set is of size at most one, we show a new preprocessing technique and system called ProxCode based on inserting shares of a linear secret sharing into the map. Each biometric is split into shares which are inserted into a map. Shares are correlated so one share is associated with each keyword. As a result, one can rely on a map instead of a multimap.
For many parameters, this approach reduces the number of LSHs for a fixed accuracy. As an example, for a dataset of 10, 000 biometrics with 25% bit error rate, we reduce the required number of LSHs from a million to 8 thousand. Our scheme yields the most improvement when combining a high accuracy requirement with a biometric with large underlying noise.
We present a prototype implementation of the scheme using a baseline unprotected map. Our approach builds on any secure map. We evaluate the scheme for both iris data and random data. For iris data, we use the ThirdEye feature extractor (Ahmad and Fuller, IJCB 2019) on the IITD dataset (Kumar and Passi, Pattern Recognition 2010).