Patent Description:
User devices and content platforms such as content distributors can query content providers in order to retrieve information stored by the content providers. However, there can be situations when it is not in the interest of the content platforms to reveal any details to the content providers about what information is being queried. In other situations, it may not be in the interest of the content providers to reveal any details to the content platforms about other information that is stored on the computing systems of the content providers. <CIT> describes, in accordance with its abstract, systems and methods for real-time collaborative computing and collective intelligence. A collaborative application runs on a collaborative server connected to a plurality of computing devices. Collaborative sessions are run wherein a group of independent users, networked over the internet, collaboratively answer questions in real-time, thereby harnessing their collective intelligence. Systems and methods for determining a group intent vector from a plurality of user intent vectors in response to user input, the group intent vector including a bias restoring vector to correct positional bias resulting from a target layout.

In general, one innovative aspect of the subject matter described in this specification can be embodied in methods that include the actions of generating a partitioned database in which a database is partitioned into shards each having a shard identifier that logically distinguishes each shard from other shards, and database entries in each shard are partitioned into buckets having a bucket identifier that logically distinguishes each bucket in the shard from other buckets in the shard; receiving, by the server including one or more processors and from a client device, a batch of client-encrypted queries, wherein the batch of client-encrypted queries includes two or more queries that have each been encrypted by the client device and specify a shard identifier for the client-encrypted query; processing, by the server, the batch of client-encrypted queries using a set of server-encrypted data stored in a database, wherein each database entry is server-encrypted and is capable of being decrypted by a corresponding decryption key, wherein the processing includes: grouping, by the server, the client-encrypted queries according to shard identifiers of the client-encrypted queries, wherein each group of client-encrypted queries includes multiple queries; executing, by the sever and for each shard, the multiple queries in the group of client-encrypted queries for the shard together in a batch execution process; and generating, by the server and for each shard, multiple server-encrypted results to the multiple queries in the group of client-encrypted queries and transmitting, by the server, the multiple server-encrypted results for each shard to the client device.

Other implementations of this aspect include corresponding apparatus, systems, and computer programs, configured to perform the aspects of the methods, encoded on computer storage devices. These and other implementations can each optionally include one or more of the following features.

Methods can include receiving a set of client-encrypted entity identifiers; encrypting, by the server, the set of client-encrypted entity identifiers to create a set of sever-client-encrypted identifiers; and transmitting, by the server, the set of server-client-encrypted identifiers to the client device.

Methods can also include generating, by the client device, a set of queries using the set of server-client-encrypted identifiers; generating, by the client device, a set of decryption keys using the set of server-client-encrypted identifiers; encrypting, by the client device, the set of queries to create the batch of client-encrypted queries.

Methods can include encrypting, by the server, a set of data stored in the database, wherein, for a plurality of entries in the database, each database entry is server-encrypted and is capable of being decrypted by a corresponding decryption key, wherein generating the partitioned database includes assigning each server-encrypted database entry to a bucket.

Methods can include applying, by the client device, the set of decryption keys generated by the client device using the set of server-client-encrypted identifiers to the multiple server-encrypted results to reveal unencrypted results to the client-encrypted queries.

Methods can include generating the partitioned database by partitioning each bucket into smaller chunks.

Methods can also include executing the multiple queries by executing each query on each chunk of the bucket, which reduces CPU usage and response time by shrinking the search space for each query execution.

The subject matter described in this specification can be implemented in particular embodiments so as to realize one or more of the following advantages. The techniques and methods described in this specification describe techniques for retrieving data from databases while preserving both client and server privacy. This allows a client to query a server without revealing any details to the server about the data that is being queried. Simultaneously, when the client is querying the server does not reveal any details regarding contents of the database that are not queried by the client. In contrast existing techniques of querying a server generally includes encrypting the entire server database and providing the encrypted database to the client for querying. This approach requires significantly more computational resources since the size of the database is generally large. Other approaches of querying the server includes providing an index of the database to the client and receiving a selection of indexes from the client that does not allow for server and client privacy.

This specification relates to data processing and information retrieval. In particular, the techniques and methods described in this specification describe techniques for retrieving data from databases while preserving both client and server privacy. For example, if the client queries a server database, the client does not reveal any details to the server about the data that is being queried (also referred to as client query privacy). Simultaneously the server does not reveal to the client any details regarding contents of the database that are not queried by the client (also referred to as server database privacy). These techniques enable batch processing of queries to provide for a more efficient information retrieval system that also protects user privacy. For example, user privacy is protected by ensuring that a server being queried cannot learn information about the users that a client is querying the server about, and also prevents the client from learning other information about the users that may be stored by the server.

<FIG> is a block diagram of an example environment <NUM> in which content is distributed and presented to a user device. The example environment <NUM> includes a network <NUM>, such as a local area network (LAN), a wide area network (WAN), the Internet, or a combination thereof. The network <NUM> connects content platforms <NUM>, and content providers <NUM>. The example environment <NUM> may include many different content providers <NUM>, content platforms <NUM>, and user devices <NUM>.

A user device <NUM> is an electronic device that is capable of requesting and receiving content over the network <NUM>. Example user devices <NUM> include personal computers, mobile communication devices, digital assistant devices, and other devices that can send and receive data over the network <NUM>. A user device <NUM> typically includes an operating system <NUM> that is primarily responsible for managing the device hardware and software resources such as applications. The user device <NUM> also includes a device storage <NUM> to store data temporarily or permanently based on the particular implementation, application, and use case. A user device <NUM> typically includes user applications <NUM> and <NUM>, such as a web browser or an email client, to facilitate the sending and receiving of data over the network <NUM>, but native applications executed by the user device <NUM> can also facilitate the sending and receiving of content over the network <NUM>. Examples of content presented at a user device <NUM> include webpages, word processing documents, portable document format (PDF) documents, images, videos, and search results pages and digital ads.

A content platform <NUM> is a computing platform that enables distribution of content. Example content platforms <NUM> include search engines, social media platforms, news platforms, data aggregator platforms, or other content sharing platforms. Each content platform <NUM> may be operated by a content platform service provider. The content platform <NUM> may present content provided by one or more content providers <NUM>. In the above example, the news platform may present content created by different authors and provided by one or more content providers <NUM>. As another example, the content platform <NUM> may be a data aggregator platform that does not publish any of its own content, but aggregates and presents news articles provided by different news websites (i.e., content providers <NUM>).

In some implementations, the content platform <NUM> can distribute digital content to one or more users. For example, the content platform <NUM> can let one or more users subscribe to and/or register with the content platform <NUM>. In response, the content platform <NUM> can retrieve digital content from the content providers <NUM> and provide the retrieved content to the user devices <NUM> of users. The content provider <NUM> includes a data storage device (also referred to as a database) that stores digital content in the form of key-value pairs. For example, the database of the content provider <NUM> can include multiple keys and for each key, a corresponding value that is retrieved by the content platform <NUM>.

In some implementations, the content platform <NUM> can assign an identifier to each user so that the content platform can distinguish between the users. In some implementations, the content platform <NUM> can use information provided by the one or more users and/or the user devices as the unique identifier. For example, the content platform <NUM> can use, as the unique identifier, an electronic mail identifier (email id) provided by a user, a cell phone number provided by a user, or a media access control (MAC) address of the user device <NUM> of the user. In some implementations, the content platform <NUM> can assign an identifier to a group of two or more users based on the characteristics of the users in the group of users. For example, the content platform <NUM> can assign to a group of users a common identifier based on similar interests in the context of digital content accessed by the users. In another example, users can be assigned to a group and can be assigned a common identifier based on the subscriptions with the digital content. In some implementations, the content platform <NUM> can assign multiple identifiers to a single user. For example, the content platform <NUM> can assign both email id and a cell phone number as an identifier for a user.

To retrieve digital content from the content providers <NUM>, the content platform <NUM> and the content provider <NUM> implements an information retrieval technique that ensures data privacy in a way that the content platform <NUM> does not reveal any details to the content providers <NUM> about what information is being queried. The retrieval technique further ensures that the content providers <NUM> does not reveal any details to the content platforms <NUM> about other information that is stored on the computing systems of the content providers <NUM>. While this specification refers to content providers <NUM> and content platforms <NUM>, the information retrieval techniques discussed herein can be used by any two systems that want to exchange information in a privacy preserving manner. The information retrieval techniques are further explained with reference to <FIG>, and entities that are requesting information from a database are referred to as clients and the entities that maintain the database of information, and return information stored in the database are referred to as servers.

<FIG> is a swim lane diagram of an example process <NUM> of retrieving content by a client from a server. Operations of the process <NUM> can be implemented, for example, by the client <NUM> and the server <NUM>. Operations of the process <NUM> can also be implemented as instructions stored on one or more computer readable media, which may be non-transitory, and execution of the instructions by one or more data processing apparatus can cause the one or more data processing apparatus to perform the operations of the process <NUM>.

The server implements a database (also referred to as server database) that stores digital content in the form of a mapping between key and value (referred to as a key-value pair). A key can be an identifier and/or a pointer for a value that is the digital content that is being queried by the client. A database can include multiple keys and for each key a respective value corresponding to the key. For example, the server can include, in the database, multiple keys where each key can uniquely identify one or more users of the clients for which the client is retrieving content from the server.

In some implementations, the key of the key-value pair of the server database is associated with the identifier that was assigned to the users by the clients. While querying the server, the client provides the server with a query that includes the identifiers in a way that the details of the identifiers are not disclosed to the server. As explained further in the document, the server can select content (e.g., data of any kind) from the server database based on the identifier even though the identifiers are masked from the server.

The client <NUM> obtains unique identifiers (<NUM>). For example, the client <NUM> can provide digital content to one or more users. To uniquely identify the one or more users, the client <NUM> can assign an identifier to each of the one or more users. In some implementations, the client <NUM> can use information provided by the one or more users and/or the user devices <NUM> as the identifiers for the one or more users and/or user devices <NUM>. For example, the client <NUM> can use, as a unique identifier, an electronic mail identifier (email-id or email address), cell phone number, or media access control (MAC) address of the user devices <NUM>. The client can be any computing system that requests information from another system (e.g., a server system) that stores information or maintains a database.

The client <NUM> device encrypts the identifiers (<NUM>). To prevent the server <NUM> from accessing the identifiers of the users in plaintext, the client <NUM> encrypts the identifiers using a deterministic and commutative encryption technique to generate an encrypted form of the identifiers (referred to as "client encrypted identifiers"). In general, a commutative encryption is a kind of an encryption that enables a plaintext to be encrypted more than once using different entity's public keys. In this system, decryption is not required before the encryption/re-encryption processes. Moreover, the resulting ciphertext (also referred to as encrypted text) can be decrypted by the designated decryption techniques without considering the order of public keys used in the encryption/re-encryption processes. In other words, the order of keys used in encryption and in decryption do not affect the computational result, and allow one encrypting party (e.g., a client <NUM>) to remove their encryption even after another party (e.g., a server) has applied further encryption to data that was encrypted by the first encrypting party.

The client <NUM> transmits the client encrypted identifiers to the server <NUM> (<NUM>). For example, after encrypting the identifiers, the client <NUM> transmits the client encrypted identifiers to the server <NUM> over the network <NUM>.

The server <NUM> encrypts the client encrypted identifiers (<NUM>). In some implementations, after receiving the client encrypted identifiers from the client <NUM>, the server <NUM> re-encrypts (e.g., further encrypts) the client encrypted identifiers using a commutative encryption technique to generate an encrypted form of the client encrypted identifiers (referred to as "server & client encrypted identifiers"). In other words, the server <NUM> adds another layer of encryption on the client encrypted identifiers. Note that the server <NUM> does not have access to the identifiers in plaintext because the identifiers were already encrypted by the client <NUM>, and the server <NUM> does not have the decryption key.

The server <NUM> transmits the server & client encrypted identifiers back to the client <NUM> (<NUM>). For example, after generating the server & client encrypted identifiers, the server <NUM> transmits the server & client encrypted identifiers of the one or more users to the client <NUM> over the network <NUM>.

The client <NUM> removes the prior client encryption from the server & client encrypted identifiers (<NUM>). In some implementations, after receiving the server & client encrypted identifiers, the client <NUM> uses techniques to decrypt (or remove) the encryption that was performed by the client <NUM> in step <NUM> to generate "server encrypted identifiers" for each of the one or more users. Note that the client <NUM> is able to remove client encryption since the encryption techniques are commutative in nature. Also note that the server encrypted identifiers that are generated after removing the client encryption are identifiers encrypted by the server using the commutative and deterministic encryption technique. In other words, after the client <NUM> removes the original encryption that was applied to the identifiers, the identifiers remain encrypted by the server, and are then only server encrypted versions of the client identifiers, which are used by the client <NUM> to generate queries that will be submitted to the server <NUM> to request information corresponding to the identifiers.

In some implementations, steps <NUM>-<NUM> of the process <NUM> can be implemented using an oblivious pseudo random function (also referred to as an Oblivious PRF or OPRF). An Oblivious PRF is a protocol between a server holding a key to a pseudo random function (PRF) and a client holding an input. At the end of the server-client interaction, the client learns the output of the OPRF on its input provided by the client and nothing else. The server learns nothing about the client's input or the OPRF output.

To facilitate creation of the queries, the client <NUM> generates a shard index and a bucket identifier for each server encrypted identifier (<NUM>). In some implementations, the client <NUM> implements a hashing technique to generate a query that can include a shard index and a bucket identifier (also referred to as a bucket-id). An example hashing technique of generating the query is further explained with reference to <FIG>.

<FIG> is a flow diagram of an example process <NUM> of generating a query from the server encrypted identifiers. Operations of the process <NUM> can be implemented, for example, by the client <NUM> that includes any entity that implements the techniques described in this document to retrieve content from another entity. Operations of the process <NUM> can also be implemented as instructions stored on one or more computer readable media which may be non-transitory, and execution of the instructions by one or more data processing apparatus can cause the one or more data processing apparatus to perform the operations of the process <NUM>.

<FIG> explains the process <NUM> of generating a query using an example identifier <NUM> (john. smith@example. After processing the identifier <NUM> using steps <NUM> to <NUM> of the process <NUM>, the server encrypted identifier <NUM> of the identifier <NUM> is represented as SERV_ENC{john. smith@example. com}:=adhf8f2g&<NUM>!d0sfgn2 where SERV_ENC is the server encryption of the server & client encrypted identifiers after the client <NUM> removes the client encryption of step <NUM> and "adhf8f2g&<NUM>!d0sfgn2" is the ciphertext of the identifier <NUM>.

The client <NUM> hashes the server encrypted identifiers to generate an unsigned integer (<NUM>). In some implementations, the client <NUM> can implement a hash function that is configured to process the server encrypted identifier <NUM> to generate an unsigned integer <NUM>. This can be represented as HASH_FN[SERV_ENC{john. smith@example. com}]:= <NUM> where HASH_FN is the hash function implemented by the client <NUM> and "<NUM>" is the unsigned integer. The hash function (also referred to as a Cryptographic Hash Function) can be any one-way function which is practically infeasible to invert or reverse and that can be used to map data of arbitrary size to a fixed-size value. Examples of such hash functions can include MD5 message-digest algorithm, Secure Hash Algorithm <NUM>, <NUM> and <NUM>.

The client <NUM> converts the unsigned integer into a converted number that is within a specified range (<NUM>). In some implementations, the client <NUM> can implement a conversion function that is configured to process the unsigned integer <NUM> to generate a converted number <NUM> that is within a specified range. Since the hash function and the conversion function are known to both the client <NUM> and the server <NUM>, the range of the converted number generated using the conversion function is pre-specified. In this example, the converted number <NUM> is represented as CONV[HASH_FN[SERV_ENC{ john. smith@example. com }]] := <NUM> where CONV is the conversion function implemented by the client <NUM>. As an example, one way to convert an unsigned integer into a number between <NUM> and <NUM> is to use the remainder of the unsigned integer divided by <NUM>.

The client <NUM> splits the converted number into a shard index and a bucket-id (<NUM>). The shard index will be a number between <NUM> and P-<NUM>, where P is the number of shards. The bucket-id will range between <NUM> and n/P-<NUM>, where n is the largest value that the converted number <NUM> generated in step <NUM> can take. In some implementations, the client <NUM> splits the converted number <NUM> generated in step <NUM> into two parts such that the first part is the shard index and the second part is the bucket-id. For example, if n is the largest value that the converted number <NUM> can take, the number of bits required to represent the number n is log<NUM>n bits. In such a scenario, if P is a power of <NUM> where P = <NUM>, the client <NUM> can use the first K bits as the shard index and the remaining, log<NUM>n - K bits can be used as a bucket-id. In this example, the client <NUM> splits the converted number <NUM> into two parts as depicted in <FIG> as result <NUM> such that the shard index is <NUM> and the bucket-id is <NUM>. In another implementation, if P represents the number of shards, the shard index can be computed as the remainder when the converted number is divided by P. In this case, the bucket-id can be computed as the integer quotient when the converted number is divided by P. In this case, if P=<NUM> then shard index <NUM> and bucket-id <NUM>.

Returning back to the process <NUM>, the client <NUM> uses the process <NUM> to generate a query for each of the server encrypted identifiers of the one or more users. For example, each query that is generated for each identifier will include the shard index and the bucket id created using the server encrypted identifier, as discussed above.

The client <NUM> generates decryption keys using each server encrypted identifier (<NUM>). In some implementations, the client <NUM> can generate a decryption key for each of the server encrypted identifiers. For example, the client <NUM> can implement a HMAC-based Extract-and-Expand Key Derivation Function (HKDF) which is a hash-based message authentication code (HMAC) cryptographic key derivation function (KDF) for expanding a key into one or more cryptographically strong secret keys. For example, the client <NUM> can use the HKDF to process the server encrypted identifier to generate a decryption key.

The client <NUM> generates and encrypts queries (<NUM>). In some implementations, the client <NUM> uses the bucket-id to generate an indicator vector of length n/P where the element with index equal to the bucket-id is <NUM> and the other elements are <NUM> (recalling that P is the number of shards and n/P is the number of distinct bucket-ids). In some implementations, the indicator vector can be compressed using well-known compression techniques. In some implementations, the client <NUM> can encrypt the indicator vector corresponding to each of the server encrypted identifiers using a fully homomorphic encryption (FHE) technique to generate a corresponding FHE encrypted bucket vector. In general, homomorphic encryption is a form of encryption that permits users to perform computations on its encrypted data without first decrypting it. These resulting computations are left in an encrypted form which, when decrypted, result in an identical output to that produced had the operations been performed on the unencrypted data. Properties of FHE can include addition, multiplication and absorption. To illustrate, if {x} denotes a FHE of x, then the addition {x} + {y} can yield {x+y} without revealing x, y or x+y. Similarly, the multiplication {x} * {y} can yield {xy} without revealing x, y or xy and the absorption {x} * y can yield {xy} without revealing x. In some implementations, the properties of FHE can include the ability to convert an encrypted vector into a specified number of separate encrypted values (one for each item in the vector) without revealing any details about the items in the vector.

After encrypting the indicator vector, the client <NUM> can generate a query that includes a shard index and a corresponding FHE encrypted bucket vector. The query can be denoted as FHE PIR QUERY (database, query) where database represents a data storage that stores a mapping of key and value i.e., the database stores multiple keys and for each key a corresponding value.

The client <NUM> transmits the query to the server <NUM> (<NUM>). For example, after generating the queries for each of the server encrypted identifiers, the client <NUM> transmits the queries to the server <NUM> over the network <NUM>. In some implementations, multiple queries are sent to the server in a batch, such that the server can process the queries at the same time (e.g., in a batch process).

The server <NUM> encrypts the database (<NUM>). The server <NUM> can encrypt the database at any time prior to receipt of the query. For example, as the server <NUM> is building the database, or adding information to the database, the server can encrypt the data being stored in the database. In some implementations, the server <NUM> encrypts the server database using an encryption technique such as the Advanced Encryption Standard (AES). For example, the server <NUM> encrypts the value of each key-value pair of the server database using the AES encryption technique based on an AES-key generated using the HKDF and the corresponding key of the key-value pair. Each key of the key-value pair of the server database is further replaced by an integer (referred to as a record key) that is generated using a hash function (e.g., SHA256) that maps the key to an integer within the range [<NUM>, n) where n is a tunable parameter known to both the server <NUM> and the client <NUM>. This results in a record key-AES encrypted value pair in place of each of the key-value pair in the database.

The hash function can further utilize cryptographic salt that is made up of random bits added to each key of the key-value pair before hashing. In some implementations, the cryptographic salt is also known to the client <NUM> that can be used by the client <NUM> while encrypting the indicator vector using FHE technique to generate a corresponding FHE encrypted bucket vector.

The server <NUM> processes the queries (<NUM>). In some implementations, the server <NUM> can process the queries using an optimized batch process that reduces the resource consumption required to retrieve content from the database. The optimized process can be implemented in a manner that facilitates concurrent processing by splitting the database into smaller chunks (referred to as shards and identified using shard index), and processing them in parallel on multiple computing systems thereby reducing the computational resources required to retrieve content from the database. This is further explained with reference to <FIG>.

<FIG> is a flow diagram of an example process <NUM> of processing queries. Operations of the process <NUM> can be implemented, for example, by the server <NUM> that includes any entity that implements a database from where content is being retrieved. Operations of the process <NUM> can also be implemented as instructions stored on one or more computer readable media which may be non-transitory, and execution of the instructions by one or more data processing apparatus can cause the one or more data processing apparatus to perform the operations of the process <NUM>.

The server <NUM> partitions the database into P shards (<NUM>). For example, by deriving shard indexes from record keys by using the same technique used by the client to derive shard indexes. Each shard may include multiple record key-AES encrypted value pairs.

The server <NUM> partitions each shard into buckets (<NUM>). In some implementations, the server <NUM> partitions each shard into even smaller partitions called buckets by deriving a bucket-id for each record key in a shard using the same technique that the client used. For example, shard index and the bucket-id can be computed as the remainder and the integer quotient respectively when the converted number is divided by P. Observe that this yields at most n/P buckets per shard.

After partitioning each shard into multiple buckets, the AES encrypted values of the record key-AES encrypted value pairs are stored inside each bucket such that the record key of the record key-AES encrypted value pairs indexes both the shard and the bucket inside the shard. It should be noted that the server <NUM> uses the same methodology as the client <NUM> to derive a shard number and bucket-id from each key of the key-value pair in the server database.

The server <NUM> combines and serializes the encrypted values (<NUM>). In some implementations, the server <NUM> concatenates the AES encrypted values of each bucket into a bytestring. For example, if a particular bucket includes <NUM> AES encrypted values, the <NUM> AES encrypted values are concatenated one after the other to generate a bytestring. The server <NUM> identifies the offset values (index location of the bytestring) of the AES encrypted values and encrypts the offset values using an encryption technique such as AES based on the corresponding record keys. For example, if the bytestring includes <NUM> AES encrypted values of uniform length, the server encrypts the offset values of each of the <NUM> AES encrypted values in the bytestring using AES based on the respective record key of the record key-AES encrypted value pair. After generating the encrypted offset values, the server <NUM> prepends the encrypted offset values to the bytestring. The server <NUM> further prepends the number of AES encrypted values to the bytestring. In this example, the server <NUM> prepends the value <NUM> to the bytestring. The server <NUM> further splits the bytestring into chunks of c bytes each where c is an integer known in advance to both the client and the server. The c-byte chunks can be further indexed based on their relative position in the bytestring. For example, if c=<NUM>, a bucket B can be represented as B = ["p","q","r","s"] where "pqrs" can be the bytestring that is split into c-byte chunks "p", "q", "r" and "s" having indices <NUM>-<NUM> in the bucket respectively. In another example, if c=<NUM>, a bucket B can be represented as B = ["pq","rs","tu","v"] where "pqrstuv" can be the bytestring that is split into c-byte chunks "pq", "rs", "tu" and "v" having indices <NUM>-<NUM> in the bucket respectively.

For each query, the server <NUM> identifies the shard using the shard-index of the query (<NUM>). As mentioned before with reference to step <NUM> of the process <NUM>, each query includes a shard index and a corresponding FHE encrypted bucket vector. After receiving a query, the server <NUM> identifies a particular shard based on the shard index of the query. For example, if the shard index of the query is <NUM>, the server identifies the 32nd shard based on the shard indexes of the server database.

For each query, the server <NUM> queries each bucket in the shard and generates a list of FHE encrypted values (<NUM>). In some implementations, the server <NUM> queries each bucket of the particular shard identified by the shard index using the FHE encrypted bucket vector from the query. For example, if there are <NUM> buckets in a shard that was identified using the shard-index from the query, the server <NUM> will query each of the <NUM> buckets.

In order to query a bucket, the server <NUM> performs an oblivious expansion operation on the FHE encrypted bucket vector from the query to obtain an FHE encrypted value for the particular bucket. Then it performs a separate FHE absorption operation between the FHE encrypted value for the particular bucket and each c-byte chunk in the bucket. This can be logically explained with the following example.

Assume that there are <NUM> buckets in the particular shard. Further assume that the 1st bucket has the following chunks ["A", "B", "C", "D"]. Similarly the 2nd, the 3rd and the 4th bucket has the following chunks ["E", "F", "G"], ["H"] and ["I", "J", "K"] respectively. Further assume that the indicator vector is [<NUM>, <NUM>, <NUM>, <NUM>]. An absorption operation will generate FHE encrypted values of chunks with index <NUM> across all four buckets that can be represented as [<NUM>, "E", <NUM>, <NUM>]. Similarly FHE encrypted values of chunks with indices <NUM>-<NUM> across all four buckets are [<NUM>, "F", <NUM>, <NUM>], [<NUM>, "G", <NUM>, <NUM>] and [<NUM>, <NUM>, <NUM>, <NUM>] respectively.

In some implementations, the server <NUM> can aggregate the values of the FHE encrypted values of the bucket vector and the c-byte chunks using the FHE addition operation across all buckets and generate a list of FHE encrypted values. In other words, all entries in the set of triples described previously with the same query and chunk_index are combined into one by summing the FHE values. For example, the aggregation operation on the values of the FHE encrypted values of the bucket vector and the c-byte chucks with a particular index, for example, index <NUM> will select the chunk "E" from among all chunks having index <NUM> across all four buckets of the shard. Similarly the aggregated values of the chunks at the 2nd, the 3rd and the 4th indices are "F","G" and <NUM> respectively across all buckets of the shard. The server <NUM> after selecting the chunks from buckets, the server <NUM> can generate a list of FHE encrypted values and transmits the list to the client <NUM>. For example, the server can generate a list ["E", "F", "G"] of FHE encrypted values that were selected using the absorption operation and transmit the list to the client <NUM>.

Even though the process <NUM> has been explained with reference to a single query, the process <NUM> can be implemented in a way that multiple queries can be processed in parallel on multiple computing systems. In some implementations, a map reduce process can be used that enables all queries to be processed as a batch of queries, which reduces the time required to generate a response to the queries, and saves processing resources relative to processing each query individually. For example, assume that the database is partitioned into n buckets by hashing keys and that the buckets are partitioned into shards based on leading k bits. In this example, the server can partition the queries by shard based on the provided shard index that is submitted with each query. The server can then fan out each query to an FHE value per (existing) bucket in its shard by decompressing the encrypted bucket selector. Within each shard, each bucket is joined with the FHE values from the queries for the bucket. For each bucket: for each pair in the cartesian product of FHE values from queries and chunks of the bucket, perform an FHE absorption. The output of this step is a multimap from (query _id, chunk_index) pairs to FHE-encrypted values. The values are aggregated using FHE addition as the aggregator. This has the same output format as the previous step, except that it's not a multimap - each key has exactly one FHE value. A list of encrypted values sorted by chunk_index is aggregated, and the output format is a map from query to a list of FHE-encrypted values. By providing the same number of queries per shard and with appropriate sharding, the computational costs can be reduced by having many shards without revealing any information about the distribution of queries. Now returning back to <FIG>.

The server <NUM> transmits the list of FHE encrypted values to the client <NUM> (<NUM>). The server <NUM> after generating the list of FHE encrypted values of the bucket vector and the c-byte chunks for each of the server encrypted identifiers, transmits the one or more lists to the client <NUM> over the network <NUM>.

The client <NUM> decrypts the FHE encryption (<NUM>). In some implementations, after receiving the one or more lists of FHE encrypted values of the bucket vector and the c-byte chunks, the client <NUM> uses the decryption keys that were generated in step <NUM> of the process <NUM> to decrypt the FHE encryption from each of the lists to obtain the value of the key-value pair that was queried and was originally stored on the server database if it exists.

In some implementations, the values of n and P can be tuned for further optimization. For example, increasing the value of P saves computation time of the server <NUM> but at the same time increases the burden of the client <NUM> to generate more queries. To compensate for additional queries for a larger value of P, a client <NUM> can generate fake queries that do not select data from the server database.

In situations, when fake queries present the issue of a malicious client using additional queries to learn about other data that is stored in the server database, the server <NUM> can ensure that the client <NUM> is only sent a result per real query, rather than the fake queries. In some implementations, this can be achieved by utilizing an additional PIR protocol on top of the results, rather than sending the full results to the client <NUM>. In some implementations, this may be very efficient because even with a large number of fake queries, the number of fake queries is orders of magnitude smaller than the server database.

In some implementations, it may be optimal to set the number of shards to equal the number of queries. By using techniques such as relative Chernoff Bounds and Union Bounds, the number of fake queries can be determined. For some implementations, for example, it may be optimal to have around <NUM>-<NUM> fake queries per real query when there are around <NUM>,<NUM> queries.

<FIG> is a block diagram of an example computer system <NUM> that can be used to perform operations described above. The system <NUM> includes a processor <NUM>, a memory <NUM>, a storage device <NUM>, and an input/output device <NUM>. Each of the components <NUM>, <NUM>, <NUM>, and <NUM> can be interconnected, for example, using a system bus <NUM>. The processor <NUM> is capable of processing instructions for execution within the system <NUM>. In some implementations, the processor <NUM> is a single-threaded processor. In another implementation, the processor <NUM> is a multi-threaded processor. The processor <NUM> is capable of processing instructions stored in the memory <NUM> or on the storage device <NUM>.

Alternatively, or in addition, the program instructions can be encoded on an artificially-generated propagated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal that is generated to encode information for transmission to suitable receiver apparatus for execution by a data processing apparatus.

Claim 1:
A method, comprising:
generating a partitioned database in which a database is partitioned into shards each having a shard identifier that logically distinguishes each shard from other shards, and database entries in each shard are partitioned into buckets having a bucket identifier that logically distinguishes each bucket in the shard from other buckets in the shard;
receiving, by a server (<NUM>) including one or more processors and from a client device (<NUM>), a batch of client-encrypted queries, wherein the batch of client-encrypted queries includes two or more queries that have each been encrypted by the client device and specify a shard identifier for the client-encrypted query;
processing, by the server (<NUM>), the batch of client-encrypted queries using a set of server-encrypted data stored in a database, wherein each database entry is server-encrypted and is capable of being decrypted by a corresponding decryption key, wherein the processing includes:
grouping, by the server (<NUM>), the client-encrypted queries according to shard identifiers of the client-encrypted queries, wherein each group of client-encrypted queries includes multiple queries;
executing, by the sever (<NUM>) and for each shard, the multiple queries in the group of client-encrypted queries for the shard together in a batch execution process; and
generating, by the server (<NUM>) and for each shard, multiple server-encrypted results to the multiple queries in the group of client-encrypted queries; and
transmitting, by the server (<NUM>), the multiple server-encrypted results for each shard to the client device (<NUM>).