Privacy—preserving data querying with authenticated denial of existence

• US 10,565,394 B2
• Filed: 09/20/2016
• Issued: 02/18/2020
• Est. Priority Date: 10/25/2012
• Status: Active Grant

• Current Assignee: VeriSign, Inc.
• Original Assignee: VeriSign, Inc.
• Inventors: Kaliski, Jr., Burton S.
• Primary Examiner(s): Le, Hung D
• Application Number:
  US15/271,192
• Publication Number:
  US 20170262651A1
• Time in Patent Office: 1,246 Days
• Field of Search: None
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: G06F 21/6263 during internet communication, e.g. revealing personal data from cookies
• CPC Class Codes: H04L 61/302 Administrative registration, e.g. for domain names at internet corporation for assigned names and numbers [ICANN]
• CPC Class Codes: H04L 61/3025 Domain name generation or assignment
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 63/0407 wherein the identity of one or more communicating identities is hidden cryptographic mechanisms or cryptographic arrangements for anonymous credentials or for identity based cryptographic systems H04L9/00
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/20 for managing network security; network security policies in general filtering policies H04L63/0227
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

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.

Claims

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.