AbstractPrivate record linkage is an actively pursued research area to facilitate the linkage of database records under the constraints of regulations that do not allow linkage agents to learn sensitive identities of record owners. Recent works have shown that linkage using commutative ciphers, which were discarded earlier for efficiency concerns, can be made feasible by leveraging precomputations, data parallelism, and probabilistic key reuse approaches. In this work, we propose further optimizations that can be performed to improve the runtime efficiency of such an approach. We transition from modular exponentiation ciphers to elliptic curve operations to improve precomputation time, eliminate memory intensive comparisons of encrypted values, and introduce data structures to detect negative comparisons. We benchmark the proposed approach using real world demographics data, and provide an extensive study of the parametric aspects of the approach. We also supplement our execution time results with an assessment of the residual privacy risk left by the approach. The approach can perform a linkage of two datasets with 105 records each in 20 minutes in a commodity laptop. This is achieved by eliminating the need to compare more than 70% of the record pairs. By design, the linkage accuracy is also retained at the same level as a nonprivate record linkage procedure.