Public-key encrypted bloom filters with applications to private set intersection
AssigneeSap SE
InventorFlorian Kerschbaum
Life of this patent
Estimating the term…
Abstract
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.
Claims19
A computer-implemented method, comprising:
- retrieving, from computer-readable memory, a first set, the first set comprising a plurality of elements;
- adding, using a computing device of a first entity, elements of the first set to a first Bloom filter, the first Bloom filter comprising a plurality of bits;
- encrypting, using the computing device, each bit of the plurality of bits of the first Bloom filter to provide a first encrypted Bloom filter, encrypting being achieved using homomorphic, public key encryption;
- and
- transmitting, to a computing device of an entity, the first encrypted Bloom filter, the entity performing an operation on the first encrypted Bloom filter.
A non-transitory computer-readable storage medium coupled to one or more processors having instructions stored thereon which, when executed by the one or more processors, cause the one or more processors to perform operations comprising:
- retrieving, from computer-readable memory, a first set, the first set comprising a plurality of elements;
- adding, using a computing device of a first entity, elements of the first set to a first Bloom filter, the first Bloom filter comprising a plurality of bits;
- encrypting, using the computing device, each bit of the plurality of bits of the first Bloom filter to provide a first encrypted Bloom filter, encrypting being achieved using homomorphic, public key encryption;
- and
- transmitting, to a computing device of an entity, the first encrypted Bloom filter, the entity performing an operation on the first encrypted Bloom filter.
A system, comprising:
- one or more computers associated with a first entity;
- and
- a computer-readable medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising:
- retrieving, from computer-readable memory, a first set, the first set comprising a plurality of elements;
- adding elements of the first set to a first Bloom filter, the first Bloom filter comprising a plurality of bits;
- encrypting each bit of the plurality of bits of the first Bloom filter to provide a first encrypted Bloom filter, encrypting being achieved using homomorphic, public key encryption;
- and
- transmitting, to a computing device of an entity, the first encrypted Bloom filter, the entity performing an operation on the first encrypted Bloom filter.
Dependencies are inferred from the claim text.