David Pointcheval

ENS Paris, France

Efficient Private Disjointness Testing

Secure Two-Party computation is a very concrete tool that allows two players to compute a function on their private inputs so that they can get the output but without revealing any additional information about their own inputs. A famous illustration is the Yao's Millionaires' Problem. But another useful example is the private disjointness testing: on two private input sets, the players will learn whether the two sets are disjoint or have a non-empty intersection.
With a new ElGamal encryption variant, combined with the Paillier encryption scheme, we will show how to perform such a private test quite efficiently (in terms of round and communication complexity). Our approach is general, and provides efficient constructions for many two-party computations on the integers.

This is a joint work with Geoffroy Couteau and Thomas Peters.