Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for retrieving, from computer-readable memory, a set, the set including a plurality of elements, adding, using a computing device, elements of the set to a Bloom filter, the Bloom filter including a plurality of bits, and encrypting, using the computing device, each bit of the plurality of bits of the Bloom filter to provide an encrypted Bloom filter, encrypting being achieved using homomorphic, public key encryption. Implementations are further directed to performing operations on the encrypted Bloom filter, and performing private set intersection (PSI) using the encrypted Bloom filter.