Private computation on common records refers to analyze data from two databases containing shared records without revealing personal information. As a basic requirement for private computation, the databases involved essentially need to be aligned by a common identification system. However, it is hard to expect such common identifiers in real world scenario. For this reason, multiple quasi-identifiers can be used to identify common records. As some quasi-identifiers might be missing or have typos, it is important to support fuzzy records setting. Identifying common records using quasi-identifiers requires manipulation of highly sensitive information, which could be privacy concerns. This work studies the problem of enabling such data analysis on the fuzzy records of quasi-identifiers. To this end, we propose "ordered threshold-one (OTO)" matching which can be efficiently realized by circuit-based private set intersection~(CPSI) protocols and some multiparty computation (MPC) techniques. Furthermore, we introduce some generic encoding techniques from traditional matching rules to the OTO matching. Finally, we achieve a secure efficient private computation protocol which supports various matching rules which have already been widely used. We also demonstrate the superiority of our proposal with experimental validation. First, we empirically check that our encoding to OTO matching does not affect accuracy a lot for the benchmark datasets found in the fuzzy record matching literature. Second, we implement our protocol and achieve significantly faster performance at the cost of communication overhead compared to previous privacy-preserving record linkage (PPRL) protocols. In the case of 100K records for each dataset, our work shows 147.58MB communication cost, 10.71s setup time, and 1.97s online time, which is 7.78 times faster compared to the previous work (50.12 times faster when considering online time only).

Circuit-based Private Set Intersection (circuit-PSI) refers to cryptographic protocols that let two parties with input set X and Y compute a function f over the intersection set X ∩ Y, without revealing any other information. The research efforts for circuit-PSI mainly focus on the case where input set sizes |X| and |Y| are similar so far, and they scale poorly for extremely unbalanced set sizes |X| ≫ |Y|. Recently, Lepoint et al. (ASIACRYPT’21) proposed the first dedicated solutions for this problem, which has online cost only linear in the small set size |Y|. However, it requires an expensive setup phase that requires huge storage of about O(|X|) on the small set holder side, which can be problematic in applications where the small set holder is assumed to have restricted equipment.