  Private record linkage (PRL) is the problem of identifying pairs of records
that are similar as per an input matching rule from databases held by two
parties that do not trust one another. We identify three key desiderata that a
PRL solution must ensure: 1) perfect precision and high recall of matching
pairs, 2) a proof of end-to-end privacy, and 3) communication and computational
costs that scale subquadratically in the number of input records. We show that
all of the existing solutions for PRL - including secure 2-party computation
(S2PC), and their variants that use non-private or differentially private (DP)
blocking to ensure subquadratic cost - violate at least one of the three
desiderata. In particular, S2PC techniques guarantee end-to-end privacy but
have either low recall or quadratic cost. In contrast, no end-to-end privacy
guarantee has been formalized for solutions that achieve subquadratic cost.
This is true even for solutions that compose DP and S2PC: DP does not permit
the release of any exact information about the databases, while S2PC algorithms
for PRL allow the release of matching records.
  In light of this deficiency, we propose a novel privacy model, called output
constrained differential privacy, that shares the strong privacy protection of
DP, but allows for the truthful release of the output of a certain function
applied to the data. We apply this to PRL, and show that protocols satisfying
this privacy model permit the disclosure of the true matching records, but
their execution is insensitive to the presence or absence of a single
non-matching record. We find that prior work that combine DP and S2PC
techniques even fail to satisfy this end-to-end privacy model. Hence, we
develop novel protocols that provably achieve this end-to-end privacy
guarantee, together with the other two desiderata of PRL.
