Private Information Retrieval (PIR) allows several clients to query a database held by one or more servers, such that the contents of their queries remain private. Prior PIR schemes have achieved sublinear communication and computation by leveraging computational assumptions, federating trust among many servers, relaxing security to permit differentially private leakage, refactoring effort into an offline stage to reduce online costs, or amortizing costs over a large batch of queries.
In this work, we present an efficient PIR protocol that combines all of the above techniques to achieve constant amortized communication and computation complexity in the size of the database and constant client work. We leverage differentially private leakage in order to provide better trade-offs between privacy and efficiency. Our protocol achieves speedups up to and exceeding 10x in practical settings compared to state of the art PIR protocols, and can scale to batches with hundreds of millions of queries on cheap commodity AWS machines. Our protocol builds upon a new secret sharing scheme that is both incremental and non-malleable, which may be of interest to a wider audience. Our protocol provides security up to abort against malicious adversaries that can corrupt all but one party.
more »
« less
Incremental Offline/Online PIR
Recent private information retrieval (PIR)
schemes preprocess the database with a query-independent
offline phase in order to achieve sublinear computation during
a query-specific online phase. These offline/online protocols
expand the set of applications that can profitably use PIR,
but they make a critical assumption: that the database is
immutable. In the presence of changes such as additions,
deletions, or updates, existing schemes must preprocess the
database from scratch, wasting prior effort. To address this,
we introduce incremental preprocessing for offline/online
PIR schemes, allowing the original preprocessing to continue
to be used after database changes, while incurring an update
cost proportional to the number of changes rather than
the size of the database. We adapt two offline/online PIR
schemes to use incremental preprocessing and show how it
significantly improves the throughput and reduces the latency
of applications where the database changes over time
more »
« less
- Award ID(s):
- 2045861
- PAR ID:
- 10312009
- Date Published:
- Journal Name:
- USENIX Security Symposium
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper develops a decision framework to automate the playbook for UAS traffic management (UTM) under uncertain environmental conditions based on spatiotemporal scenario data. Motivated by the traditional air traffic management (ATM) which uses the playbook to guide traffic using pre-validated routes under convective weather, the proposed UTM playbook leverages a database to store optimal UAS routes tagged with spatiotemporal wind scenarios to automate the UAS trajectory management. Our perspective is that the UASs, and many other modern systems, operate in spatiotemporally evolving environments, and similar spatiotemporal scenarios are tied with similar management decisions. Motivated by this feature, our automated playbook solution integrates the offline operations, online operations and a database to enable real-time UAS trajectory management decisions. The solution features the use of similarity between spatiotemporal scenarios to retrieve offline decisions as the initial solution for online fine tuning, which significantly shortens the online decision time. A fast query algorithm that exploits the correlation of spatiotemporal scenarios is utilized in the decision framework to quickly retrieve the best offline decisions. The online fine tuning adapts to trajectory deviations and subject to collision avoidance among UASs. The solution is demonstrated using simulation studies, and can be utilized in other applications, where quick decisions are desired and spatiotemporal environments play a crucial role in the decision process.more » « less
-
Private information retrieval (PIR) enables clients to query and retrieve data from untrusted servers without the untrusted servers learning which data was retrieved. In this paper, we present a new class of multi-server PIR protocols, which we call heterogeneous PIR (HPIR). In such multi-server PIR protocols, the computation and communication overheads imposed on the PIR servers are non-uniform, i.e., some servers handle higher computation/communication burdens than the others. This enables heterogeneous PIR protocols to be suitable for a range of new PIR applications. What enables us to enforce such heterogeneity is a unique PIR-tailored secret sharing algorithm that we leverage in building our PIR protocol. We have implemented our HPIR protocol and evaluated its performance in comparison with regular (i.e., homogenous) PIR protocols. Our evaluations demonstrate that a querying client can trade off the computation and communication loads of the (heterogeneous) PIR servers by adjusting some parameters. For example in a two-server scenario with a heterogeneity degree of 4/1, to retrieve a 456KB file from a 0.2GB database, the rich (i.e., resourceful) PIR server will do 1.1 seconds worth of computation compared to 0.3 seconds by the poor (resource-constrained) PIR server; this is while each of the servers would do the same 1 seconds of computation in a homogeneous setting. Also, for this given example, our HPIR protocol will impose a 912KB communication bandwidth on the rich server compared to 228KB on the poor server (by contrast to 456KB overheads on each of the servers for a traditional homogeneous design).more » « less
-
We will demonstrate a prototype query-processing engine, which utilizes correlations among predicates to accelerate machine learning (ML) inference queries on unstructured data. Expensive operators such as feature extractors and classifiers are deployed as user-defined functions (UDFs), which are not penetrable by classic query optimization techniques such as predicate push-down. Recent optimization schemes (e.g., Probabilistic Predicates or PP) build a cheap proxy model for each predicate offline, and inject proxy models in the front of expensive ML UDFs under the independence assumption in queries. Input records that do not satisfy query predicates are filtered early by proxy models to bypass ML UDFs. But enforcing the independence assumption may result in sub-optimal plans. We use correlative proxy models to better exploit predicate correlations and accelerate ML queries. We will demonstrate our query optimizer called CORE, which builds proxy models online, allocates parameters to each model, and reorders them. We will also show end-to-end query processing with or without proxy models.more » « less
-
Dunkelman, D. ; Dziembowski, S. (Ed.)We construct new private-information-retrieval protocols in the single-server setting. Our schemes allow a client to privately fetch a sequence of database records from a server, while the server answers each query in average time sublinear in the database size. Specifically, we introduce the first single-server private-information-retrieval schemes that have sublinear amortized server time, require sublinear additional storage, and allow the client to make her queries adaptively. Our protocols rely only on standard cryptographic assumptions (decision Diffie-Hellman, quadratic residuosity, learning with errors, etc.). They work by having the client first fetch a small “hint” about the database contents from the server. Generating this hint requires server time linear in the database size. Thereafter, the client can use the hint to make a bounded number of adaptive queries to the server, which the server answers in sublinear time—yielding sublinear amortized cost. Finally, we give lower bounds proving that our most efficient scheme is optimal with respect to the trade-off it achieves between server online time and client storage.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
