Femur: A Flexible Framework for Fast and Secure Querying from Public Key-Value Store DOI: XXXXXXX.XXXXXXX Conference: 2025 ACM SIGMOD/PODS Conferences; June 22-27; Berlin, Germany

Jiaoyi Zhang, Liqiang Peng, Mo Sha, Weiran Liu, Xiang Li, Sheng Wang, Feifei Li, Mingyu Gao, Huanchen Zhang · 2025

Read Femur: A Flexible Framework for Fast and Secure Querying from Public Key-Value Store DOI: XXXXXXX.XXXXXXX Conference: 2025 ACM SIGMOD/PODS Conferences; June 22-27; Berlin, Germany by Jiaoyi Zhang, Liqiang Peng, Mo Sha, Weiran Liu, Xiang Li, Sheng Wang, Feifei Li, Mingyu Gao, Huanchen Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-05376.txt.

Introduction

Jiaoyi Zhang and co-authors present Femur, a framework for fast and secure queries to a public key-value store. Their 2025 paper starts from a privacy need: user query data must be protected when a public database is accessed.

Private information retrieval gives full security but scales poorly. The authors argue that many users would rather set their own privacy level, guided by theory, and trade some security for speed. They define distance-based indistinguishability to give provable guarantees for such relaxed settings. Femur then uses that idea to query public stores with flexible trade-offs. The design aims at large-scale use where full private retrieval is too slow.

Catalog record

CREATORJiaoyi Zhang, Liqiang Peng, Mo Sha, Weiran Liu, Xiang Li, Sheng Wang, Feifei Li, Mingyu Gao, Huanchen Zhang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE88 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-05376

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Femur: A Flexible Framework for Fast and Secure Querying from Public Key-Value Store DOI: XXXXXXX.XXXXXXX Conference: 2025 ACM SIGMOD/PODS Conferences; June 22-27; Berlin, Germany Jiaoyi Zhang, Liqiang Peng, Mo Sha, Weiran Liu, Xiang Li, Sheng Wang, Feifei Li, Mingyu Gao, Huanchen Zhang Abstract . With increasing demands for privacy, it becomes necessary to protect sensitive user query data when accessing public key-value databases. Existing Private Information Retrieval (PIR) schemes provide full security but suffer from poor scalability, limiting their applicability in large-scale deployment. We argue that in many real-world scenarios, a more practical solution should allow users to flexibly determine the privacy levels of their queries in a theoretically guided way, balancing security and performance based on specific needs. To formally provide provable guarantees, we introduce a novel concept of distance-based indistinguishability, which can facilitate users to comfortably relax their security requirements. We then design Femur, an efficient framework to securely query public key-value stores with flexible security and performance trade-offs. It uses a space-efficient learned index to convert query keys into storage locations, obfuscates these locations with extra noise provably derived by the distance-based indistinguishability theory, and sends the expanded range to the server. The server then adaptively utilizes the best scheme to retrieve data. We also propose a novel variable-range PIR scheme optimized for bandwidth-constrained environments. Experiments show that Femur outperforms the state-of-the-art designs even when ensuring the same full security level. When users are willing to relax their privacy requirements, Femur can further improve the performance gains to up to 163.9 × \times , demonstrating an effective trade-off between security and performance. 1. Introduction The growing data volumes and pervasive cloud services have spurred efforts to protect user data privacy. Protecting user queries to public datasets is as critical as protecting the underlying database. For example, users checking phone numbers against a public scam database are vested in keeping the numbers private to the hosting server. Similarly, users querying sensitive health or financial data risk potential discrimination (e.g., biased treatment in insurance or employment) if their queries are revealed. These use cases highlight the need for secure and efficient query mechanisms for accessing public key-value stores while keeping queries confidential. Private Information Retrieval (PIR) schemes ( Chor et al. 1997 ; Menon and Wu 2022 ; Mughees et al. 2021 ; Melchor et al. 2016 ; Corrigan-Gibbs and Kogan 2020 ; Kogan and Corrigan-Gibbs 2021 ; Henzinger et al. 2023b ) have emerged to address the above concerns. They allow users to upload encrypted keys for confidential server-side computation and results return without decryption. The entire process ensures that sensitive information remains secure. Despite advancements in PIR techniques—such as improvements in cryptographic protocols ( Davidson et al. 2023 ; Gentry 2009 ; Brakerski et al. 2014 ; Mahdavi and Kerschbaum 2022 ; Ahmad et al. 2022 ) , encoding strategies ( Angel et al. 2018 ) , and pre-processing optimizations ( Davidson et al. 2023 ; Chen et al. 2017 ; Celi and Davidson 2024 ; Zhou et al. 2024 ) —they still face challenges with scaling. To guarantee query path privacy, most designs must process all the n key-value pairs in the database with up to O(n) complexity, leading to high query response time in large-scale applications. For example, Pantheon ( Ahmad et al. 2022 ) takes 1.15 seconds to execute a query on only 65,536 key-value pairs. In this paper, we propose a more practical solution that relaxes security while upholding theoretical guarantees. Existing PIR schemes yield impractical processing times for large real-world datasets, with delays ranging from seconds to hours (Pantheon ( Ahmad et al. 2022 ) takes over 2 hours on 2^{24} records). Moreover, full dataset obfuscation may not be necessary in many applications. For example, an American user may only need to hide their queries within the U.S. phone numbers rather than the global dataset. In fact, industry practices often relax security by using hash functions ( Heinrich et al. 2021 ) to partition datasets into smaller buckets to improve query performance by reducing the number of key-value pairs involved per query. However, this method lacks formal security guarantees: the bucket IDs are exposed during computation, and an uneven hash partition could produce single-pair buckets, thus revealing the user’s query. We introduce Femur, a framework enabling users to control and balance performance and privacy with theoretical security guarantees. Femur allows users to configure from no security to full security backed by our formal definition of “relaxed security” (i.e., distance-based indistinguishability ). Depending on the chosen level, Femur’s user-side module automatically sends an obfuscated range of keys (including the user’s real key) to the server, ensuring that the real key is indistinguishable under the relaxed security level without unnecessary performance loss. When this key range extends to the entire database, Femur achieves full privacy as before. Femur consists of three main components: key-to-position conversion, obfuscated range generation, and adaptive key-value retrieval. First, the user-side key-to-position conversion module maps query keys to their storage locations within the database, similar to existing keyword PIR schemes. The novelty lies in that we use the PGM-index ( Ferragina and Vinciguerra 2020 ) , a state-of-the-art, space-efficient learned index for the mapping. The prediction error of PGM-index can be handled together with the obfuscated query range. Learned indexes are typically faster and smaller than traditional indexes (e.g., B+trees) and can therefore speed up the conversion while significantly reducing the index size stored on the client side. Second, the obfuscated range generation module adds noise to the range predicted by the PGM-index before sending it to the server so that the server-side computation is confined to the key-value pairs within the range. This obfuscated range satisfies distance-based indistinguishability with a user-specified security level guaranteed by our theory. The higher the security level, the slower the query. Third, the server-side adaptive key-value retrieval module employs a cost model to choose the best strategy, trading between computation and network bandwidth. For high-bandwidth networks, the client side downloads all key-value pairs in the obfuscated range (of length s ) in plaintext. This approach conceals the query key without homomorphic computation but incurs O(s) transmission complexity. When the bandwidth is limited, we propose a novel variable-range PIR scheme with a transmission complexity of O(1) but a computation complexity of O(s) . Our experiments show that Femur scales well on a dataset containing 200 million records (a size infeasible for previous solutions) and outperforms the two baselines (Chalamet ( Celi and Davidson 2024 ) and Pantheon ( Ahmad et al. 2022 ) ) by 1.05 \times and 7.71 \times , respectively under full security, and by 163.9 \times and 1206.1 \times , respectively with a relaxed security guarantee. Additionally, Femur’s offline initialization phase only takes a few minutes, compared to several hours from previous designs. We also integrated Femur into Redis ( red 2009 ) , a popular in-memory key-value store, and demonstrated that Femur also supports efficient value updates in real-world scenarios. We make the following contributions. • We identify that full security prevents current PIR schemes from scaling and is often unnecessary in real-world applications. • We introduce relaxed security by formally defining “distance-based indistinguishability” to allow users to trade between performance

Read the complete text