The digital world is replete with situations in which parties wish to
exchange information, while still maintaining as much privacy as
possible. For example, email recipients might seek whether they have
friends in common with senders for automated whitelisting during spam
filtering. Or, airlines might seek to detect if passengers are listed
on a centrally-maintained "No Fly" list, yet without disclosing
everybody's travel plans to the government. Cryptographic protocols
can enable these types of set membership applications without requiring
trusted intermediaries.

We show how oblivious transfer protocols, when instantiated with
homomorphic encryption, can enable the conditional disclosure of
secrets between parties (i.e., support AND, OR, and NOT operations).
We use this generalized application of oblivious transfer to enable
the oblivious evaluation of datasets encoded in polynomials. In this
talk, we show how this polynomial-based construction can be used to
build efficient private matching (PM) and private keyword search (KS)
protocols:

1. PM [1]: We consider the problem of computing the intersection of
private datasets of two parties, where the datasets contain lists of
elements taken from a large domain. For lists of length $k$, we
obtain $O(k)$ communication overhead and $O(k ln ln k)$ computation.
We describe protocols for the semi-honest and malicious environments.

2. KS [2]: We consider the problem of privacy-preserving keyword
search, where records in the database are accessed according to their
associated keywords and where we care for the privacy of both the
client and the server. While an efficient instantiation uses our
polynomial construction, we also propose a general solution that
relies on a new connection between KS and the oblivious evaluation of
pseudorandom functions (OPRFs).

Finally, of more practical interest, we briefly describe our recent
implementation of private matching as part of an anti-spam system that
uses social networks to automatically whitelist valid email [3]. We
describe performance results and some observations on how naive usage
of privacy-preserving protocols can often leak critical information.

-----

[1] Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. Efficient
Private Matching and Set Intersection. In EUROCRYPT. May 2004.

[2] Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold.
Keyword Search and Oblivious Pseudorandom Functions. In Theory of
Cryptography Conference (TCC). February 2005.

[3] Michael J. Freedman, Scott Garriss, Michael Kaminsky, Brad Karp,
David Mazieres, Haifeng Yu. Re: Reliable Email. To appear at
Networked Systems Design and Implementation (NSDI). May 2006.