Title: Efficient robust private set intersection

Authors: Dana Dachman-Soled; Tal Malkin; Mariana Raykova; Moti Yung

Addresses: Microsoft Research New England, 1 Memorial Drive, Cambridge, MA 02142, USA. ' Columbia University, 1214 Amsterdam Avenue, New York, New York 10027, USA. ' Columbia University, 1214 Amsterdam Avenue, New York, New York 10027, USA. ' Google Inc. and Columbia University, 1214 Amsterdam Avenue, New York, New York 10027, USA

Abstract: Computing set intersection privately and efficiently between two mutually mistrusting parties is an important basic procedure in the area of private data mining. Assuring robustness, namely, coping with potentially arbitrarily misbehaving (i.e., malicious) parties, while retaining protocol efficiency (rather than employing costly generic techniques) is an open problem. In this work, the first solution to this problem is presented.

Keywords: set intersection; secure two-party computation; cryptographic protocols; privacy preservation; privacy protection; data mining; cryptography; robust private sets; mutual mistrust; protocol efficiency; security.

DOI: 10.1504/IJACT.2012.048080

International Journal of Applied Cryptography, 2012 Vol.2 No.4, pp.289 - 303

Published online: 30 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article