Search

EP-4406195-B1 - PRIVATE SET MEMBERSHIP USING SUCCINCT FILTERS

EP4406195B1EP 4406195 B1EP4406195 B1EP 4406195B1EP-4406195-B1

Inventors

  • YEO, Kevin
  • SEO, JOON YOUNG
  • PATEL, SARVAR

Dates

Publication Date
20260513
Application Date
20220913

Claims (15)

  1. A computer-implemented method (600) when executed by data processing hardware (122) of a client device (10) causes the data processing hardware (122) to perform operations comprising: obtaining, from a server (140), a succinct filter (400) comprising a set of encrypted identifiers (152E), each encrypted identifier of the set of encrypted identifiers (152E) encrypted with a server key (162) controlled by the server (140); obtaining a request (170) from a user (12), the request (170) requesting the data processing hardware (122) to determine whether a query identifier (172) is a member of a set of identifiers (152), the set of identifiers (152) corresponding to the set of encrypted identifiers (152E); transmitting an encryption request (212) to the server (140), the encryption request (212) requesting the server (140) to encrypt the query identifier (172); receiving, from the server (140), an encrypted query identifier (172E) comprising the query identifier (172) encrypted by the server key (162); determining, using the succinct filter (400), whether the encrypted query identifier (172E) is not a member of the set of encrypted identifiers (152E); and when the encrypted query identifier (172E) is not a member of the set of encrypted identifiers (152E), reporting, to the user (12), that the query identifier (172) is not a member of the set of identifiers (152).
  2. The method (600) of claim 1, wherein the operations further comprise, when the encrypted query identifier (172E) is a member of the set of encrypted identifiers (152E), reporting, to the user (12), that the query identifier (172) may be a member of the set of identifiers (152).
  3. The method (600) of claim 1 or claim 2, wherein the operations further comprise, when using the succinct filter (400) determines that the encrypted query identifier (172E) may be a member of the set of encrypted identifiers (152E): determining, using a cryptographic protocol (230) based on ring learning with errors, whether the encrypted query identifier (172E) is a member of the set of encrypted identifiers (152E); when using the cryptographic protocol (230) determines that the encrypted query identifier (172E) is a member of the set of encrypted identifiers (152E), reporting, to the user (12), that the query identifier (172) is a member of the set of identifiers (152); and when using the cryptographic protocol (230) determines that the encrypted query identifier (172E) is not a member of the set of encrypted identifiers (152E), reporting, to the user (12), that the query identifier (172) is not a member of the set of identifiers (152).
  4. The method (600) of any of claims 1-3, wherein the succinct filter (400) comprises a cuckoo filter or a bloom filter.
  5. The method (600) of any of claims 1-4, wherein the succinct filter (400) comprises a plurality of portions (410), each portion (410) of the plurality of portions (410) comprising a respective subset of encrypted identifiers (152E).
  6. The method (600) of claim 5, wherein the operations further comprise: receiving, from the server (140), an update to one of the plurality of portions (410); and replacing the one of the plurality of portions (410) with the updated portion (410), wherein the operations optionally further comprise, prior to receiving the update to the one of the plurality of portions (410), requesting the update from the server (140).
  7. The method (600) of any of claims 1 to 6, wherein: the encryption request (212) comprises an oblivious pseudorandom function; and the oblivious pseudorandom function conceals an identity of the query identifier (172) from the server (140).
  8. The method (600) of any of claims 1 to 7, wherein a storage size of the succinct filter (400) is less than a storage size of the set of encrypted identifiers (152E), and/or wherein the set of identifiers (152) comprises a set of Uniform Resource Locators, URLs, and the set of encrypted identifiers (152E) comprises the set of URLs encrypted with the server key (162).
  9. A system (100) comprising a client device (10) and a server (140), the client device (10) comprising: data processing hardware (122); and memory hardware (124) in communication with the data processing hardware (122), the memory hardware (124) storing instructions that when executed on the data processing hardware (122) cause the data processing hardware (122) to perform operations comprising: obtaining, from the server (140), a succinct filter (400) comprising a set of encrypted identifiers (152E), each encrypted identifier of the set of encrypted identifiers (152E) encrypted with a server key (162) controlled by the server (140); obtaining a request (170) from a user (12), the request (170) requesting the data processing hardware (122) to determine whether a query identifier (172) is a member of a set of identifiers (152), the set of identifiers (152) corresponding to the set of encrypted identifiers (152E); transmitting an encryption request (212) to the server (140), the encryption request (212) requesting the server (140) to encrypt the query identifier (172); receiving, from the server (140), an encrypted query identifier (172E) comprising the query identifier (172) encrypted by the server key (162); determining, using the succinct filter (400), whether the encrypted query identifier (172E) is not a member of the set of encrypted identifiers (152E); and when the encrypted query identifier (172E) is not a member of the set of encrypted identifiers (152E), reporting, to the user (12), that the query identifier (172) is not a member of the set of identifiers (152).
  10. The system (100) of claim 9, wherein the operations further comprise, when the encrypted query identifier (172E) is a member of the set of encrypted identifiers (152E), reporting, to the user (12), that the query identifier (172) may be a member of the set of identifiers (152).
  11. The system (100) of claim 9 or 10, wherein the operations further comprise, when using the succinct filter (400) determines that the encrypted query identifier (172E) may be a member of the set of encrypted identifiers (152E): determining, using a cryptographic protocol (230) based on ring learning with errors, whether the encrypted query identifier (172E) is a member of the set of encrypted identifiers (152E); when using the cryptographic protocol (230) determines that the encrypted query identifier (172E) is a member of the set of encrypted identifiers (152E), reporting, to the user (12), that the query identifier (172) is a member of the set of identifiers (152); and when using the cryptographic protocol (230) determines that the encrypted query identifier (172E) is not a member of the set of encrypted identifiers (152E), reporting, to the user (12), that the query identifier (172) is not a member of the set of identifiers (152).
  12. The system (100) of any of claims 9 to 11, wherein the succinct filter (400) comprises a cuckoo filter or a bloom filter.
  13. The system (100) of any of claims 9 to 12, wherein the succinct filter (400) comprises a plurality of portions (410), each portion (410) of the plurality of portions (410) comprising a respective subset of encrypted identifiers (152E),wherein the operations optionally further comprise: receiving, from the server (140), an update to one of the plurality of portions (410); and replacing the one of the plurality of portions (410) with the updated portion (410), and wherein the operations optionally further comprise, prior to receiving the update to the one of the plurality of portions (410), requesting the update from the server (140).
  14. The system (100) of any of claims 9 to 13, wherein: the encryption request (212) comprises an oblivious pseudorandom function; and the oblivious pseudorandom function conceals an identity of the query identifier (172) from the server (140).
  15. The system (100) of any of claims 9 to 14, wherein a storage size of the succinct filter (400) is less than a storage size of the set of encrypted identifiers (152E), and/or wherein the set of identifiers (152) comprises a set of Uniform Resource Locators, URLs, and the set of encrypted identifiers (152E) comprises the set of URLs encrypted with the server key (162).

Description

TECHNICAL FIELD This disclosure relates to determining private set membership using succinct filters. BACKGROUND Private set membership is a cryptographic problem where a server or other device maintains a set of identifiers and a client desires to query whether a query identifier is a member of the server-held set in a privacy-preserving manner. For example, the client may desire to keep the query identifier secret from the server and/or the server may desire to keep the set of identifiers secret from the client. US 10,635,824 B1 discloses methods and apparatus for private set membership using aggregation for reduced communications. MESKANEN TOMMI ET AL: "Private Membership Test for Bloom Filters", XP032819695, discloses protocols for private membership testing. ASRA ALI ET AL: "Communication--Computation Trade-offs in PIR", XP061033976, discloses methods and apparatus for private set membership using aggregation. SUMMARY The claimed subject-matter is defined in the independent claims. The dependent claims define embodiments thereof. One aspect of the disclosure provides a computer-implemented method that, when executed by data processing hardware, causes the data processing hardware to perform operations. The operations include obtaining, from a server, a filter including a set of encrypted identifiers. Each encrypted identifier of the set of encrypted identifiers is encrypted with a server key controlled by the server. The operations also include obtaining a request from a user. The request requests the data processing hardware to determine whether a query identifier is a member of a set of identifiers. The set of identifiers correspond to the set of encrypted identifiers. The operations also include transmitting an encryption request to the server. The encryption request requests the server to encrypt the query identifier. The operations include receiving, from the server, an encrypted query identifier including the query identifier encrypted by the server key. The operations also include determining, using the filter, whether the encrypted query identifier is not a member of the set of encrypted identifiers and when the encrypted query identifier is not a member of the set of encrypted identifiers, reporting, to the user, that the query identifier is not a member of the set of identifiers. Implementations of the disclosure may include one or more of the following optional features. In some implementations, the operations further include, when the encrypted query identifier is a member of the set of encrypted identifiers, reporting, to the user, that the query identifier may be a member of the set of identifiers. Optionally, the operations further include, when using the filter determines that the encrypted query identifier may be a member of the set of encrypted identifiers, determining, using a cryptographic protocol based on ring learning with errors, whether the encrypted query identifier is a member of the set of encrypted identifiers. When using the cryptographic protocol determines that the encrypted query identifier is a member of the set of encrypted identifiers, the operations include reporting, to the user, that the query identifier is a member of the set of identifiers and when using the cryptographic protocol determines that the encrypted query identifier is not a member of the set of encrypted identifiers, the operations include reporting, to the user, that the query identifier is not a member of the set of identifiers. In some implementations, the filter includes a cuckoo filter or a bloom filter. In some examples, the filter includes a plurality of portions and each portion of the plurality of portions includes a respective subset of encrypted identifiers. In these examples, the operations further includes receiving, from the server, an update to one of the plurality of portions and replacing the one of the plurality of portions with the updated portion. The operations may further include, prior to receiving the update to the one of the plurality of portions, requesting the update from the server. In some implementations, the encryption request includes an oblivious pseudorandom function and the oblivious pseudorandom function conceals an identity of the query identifier from the server. In some examples, a storage size of the filter is less than a storage size of the set of encrypted identifiers. The set of identifiers may include a set of Uniform Resource Locators (URLs) and the set of encrypted identifiers includes the set of URLs encrypted with the server key. Another aspect of the disclosure provides data processing hardware and memory hardware in communication with the data processing hardware. The memory hardware stores instructions that when executed on the data processing hardware cause the data processing hardware to perform operations. The operations include obtaining, from a server, a filter including a set of encrypted identifiers. Each encrypted identifier of the set of enc