Syed Mahbub Hafiz (University of California, Davis), Chitrabhanu Gupta (University of California, Davis), Warren Wnuck (University of California, Davis), Brijesh Vora (University of California, Davis), Chen-Nee Chuah (University of California, Davis)

An essential part of ensuring privacy for internet service users is to protect what data they access so that the database host cannot infer sensitive information (e.g., political affiliation, sexual orientation, etc.) from the query pattern to exploit it or share it with third parties. Often, database users submit aggregate queries (e.g., SUM, MEAN, etc.) with searching and filtering constraints to extract statistically meaningful information from a database by seeking the privacy of its query's sensitive values and database interactions. Private information retrieval (PIR), a privacy-preserving cryptographic tool, solves a simplified version of this problem by hiding the database item that a client accesses. Most PIR protocols require the client to know the exact row index of the intended database item, which cannot support the complicated aggregation-based statistical query in a similar setting. Some works in the PIR space contain keyword searching and SQL-like queries, but most need multiple interactions between the PIR client and PIR servers. Some schemes support searching SQL-like expressive queries in a single round but fail to enable aggregate queries. These schemes are the main focus of this paper. To bridge the gap, we have built a general-purpose novel information-theoretic PIR (IT-PIR) framework that permits a user to fetch the aggregated result, hiding all sensitive sections of the complex query from the hosting PIR server in a single round of interaction. In other words, the server will not know which records contribute to the aggregation. We then evaluate the feasibility of our protocol for both benchmarking and real-world application settings. For instance, in a complex aggregate query to the Twitter microblogging database of $1$ million tweets, our protocol takes $0.014$ seconds for a PIR server to generate the result when the user is interested in one of ~$3k$ user handles. In contrast, for a much-simplified task, not an aggregate but a positional query, Goldberg's regular IT-PIR (Oakland 2007) takes $1.13$ seconds. For all possible user handles, $300k$, it takes equal time compared to the regular IT-PIR. This example shows that complicated aggregate queries through our framework do not incur additional overhead if not less, compared to the conventional query.

View More Papers

Certificate Transparency Revisited: The Public Inspections on Third-party Monitors

Aozhuo Sun (Institute of Information Engineering, Chinese Academy of Sciences), Jingqiang Lin (School of Cyber Science and Technology, University of Science and Technology of China), Wei Wang (Institute of Information Engineering, Chinese Academy of Sciences), Zeyan Liu (The University of Kansas), Bingyu Li (School of Cyber Science and Technology, Beihang University), Shushang Wen (School of…

Read More

Towards Precise Reporting of Cryptographic Misuses

Yikang Chen (The Chinese University of Hong Kong), Yibo Liu (Arizona State University), Ka Lok Wu (The Chinese University of Hong Kong), Duc V Le (Visa Research), Sze Yiu Chau (The Chinese University of Hong Kong)

Read More

The Impact of Workload on Phishing Susceptibility: An Experiment

Sijie Zhuo (University of Auckland), Robert Biddle (University of Auckland and Carleton University, Ottawa), Lucas Betts, Nalin Asanka Gamagedara Arachchilage, Yun Sing Koh, Danielle Lottridge, Giovanni Russello (University of Auckland)

Read More

Exploiting Diagnostic Protocol Vulnerabilities on Embedded Networks in Commercial...

Carson Green, Rik Chatterjee, Jeremy Daily (Colorado State University)

Read More