Privacy—preserving data querying with authenticated denial of existence
In one embodiment, a tokenized list holder enables privacy-preserving querying with denial of existence functionality. Both an information requester and the tokenized list holder access related (or identical) tokenizing algorithms to generate tokenized terms based on original terms. Prior to receiving a query for information based on a tokenized query term, the tokenized list holder generates sorted tokenized data terms that are associated with a database. Upon receiving the query, the tokenized list holder determines that the tokenized query term is not included in the sorted tokenized data terms. The tokenized list holder then generates a signed response that specifies a gap in the sorted tokenized data terms to indicate that the information is not included in the database. Advantageously, because neither the query nor the response includes original (i.e., untokenized) terms, the privacy of both the information requester and the database is preserved.
1. A computer-readable storage medium including instructions that, when executed by a processor, cause the processor to perform the steps of:
generating a plurality of sorted tokenized data terms that are associated with a database and based on a first tokenizing algorithm and a sorting order;
receiving a query for information that includes a tokenized query term derived using the first tokenizing algorithm or a related second tokenizing algorithm;
determining that the information is not included in the database based on the plurality of sorted tokenized data terms; and
in response, generating a signed response that specifies a gap in the plurality of sorted tokenized data terms to indicate that the information is not included in the database.
2. The computer-readable storage medium of claim 1 , wherein generating the signed response comprises:
determining that the tokenized query term lies between a first tokenized data term included in the plurality of sorted tokenized data terms and a second tokenized data term included in the plurality of sorted tokenized data terms; and
generating a gap statement that includes the first tokenized data term and the second tokenized data term.
3. The computer-readable storage medium of claim 1 , wherein generating the plurality of sorted tokenized data terms comprises:
identifying a plurality of data terms that are included in the database;
interacting with a centralized tokenizing authority that implements a least a portion of the first tokenizing algorithm to generate a plurality of tokenized data terms based on the plurality of data terms; and
sorting the plurality of tokenized data terms based on the sorting order.
4. The computer-readable storage medium of claim 3 , wherein interacting with the centralized tokenizing authority comprises:
applying a blinding algorithm to the plurality of data terms to generate a plurality of blinded data terms;
transmitting the plurality of blinded data terms to the centralized tokenizing authority and, in response, receiving a plurality of blinded tokenized data terms from the centralized tokenizing authority; and
applying an unblinding algorithm to the plurality of blinded tokenized data terms to generate the plurality of tokenized data terms.
5. The computer-readable storage medium of claim 4 , wherein the blinding algorithm is a homomorphism with respect to the first tokenizing algorithm.
6. The computer-readable storage medium of claim 1 , wherein the tokenized query term is derived from a query term using the first tokenizing algorithm or the related second tokenizing algorithm.
7. The computer-readable storage medium of claim 6 , wherein the query term comprises either a domain name or an Internet Protocol address, and the query comprises either a WHOIS request or a registration data access protocol (RDAP) request.
8. The computer-readable storage medium of claim 1 , wherein the first tokenizing algorithm is compliant with an NSEC5 protocol.
9. A method for querying a database, comprising:
determining a tokenized query term based on a query term and a first tokenizing algorithm;
transmitting a request for information to a tokenized list holder that includes the tokenized query term, wherein the tokenized list holder has access to the database and a plurality of tokenized data terms that are associated with the database; and
receiving a signed response from the tokenized list holder that specifies a gap in the plurality of tokenized data terms where the tokenized query term should be listed based on a predetermined sort order.
10. The method of claim 9 , further comprising verifying a digital signature associated with the signed response.
11. The method of claim 9 , wherein the plurality of tokenized data terms are derived from the database using the first tokenizing algorithm or a related second tokenizing algorithm.
12. The method of claim 9 , wherein determining the tokenized query term comprises transmitting the query term to a centralized tokenizing authority that implements the first tokenizing algorithm and, in response, receiving the tokenized query term from the centralized tokenizing authority.
13. The method of claim 9 , wherein the query term comprises either a domain name or an Internet Protocol (IP) address.
14. The method of claim 9 , wherein the query comprises a WHOIS request or a registration data access protocol (RDAP) request.
15. The method of claim 9 , wherein the tokenized list holder comprises a name server.
16. The method of claim 9 , wherein determining the tokenized query term comprises:
applying a blinding function to the query term to generate a blinded query term;
transmitting the blinded query term to a centralized tokenizing authority that implements at least a portion of the first tokenizing algorithm and, in response, receiving one or more blinded responses from the centralized tokenizing authority; and
generating the tokenized query term based on the one or more blinded responses.