KR20240101543A - Privacy-Protecting Domain Name Service (DNS) - Google Patents

Abstract

The described systems and methods enable performing privacy-preserving DNS exchange. In some embodiments, a client machine participates in a private information retrieval (PIR) exchange with a name server. In response to receiving an encrypted query generated according to a domain name from a client, the name server may extract records (e.g., IP addresses) from the domain name database without decrypting each query. . Some embodiments achieve this information retrieval by using homomorphic encryption.

Description

Privacy-Protecting Domain Name Service (DNS)

The present invention relates to systems and methods for protecting the privacy of online communications, particularly for preventing remote entities from obtaining information about the browsing habits of Internet users.

Internet browsing has become an essential part of modern life and work. As Internet access explodes, some commercial entities, as well as malicious entities, are increasingly interested in accessing and analyzing the browsing history and/or patterns of individual Internet users. And this information can be used to target advertisements and provide various services to each user. However, the same type of information may be used to profile and/or target users based on more sensitive aspects of their personality, such as sexual orientation, political and religious views, race, drug use, intelligence, etc. More and more Internet users are concerned about their privacy and how allowing companies and/or countries to monitor their online behavior affects their rights and exposes them to various kinds of threats and abuses. I'm doing it.

A common way a user's browsing history is collected is through DNS (Domain Name Service) requests. DNS generally refers to a service that translates domain names into network (e.g. IP) addresses and then allows electronic devices to exchange data over communications networks. Because DNS was originally designed for speed and convenience, not privacy, DNS providers and Internet service providers have traditionally had virtually unimpeded access to DNS requests issued by clients. There have been some efforts in recent years to provide alternatives to traditional DNS. Some examples include the suite of protocols known as 'DNS over Transport Layer Security (TLS)' and 'DNS over Hypertext Transfer Protocol Secure (HTTPS)', among others. This version of DNS encrypts individual requests from the client and/or server responses so that, in principle, no entity except the end client and name server has access to the individual data. For example, these protocols can prevent Internet service providers and/or malicious third parties from snooping on users' DNS requests. However, because data is only encrypted in transit between the client and the name server, these protocols do not prevent DNS providers themselves from collecting individual users' browsing data.

Therefore, there is a significant need to develop more capable and robust privacy-preserving domain name services.

According to one aspect, a method of performing a domain name service (DNS) lookup includes, in response to receiving an indicator of a domain name, determining whether privacy conditions are satisfied according to the domain name. In order to do so, it includes employing at least one hardware processor in the computer system. The method, in response to determining whether the privacy condition is satisfied, formulating a private query that, if so, includes encryption of a hash index indicating the location of the record in the domain name database. It further includes, wherein the hash index is encrypted according to a homomorphic encryption procedure, and the hash index is determined according to the domain name. The method includes, in response to generating the private query, sending the private query to a name server configured to perform an encrypted lookup to the domain name database according to the private query, thereby producing encryption of the record. ; and in response to receiving a private response containing encryption of the record from the name server, decrypting the contents of the private response according to a homomorphic decryption procedure.

According to another aspect, a computer system includes at least one hardware processor configured to, in response to receiving an indicator of a domain name, determine whether a privacy condition is satisfied according to the domain name. the at least one hardware processor is further configured to, in response to determining whether the privacy condition is satisfied, generate a private query that, if so, includes encryption of a hash index indicating the location of the record in the domain name database, The hash index is encrypted according to a homomorphic encryption procedure, and the hash index is determined according to the domain name. The at least one hardware processor, in response to generating the private query, transmits the private query to a name server configured to perform an encrypted lookup to a domain name database according to the private query to perform encryption of the record. to create; and in response to receiving a private response including encryption of the record from the name server, decrypt the content of the private response according to a homomorphic decryption procedure.

According to another aspect, a non-transitory computer-readable medium, when executed by at least one hardware processor of a computer system, causes the computer system, in response to receiving an indicator of a domain name, to set a privacy condition to the domain name. Stores a command that determines whether it is satisfied according to . The instructions also cause the computer system, in response to determining whether the privacy condition is satisfied, to generate a private query that includes an encryption of a hash index indicating the location of the record in the domain name database, and if so, the computer system is configured to: , the hash index is encrypted according to a homomorphic encryption procedure, and the hash index is determined according to the domain name. The instructions also cause the computer system, in response to generating the private query, to transmit the private query to a name server configured to perform an encrypted lookup to the domain name database in accordance with the private query to retrieve the record. generate an encryption of; And in response to receiving a private response containing encryption of the record from the name server, decrypt the contents of the private response according to a homomorphic decryption procedure.

According to another aspect, a server computer system is configured to participate in Domain Name Service (DNS) transactions with a plurality of clients. the server computer system includes at least one hardware processor configured to receive a private query from a client of the plurality of clients, the private query comprising encryption of a hash index indicating the location of a record in a domain name database, The hash index is encrypted according to a homomorphic encryption procedure, and the hash index is determined according to the domain name. wherein the at least one hardware processor, in response to receiving the private query, performs an encrypted lookup to the domain name database according to the private query to produce an encryption of the record; and transmit a private response including encryption of the record to the client.

The foregoing aspects and advantages of the present invention will be better understood by reading the following detailed description and referring to the following drawings:
1 illustrates an exemplary privacy preserving electronic communication system in accordance with some embodiments of the present invention.
2 illustrates an exemplary Domain Name Service (DNS) server system including a plurality of communicatively coupled name servers in accordance with some embodiments of the present invention.
Figure 3 shows a typical DNS transaction as known in the art.
Figure 4 shows DNS queries and responses as known in the prior art.
Figure 5 shows a plurality of example partially qualified domain names (PQDNs) and example fully qualified domain names (FQDNs) of an Internet domain, according to some embodiments of the invention.
Figure 6 illustrates an example domain name space according to some embodiments of the invention.
Figure 7 shows a DNS transaction according to some embodiments of the invention, where the transaction includes a private query and a private reply.
Figure 8 shows example content of a domain name database according to some embodiments of the invention.
9 shows an example Private Information Retrieval (PIR) query and an example PIR response according to some embodiments of the present invention.
Figure 10 illustrates example components executing on a client system according to some embodiments of the invention.
11 illustrates an exemplary sequence of steps performed by a client system DNS resolver (translator) in accordance with some embodiments of the invention.
Figure 12 shows example components running on a DNS server system according to some embodiments of the invention.
13 illustrates an example sequence of steps performed by a DNS server database maintenance module in accordance with some embodiments of the invention.
Figure 14 shows an example sequence of steps performed by a DNS server PIR module in accordance with some embodiments of the invention.
Figure 15 shows an example sequence of steps performed by a client DNS resolver (resolver) to perform a DNS lookup according to some embodiments of the present invention.
Figure 16 shows an example set of domains grouped into clusters according to some embodiments of the invention.
Figure 17 shows example hardware components of a computing appliance configured to perform some of the methods and algorithms described herein.

In the following description, it is understood that all connections mentioned between structures may be direct operative connections or indirect operative connections through intermediate structures. A set of components includes one or more components. Any enumeration of components is understood to refer to at least one component. A plurality of components includes at least two components. Unless otherwise required, any method steps described are not necessarily performed in the specific order described. A first component (e.g., data) derived from a second component can be a first component generated by processing the same first component as the second component as well as the second component and, optionally, other data. contains elements. Determining or judging according to a parameter includes determining or judging according to a parameter and optionally according to other data. Unless otherwise specified, an indicator of some quantity/data may be the quantity/data itself, or an indicator that is different from the quantity/data itself. A computer program is a sequence of processor instructions that perform a task. The computer programs described in some embodiments of the invention may be stand-alone software objects or sub-objects (e.g., subroutines, libraries) of other computer programs. A network domain consists of a group of interconnected computing devices that form individual parts of a computer network. An Internet domain is a network domain connected to the public internet. A domain name is a label/alias that identifies the address of a network/Internet domain. The term 'database' is used here to refer to any organized collection of data. Computer-readable media includes non-transitory media such as magnetic, optical, and semiconductor storage media (e.g., hard drives, optical disks, flash memory, DRAM), as well as conductive cables and fiber optic links. Includes communication links. According to some embodiments, the present invention provides, among other things, hardware (e.g., one or more processors) programmed to perform the methods described herein, as well as encoding instructions for performing the methods described herein. A computer system including a computer-readable medium is provided.

The following description describes embodiments of the present invention by way of example and is not necessarily limiting.

1 shows a privacy preserving electronic communication system 10 in accordance with some embodiments of the present invention. A set of exemplary client devices 12a-f communicate with each other and/or a remote content server computer 16 over communication links to exchange data such as web content, electronic messages, various documents, and the like. Client devices 12a-f may include personal computer systems, enterprise mainframe computers, mobile computing platforms (e.g., laptop computers, tablets, mobile phones), entertainment devices (e.g., televisions, gaming consoles), wearable devices (e.g., e.g., smartwatches, fitness bands), home appliances (e.g., refrigerators, washing machines), and any device that includes a processor, memory, and a communication interface that allows each device to communicate with other devices/computer systems. may include other electronic devices.

In the example configuration of Figure 1, client devices 12a-e are interconnected by a local network 13, such as a local area network (LAN). In one example use case scenario, devices 12a-e represent electronic devices within the home and local network 13 represents the home network. In another use case scenario, client devices 12a-e may represent computers located in a corporate office or department and interconnected by a corporate LAN. Devices 12a-e may be further connected to an extended network 15, such as a wide area network (WAN) and/or the Internet. In some embodiments, router 14 may, for example, assign network addresses to clients 12a-e connected to local network 13 and route individual communications according to these addresses. ) Control and/or manage data traffic within. In some embodiments, as shown in Figure 1, router 14 allows at least a portion of the network traffic between client devices 12a-e and extended network 15 to traverse router 14. In the sense it is configured as a gateway to the local network 13. Other client devices, such as the example device 12f of Figure 1, may not be connected to the local network 13, but instead directly to the extended network 15, for example via a mobile phone network or a public WiFi hotspot. You can connect.

Domain name service (DNS) server system 20 provides privacy preserving domain name services to client devices 12a-f in accordance with some embodiments of the present invention. Domain name services herein include the translation of domain names into network addresses and/or vice versa, and, inter alia, domain registration data (e.g. WHOIS data) and whether a particular domain belongs to a particular category/cluster of domains. , is understood to include providing other domain information, including indicators indicating whether the domain distributes adult content, whether the domain is involved in malicious activity (e.g. botnets, Internet fraud), etc. DNS server system 20 generally represents a set of communicatively coupled computers, such as the example name servers 20a-d shown in Figure 2. The functionality of each of these name servers is described in detail below. Sending a request to the DNS server system 20 includes sending each request to one of the name servers 20a-d.

A typical data exchange between client device 12a-f and content server 16 involves several steps. Transmission typically requires knowledge of the network address (e.g., Internet Protocol - IP address) of the content server 16. Often this address is not known to the client device for various reasons. For example, there may be multiple mirror content server machines, and clients may be dynamically assigned to the most convenient one depending on the current load on each mirror server or based on the current geographic location of the client device. However, the client device can know the domain name of the server 16. The term 'domain name' here refers to an arbitrary alias for the required network address. To establish a connection to the content server 16, a software entity running on each client device may therefore issue a request to access the respective domain name, instead of the IP address itself. In response, another software entity (e.g., a component of the operating system running on the respective client) may intercept the request, attempt to translate the alias/domain name to a real network address, and then You can send it to the correct network location. This conversion may invoke a DNS provider, such as server system 20 of Figure 1.

Figures 3-4 illustrate a typical message exchange according to DNS protocols known in the art. Client device 12 sends a DNS query 22 to DNS server system 20, where query 22 is an indicator of an Internet domain 30 (e.g., a domain name as shown in FIG. 12). and an indicator of the type of question (Q). The type of question indicates the type of DNS resource record returned by the DNS server 20. Example questions include 'A', which requests an IP address generated with the 4th version of the Internet Protocol (IPv4), and 'AAAA', which returns an IP address generated with the 6th version of the Internet Protocol (IPv6). do. Other example question/resource record types include 'TXT', 'PTR', 'LOC', etc. In response, DNS server system 20 may return to the requesting client a DNS response 24 containing an encoding of the resource record network corresponding to each domain name/alias. In the example of Figure 4, the type of record is IP address 40 in 32-bit IPv4 format. In some cases, for example, in systems using the DNS over HTTPS protocol, DNS queries 22 and/or DNS responses 24 may be encrypted.

Figure 5 shows example domain names for Internet domains. A domain name is a fully qualified domain name (FQDN) that fully and unambiguously identifies each domain through an ordered sequence of tokens/labels 32a-d separated by delimiter symbols 34 (dots in the example shown). qualified domain name) (36). A fragment of FQDN 36 containing a subset/subsequence of FQDN tokens 32a-d is commonly known as a partially qualified domain name (PQDN). Items 38a-c represent various example PQDNs of FQDN 36. Unlike FQDN 36, each PQDN 38a-c specifies each domain with some degree of ambiguity, that is, there may be multiple FQDNs with the same characteristic PQDN.

The representation of a domain name as a sequence of tokens (see Figure 5) corresponds to a tree-like hierarchical representation of the domain name space as shown in Figure 6, where each token 32a-d of FQDN 36 is a tree corresponds to a branch of , and each instance of a delimiter (e.g., a dot) corresponds to a branch point. The domain name hierarchy is at least the root level ('.'), a top level domain (TLD) level that includes tokens such as com, net, fashion, tv, and country-denoting tokens such as ro, fr, etc. There are several notable levels, including the domain level, which contains tokens such as , wikipedia, facebook, etc., and the subdomain level, which contains various domain-specific prefix tokens. Therefore, combining FQDN 36 from individual tokens corresponds to traversing the tree hierarchy from end-leaf to root, as illustrated in FIG. 6. For clarity, the token that characterizes the domain name at the TLD level (usually the last token of the FQDN 36) is considered the TLD token herein. Likewise, the token that characterizes the domain name at the domain level (typically the penultimate token of the FQDN 36) is considered a domain token herein. Finally, any token preceding the domain token in FQDN 36 is considered a prefix token here.

A domain name service may be organized so that no single name server can independently resolve a fully qualified domain name. Instead, the domain namespace is divided into multiple authority areas, with each authority area resolved by a separate name server. Typically, each authority area includes a selected subtree/branch of the domain name hierarchy, as illustrated by example authority areas 37a-c in Figure 6. In the example shown, name servers 20b-c-d each resolve domain names within authority areas 37a-b-c.

In some embodiments, resolving an FQDN into a corresponding IP address proceeds in an iterative manner, with each successive iteration proceeding to successive levels of the domain name hierarchy. Each successive repetition may be determined according to a distinctive token of the FQDN 36. Each iteration may include sending a DNS query to a distinct nameserver, and receiving a DNS response specifying the IP address of the other nameserver in response. The server that resolves the TLD level of the domain name, that is, the TLD token such as '.org', is considered the root name server in this specification (see, for example, the root name server 20b). Servers that resolve (resolve) domain names, i.e. domain tokens of FQDNs (36), at the domain level are considered TLD name servers herein (e.g., servers that resolve between domains of the '.org' top-level domain). (see TLD nameserver (20c)). Servers that resolve the subdomain level, i.e. the prefix token(s) of the FQDN 36, are considered herein as authoritative servers for each domain (e.g. 'wikimedia.org' (see authoritative server 20d decomposing between subdomains). In one example according to Figure 6, resolving the domain name 'text-lb.codfw.wikimedia.org' involves sending a first DNS query to the root name server 20b and, in response, from the name server 20b It involves receiving the IP address of the TLD nameserver (20c), which is responsible for resolving the authority zone of the '.org' top-level domain. The next step in the iteration is to send a second DNS query to the TLD nameserver 20c and, in response, receive from the nameserver 20c the IP address of the authoritative nameserver 20d for the 'wikimedia.org' domain. It may include doing. Another step in the iteration involves sending a third DNS query to the authoritative nameserver 20d, and in response, content identified by the FQDN 'text-lb.codfw.wikimedia.org' from the nameserver 20d. This may include receiving the IP address of the server.

In some embodiments, queries sent in all stages of iterative DNS resolution include a PQDN. In alternative privacy enhancing embodiments, the DNS query sent in each iteration may include, among other things, a distinctive PQDN (eg, a single token) and possible additional characters such as the wildcard '*'. For example, the PQDN sent to the selected nameserver may contain each FQDN leaving only one token more than each nameserver's authority zone. In the example of Figure 6, a DNS query sent to the root name server 20b may query the PQDN '.org', while a DNS query sent to the TLD name server 20c may query the PQDN '*.wikimedia.org'. You can ask questions about

In some embodiments, this iterative domain resolution is performed by a specialized resolver name server 20a (FIG. 2), which maintains a DNS cache containing the results of recent and/or popular DNS lookups. can be managed additionally. In this configuration, client devices 12a-f may send a single DNS query to resolver name server 20a, with each query requesting resolution of an FQDN. The name server 20a can then perform cache lookups and/or perform necessary repetitive DNS queries on behalf of the client. Once each FQDN is completely resolved (resolved), the name server 20a may return the IP address associated with each FQDN to the requesting client.

Figure 7 shows an example privacy preserving DNS transaction according to some embodiments of the invention. A transaction involves a first party (e.g., a client) issuing a request for an item to a second party (e.g., a server), and the second party receives the requested item from a data store/database. , where the search procedure is performed without revealing the item to the second party. In other words, the server does not know which item was requested, but nevertheless retrieves the requested item from the repository. In one example privacy preserving transaction, as described below, a request issued by a client is encrypted, and the server retrieves an encrypted version of the requested item without decrypting the request. Therefore, customer privacy is protected.

In some embodiments, privacy-preserving DNS transactions are performed according to a private information retrieval procedure (PIR). The example exchange depicted in FIG. 7 is one in which client device 12 (represented generally any of client devices 12a-f in FIG. 1) sends a private query (illustrated as PIR query 52) to a DNS server system. 20 and, in response, receiving a private response (exemplified by PIR response 54) from server system 20.

In some embodiments, the PIR procedure uses homomorphic encryption to ensure privacy of the exchange. Homomorphic encryption is a specific type of encryption that allows you to perform certain calculations (such as addition and/or multiplication) on encrypted data, and decrypting the results of these calculations makes it possible to perform each calculation on an unencrypted version of the same data. The same output as applied is produced. In other words, Enc (m)=c represents a homomorphic encryption operation, where m represents the plaintext message, c represents the corresponding ciphertext, and Dec(c)=m represents the Represents the homomorphic decryption operation to recover each message, and Eval (F, {c ₁ , ..., c _k })=C is in the set of ciphertext c _i . By applying function F It represents the homomorphic evaluation procedure for generating the encrypted ciphertext C , as follows:

[One]

Here m _i =Dec(c _i ), i =1, ..., k . In formal mathematical language, the encryption and decryption procedures of a homomorphic encryption system are called homomorphism between the plaintext space and the ciphertext space.

Several homomorphic encryption schemes/cipher systems are known in the art. A system that protects homomorphic properties against arbitrary combinations of addition and multiplication is generally known as fully homomorphic . For example, among them is the GSW (Gentry-Sahai-Waters) system. Other systems/algorithms are isomorphic for certain types of operations, for example only addition in the case of the Paillier system and only multiplication in the case of the Rivest-Shamir-Adelman (RSA) system. This system is known in the art as partial homomorphic . In contrast, ciphers that do not have the homomorphism properties described above are considered non-homomorphic herein. Examples of non-homomorphic ciphers include the Advanced Encryption Standard (AES) and other ciphers used in the Transport Layer Security (TLS) family of communications protocols.

In an example PIR procedure using homomorphic encryption, the function F may represent a set of operations corresponding to performing a database lookup. As a simple example, the server holds three elements in database D= { a, b, c }. The client attempts to retrieve the second element (i.e. ' b ') without revealing that information to the server. The client can indicate the desired element using a lookup index, for example, a bitmap I containing zeros everywhere except the position of the desired element in the database D. In the current example, I= {0, 1, 0}. The client can then homomorphically encrypt each bitmap and transmit it to the server. In turn, the server can apply function F to the encrypted bitmap:

, [2]

Here, * represents matrix multiplication and T represents transposition. The server then sends the generated encrypted vector C back to the client. The homomorphism property guarantees that decrypting C produces the same result as applying function F to the unencrypted bitmap I.

[3]

Therefore, the client searches for b while the server only looks at the encrypted bitmap and performs all associations without decrypting the information received from the client.

In some embodiments, DNS server system 20 is communicatively coupled to domain name database 50, which stores a set of records indexed according to domain names. An index attached to each record may indicate the location of each record within each data store, or may otherwise enable selective identification/retrieval of each record in/from database 50. It can be made possible. In a simple example where data is organized in tabular form, each row can represent a separate record and rows are indexed by unique row numbers and/or labels. Each record may contain a set of entries representing various characteristics of each domain. In one embodiment implementing a DNS lookup service, example entries may include the IP address of a computer forming part of each domain and/or the IP address of a name server (e.g., name server 20a of FIGS. 2 and 6 -d)). Other exemplary entries include domain registration data for each domain (e.g., owner identity data, billing data, owner contact data such as street address, telephone number, email address, domain name expiration date, identifier of current domain registrar, etc.) Includes. Another example entry may include an indicator of whether or not each domain belongs to a particular category, or an indicator of the category to which each domain belongs. For example, entries can determine whether each domain is on a blacklist/whitelist, whether each domain is known to distribute fraudulent documents and/or unsolicited communications (spam), whether each domain is part of a botnet, or a denial of service. (DoS) may indicate whether or not the device is involved in an attack. Other example entries may indicate whether each domain is located within a selected geographic area or sub-network (eg, geofencing). Another example entry may indicate whether each domain is owned by or associated with a selected commercial entity. Other examples will be described below.

In some embodiments, the index that identifies each record is determined according to the domain name, thereby enabling association between the domain name and the various entries of each record. Each domain name can be either an FQDN or a PQDN. One example index includes a hash computed for each domain name. Here, hash represents the result of applying the hash function. A hash function is a specific type of mathematical function that maps data of arbitrary size to a number with a predetermined universal upper bound. Because strings can be represented as numbers, hash functions can also map arbitrary strings to numbers (e.g., 256-bit integers). Exemplary hash functions include, among others: H (n)= n mod m, where n and m are integers, checksum hashes (e.g., cyclic redundancy check (CRC)), It also includes cryptographic hash functions such as message digest hash family (e.g., MD5) and secure hash family (e.g., SHA-3). The index computed as a result of applying the hash function is considered a hash index here.

In some embodiments, an index identifying a record in domain name database 50 is computed using a cuckoo hash scheme employing a plurality of hash functions ( H ₁ , ..., H _K ). do. An example of such hashing is illustrated in FIG. 8, where the database 50 includes a plurality of hash tables 51a-c. Each row of each hash table represents an individual record indexed according to each domain name, denoted by d _j , j=1,2,... Each record contains at least an entry denoted e(d _j ) , which may contain, for example, the IP address of the respective domain. In each hash table 51a-c, an index identifying each record is determined by applying a hash function to each domain name. However, each table 51a-c uses a separate hash function to determine its respective indices. In an example cuckoo hash scheme, records are serially inserted by computing an index for each record using a first hash function. If the row indicated by each index is empty, the current record is inserted into that row. If each row is already occupied, another hash index is computed according to the second hash function, and so on. If the index calculated according to any hash function points to a row that is already occupied, one of the resident records is replaced with the current record. The previous occupant of each row is then placed in an alternative location (i.e. an index computed using a different hash function), possibly replacing another record. This process continues recursively until all records have found their positions within one or another hash table. However, it is possible for this insertion process to fail, for example by entering an infinite loop. In this case the hash table is rebuilt using a new selection of hash functions.

9 illustrates example content of a PIR query 52 and a PIR response 54 according to some embodiments of the invention. PIR query 52 may include ciphertext that includes encryption of an index identifying the selected record in domain name database 50. In the example of Figure 9, the index contains a hash of the domain name. In an embodiment that uses Cuckoo hashing, for each domain name, client device 12 may transmit multiple encrypted hash indices, each computed according to a separate hash function Hj . These encrypted hash indexes can be packaged into individual PIR queries or bundled together into a single PIR query.

In some embodiments, PIR query 52 further includes an indicator of the hash function (denoted below as h ) used to compute each hash index. For example, h may be the software version number or whether the hash function(s) used by the DNS server system 20 by each client matches the hash function used to build the hash table in the domain name database 50. It may include some other parameter values that allow you to decide whether or not to Details on how to ensure consistency of hashing are described below with respect to FIG. 13.

When database 50 includes records identified by each index, PIR response 54 may return ciphertext containing encryption of at least entry e of each database record. When no such record exists in database 50, some embodiments may create a predetermined dummy entry (e.g., a predetermined symbol indicating that database 50 does not currently have a record with the requested index). ) can be responded with encryption.

10 illustrates example components executing on client device 12 according to some embodiments of the invention. Such software may include an operating system (OS) 62, which may be any widely available operating system such as Microsoft Windows®, MacOS®, Linux®, iOS®, or Android®, among others. there is. OS 62 provides an interface between the hardware of client device 12 and a set of applications, including, among other things, domain name resolver 66 and client application 64. Client application 64 collectively refers to any computer program such as word processing, spreadsheet, image processing, gaming, telecommunications, web browsing, and social media applications, among others. In some embodiments, application 64 may, for example, filter/block traffic to/from certain Internet domains, prevent incoming and/or outgoing electronic communications from containing malicious code, unsolicited content (spam), etc. Provides computer security services to each client system by determining whether it includes.

Application 64 may connect to content server 16 and exchange data, for example, through a set of HTTP requests. As part of this exchange, application 64 may transmit an indicator of the domain name (d) to domain name resolver 66, and in response, retrieve from resolver 66 a domain name database entry e characterizing each domain. (d) can be received. In a simple DNS lookup example, e(d) may contain the IP address of domain (d). In another example, e(d) may include a set of registration data for domain d (e.g., the identity of the owner of each domain). In another example, e(d) determines whether accessing domain d exposes each client to computer security threats, for example, whether domain d is known to distribute fraudulent documents. indicator It can be included. In general, e(d) may include any data stored in domain name database 50 and indexed under domain d.

In some embodiments, domain name resolver 66 is configured to engage in privacy preserving DNS transactions with DNS server system 20 (see also Figure 8). In this way, the decomposer 66 can formulate and transmit the PIR query 52 according to the domain name received from the application 64. Decomposer 66 may further receive the PIR response 54, extract the cleartext data entry e(d ), and forward it to the application 64. The domain name resolver 66 may further include a cryptographic engine 68 configured to perform encryption and/or decryption operations. In some embodiments, engine 68 implements a set of homomorphic encryption algorithms/procedures. The encryption engine 68 may be implemented in software, hardware, or a combination thereof.

In an alternative embodiment to that illustrated in FIG. 10 , the domain name resolver 66 is on a machine distinct from the client device 12, such as a router connecting the client device 12 to the extended network 15. 14 or on another gateway device (see Figure 1), or partially or entirely on the resolver name server 20a (Figure 2).

Figure 11 shows an example sequence of steps performed by domain name resolver 66 in accordance with some embodiments of the invention. The illustrated decomposer may wait for a trigger event, such as a communication received from application 64 and/or a remote server. When an event is detected, a course of action is determined depending on the type of event. When the detected event includes a domain lookup request from application 64 (step 206 returns “yes”), then at step 208 some embodiments may configure the name server according to the received lookup request. You can choose. In some embodiments, separate types of domain name services may be provided by separate servers. For example, some name servers may be dedicated to returning IP addresses, while others may return database entries related to computer security. Moreover, when domain name service involves determining the IP address of a selected domain, some embodiments may employ PIR only when querying selected nameservers (see details below).

Next, at step 210, resolver 66 may generate at least one PIR query 52 for each domain name. Step 210 may, among other things, apply the selected hash function to each domain name and encrypt the result of the hashing, e.g., using a homomorphic encryption procedure/algorithm, to encrypt the encryption engine 68. This may include hiring. The engine 68 may use any homomorphic encryption procedure known in the art, for example, an encryption algorithm of a fully homomorphic encryption scheme (scheme) such as GSW (Gentry-Sahai-Waters). Some of these procedures can be seen, for example, in Gentry C., Halevi S. "Compressible FHE with Applications to PIR", In: Hofheinz D., Rosen A. (eds) Theory of Cryptography, TCC 2019, Lecture Notes in Computer Science, vol. 11892, Springer, Cham, for the purpose of reducing computing load on the client and/or server side. An encrypted PIR query is then sent to the nameserver of your choice.

When the trigger event includes receiving a PIR response 54 from a server, at step 216 the decomposer 66 will use the encryption engine 68 to decrypt the ciphertext(s) contained in the response 54. and thus recover database entries (e.g., IP addresses) associated with the queried domain name. If the domain name database 50 does not contain an entry associated with each domain name, a dummy message indicating failure may be generated when decrypting each ciphertext(s). A further step 218 may transmit the results of the decryption procedure to the application 64 . Step 216 is a homomorphic decryption procedure/algorithm, e.g., Gentry C., Halevi S. "Compressible FHE with Applications to PIR", In: Hofheinz D., Rosen A. (eds) Theory of Cryptography, TCC 2019, Use full isomorphism as described in Lecture Notes in Computer Science, vol 11892, Springer, Cham.

Figure 12 shows example components of a DNS server system 20 in accordance with some embodiments of the invention. The illustrated components may run on a single physical machine or on separate, communicatively coupled machines. Server system 20 collectively represents a set of name servers as illustrated in FIG. 2.

In some embodiments, database maintenance module 26 inserts records corresponding to the new domain name, makes changes to selected records (e.g., changes to domain registration data, respectively) (changing the cluster assignment of domains, removing each domain from a blacklist, etc.), and/or deleting expired records to keep the domain name database 50 up to date. Exemplary operation of module 26 is shown in FIG. 13 . In the sequence of steps 222-224, module 26 may check whether database update conditions are met. Some embodiments may perform database updates on a schedule (eg, hourly) or on-demand (as needed). In an alternative embodiment, the update agent may accumulate incoming domain data 55 in a queue and determine that an update condition is met when the queue is full. When the update condition is met, step 226 may attempt to update database 50, for example, by inserting a new set of records. Step 226 may include calculating a hash index, for example, by applying a hash function to each new domain name and inserting a record into a table row with the newly calculated index. However, this insertion operation may fail, for example in case of a hash collision, i.e. when two distinct domain names are hashed to the same index. In embodiments that use a cuckoo hash scheme, collisions may be resolved by calculating another index using a second hash function, etc. Even in these embodiments, inserting a specific record may not be possible due to multiple hash collisions. This situation may require selecting a new set of hash functions and re-indexing the database 50 using the new hash functions (steps 230-232 of Figure 13).

In response to a successful database update, when the hash function has changed, step 234 may distribute a set of updated hash function specifications 56 to clients (e.g., Figure 7 , 10 and 12). Accordingly, step 234 can ensure hashing consistency, that is, all clients consistently formulate PIR requests using the version of the hash function used in indexing database 50.

In some embodiments, PIR module 28 of DNS server system 20 is configured to perform an encrypted lookup to domain name database 50 in response to query 52. Here, the term 'encrypted lookup' refers to retrieving a record from the database 50, which record is included in encrypted form in the PIR query 52 without decrypting the respective index. It is indicated by the index. The encrypted lookup procedure may include performing a series of operations, such as addition and multiplication, directly on the encrypted data to produce an encrypted result, as illustrated by equation [2] above. Thus, an encrypted lookup can be performed, for example, in a conventional version of encrypted DNS, such as DNS-over-HTTPS, by first decrypting the query to create a clear text index, and then extracting said clear text index into each database. It does not include lookup.

Exemplary operation of PIR module 28 is illustrated in Figure 14. The sequence of steps 242-244 may listen for incoming PIR queries. Once the query is received, step 246 may check the consistency of the hashing. In other words, step 246 may determine whether each query was generated according to the same hash function specification as used to index domain name database 50. If not, in step 254, DNS server system 20 may return an error message to each requesting client. Some embodiments may further push updated hash function specifications 56 to each client.

In response to determining that the hashing is consistent, step 248 executes an encrypted lookup to database 50 according to PIR query 52. Step 248 can be described, for example, in Gentry C., Halevi S. "Compressible FHE with Applications to PIR", In: Hofheinz D., Rosen A. (eds) Theory of Cryptography, TCC 2019, Lecture Notes in Computer Science , vol 11892, Springer, Cham, any method known in the art may be employed. The sequence of steps 250-252 may then generate a PIR response 54 and transmit the response 54 to each client device.

Various domain name services can be implemented in a manner that protects privacy as described above. Some example use case scenarios include:

Resolving domain names into addresses (IP address lookup)

One application of the systems and methods described herein is to perform a DNS lookup, that is, to return the IP address associated with a selected domain name. In these embodiments, domain name database 50 may store a set of IP addresses indexed by a domain name. PIR query 52 may include encryption of the index determined by hashing each domain name and possibly other data (e.g., encoding of question Q, see, e.g., FIG. 9). In response, DNS server system 20 may return a PIR response 54 containing an encryption of the respective IP address. The clients (or other machines communicating with each client) can then decrypt and use each IP address to route electronic communications (e.g., web browsing).

An exemplary sequence of steps performed by domain name resolver 66 in an embodiment configured to perform domain name resolution (mapping domain names to IP addresses) is shown in FIG. 15. To optimize DNS lookups, some embodiments may maintain a local cache that stores previously resolved IP addresses of TLDs and/or authoritative nameservers. In response to receiving a request to resolve a selected domain name, some embodiments may iterate through successive levels of the domain name hierarchy. If each FQDN has not yet been fully resolved into an IP address, step 268 may determine the PQDN of each domain name. A PQDN may contain part of a specified FQDN up to a selected level of the hierarchy (e.g., up to a TLD such as '.org' (see Figure 6)). At step 270, resolver 66 may check whether each PQDN has been previously resolved by performing a cache lookup. If "yes", the cache may hold the IP address of the nameserver from which it can resolve the next level FQDN (36). If “no”, step 272 may select a nameserver to resolve the current PQDN. In an example where the PQDN is '.org', the selected name server may be the root name server 20b, etc.

Some embodiments rely on PIR procedures being computationally expensive in both processor load and communication size. Additionally, as previously described in conjunction with Figure 6, a typical DNS lookup involves multiple iterative queries, for example, first to the root nameserver, then to the TLD nameserver, and finally to the authoritative server. You may need it. In other words, a single DNS lookup can double the cost of the PIR procedure manifold. Further complicating the problem is the fact that DNS lookups are relatively frequent; for example, accessing a single web page may involve several consecutive DNS lookup operations.

Some embodiments further rely on some FQDNs being more privacy sensitive than others. For example, a user may not be interested in disclosing selected parts of his or her browsing history (e.g., visits to online news or reference sites such as Wikipedia, among others) as opposed to other parts (e.g., visits to adult content sites). Additionally, some parts of the FQDN may be more privacy sensitive than others. For example, using the example in Figure 6, knowing that a user wants to access the .org top-level domain is much less informative or raises privacy concerns than knowing that the user actually wants to access wikimedia.org. not related to

To alleviate some of the computational cost incurred by PIR, some embodiments therefore intentionally use PIR for only a subset of DNS queries. Deciding whether to use PIR may include determining whether a privacy condition is satisfied, i.e., whether the current query is privacy sensitive or not. Example step 274 of Figure 15 evaluates privacy conditions. If the current query is considered privacy sensitive (“Yes” branch), the sequence of steps 276-277 may use homomorphic encryption (PIR) to formulate the current query. Otherwise, the current query can be performed using conventional DNS.

Some embodiments determine whether privacy conditions are satisfied according to the authority area of the selected name server. For example, some embodiments only send PIR queries to the TLD nameserver(s) 20c and/or authoritative nameserver(s) 20d, while addressing to the root nameserver(s) 20b. The queries are generated using conventional DNS. In other words, these embodiments resolve the TLD tokens of FQDN 36 via conventional (non-private) DNS queries and use PIR to resolve domain and/or prefix tokens.

Some embodiments of resolver 66 determine whether a privacy condition is satisfied according to at least one of the tokens of FQDN 36. For example, resolver 66 may use conventional (i.e. non-private) DNS queries to resolve selected PQDNs, e.g. 'google.com', 'wikipedia.org', 'amazonaws.com', etc. (interpretation), and can use PIR queries to decompose (interpretation) other PQDNs such as 'facebook.com', 'pornhub.com', etc. These embodiments allow some online activities (e.g., performing a Google search, accessing news sites, searching for weather reports or sports scores, etc.) to occur while other activities (e.g., accessing adult content, etc.) , streaming movies, accessing selected e-commerce, online banking, or social media portals, etc.) relies on having fewer privacy concerns. In another embodiment, knowing that a user is accessing a cloud computing service (e.g., Amazon Web Services™ from Amazon, Inc., or Azure™ from Microsoft) means that each domain has thousands of different subdomains. Because it can be hosted, it may not be very informative or have privacy concerns. To enable selective PIR querying, some embodiments maintain a blacklist of PQDNs that are considered privacy sensitive and/or a whitelist of PQDNs that can be searched using conventional DNS. Exemplary whitelists may include, among others, search engine domains, news domains, online advertising and/or other content distribution domains, and domains that provide various cloud computing services (file hosting, infrastructure as a service, etc.) . Next step 274 is looking up the current PQDN/domain name token in the whitelist, sending a conventional query if each PQDN/token is on the whitelist, otherwise a PIR query. It may include deciding to transmit. Alternatively, resolver 66 may decide to search the blacklist (lookup) and send a PIR query if each PQDN/token is on the blacklist, and send a conventional DNS query otherwise. .

Selective PIR querying can also be performed at the subdomain level. Some embodiments note that in cases where leaking of a domain-level PQDN may not specifically raise privacy concerns (e.g., google.com), leaking of some subdomain token(s) may be problematic. It depends on the point. For example, 'www.google.com' may be less privacy-sensitive than 'meet.google.com'. Therefore, some embodiments maintain a whitelist and/or blacklist of prefix tokens and/or FQDNs and determine whether to query each authoritative server using PIR or conventional DNS. A simple embodiment could use conventional DNS queries to resolve the 'www' subdomain, or alternatively use PIR queries.

Table 1 lists some examples of FQDNs and their associated privacy issues.

Table 1

If step 274 determines that the conditions for using PIR are met, then at step 276 the decomposer 66 connects the server system 20 with a set of homomorphic encryption parameters (e.g., key, shared secret, nonce). (nonce), etc.) can be negotiated. Some embodiments use homomorphic encryption schemes to generate private-public key pairs and/or encryption-decryption key pairs. Step 277 then proceeds, for example, by hashing each PQDN and using the negotiated pair's public key to encrypt each hash and possibly other data, such as the indicator of question Q, A PIR query 52 can be generated (see Figure 9).

If step 274 determines that the conditions for using PIR are not met, some embodiments may formulate (generate) a conventional DNS query (see Figures 3-4). Step 278 may further include negotiating a pair of session encryption keys under the DNS over HTTPs protocol and encrypting each DNS query using, for example, the public key of the key pair. In some embodiments, both conventional and PIR queries are encrypted and transmitted over a protocol such as DNS over HTTPs. This strategy can benefit from other features of the protocol, such as ensuring the integrity of each transmission. However, PIR queries involve an additional layer of encryption compared to conventional DNS queries, and that additional layer is equivalent to the homomorphic encryption that makes PIR possible. The layer of encryption corresponding to DNS over HTTPs or similar protocols is removed by the server. Nonetheless, while this decryption creates a clear text version of a conventional DNS query, the server does not remove the homomorphic encryption layer from the PIR query, leaving the PIR query unreadable by the DNS server system 20. Remains.

Once the query is sent to the appropriate nameserver, resolver 66 can wait for a response from each server at step 282. An additional sequence of steps 284-286 may extract the IP address currently associated with the PQDN from the server's response and cache each IP address for further use. Each IP address may contain the address of the nameserver of the fully resolved IP address associated with the current FQDN. If the server's response includes a PIR response 54, step 284 may include decrypting the enclosed IP address using a homomorphic decryption procedure.

Some embodiments implement additional optimizations to mitigate the significant computational cost of PIR. One of these examples includes reducing the size of domain name database 50 by partitioning it into subunits/buckets, depending on the total count of records, and/or depending on desired lookup performance and/or desired level of privacy. In these embodiments, instead of searching the entire database of domain names, the server will search only within the bucket(s) holding the record for each domain. The smaller the bucket, the greater the reduction in lookup time, but at the same time, because the uncertainty of the identity of each domain is reduced, privacy protection is also reduced. An exemplary bucket size that can provide a compromise between speed and privacy is 2 ¹⁶ =65536, i.e., an individual bucket can enable resolution (resolution) among up to 65536 individual domain names. Each bucket can additionally store a plurality of hash tables as described above with reference to FIG. 8. Individual buckets may be operated by separate computer systems and may be assigned to separate processor cores, such as on the same computer.

Next, some embodiments may use a hash function (e.g., a variant of the Fowler-Noll-Vo hash, such as FNV-1) to identify the bucket holding each record. The output of the hash function can be truncated to the number of buckets by applying a modulo operation. An example bucket index on the server side can be calculated as follows:

, [4]

Here, d and Q represent the domain name and question (e.g., A vs. AAAA), respectively, H ^B represents the hash function used for bucketing, and N ^B represents the bucket count. , [ Qd ] represents the concatenation of Q and d . Those skilled in the art will understand that the illustrated method of calculating the bucketing index is meant as an example only and does not limit the scope of the invention.

For each domain name in database 50, database maintenance module 26 may compute I ^B and place each record into a bucket with index I ^B. Placing records may include applying a cuckoo hashing scheme to find the location for each record within one of the plurality of hash tables, as described above. In turn, on the client side, decomposer 66 can compute I ^B and attach it to PIR query 52. Bucket indexes can be transmitted as clear text or encrypted. When receiving a PIR query 52, the server 20 may determine a bucket according to the query 52 and then perform a PIR according to the contents of each bucket to generate a PIR response 54.

Computer security and analytics applications

Some embodiments may be suitable for computer security and data analysis applications. In this use case scenario, domain name database 50 stores records indicating each domain's membership in a particular class or category of domains. In some embodiments, the categories may be related to computer security. For example, a category may include domains characterized by distributing adult content. Another example category may include a blacklist of domains known to engage in fraudulent activity. Another example category includes domains that are characterized as engaging in denial-of-service attacks (e.g., members of a particular botnet).

Different categories may relate to various aspects of data analysis. For example, domains can be grouped into classes/categories based on content (e.g. games, news, reference, education, etc.). Other grouping/classification criteria may include ownership and/or commercial relationships. For example, all domains owned by the same corporation or members of the same conglomerate or corporate association may be grouped together into distinct domain categories. Another classification criterion includes membership in specific online activities. For example, all domain names associated with a particular online game and/or games produced by a particular game creator may be grouped together into a separate category. Another classification criterion may include geographic location: domains from specific geographic regions, countries, etc. may be grouped together. Other example criteria may include domain age/time of first registration.

In another example of classification, domains may be grouped into clusters based on shared characteristics or similarities between different types of domains. Figure 16 shows a set of domains 30a-b and a set of clusters 60a-b according to some embodiments of the invention. Cluster membership does not have to be exclusive. In the example of Figure 16, domain 30b belongs to both clusters 60a-b. In some embodiments, the similarity of two domains may be evaluated according to the hyperdistance separating the two domains in an N-dimensional abstract feature space. However, the similarity need not be based on the domain features themselves. In one of these examples, two domains may be considered similar when they frequently appear together in sequences of DNS queries; These two domains can be placed in the same cluster. In another example, clusters may be automatically generated by a neural network classifier using an unsupervised learning algorithm. Individual clusters may or may not correspond to individual (distinct) domain categories. For example, the 'malicious' domain category may contain multiple clusters, where each cluster may contain domains from a separate botnet.

Domain clustering and/or classification per se (i.e., grouping domains into categories or clusters) is beyond the scope of this disclosure and may be accomplished using any method known in the art of data mining. You can. This specification will focus on accessing a dictionary's pre-existing classification through PIR. In some embodiments, a record stored in domain name database 50 may include a boolean value indicating whether a domain belongs to a particular category or not. Alternatively, the record may contain a label or other identifier of the category/cluster to which each domain belongs. These records can be accessed using the PIR query and response mechanism described above. In some embodiments, PIR query 52 includes encryption of an index into database 50 (e.g., a hash of a domain name), while PIR response 54 identifies each domain's category/cluster membership. May contain ciphertext encoding the database entry it represents.

Some embodiments may employ the bucketing strategy described above with respect to DNS lookups to accelerate server response, even in security and/or analytics applications. Individual buckets can correspond to individual security categories such as malware, fraud, botnets, spam, etc. If the number of records within such a category exceeds a predetermined threshold, some embodiments break the database corresponding to each category into sub-buckets and identify the bucket containing each individual record. You can use hashing to do this. When issuing a query, the client can send the bucket/category index as clear text or cipher text.

17 shows an example hardware configuration of a computing appliance 80 programmed to perform some of the methods described herein. Appliance 80 may represent any of client devices 12a-f, router 14, and server 20. The appliance shown is a personal computer. Other computing devices, such as servers, mobile phones, tablet computers, and wearable computing devices, may have slightly different configurations. Processor(s) 82 may be a physical device (e.g., a microprocessor, a multi-core integrated circuit formed on a semiconductor substrate) configured to perform arithmetic (computing) and/or logic operations on sets of signals and/or data. Includes. These signals or data may be encoded and delivered to processor(s) 82 in the form of processor instructions, e.g., machine code. Processor(s) 82 may include an array of central processing units (CPUs) and/or graphics processing units (GPUs).

Memory unit 84 includes a volatile computer-readable medium (e.g., dynamic random access memory-DRAM) that stores data and/or instructions accessed or generated by processor(s) 82 while performing operations. can do. Input devices 86 may include, among other things, a computer keyboard, mouse, and microphone, as well as separate hardware interfaces and/or adapters that allow a user to introduce data and/or commands into appliance 80. Output devices 88 may include, among other things, display devices such as monitors and speakers, as well as hardware interfaces/adapters such as graphics cards that enable each computing device to communicate data to the user. In some embodiments, input and output devices 86-88 share a common piece of hardware (e.g., a touch screen). Storage device 92 includes a computer-readable medium that enables non-volatile storage, reading, and writing of software instructions and/or data. Exemplary storage devices include removable media such as magnetic and optical disks and flash memory devices, as well as CD and/or DVD disks and drives. Network adapter(s) 94 may be a mechanical, electrical and electrical device for communicating data over a physical link coupled to a telecommunications network (e.g., networks 13 and 15 of FIG. 1) and/or other devices/computer systems. Includes mechanical, electrical, and signaling circuitry. Adapter(s) 94 may be configured to transmit and/or receive data using various communication protocols.

Controller hub 90 provides a plurality of system, peripheral, and/or chipset buses, and/or any other circuitry that enables communication between processor(s) 82 and the remaining hardware components of appliance 80. is generally indicated. For example, the controller hub 90 may include a memory controller, an input/output (I/O) controller, and an interrupt controller. Depending on the hardware manufacturer, some such controllers may be combined into a single integrated circuit and/or integrated with the processor(s) 82. In another example, controller hub 90 includes a northbridge connecting processor 82 to memory 84, and/or a southbridge connecting processor 82 to devices 86, 88, 92, and 94. It can be included.

Additionally, it will be apparent to those skilled in the art that aspects of the invention as described above may be implemented in various forms of software, firmware, and hardware, or combinations thereof. For example, certain parts of the invention may be described as specialized hardware logic that performs one or more functions. This specialized logic may include an Application Specific Integrated Circuit (ASIC) or a Field Programmable Gate Array (FPGA). The actual software code or specialized control hardware used to implement aspects consistent with the principles of the invention do not limit the invention. Accordingly, the operation and behavior of aspects of the invention have been described without reference to specific software code, and those skilled in the art will be able to design software and hardware to implement the aspects based on the description herein. It is understood that can be controlled.

The above-described exemplary systems and methods enable performing various domain name services while protecting the privacy of beneficiaries of each service. For example, some embodiments enable translation between domain names and IP addresses, where the name server performing the actual translation/database lookup is unaware of the respective domain names and IP addresses. . Some embodiments use homomorphic encryption to enable a server-side private information retrieval (PIR) procedure. The server returns the ciphertexts to the client, and the client then decrypts each ciphertext to produce the desired database entry (e.g., IP address).

In conventional DNS, client queries and/or server responses are not encrypted, allowing any third party to snoop the respective DNS data. Recent developments in DNS technology encrypt queries and/or client responses, in principle keeping data private during transmission. However, in this DNS variant, the name server still decrypts DNS queries to generate clear text domain names. In contrast to this conventional DNS, in some embodiments, the name server no longer accesses transaction data in cleartext because the PIR procedure uses encrypted inputs. Therefore, some embodiments guarantee a stronger level of privacy compared to conventional DNS solutions.

The PIR procedure is relatively expensive in terms of computing and the amount of data exchanged in each client-server transaction. To mitigate cost, some embodiments do not perform all steps of domain name resolution using PIR. Instead, clients can query top-level domain (TLD) nameservers using traditional DNS or a non-homomorphically encrypted variant, such as DNS over HTTPS, for domains and/or sub-domains in the domain name hierarchy. You can use the PIR procedure only when querying selected name servers that resolve each domain name at the domain level. This strategy relies on the information provided by the latter name servers being relatively more important to privacy than, for example, the TLD portion of the domain name. Some embodiments additionally selectively apply a PIR according to at least a token of each FQDN. In other words, decomposition of certain tokens (e.g. 'google.com', 'www', etc.) can be done via traditional DNS, while decomposition of other, more privacy-concern tokens can be done via PIR. there is.

DNS databases can hold millions of distinctive records. The sheer size of these databases can make PIR queries impractical. To address these limitations, some embodiments further employ a bucketing approach to reduce the size of the database and thus the complexity of PIR calculations and the size of queries and server responses. Computer experiments have shown that reducing the database size to 65536 records can keep the average time required to perform a DNS lookup below 1 second, making the application of the current system and method commercially and technically feasible. The caveat of this approach is that reducing the size of the database inherently reduces privacy. However, some choices of database size may provide an acceptable compromise between privacy and speed. Moreover, since the PIR procedure is in principle parallelizable, a parallel computing configuration can be used to set up server-side PIR, for example by using multiple interconnected processor cores or graphics processing unit (GPU) farms. , more gains in speed can be achieved.

Some embodiments of the invention may be adapted to a variety of other scenarios distinct from domain name resolution, such as computer security, application control, parental control, etc. In one example use case scenario, a computer security component, which may be running on a client, on a router/network gateway, or on a remote security server, participates in a PIR exchange with a server configured to perform a database lookup without decrypting each query. You can. Database records may indicate whether certain domains are associated with certain categories related to computer security (e.g., whether each domain is blacklisted or engaged in fraudulent activity, etc.). In a parental control use case scenario, a database record could indicate, for example, whether a particular domain distributes adult material. In an application control use case scenario, database records could indicate whether each domain is associated with a particular kind of online activity (gaming, social media, etc.). Therefore, some embodiments allow selective filtering of traffic to and from specific domains or blocking users from accessing specific domains. Such filtering/blocking is well known in the art, but unlike conventional traffic control procedures, in some embodiments of the invention, the server performing the actual database lookup does not know the domain name for which each piece of information is requested. This makes it possible, for example, for servers and associated domain name databases to be owned and/or operated by providers of security/parental control/application control services and other entities without compromising the privacy of users.

It will be apparent to those skilled in the art that the above embodiments may be changed in various ways without departing from the scope of the present invention. Accordingly, the scope of the present invention should be determined by the following claims and their legal equivalents.

Claims (20)

A method of performing a domain name service (DNS) lookup, comprising:
In response to receiving an indicator of a domain name, to determine whether privacy conditions are satisfied according to the domain name,
In response to determining whether the privacy conditions are satisfied, if so, to formulate a private query that includes encryption of a hash index indicating the location of the record in the domain name database (when , the hash index is encrypted according to a homomorphic encryption procedure, and the hash index is determined according to the domain name),
in response to generating the private query, transmitting the private query to a name server configured to perform an encrypted lookup to the domain name database according to the private query, thereby producing encryption of the record; and
In response to receiving a private response containing encryption of the record from the name server, decrypt the contents of the private response according to a homomorphic decryption procedure,
A method comprising employing at least one hardware processor of a computer system. According to paragraph 1,
In response to determining whether the above privacy conditions are satisfied, if not,
to generate another query according to the domain name (where the content of the other query is encrypted according to a non-homomorphic encryption procedure); and
To transmit the other query to the name server,
The method of claim 1 , further comprising employing at least one hardware processor of the computer system. According to paragraph 1,
The domain name includes a sequence of tokens,
wherein determining whether the privacy condition is satisfied includes determining whether a selected token of the sequence of tokens matches any member of a reference list of tokens. According to paragraph 3,
Wherein the selected token includes a domain token or a prefix token. According to paragraph 1,
and determining whether the privacy condition is further satisfied according to the authority area of the name server. According to clause 5,
If the name server includes a top-level domain (TLD) name server, determining that the privacy condition is not satisfied. According to paragraph 1,
The method characterized in that the private query further includes a bucket index that identifies the domain name database among a plurality of domain name databases connected to the name server. According to paragraph 1,
and wherein the record includes an Internet Protocol (IP) address. According to paragraph 1,
and wherein the record includes a security indicator indicating whether accessing the domain represented by the domain name exposes the user to a computer security threat. In response to receiving an indicator of a domain name, determine whether privacy conditions are satisfied according to the domain name,
In response to determining whether the privacy condition is satisfied, if so, to generate a private query that includes encryption of a hash index indicating the location of the record in the domain name database, where the hash index is encrypted according to, and the hash index is determined according to the domain name),
in response to generating the private query, send the private query to a nameserver configured to perform an encrypted lookup to the domain name database according to the private query, thereby producing encryption of the record; and
A computer system comprising at least one hardware processor configured to, in response to receiving a private response containing encryption of the record from the name server, decrypt the contents of the private response according to a homomorphic decryption procedure. According to clause 10,
The at least one hardware processor, in response to determining whether the privacy condition is satisfied, if not, states:
generate another query according to the domain name (where the content of the other query is encrypted according to a non-homomorphic encryption procedure); and
send the other queries to the name server; A computer system, characterized in that it is further configured. According to clause 10,
The domain name includes a sequence of tokens,
and determining whether the privacy condition is satisfied includes determining whether a selected token of the sequence of tokens matches any member of a reference list of tokens. According to clause 12,
and wherein the selected token includes a domain token or a prefix token. According to clause 10,
wherein the at least one hardware processor is configured to determine whether the privacy condition is satisfied further according to an authority zone of the name server. According to clause 14,
wherein the at least one hardware processor is further configured to determine that the privacy condition is not met when the name server includes a top-level domain (TLD) name server. According to clause 10,
The computer system, wherein the private query further includes a bucket index that identifies the domain name database among a plurality of domain name databases connected to the name server. According to clause 10,
and wherein the record includes an Internet Protocol (IP) address. According to clause 10,
and the record includes a security indicator indicating whether accessing the domain represented by the domain name exposes the user to a computer security threat. When executed by at least one hardware processor of a computer system, it causes the computer system to:
In response to receiving an indicator of a domain name, determine whether privacy conditions are satisfied according to the domain name, and
In response to determining whether the privacy condition is satisfied, if so, generate a private query that includes encryption of a hash index indicating the location of the record in the domain name database, wherein the hash index is homomorphically encrypted. encrypted according to the procedure, and the hash index is determined according to the domain name),
In response to generating the private query, send the private query to a name server configured to perform an encrypted lookup to the domain name database according to the private query to generate encryption of the record; and
In response to receiving a private response containing encryption of the record from the name server, a non-transitory computer-readable medium storing instructions to decrypt the contents of the private response according to a homomorphic decryption procedure. A server computer system configured to participate in Domain Name Service (DNS) transactions with a plurality of clients, comprising:
The server computer system is,
To receive a private query from a client of the plurality of clients (wherein the private query includes encryption of a hash index indicating the location of a record in the domain name database, and the hash index is encrypted according to a homomorphic encryption procedure, The hash index is determined according to the domain name),
in response to receiving the private query, perform an encrypted lookup to the domain name database according to the private query to produce encryption of the record; and
send a private response containing encryption of the record to the client; A server computer system comprising at least one hardware processor configured.