AMPPERE: A Universal Abstract Machine for Privacy-Preserving Entity Resolution Evaluation

We formalize the ER problem as a triple $P=(D_{1},\allowbreak D_{2},\allowbreak M)$ where $D_{1}$ and $D_{2}$ are two different datasets consisting of a collection of unique records. $M$ denotes the matching record pairs between the two datasets, that is, $M=\{(r_{i},r_{j})\,|\,r_{i}=r_{j},r_{i}\in D_{1},r_{j}\in D_{2}\}$ where $r_{i}=r_{j}$ indicates that $r_{i}$ and $r_{j}$ refer to the same entity in the real world. With PPER, we still deal with $D_{1}$, $D_{2}$, and $M$, however, we additionally say the probability that the data owners of $D_{1}$, $D_{2}$ learn any information outside of what record pairs exist in $M$ is negligible, and the probability that an adversary $A$ learns anything, including $M$ or any part of $M$, is negligible.

Additionally, we define a full comparison between $D_{1}$ and $D_{2}$ to be $T=\{(r_{i},r_{j})\,|\,r_{i}\in D_{1},r_{j}\in D_{2}\}$, and the number of candidate pairs to be $|T|$, the Cartesian product between sizes of $D_{1}$ and $D_{2}$ (i.e. $|D_{1}|\times|D_{2}|$). We focus on token-based entity resolution algorithms for finding $M$, where each record is represented by a set of unique tokens $r=(t_{1},t_{2},\cdots)$. Blocking algorithms prune $T$ by removing pairs that are unlikely to be part of the solution $M$. Inverted-index blocking algorithms are popular methods that use a function $\beta$ to encode each record into blocking keys $\beta(r)=(k_{1},k_{2},\cdots)$, preserving candidate record pairs that share at least one $k$. Therefore, the pruned candidate pair set is defined as $T^{\prime}=\{(r_{i},r_{j})\,|\,|\beta(r_{i})\cap\beta(r_{j})|>0,r_{i}\in D_{1},r_{j}\in D_{2}\}$. A good blocking algorithm reduces as many candidate pairs as possible without losing truly matched pairs (Michelson and Knoblock, 2006). We use pairs completeness ($PC$) to measure the percentage of true pairs that are blocked, and reduction ratio ($RR$) to measure how well the method reduces the number of candidate pairs. These are formally defined as: $PC=\tfrac{M\cap T^{\prime}}{M}$, $RR=1-\tfrac{|T^{\prime}|}{|T|}$, and $F\textnormal{-}score=\tfrac{2*PC*RR}{PC+RR}$.

We now introduce our main algorithmic tools for entity resolution: the set similarity metric of Jaccard similarity (Jaccard, 1901) and its derivative MinHashLSH (Leskovec et al., 2014), which is a MinHash-based variant of Local Sensitive Hashing (LSH) designed for searching similar documents from a large corpus. We also introduce the two main cryptographic and privacy tools that we leverage in our implementations of AMPPERE: secure multi-party computation (MPC) (Yao, 1982) and homomorphic encryption (HE)  (Abbas Acar, 2018).

Jaccard similarity (Jaccard, 1901) is a well-known and widely used set-based similarity metric, commonly used for feature generation and similarity measurement in data mining and information retrieval tasks. Given two sets of tokens $x$ and $y$, Jaccard similarity refers to the size of the intersection divided by the size of the union of the token-sets, that is, $Sim_{Jaccard}(x,y)=\frac{|x\cap y|}{|x\cup y|}=\frac{|x\cap y|}{|x|+|y|-|x\cap y|}$.

Some existing PPER approaches (Sehili et al., 2015) extend the Jaccard similarity metric to privacy-preserving settings by encrypting input sets into bit arrays (or fingerprints), and comparing them using Tanimoto similarity (Tanimoto, 1958), which computes similarity in a manner similar to Jaccard: $Sim_{Tanimoto}(x,y)=\frac{|x\wedge y|}{|x\vee y|}=\frac{|x\wedge y|}{|x|+|y|-|x\wedge y|}$, where $|x|$ and $|y|$ denotes the number of set bits (cardinality) in the bit array $x$ and $y$ respectively. We use Jaccard similarity to perform ER by selecting a threshold $t$ such that $(r_{1},r_{2})\in M$, if $Sim_{Jaccard}(r_{1},r_{2})>t$.

MinHash exploits min-wise independent permutations to generate similarity-preserving signatures for each record. The probability of getting two similar MinHash signatures from two permutations of sets is identical to applying Jaccard directly over the them; formally, $Pr[h_{min}(perm(x)),\allowbreak h_{min}(perm(y))]\allowbreak=\allowbreak Sim_{Jaccard}(x,y)$ where $h_{min}$ denotes MinHash and $perm$ denotes the random permutation function. The LSH algorithm then splits the signature into smaller bands (chunks) of a fixed length where only the records that share at least one band are considered to be potentially similar (i.e. they have partially common signatures). MinHashLSH Blocking  (Leskovec et al., 2014) is an inverted-index inspired method utilizing MinHashLSH bands as blocking keys and associated record ids as values.

MinHashLSH is statistically robust and efficient for finding similar records or documents; since blocking keys are signatures, they do not reveal information relating to original records. For these reasons, we use it as our blocking method of choice in section 3.1.3.

In our two implementations of AMPPERE, we use Sharemind (Cybernetica, 2019b), a client-server platform for black-box general-purpose MPC computation, and PALISADE (team, 2020), an open-source lattice-based HE (& threshold-HE) library.

Our model is presented such that it can be instantiated using only simple platform-agnostic, privacy-preserving primitive operations. As shown in fig. 1, both dataset providers (i.e. $P_{1}$, $P_{2}$) negotiate on parameters first (e.g., Jaccard, blocking threshold), then apply encoding on each of their records, individually, while also computing blocks. Encoded records and blocks are then uploaded and stored in a cloud owned by a third party (i.e $P_{3}$), where blocks are merged and deduplicated, and candidate pairs are filtered. ER (privately) is performed on the remaining qualified pairs. The accuracy, in performing PPER, of our abstractions and algorithms is 100% given correct implementations, as evidenced by section 3.2 & section 3.3.

SecreC (Cybernetica, 2019a) is a C-like domain-specific programming language designed for the Sharemind platform application (Randmets et al., 2017). SecreC provides generic programming facilities, hiding details of its underlying secure protocol; it has many differences as compared to general-purpose languages: (i) SecreC distinguishes between public and private data types at the system level via a security type (separate from the data type). The programmer must indicate whether certain data is public or private, and then the implementation can automatically convert one-way from public to private if necessary. (ii) Operations on private data types are limited. For example, bool, int, uint and float do not support bitwise and and bitwise or operators. (iii) Private values cannot be used in conditional statements. (iv) No file system access. The host machine and running environment can exchange data only via input arguments, via keydb, a key value store based on Redis, or via a vector-based table_database; the data has to be batched and pre-uploaded through command line arguments to these containers.

Our implementation has two components: upload and link. upload loads encoded records and blocks to the Sharemind keydb instance and link is used for entity resolution. The key for a record is a public string in the form {dataset id}_{record id}, and the value is a private uint64 array which stores encoded tokens. The format of a block is similar to a record, but the key has an additional prefix as a namespace. For a record, if the associated blocking key exists, the program will fetch the corresponding vector back and merge the record id into it with the cat function;

The blocking keys belonging to $D_{1}$ are acquired from the keydb instance, and are constructed with the blocking keys with $D_{2}$’s identifier; the blocks belonging to different datasets, but with the same blocking key are fetched, candidate pairs are generated and deduplicated, and finally stored into $cand\_pairs$ with matrixUpdate. After this, the link program obfuscates the candidate pairs, and runs filtering and ER. Utilizing Sharemind’s API, we implemented the following methods for computing set intersection size: Pairwise join, Vector extension (with internal function gather_uint64_vec), Sorting (with quicksort) and Matrix join (with tableJoinAes128). In the end, $results$ is reshaped to a 1D array (as Sharemind does not allow matrices to be returned) and is shipped back to the host.

Our PALISADE implementations work with the Brakersi-Gentry-Vaikuntanathan (BGV) (Brakerski et al., 2011) (for integer arithmetic) and the Cheon-Kim-Kim-Song (CKKS) (Jung Hee Cheon, 2017) (for approximate numbers) constructions, in the form of their respective RNS (residue number system) variants (Craig Gentry, 2012)(Jung Hee Cheon & Kyoohyung Han, 2019). As a first step in utilizing any scheme within PALISADE, one must instantiate a corresponding CryptoContext object for encryption functionality. Each context must be configured with relevant parameters that provide certain bit-security levels and performance; in our implementations we configured the following: multiplicative depth, scale factor bits, plaintext modulus, batch size, key switching technique, and security level. Both BGV and CKKS are fully homomorphic (FHE) in the sense that they both support (an arbitrary, unbounded number of) additive and multiplicative homomorphic operations (Gentry, 2009). In PALISADE, these schemes work as parametrized, leveled versions, meaning computations are computed up to a pre-determined depth. To establish a fair comparison between both schemes, we keep their corresponding ring dimensions and CRT moduli  (Albrecht et al., 2019) the same. Table 2 displays our value choices for the parameters above; further fine-tuning can be done for potentially more efficient runtimes.

We developed 4 specific implementations in PALISADE: a two party protocol in both BGV and CKKS respectively, and their corresponding threshold (MPC) variants. In the two party protocol, $P_{2}$ encrypts their data, sends it to $P_{1}$ who then operates with $P_{2}$’s encrypted data, and their own data (in clear). In the MPC version, we apply threshold HE where $P_{1}$ and $P_{2}$ must first agree on a public/private key-pair to be used for encryption, and distributed decryption. Then, both parties encrypt and send their data to $P_{3}$ to carry out the computation over both of their (encrypted) data. Parties are modeled via individual data-structures, each referencing public/private keys generated via the KeyGen function and are realized as separate entities through different threads that take on the evaluation compute. We implemented the Pairwise join, Vector extension, and Vector rotation set intersection size approaches within PALISADE. PJ encodes each token of each record as a separate Ciphertext object with the value of the integer located at slot 0, whereas VR and VE are able to take advantage of plaintext packing (i.e. how many plaintexts you can fit into a single ciphertext slot) by encoding an entire record of tokens together as one ciphertext (Single Instruction Multiple Data (SIMD) computations). PJ computes the ER process in serial, and only relies on the PALISADE function EvalSub to homomorphically compare each token of one record, pairwise with each token of another record. VR and VE both utilize EvalAtIndex to homomorphically rotate (right shift) along with EvalSub for subtractions, while VE additionally uses EvalSum to repeat elements for a certain batchSize over the ring dimension.

We implemented blocking in the CKKS scheme. A discussion around why we chose CKKS vs. BGV for blocking is located in section 4.2.2. We used our own custom HE implementation of ternary operators (algorithm 1) and private matrix manipulation (algorithm 2) for deduplication and filtering (algorithm 3).

This section describes the dataset used for evaluation and the configurations used for our two implementations.

We used Datasketch (Zhu, 2017) to calculate MinHash signatures for records and to generate LSH blocking keys. We set the number of permutations to 128, and the relative importance of false positive/negative probability to 0.5 each. Datasketch calculates range and band to minimize the weighted sum of probabilities of false positives/negatives with all range and band combinations under a given threshold. The optimal blocking key sizes (the same as range) in different thresholds are shown in fig. 4. The blocking key size is correlated with the $b$: the blocking threshold.

The Sharemind runtime environment (Cybernetica, 2019b) and implementations are deployed on all three servers, as for the SecreC program the shared3p private domain requires distributed across 3 different nodes. For the fairest comparison of evaluation results with Sharemind, we used the following configurations in PALISADE: compiled the PALISADE cmake project with the -DWITH-NATIVEOPT flag set to on; used single-threaded runtimes to establish baselines between systems, configured via export OMP-NUM-THREADS=1; turned CPU scaling off. We also disabled obfuscation (for both platforms) to achieve the most optimal running time possible.

We tested the efficiency of executing Jaccard similarity with the different approaches for computing set intersection size described in section 3.1.1. For each approach, we recorded the execution time of Jaccard similarity on 100 randomly sampled single pairs.

In this experiment, we show the effectiveness of blocking in performing (private) entity resolution with the two implementations. We used the non-blocking approach as the baseline (performs all 1,600 pairwise comparisons) and ran blocking with a MinHashLSH threshold $t$ of t=0.2, 0.5, and 0.8. The blocking key sizes corresponding to these threshold values are 28, 25 and 9 (resp.) and the numbers of distinct comparisons after blocking are limited to 1,314, 118 and 36 (resp.) as compared to the overall 1,600.

Figure 6(b) demonstrates the total and step time cost of PPER with blocking in Sharemind. The baseline takes around 6,000 seconds to make all 1,600 pair-wise similarity comparisons, whereas, for the blocking version, the dataset upload cost depends on the size of blocking keys. Hence, when $t=0.8$, it takes the least amount of time to upload data as there are only 9 keys per record and block merging, deduplication and candidate pair generation costs are minor. In the entity resolution step, when $t=0.2$, it needs 1,314 comparisons, which while smaller than the baseline, shows an overall longer runtime due to extra overhead incurred via data upload and block operations. When $t=0.5$, the number of comparisons along with execution time drops drastically, and this trend continues when $t=0.8$, but with recall loss as a trade-off cost.

As with Sharemind, blocking in PALISADE shows great time cost savings as it filters out unnecessary pairwise record comparisons. Figure 6(c) shows the overall time cost resulting in PALISADE with the various blocking thresholds against the non-blocking baseline. We implement blocking in both the $SR$ and $3PC$ variants with CKKS as opposed to BGV due to the optimized performance in dealing with rescaling after multiplications, and because of good support for scalar/plaintext & ciphertext operations in implementing ternary operators presented in algorithm 1. Unlike Sharemind, we perform blocking in PALISADE we three main steps: preprocessing (generating block data structures), block merging + deduplication + candidate pair generation, and filtering + ER calculations. In fig. 6(c), we group the runtime of steps 1 and 2 into one bar as, for all blocking threshold levels, preprocessing remains $<1$ second. For both $SR$ and $3PC$ variants, when $t=0.2$, the overall time-cost is actually longer than the baseline (just like with Sharemind), because while filtering is applied through deduplication and candidate pair generation, it only removes around 300 overall comparisons, which does not outweigh the overhead incurred by those steps. When $t=0.5,0.8$, blocking and filtering is able to brunt much of the computation, by limiting the number of comparisons needed drastically, allowing for the ER calculation to be as minimal as possible.