Private information retrieval with sublinear public-key operations

A method (500) includes initializing a client state (250) on a client device (120) be executing a private batched sum retrieval instruction (200) to compute c sums O of data blocks (102) from an untrusted storage device (150). Each computed sum O stored on memory hardware (122) of the client device and including a sum of a corresponding subset S of exactly k data blocks. The method also includes a query instruction (300) to retrieve a query block Bq stored on the untrusted storage device by iterating through each of the c sums O of data blocks to identify one of the c sums O that does not include the query block Bq, instructing a service to pseudorandomly partition the untrusted storage device into partitions and sum the data blocks in each partition to determine a corresponding encrypted data block sum (302).

TECHNICAL FIELD

This disclosure relates to private information retrieval with sublinear encrypted operations.

BACKGROUND

Enterprises and individuals are using distributed storage systems (i.e., cloud storage services) to store data on memory overlying multiple memory locations. In order to use essential functionalities offered by the cloud storage services, such as performing search queries on stored data, enterprises are required to provide plaintext access to the cloud storage services. As a result, many government and sensitive private sectors, such as health, finance, and legal, or reluctant to use cloud storage services, despite their increased convenience and cost advantages. For instance, data access patterns by users can provide a significant amount of information about the data and/or the user.

Private information retrieval (PIR) schemes allow a user to retrieve data from one or more storage devices while not revealing any knowledge about the user or the retrieved data to a server hosting the one or more storage devices. For PIR, server storage devices are generally not protected and private information is retrieved from either a public storage device or a server storage device with a group of subscribers all permitted to download data from the entire storage device. While users may simply download all of the content from a server storage device so that access patterns are not revealed, this takes too long when having to download all the contents from a cloud storage service spanning multiple storage devices. Moreover, conventional PIR schemes allowing access to multiple users generally require the users to be stateless in order to allow simultaneous and independent querying without collisions or conflicts between the users. Since the users do not hold any state, these conventional PIR schemes are computational expensive requiring the server to perform Ω(n) encrypted operations for a database of n blocks.

SUMMARY

In a single-server Private Information Retrieval (PIR) system with multiple clients, the server will store a set of plaintext blocks of data on storage resources. While the server is responsible for generating and storing the data blocks, a client retrieving a specific data block from the storage resources wants the guarantee that the server will be unable to identify which block was retrieved by the client. For instance, the plaintext data blocks may include machine learning models that the server generates and distributes for a multiplicity of different applications. If clients retrieved machine learning models in the plaintext, the server, and ultimately an entity associated with the server, would be able to learn important private information about the clients without the guarantees provided by PIR.

In existing PIR protocols that employ two or more servers, each jointly responsible for hosting the plaintext data to provide access by multiple clients, there is an assumption that the servers are non-colluding, i.e., the servers do not share information amongst themselves. However, in real-world scenarios, the multi-server PIR protocol is infeasible since the different entities associated with the servers that jointly host the plaintext data could be competitors with one another. On the other hand, existing PIR protocols that employ a single-server, require client devices to not hold state in order to ensure that the client devices can simultaneously access plaintext data blocks independently from one another. However, as modern client devices such as smart phones allow applications to store 100 megabytes of data, the requirement of stateless clients is wasteful and computationally expensive due to the number of encrypted operations the single server has to be perform.

Implementations herein are directed toward a single-server PIR routine that employs an asynchronous client storage model where each client is allowed to keep state independently from the state of the other clients. Accordingly, client devices may update their state independently from the state of the other client devices after performing a query for plaintext data blocks stored on storage resources managed by the server. Similarly, when a client's state is lost, only that client needs to perform computations with the server to regain the state. As a result of allowing the clients to utilize their local storage to keep state independently from one another, the single-server PIR routine drastically improves computational efficiency by minimizing the number of encrypted operations needed to ensure that data blocks are retrieved in a manner that is oblivious to the server. For instance, 1-million encrypted operations (exponentiation) requires minutes of CPU time, while 1-million plaintext operations (e.g., addition/XOR) requires less than a second time.

While oblivious random access memory (RAM) protocols also use local client storage to improve efficiency, oblivious RAM protocols often sacrifice the ability to perform queries from multiple clients easily. For instance, oblivious RAM protocols that use local client storage require the clients to have synchronized states such that not only does a querying client need to update state, all other non-querying clients must also update there state. As a result, in order to keep the client states synchronized, either the clients need to communicate with one another or the server has to keep track of the states of each client, thereby leading to larger storage costs for the server. Moreover, most oblivious RAM protocols do not allow clients to access the storage resources in parallel, or require client-to-client communication for parallel oblivious RAM protocols.

On the other hand, Doubly Efficient PIR protocols achieve faster computational times at the cost of trusting all of the clients to share a private key and be honest with one another. For instance, Doubling Efficient PIR protocols avoid performing operations on each storage resource element through the use of smooth, locally decodable codes (e.g., Reed-Muller code), but require the use of a designated client model that requires each client to share a single private key to query the storage resources. In scenarios where multiple clients share the single private key, a single client leak of the private key to the server can allow the server to determine all of the queried indices of all clients. Moreover, Doubly Efficient PIR protocols must store poly (N, q) database sizes to be able to handle q queries securely. After q queries, the database must be re-initialized privately by a single client and new keys must be provided to all clients. By allowing clients to hold state, the single-server PIR routine of the present disclosure avoids re-initializing across many clients, and after a specific client performs q queries, only that client has to update state with the server to continue efficient querying, while other clients maintain their state and are free to continue querying.

One aspect of the present disclosure provides a method for obliviously retrieving data blocks on an untrusted storage device using private information retrieval (PIR). The method includes initializing, by data processing hardware of a client device, a client state on the client device by executing a private batched sum retrieval instruction to compute c sums O of data blocks from an untrusted storage device, each computed sum O stored on memory hardware of the client device and including a sum of a corresponding subset S of exactly k data blocks. The method also includes executing, by the data processing hardware, a query instruction to retrieve a query block Bqstored on the untrusted storage device by: iterating through each of the c sums O of data blocks stored on the memory hardware to identify one of the c sums O that does not include the query block Bq; instructing a service managing the untrusted storage device to pseudorandomly partition the untrusted storage device of n data blocks into

nk+1
partitions each containing k+1 data blocks and summing the k+1 data blocks in each of the

nk+1
partitions to determine a corresponding encrypted data block sum for each of the

nk+1
partitions, one of the

nk+1
partitions including a fixed partition that includes the identified c sum O of data blocks that does not include the query block Bq; retrieving the encrypted data block sum for the

nk+1
partition that includes the fixed partition from the service managing the untrusted storage device, and decrypting and subtracting the encrypted data block sum from the identified c sum O of data blocks stored on the memory hardware of the client device to obtain the query block Bq. The method also includes determining, by the data processing hardware (124), whether the number of queries (q) exceeds a query threshold and re-initializing, by the data processing hardware (124), the client state when the number of queries (q) exceeds the query threshold.

Implementations of the disclosure may include one or more of the following optional features. In some implementations, executing the private batched sum retrieval instruction to compute the c sums O of data blocks includes, streaming every data block stored on the untrusted storage device to the client device, the untrusted storage device storing n data blocks; assigning selected data blocks streamed from the untrusted storage device to corresponding subsets S of c subsets S of data blocks; and computing each c sum O of data blocks by summing the selected data blocks assigned to the corresponding subset S. In other implementations, executing the private batched sum retrieval instruction to compute the c sums O of data blocks includes downloading in data blocks from the untrusted storage device to compute the c sums U of data blocks for storage on the memory hardware. Here, the number of m data blocks downloaded by the client device is equal to the product between the number of k data blocks and the number of c sums O of data blocks.

In even other implementations, executing the private batched sum retrieval instruction to compute the c sums O of data blocks includes: sending a private information retrieval request from the client device to a service managing the untrusted storage device to retrieve the t data blocks from each of the k buckets, the private information request causing the service to encrypt and store each t data block as a corresponding private information retrieval result on the untrusted storage device; generating a vector of additively homomorphic encryptions, uploading the vector of additively homomorphic encryptions to the untrusted storage device, the vector of additively homomorphic encryptions causing the service managing the untrusted storage device to execute an additive homomorphic encryption computation on the private information retrieval results using the vector of additively homomorphic encryptions, the additive homomorphic encryption computation corresponding to a ciphertext value for the corresponding c sum O of data blocks; and receiving and decrypting the ciphertext from the service managing the untrusted storage device to obtain the corresponding c sum O of data blocks. The additive homomorphic encryption computation includes a dot product computation. Additionally or alternatively, t may be equal to one.

In some examples, instructing a service managing the untrusted storage device to pseudorandomly partition the untrusted storage device of n data blocks into

nk+1
partitions includes generating a vector of pseudorandom permutation partitioning keys (κ) that includes the instructions for pseudorandomly partitioning the untrusted storage device of n data blocks into

nk+1
partitions; and sending a request from the client device to the service managing the untrusted storage device that includes the vector of pseudorandom permutation partitioning keys, the request causing the service to pseudorandomly partition the untrusted storage device of n data blocks into the

nk+1
partitions with one of the

nk+1
partitions including the fixed partition that includes the identified c sum O of data blocks that does not include the query block Bq. The pseudorandom partition includes a two-dimensional matrix with each row including a corresponding partition and each column including an incrementally generated pseudorandom permutation for a corresponding one of the k+1 blocks in each partition.

A system aspect of the present disclosure provides a method for obliviously retrieving data blocks on an untrusted storage device using private information retrieval (PIR). The system includes data processing hardware of a client device and memory hardware of the client device in communication with the data processing hardware. The memory hardware stores instructions that when executed by the data processing hardware cause the data processing hardware to perform operations that includes initializing a client state on the client device by executing a private batched sum retrieval instruction to compute c sums O of data blocks from an untrusted storage device, each computed sum O stored on memory hardware of the client device and including a sum of a corresponding subset S of exactly k data blocks. The operations also include executing a query instruction to retrieve a query block Bqstored on the untrusted storage device by: iterating through each of the c sums O of data blocks stored on the memory hardware to identify one of the c sums O that does not include the query block Bq; instructing a service managing the untrusted storage device to pseudorandomly partition the untrusted storage device of n data blocks into

nk+1
partitions each containing k+1 data blocks and summing the k+1 data blocks in each of the

nk+1
partitions to determine a corresponding encrypted data block sum for each of the

nk+1
partitions, one of the

nk+1
partitions including a fixed partition that includes the identified c sum O of data blocks that does not include the query block Bq; retrieving the encrypted data block sum for the

nk+1
partition that includes the fixed partition from the service managing the untrusted storage device; and decrypting and subtracting the encrypted data block sum from the identified c sum O of data blocks stored on the memory hardware of the client device to obtain the query block Bq. The method also includes determining whether the number of queries (q) exceeds a query threshold and re-initializing the client state when the number of queries (q) exceeds the query threshold.

This aspect of the present disclosure may include one or more of the following optional features. In some implementations, executing the private batched sum retrieval instruction to compute the c sums O of data blocks includes: streaming every data block stored on the untrusted storage device to the client device, the untrusted storage device storing n data blocks; assigning selected data blocks streamed from the untrusted storage device to corresponding subsets S of c subsets S of data blocks; and computing each c sum O of data blocks by summing the selected data blocks assigned to the corresponding subset S. In other implementations, executing the private batched sum retrieval instruction to compute the c sums O of data blocks includes downloading n data blocks from the untrusted storage device to compute the c sums O of data blocks for storage on the memory hardware. Here, the number of in data blocks downloaded by the client device is equal to the product between the number of k data blocks and the number of c sums O of data blocks.

In even other implementations, executing the private batched sum retrieval instruction to compute the c sums O of data blocks includes: sending a private information retrieval request from the client device to a service managing the untrusted storage device to retrieve the t data blocks from each of the k buckets, the private information request causing the service to encrypt and store each r data block as a corresponding private information retrieval result on the untrusted storage device; generating a vector of additively homomorphic encryptions; uploading the vector of additively homomorphic encryptions to the untrusted storage device, the vector of additively homomorphic encryptions causing the service managing the untrusted storage device to execute an additive homomorphic encryption computation on the private information retrieval results using the vector of additively homomorphic encryptions, the additive homomorphic encryption computation corresponding to a ciphertext value for the corresponding c sum O of data blocks; and receiving and decrypting the ciphertext from the service managing the untrusted storage device to obtain the corresponding c sum O of data blocks. The additive homomorphic encryption computation includes a dot product computation. Additionally or alternatively, t may be equal to one.

In some examples, instructing a service managing the untrusted storage device to pseudorandomly partition the untrusted storage device of n data blocks into

nk+1
partitions includes generating a vector of pseudorandom permutation partitioning keys (κ) that includes the instructions for pseudorandomly partitioning the untrusted storage device of n data blocks into

nk+1
partitions; and sending a request from the client device to the service managing the untrusted storage device that includes the vector of pseudorandom permutation partitioning keys, the request causing the service to pseudorandomly partition the untrusted storage device of n data blocks into the

nk+1
partitions with one of the

nk+1
partitions including the fixed partition that includes the identified c sum O of data blocks that does not include the query block Bq. The pseudorandom partition includes a two-dimensional matrix with each row including a corresponding partition and each column including an incrementally generated pseudorandom permutation for a corresponding one of the k+1 blocks in each partition.

DETAILED DESCRIPTION

Implementations herein are directed toward a single-server private information retrieval (PIR) routine that allows multiple client devices, each having an asynchronous state, to obliviously retrieve data blocks stored on untrusted memory managed by a service provider. The untrusted memory may include storage resources of a distributed storage system that executes in a cloud-environment accessible to the client devices. The data blocks stored on the untrusted memory are publically-known and un-encrypted (e.g., plaintext). Thus, the single-server PIR routine with multiple client devices having independent storage (e.g., asynchronous state) effectively conceals access patterns of the publically-known and un-encrypted data from the untrusted memory. In one example, the service provider managing storage resources (e.g., untrusted memory), may generate machine learning models for distribution to client devices. Here, the server provider may store the generated machine learning models as data blocks on the storage resources and the client devices may query for specific machine learning models using private information about the client. The single-server PIR routine prevents the service provider that distributes the machine learning models from learning which machine learning model was retrieved by a client device. In another example, client devices undergoing a factory reset often check whether the client device is associated with an enterprise group or an individual. A manufacturer of the client device (or provider of an operating system or other software executing on the client device) may store a set of enterprise identifiers and associated client identifiers as plaintext. While extra operations may be required for completing the factory reset when the client device belongs to a specific enterprise group, the single-server PIR routine ensures that the client identifier associated with the client device is never leaked to the manufacturer when the client device does not belong to an enterprise group.

The asynchronous state refers to each client device having independent storage from the other client devices to allow the client devices to update their state independently from one another after performing a query for data stored on the untrusted memory. Similarly, when a client device decides to release state, the queries of all the other client devices remains hidden from the server managing the untrusted memory. To construct the single-server PIR routine and provide more efficient online querying at a later time, the client devices first initialize their state by executing a private batched sum retrieval routine, and thereafter executing a constrained pseudorandom partitioning instruction that allows the client devices to communicate fixed partitions to the service managing the untrusted memory when the client devices execute queries for data blocks stored on the untrusted memory.

FIGS.1A and1Bdepict an example system100for storing publically-known and un-encrypted n data blocks (B)102on a distributed system140and allowing multiple client devices120,120a-nholding asynchronous state250to use private information retrieval (PIR) for obliviously retrieving data blocks (B)102to conceal access patterns while preserving search functionalities on the data blocks (B)102by the client devices120. Thus, the client device120may not own the data blocks102and the content of the data blocks102are available to the public in configurations. A client device120(e.g., a computer) associated with the client10communicates, via a network130, with the distributed system140having a scalable/elastic non-transitory storage abstraction150. The client device120may include associated memory hardware122and associated data processing hardware124. Each client device120may leverage the associated memory hardware122to hold a state250for storing one or more of the data blocks (B)102when executing query instructions300to query for data blocks (B)102stored on the storage abstraction150. The storage abstraction150(e.g., file system, data store, etc.) is overlain on storage resources114to allow scalable use of the storage resources114by one or more client devices120.

In some implementations, the distributed system140executes a computing device112(e.g., server) that manages access to the storage abstraction150. For instance, the server may generate and store data blocks on the storage abstraction in the plaintext, and the client devices120may retrieve the data blocks102in the plaintext from the storage abstraction ISO. While the example shown depicts the system100having a trusted side associated with the client devices120in communication, via the network130, with an untrusted side associated with the distributed system140, the system100may be alternatively implemented on a large intranet having a trusted computing device(s) (CPU) and untrusted data storage. The untrusted side associated with the distributed system140or data storage is considered “honest-but-curious”, in that the computing device112follows the protocol honestly but may perform any probabilistically polynomial time algorithm using information leaked by the distributed system140to gain additional insight.

In some implementations, the distributed system100includes resources110,110a-z. The resources110may include hardware resources and software resources. The hardware resources110may include computing devices112(also referred to as data processing devices and data processing hardware) or non-transitory memory114(also referred to as memory hardware and storage resources). The software resources110may include software applications, software services, application programming interfaces (APIs) or the like. The software resources110may reside in the hardware resources110. For example, the software resources110may be stored in the memory hardware114or the hardware resources110(e.g., the computing devices112) may be executing the software resources110.

The memory hardware114,122may be physical devices used to store programs (e.g., sequences of instructions) or data (e.g., program state information) on a temporary or permanent basis for use by a computing device112and/or the client devices120(i.e., the data processing hardware124of the client devices120). The memory hardware114,122may be volatile and/or non-volatile addressable semiconductor memory. Examples of non-volatile memory include, but are not limited to, flash memory and read-only memory (ROM)/programmable read-only memory (PROM)/erasable programmable read-only memory (EPROM)/electronically erasable programmable read-only memory (EEPROM) (e.g., typically used for firmware, such as boot programs). Examples of volatile memory include, but are not limited to, random access memory (RAM), oblivious random access memory (ORAM), dynamic random access memory (DRAM), static random access memory (SRAM), phase change memory (PCM) as well as disks or tapes.

The network130may include various types of networks, such as local area network (LAN), wide area network (WAN), and/or the Internet Although the network130may represent a long range network (e.g., Internet or WAN), in some implementations, the network130includes a shorter range network, such as a local area network (LAN). In some implementations, the network130uses standard communications technologies and/or protocols. Thus, the network130can include links using technologies, such as Ethernet, Wireless Fidelity (WiFi) (e.g., 802.11), worldwide interoperability for microwave access (WiMAX), 3G, Long Term Evolution (LTE), digital subscriber line (DSL), asynchronous transfer mode (ATM), InfiniBand, PCI Express Advanced Switching, Bluetooth, Bluetooth Low Energy (BLE), etc. Similarly, the networking protocols used on the network130can include multiprotocol label switching (MPLS), the transmission control protocol/Internet protocol (TCP/IP), the User Datagram Protocol (UDP), the hypertext transport protocol (HTTP), the simple mail transfer protocol (SMTP), the file transfer protocol (FTP), etc. The data exchanged over the network130can be represented using technologies and/or formats including the hypertext markup language (HTML), the extensible markup language (XML), etc. In addition, all or some of the links can be encrypted using conventional encryption technologies, such as secure sockets layer (SSL), transport layer security (TLS), virtual private networks (VPNs), Internet Protocol security (IPsec), etc. In other examples, the network130uses custom and/or dedicated data communications technologies instead of, or in addition to, the ones described above.

The data blocks102correspond to atomic units of data and each have size B bytes each. For example, a typical value for B for storage on a distributed system may be 64 KB to 256 B. A notation n denotes a number of the data blocks102associated with the storage resource(s)114and stored on the storage abstraction150using PIR. Each of the n data blocks (B)102is stored at a corresponding memory location118,118a-n(FIG.1B) of the storage abstraction150overlain across the memory hardware114. Specifically, the in data blocks (B)102are associated with PIR storage whereby the n data blocks (B)102are stored on one or more storage resources114and are un-encrypted and available to the public. For instance, the un-encrypted and public data blocks (B) may be associated with machine learning models generated by the distributed system140and available for download by the client devices120.

To provide more efficient querying for the publically-known plaintext data blocks102stored by the storage abstraction150(e.g., database) of the distributed system140, each client device120initializes the corresponding state250by executing a private batched sum retrieval (BSR) instruction200that causes the client device120to compute c sums of O data blocks120from the storage abstraction150for storage on the memory hardware122of the client device120. Here, each of the c computed sums O includes a sum of a corresponding subset S of exactly k data blocks120. In some implementations, each client device120generates and applies a random permutation (π1, πj, . . . , πk) to each k block in a corresponding subset S1, S2, . . . , SCbefore computing each c sums O1, O2, . . . , OCof data blocks102. The client devices120may initialize state250and execute private BSR instructions200during downtimes (e.g., nighttime) in order to provide more efficient querying for data blocks102at later times. After performing a threshold number of queries, each client device120re-initializes its state250independently of the state250of the other client devices120and without interrupting querying by the other client devices120.

The client devices120may select different private BSR instructions200based on one or more factors including, without limitation, size of the database (e.g., number of n data blocks102), computational requirements, and/or bandwidth requirements. For instance, the private BSR instruction200may include a streaming private BSR instruction200a,200(FIG.2A) that streams every n data block102from the storage abstraction150and assign selected data blocks102to corresponding c subsets S for computing each c sum O of data blocks. In other examples, the private BSR instruction200includes a batched private BSR instruction200b,200(FIG.2B) that downloads m data blocks102from the storage abstraction150for computing the c sums O of data blocks. In yet other examples, the private BSR instruction200includes a batch code private BSR instruction200c,200(FIGS.2C-2E) that partitions the storage abstraction150into k buckets, and for each c sum O of data blocks102to be computed, downloads t data blocks from each of the k buckets to compute the corresponding sum O of data blocks102for storage on the memory hardware122(i.e., within the state250). Generally, the streaming private BSR instruction200ais most efficient for databases of smaller sizes, while the batch code private BSR instruction200cis most efficient for databases of larger sizes. The batched private BSR instruction200bmay provide the best querying efficiencies on medium-sized databases.

After initializing state250, a client device120executes a query instruction300to obliviously retrieve a query block Bqstored on the storage abstraction200. Here, the client device120iteratively searches through the corresponding state250to identify one of the c sums O that does not include the query block Bq. Upon identifying the c sums O that does not include the query block Bq, the client device120may send a partition request320that instructs a service (e.g., server)160managing the storage abstraction150to pseudorandomly partition the storage abstraction of n data blocks into

nk+1
partitions350each containing k+1 data blocks and summing the k+1 data blocks in each of the

nk+1
partitions to determine a corresponding encrypted data block sum302for each of the

nk+1
partitions includes a two-dimensional matrix. Advantageously, the partition request320embeds a fixed partition that includes the identified c sum O to one of the

nk+1
partitions, whereby the identified c sum O is embedded into a random row (e.g., rthrow) of the two-dimensional matrix. Obliviously, the service160may return the encrypted data block sum302that includes the fixed partition for the identified c sum O of data blocks102(i.e., k data blocks) as well as the query block Bq(e.g., the +1 block). Responsive to receiving the encrypted data block sum302, the client device120(e.g. via the data processing hardware124) decrypts and subtracts the encrypted data block sum302from the identified c sum O of data blocks102stored on the client device120to obtain the query block Bq. Thus, by executing the instruction300, the client device120is able to retrieve the data block Bqwithout revealing the contents of the data block102as well as the sequence of the query executed by the client device120to the distributed system140. The service160may execute on the data processing hardware112.

Referring toFIG.1B, in some implementations, the distributed storage system140includes loosely coupled memory hosts110,110a-z(e.g., computers or servers), each having a computing resource112(e.g., one or more processors or central processing units (CPUs)) in communication with storage resources114(e.g., memory hardware, memory hardware, flash memory, dynamic random access memory (DRAM), phase change memory (PCM), and/or disks) that may be used for caching data. The storage abstraction150overlain on the storage resources114allows scalable use of the storage resources114by one or more client devices120,120a-n. The client devices120may communicate with the memory hosts110through the network130(e.g., via remote procedure calls (RPC)). The computing resources112may execute the service160.

In some implementations, the distributed storage system140is “single-sided,” eliminating the need for any server jobs for responding to queries from client devices120to retrieve data blocks102from the storage abstraction150when the client devices120executes instructions300to execute queries (q) for data blocks102. “Single-sided” refers to the method by which most of the request processing on the memory hosts110may be done in hardware rather than by software executed on CPUs112of the memory hosts110. Additional concepts and features related to a single-sided distributed caching system can be found in U.S. Pat. No. 9,164,702, which is hereby incorporated by reference in its entirety.

The distributed system140may obliviously move data blocks102around the storage resources114(e.g., memory hardware) of the remote memory hosts110(e.g., the storage abstraction200) and get the data blocks102from the remote memory hosts110via RPCs or via remote direct memory access (RDMA)-capable network interface controllers (NIC)116. A network interface controller116(also known as a network interface card, network adapter, or LAN adapter) may be a computer hardware component that connects a computing device/resource112to the network130. Both the memory hosts110a-zand the client device120may each have a network interface controller116for network communications. The instruction300executing on the physical processor112of the hardware resource110registers a set of remote direct memory accessible regions/locations118A-N of the memory114with the network interface controller116. Each memory location118is configured to store a corresponding data block102.

FIG.2Aprovides an example streaming private BSR instruction200aexecuting on the client device120to stream the entire contents of a PIR storage abstraction114,150(e.g., storage abstraction/database) in order for computing the c sums O of data blocks102with each sum containing exactly k data blocks. To initiate the streaming of the n data blocks102, the client device102may send a stream request202to the service160managing the PIR storage abstraction150. Since all of the in data blocks102are streamed, the instruction200adoes not have to hide from the server160which data blocks102were accessed by the client device120. The client device120may assign selected data blocks102in the stream to corresponding ones of the subsets S1, S2, . . . , SCamong the e subsets of data blocks102. Thereafter, the client device120computes each c sum O1, O2, . . . , OC(e.g., output) by summing the selected k data blocks assigned to the corresponding subset S1, S2, . . . , SC(e.g., input). For each subset S, the client device120may further apply a corresponding random permutation to each data block B1, B2, . . . , Bkincluded in the subset S. The total number m of data blocks stored on the memory hardware122of the client device is equal the total number c of subsets S times the number of data blocks k assigned to each subset. The streaming private BSR instruction200amay use O(n) bandwidth, O(m) additions, and O(c) local memory at the client device120.

FIG.2Bprovides an example batched private BSR instruction200bexecuting on the client device120that causes the client device120to send a download request204to download exactly m data blocks from the PIR storage abstraction114,150for computing the c sums O of data blocks102with each sum containing exactly k data blocks. Thus, whereas the streaming private BSR instruction200bstreams all n data blocks from the PIR storage abstraction114,150, the batched private BSR instruction200bonly downloads the m data blocks102needed to assemble the c subsets S of the client state250. Since the number of m data blocks downloaded by the client device is equal to the product between the number of k data blocks and the number of c sums O of data blocks, the instruction200bassigns exactly k data blocks to corresponding ones of the subsets S1, S2, . . . , SCamong the c subsets of data blocks102. Thereafter, the client device120computes each c sum O1, O2, . . . , OC(e.g., output) by summing the selected k data blocks assigned to the corresponding subset S1, S2, . . . , SC(e.g., input). For each subset S, the client device120may further apply a corresponding random permutation to each data block B1, B2, . . . , Bkincluded in the subset S. The batched private BSR instruction200bmay use O(m logit n+λ+mB) bandwidth and O(n) of computation.

FIGS.2C-2Eprovide an example batch code private BSR instruction200bexecuting on the client device120that partitions/divides/segments the PIR storage abstraction114,150of n data blocks into k buckets260, and for each c sum O of data blocks102to be computed for storage on the client device120, downloads r data blocks from each of the k buckets260to compute the corresponding sum O of data blocks102. The smaller buckets260subdivide the storage abstraction150to increase bandwidth when the client device120is initializing the state250during execution of the batch code private BSR instruction200b. The number of k buckets260partitioned at the distributed system140by the client device120is tunable based on security and/or bandwidth requirements. In the examples shown, the n data blocks102of the storage abstraction150is partitioned into four buckets260,260a-dsuch that the four buckets250,260a-dcollectively include N (e.g., 16) data blocks102A-102N. Moreover, the data blocks102within each k bucket260are encrypted using an encoding function.

FIG.2Cshows the client device initiating the instruction200bby sending batch codes262to the service160that causes the service160to partition the storage abstraction150into the k buckets250a-dand encode the N blocks102that appear in all k buckets using an encoding function. The batch codes262ensure that for any subset S with at most in items, the set of blocks102assigned to the corresponding subset S may be retrieved by reading at most t items in each of the k buckets260. Implementations herein, set t equal to one (1). In some examples, the batch codes262include cuckoo batch codes. The client devices120may include an encryption module305in communication with the data processing hardware124to provide the batch codes262. The encryption module305may include software executing on the data processing hardware124or may include a separate hardware that communicates with the data processing hardware124.FIG.2Cfurther shows the state250of the client device120initializing to retrieve exactly k data blocks for first and second subsets S1, S2, e.g., c equals two subsets S. While only two subsets are shown by example, other examples may include more than two subsets.

FIG.2Dshows the client device120, while executing the batch code private BSR instruction200c, sending a PIR request264to the service160to download t data blocks102from each of the k buckets260a-260dfor the first subset S1. While not shown, the client device120also sends a corresponding PIR request264to download t data blocks102from each of the k buckets for input to the second subset S2. In response to receiving the PIR request264, the service encrypts and stores each t data block102retrieved from the k buckets260as a corresponding private information retrieval result r1, r2, r3, r4associated with the first subset S1. Thus, the results are stored on the storage resources114of the distributed system140. In the example shown, t is equal to one such that the service160randomly downloads, encrypts, and stores block 2 from Bucket 1260aas PIR result r1; downloads, encrypts, and stores block 7 from Bucket 2260bas PIR result r2; downloads, encrypts, and stores block 12 from Bucket 3260cas PIR result r3; and downloads, encrypts, and stores block 15 from Bucket 4260das PIR result r4.

After sending the PIR request304to download the t data blocks102from each of the buckets260for the first subset S1, the client device generates a vector of additively homomorphic encryptions266and uploads the vector of additively homomorphic encryptions (e1, e2, e3, e4)266to the distributed system140(e.g., the storage abstraction150). In some examples, a homomorphic encryption ejis an encryption of one (1) if and only if the sum Oi to be computed requires the block102from the i-th bucket260as part of the sum and homomorphic encryption ejis an encryption of zero (0) otherwise. The vector of additively homomorphic encryptions (e1, e2, e3, e4)266causes the service160to execute an additive homomorphic encryption computation268on the private information retrieval results r1, r2, r3, r4associated with the first subset S1using the vector of additively homomorphic encryptions (e1, e2, e3, e4)266. The additive homomorphic encryption computation268corresponding to a ciphertext value for the corresponding c sum O of data blocks. Additively homomorphic encryptions allow the service160to perform the additive homomorphic encryption computation268so that the encoded results downloaded from the k buckets260can be summed, thereby alleviating computational costs associated with performing encrypted operations. In the example shown, the additive homomorphic encryption computation268includes a dot product computation. Thereafter, the service160returns the ciphertext value for the corresponding c sum O of data blocks (e.g., sum O1in the example ofFIG.2D) to the client device120and the client device120decrypts the ciphertext value to compute the c sum O of data blocks (e.g., sum O2in the example ofFIG.2D) for storage on the local memory hardware122to initialize the state250. This process repeats for each c sum O of data blocks to be computed.

FIGS.3A-3Cprovide an example query instruction300executing on the client device120for retrieving the query block Bqfrom the storage abstraction150after initializing the state250via execution of the private BSR instruction200ofFIGS.2A-2E).FIG.3Ashows the client device120iterating through each of the c sums O of data blocks 1-2 stored on the memory hardware122to identify one of the e sums O that does not include the query block Bq. In the example shown, the client device120ceases iterating through the c sums O upon identifying that the third sum O does not include the query block Bq. Sums O1, O2, and Ocall include the query block Bq. The storage abstraction150includes the database of n data blocks102,102a-n. The database of the storage abstraction150in the present disclosure may include an online partial sums data structure with integers ordered 1 to n to allow efficient construction of partial sums, update items, and select values efficiently.

FIG.3Bshows the client device120generating a vector of keys κ (PRPartition.GenerateKey(n, k+1, S)) after identifying the c sum O (e.g., sum O3) that does not include the query block Bq.FIG.4Aprovides an example algorithm400afor generating the vector of keys κ (PRPartition.GenerateKey(n, k+1, S)). The vector of keys κ generated by the client device120during execution of the query instruction200includes instructions for pseudorandomly partitioning the untrusted storage device of n data blocks into

nk+1
partitions350include a two-dimensional matrix of constrained pseudorandom partitions such that one of the partitions is a fixed partition that includes the identified c sum O (e.g., sum O3) of data blocks that does not include the query block Bq. Thus, the vector of keys κ embeds, in a manner oblivious from the storage abstraction150and the service160managing the storage abstraction150, the subset S (e.g., subset S3) corresponding to the identified c sum O (e.g., sum O3) of data blocks that does not include the query block Bqinto a random rthrow of the partitions350as a fixed partition. Advantageously, the client device120may generate the vector of keys κ for partitioning the storage abstraction150locally without requiring any computations at the distributed system140.

The client device120instructs the service160to execute the constrained pseudorandom partitioning to sample random subsets of data of a given size with space-efficient representations. Namely, the vector of keys κ uses a pseudorandom family of permutations over the storage abstraction150(e.g., database) of [i] integers (e.g., data blocks102) by generating a random key/seed K and using a set {F(κ, 1), . . . , F(κ, k)}. As a result, the request320causes service160to partition the [n] integers into

nk+1
sets of size k+1 integers as a two-dimensional matrix in which each row will represent a corresponding partition. The two-dimensional matrix is initially empty and a pseudorandom permutation to select a row to embed an input subset S in a randomly chosen order. The remaining elements of [n] integers should be randomly distributed to empty matrix. One of the

nk+1
partitions is fixed to an input subset S of exactly k data blocks102. This fixed input subset S corresponds to one of the computed c sums O of data blocks102stored locally on the memory hardware122of the client device120. Specifically, the execution of the CPP instruction300guarantees that the fixed input subset S corresponds to one of the c sums O previously computed by the BSR instruction200by picking a pivot such that one of the

pivot+(nk)-1
is the desired fixed input subset S. Thus, the fixed input subset S will correspond to the evaluations of the permutation at the

In some examples, to find the pivot associated with a fixed element s, the pivot may be set to be π−1 (s)−r where r is uniformly chosen at random from

{0,…,(nk)-1}
guaranteeing that s will appear in the generated subset. The sampling only succeeds when the random subset of size

(nk)-1
generated around the fixed element does not contain any other elements from the input subset. The probability that the random subset does not contain an input subset element can be described as follows.

Based on this approach, a permutation key may represent the subsets in each column of the matrix such that all column subsets contain exactly one element from the fixed input subset S embedded into one of the rows of the matrix. Additionally, all column subsets must be pairwise disjoint. In some examples, the instruction300generates a random key for a pseudorandom permutation over all possible remaining items. An evaluation of a pseudorandom permutation It=F(K,i) maps to the I1-th largest remaining element. The subset of size k specified from a permutation n is simply the set containing the I1-th, . . . , Ik-th largest remaining elements, thereby ensuring all future sampled subsets are disjoint with any pervious fixed column subsets. With the ability to ensure disjoint sampled subsets, each column subset can be generated using a constant number of samples.

While explicitly stoning all unused elements requires linear storage, the instruction300only requires knowledge of the remaining unused items from the input subset. In particular, knowledge is required for the number of unused items which are smaller in value for each remaining input subset element, dented as the rank. The items of the input subset are stored in sorted order such that the particular sum up to an index i will be equal to the rank of i-th largest member of the input subset. When initializing the data structure, differences are stored between adjacent elements of the sorted input subset to ensure that rank can be retrieved by performing a partial sum query. Removing an element from the set of unused elements requires decreasing the rank of all input subset elements that are larger than the removed element by one. This can be achieved by simply subtracting one from the index of the smallest item in the input subset that is larger than the element to be removed. As a result, the rank of all input subset elements larger will also decrease by one. Finding the smallest element from the input subset larger than the removed element requires a single PartialSums.Select operation while retrieving the rank and updating an entry requires a single PartialSums.Sum and PartialSums.Update operation respectively. The entire data structure only requires storing a single entry for each input subset item meaning storage requirements are linear in the input subset size.

With continued reference toFIG.3B, the client device120sends a request320to the service160that includes the vector of pseudorandom permutation partitioning keys κ. The request320, when received by the service160, causes the service160to pseudorandomly partition (PRPartition.GetPartition(κ)) the storage abstraction150of n data blocks102into the

nk+1
partitions350with one of the

nk+1
partitions350including the fixed partition that includes the identified c sum O (e.g., sum O3) of data blocks102that does not include the query block Bq.FIG.4Bprovides an example algorithm400bfor using the vector of pseudorandom permutation partitioning keys κ to pseudorandomly partition the storage abstraction150into the

nk+1
partitions350. In the example shown, the third partition P3of the

nk+1
partitions350includes the fixed partition that includes the query block Bqand the identified c sum O (e.g., sum O3) of data blocks102that does not include the query block Bq. Here, the third partition P3includes the k blocks of the identified c sum O of data blocks102and one additional block that includes the query block Bq. The third partition P3corresponds to the 3rdrow of the two-dimensional matrix representing the

nk+1
partitions350. The pseudorandomly partitioning of the PIR storage abstraction150(e.g., database) by the service160further includes the service160summing the k+1 data blocks in each of the partitions350to determine a corresponding encrypted data block sum T1, T2, . . . , T(n/k+1)302for each partition P1, P2, . . . , P(n/k+1).

FIG.3Cshows the service160obliviously returning the encrypted data block sum T3302for the third partition P3that includes the k blocks of the identified c sum O of data blocks102and the one additional block that includes the query block Bq. In response to receiving the encrypted data block sum T3302, the client device120decrypts the encrypted data block sum T3302, retrieves the identified c sum O (e.g., sum O3) of data blocks102that does not include the query block Bq, and subtracts the decrypted data block sum T3302from the identified c sum O3 of k data blocks102to obtain the query block Bq.

FIG.4Cprovides an example algorithm400cfor initializing the client state250by executing one of the private BSR instructions200,200a,200b,200cset forth in the remarks above.FIG.4Dprovides an example algorithm400dfor executing the query (q) to retrieve a query block Bq. The example algorithm400dincludes the PRPartition.GenerateKey(n, k+1, S) step for generating the vector of pseudorandom partitioning keys κ locally at the client device120and the subsequent PRPartition.GetPartition(κ) step for pseudorandomly partitioning the PIR storage using the vector of pseudorandom partitioning keys κ.

In other implementations, the constrained pseudorandom partitions are replaced with obliviously constrained partitions that make use of pseudorandom functions. A subroutine may generate the obliviously constrained partitions by extracting an ordered subject of size m blocks from the storage abstraction150of n data blocks102given any seed/key κ to evaluate a pseudorandom function (PRF) for consecutive inputs until m distinct values are encountered. Given a set Tκ generated by seed/key κ, the routine may fix the r-th element of Tκ to be any value, such that the r-th value of a re-oriented subset is i and the remaining m−1 elements are random. As such a random constrained subset can be generated by sampling a random κ, generating Tκ, and fixing the r-th element into the two-dimensional matrix representing the

nk+1
partitions350. Here, sampling only requires knowledge of remaining unused items rom the constraint subset because only a check is required to determine whether a randomly generated constrained subset interacts with the constrained subset beyond the fixed element. Put another way, sampling only requires knowledge of the number of unused numbers which are smaller in value than each remaining constraint subset element. This knowledge corresponds to a crank of each constrained subset element. As such, only the constraint subset and corresponding rank amongst all unused items requires explicitly storage. Therefore, once a column subset is fixed, the rank of all input subset elements must be updated to reflect all fixed items that are no longer used. That is, the rank of all constraint subset elements must be decreased by all items in the column subset that are smaller. As a consequence, the sub-routine for generating oblivious constrained partitions only requires O(k) storage to maintain the ranks.

The routine for generating the obliviously constrained partitions may include a generate key step (OCP.GenerateKey) for generating keys and an extract partition step (OCP ExtractPartition) for extracting the fixed partitionFIG.4Eprovides an example algorithm400eof the OCP.GenerateKey step for generating the keys andFIG.4Fprovides an example algorithm400ffor extracting the fixed partition In some implementations, the example algorithm400dfor executing the query instruction300to retrieve the data block Bqmay instead replace the pseudorandom partitions with obliviously constrained partitions that make use of the pseudorandom functions without departing from the scope of the present disclosure. Here, the algorithm400dmay replace the PRPartition.GenerateKey(n, k+1, S) step (FIG.4A) with the OCP.GenerateKey step (FIG.4E) for generating keys and replace the subsequent PRPartition.GetPartition(κ) step (FIG.4B) with the extract partition step OCP ExtractPartition (FIG.4F) for obliviously partitioning the PIR storage and extracting the fixed partition based on the PRF keys.

FIG.5is a flow chart of an example arrangement of operations for a method500using private information retrieval (PIR) to retrieve publically-known data blocks102stored as plaintext on an untrusted storage device114,150. The untrusted storage device may include one or more storage devices114implementing the storage abstraction150on the distributed system140. The untrusted storage device114,150may be any data store or database that stores publically-known and un-encrypted data blocks available for multiple client devices to access. The PIR aspect guarantees that the untrusted storage device150, or service160managing the storage device150, does not learn the access patterns or data retrieved from the storage device150. The data processing hardware124of each client device120may execute the operations for the method500by executing instructions stored on the memory hardware122. At operation502, the method502includes initializing a client state250on the client device120by executing a private batched sum retrieval instruction200to compute c sums O of data blocks102from an untrusted storage device150, each computed sum O stored on memory hardware122of the client device120and including a sum of a corresponding subset S of exactly k data blocks102

At operation504, the method500includes executing a query instruction300to retrieve a query block Bqstored on the untrusted storage device150by iterating through each of the c sums O of data blocks102stored on the memory hardware124to identify one of the c sums O that does not include the query block Bq. At operation506, execution of the query instruction300further includes instructing a service160managing the untrusted storage device150to pseudorandomly partition the untrusted storage device150of n data blocks into

nk+1
partitions350each containing k+1 data blocks102and summing the k+1 data blocks102in each of the

nk+1
partitions350to determine a corresponding encrypted data block sum302for each of the

nk+1
partitions350, one of the

nk+1
partitions350including a fixed partition that includes the identified c sum O of data blocks that does not include the query block Bq. Operation506may generate the partitions350based on the constrained pseudorandom partitions via algorithms400a,400bofFIGS.4A and4Bor based on the obliviously constrained partitions via algorithms400e,400fofFIGS.4E and4F.

At operation508, execution of the que instruction300further includes retrieving the encrypted data block sum302for the

nk+1
partition that includes the fixed partition from the service managing the untrusted storage device150. At operation510, execution of the query instruction300further includes decrypting and subtracting the encrypted data block sum302from the identified c sum O of data blocks stored on the memory hardware122of the client device120to obtain the query block Bq. The method may include determining whether the number of queries (q) exceeds a query threshold, and re-initializing the client state250when the number of queries (q) exceeds the query threshold.

The computing device600includes a processor610, memory620, a storage device630, a high-speed interface/controller640connecting to the memory620and high-speed expansion ports650, and a low speed interface/controller660connecting to low speed bus670and storage device630. Each of the components610,620,630,640,650, and660, are interconnected using various busses, and may be mounted on a common motherboard or in other manners as appropriate. The processor610can process instructions for execution within the computing device600, including instructions stored in the memory620or on the storage device630to display graphical information for a graphical user interface (GUI) on an external input/output device, such as display680coupled to high speed interface640. In other implementations, multiple processors and/or multiple buses may be used, as appropriate, along with multiple memories and types of memory. Also, multiple computing devices600may be connected, with each device providing portions of the necessary operations (e.g., as a server bank, a group of blade servers, or a multi-processor system).

The storage device630(e.g. memory hardware) is capable of providing mass storage for the computing device600. In some implementations, the storage device630is a computer-readable medium. In various different implementations, the storage device630may be a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid state memory device, or an array of devices, including devices in a storage area network or other configurations. In additional implementations, a computer program product is tangibly embodied in an information carrier. The computer program product contains instructions that, when executed, perform one or more methods, such as those described above. The information carrier is a computer- or machine-readable medium, such as the memory620, the storage device630, or memory on processor610.

The high speed controller640manages bandwidth-intensive operations for the computing device600, while the low speed controller660manages lower bandwidth-intensive operations. Such allocation of duties is exemplary only. In some implementations, the high-speed controller640is coupled to the memory620, the display680(e.g., through a graphics processor or accelerator), and to the high-speed expansion ports650, which may accept various expansion cards (not shown). In some implementations, the low-speed controller660is coupled to the storage device630and low-speed expansion port670. The low-speed expansion port670, which may include various communication ports (e.g., USB, Bluetooth, Ethernet, wireless Ethernet), may be coupled to one or more input/output devices, such as a keyboard, a pointing device, a scanner, or a networking device such as a switch or router, e.g., through a network adapter.

The computing device600may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a standard server600aor multiple times in a group of such servers600a, as a laptop computer600b, or as part of a rack server system600c.