Privately querying a database with private set membership using succinct filters

A system comprising:

• data processing hardware;
• and
• memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:
• causes the data processing hardware to perform operations comprising:
• obtaining, from a server, a probabilistic data structure representing a set of encrypted identifiers, each encrypted identifier of the set of encrypted identifiers representing an identifier of a set of identifiers encrypted with a server key controlled by the server;
• obtaining a request to determine that a query identifier is a member of the set of identifiers;
• transmitting an encryption request to the server, the encryption request requesting the server to encrypt the query identifier with the server key;
• receiving, from the server, an encrypted query identifier comprising the query identifier encrypted by the server key;
• determining, using the probabilistic data structure that uses a succinct filter, that the encrypted query identifier is not a member of the set of encrypted identifiers;
• and
• in response to determining that the encrypted query identifier is not a member of the set of encrypted identifiers, generating a notification that the query identifier is not a member of the set of identifiers.