Paper 2024/999

ProxCode: Efficient Proximity Searchable Encryption from Error Correcting Codes

Abstract

This work builds approximate proximity searchable encryption. Secure biometric databases are the primary application. Prior work (Kuzu, Islam, and Kantarcioglu, ICDE 2012) combines locality-sensitive hashes, or LSHs, (Indyk, STOC '98), and secure multimaps. The multimap associates LSH outputs as keywords to biometrics as values. When the desired result set is of size at most one, we show a new preprocessing technique and system called \sysname that inserts shares of a linear secret sharing into the map instead of the full biometric. Instead of choosing shares independently, shares are correlated so exactly one share is associated with each keyword/LSH output. As a result, one can rely on a map instead of a multimap. Secure maps are easier to construct with lower leakage than multimaps. This approach reduces the required number of LSHs for a fixed accuracy for many parameters. Our scheme improves most when combining a high accuracy requirement with a biometric with large underlying noise. Our approach builds on any secure map. To benchmark, we implement the scheme using the tree based oblivious map of Wang et al. (CCS, 2014) and evaluate efficiency and accuracy for iris, synthetic, and random data. Compared to the recent work of Ha et al. (Codaspy 2025), for the largest parameters tested and a comparable true accept rate, our work reduces the number of LSHs by a factor of $4.3$. This reduction impacts all efficiency metrics; our rounds are smaller by 2, storage by a factor of $6.5$, and parallel time by a factor of $8$.