att_abstract={{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 the variants of S2PC techniques, even for the
solutions that compose DP and S2PC, because of a fundamental
disconnect between these two privacy guarantees: 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.
Our empirical evaluation also shows that our protocols obtain high
recall, scale near linearly in the size of the input databases and
the output set of matching pairs, and have communication and
computational costs that are at least 2 orders of magnitude smaller
than S2PC baselines.}},
	att_authors={ds8961, cf5264},
	att_copyright_notice={{(c) ACM, 2017. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Conference on Computer and Communications Security (CCS) {{, 2017-10-30}}.
	author={Divesh Srivastava and Cheryl Flynn and Xi He and Ashwin Machanavajjhala},
	institution={{ACM Conference on Computer and Communications Security (CCS)}},
	title={{Composing Differential Privacy and Secure Computation: A case study on scaling private record linkage}},