DPF-PIR: a scheme of feasible two-server keyword PIR with logarithmic communication

Abstract

Private information retrieval (PIR) allows a client to privately request a block of data from a database such that no information about the queried block is revealed to the database owner. With the rapid rise of cloud computing, data is often shared across multiple servers, making multi-server PIR a promising privacy-enhancing technology. As the demand for faster keyword PIR protocols increases, current single-server PIR schemes suffer from significant computational and communication costs, while two-server PIR schemes demonstrate superior performance in this regard. In this paper, we address the problem of the keyword PIR against some adversary who can corrupt at most one party in our protocols in the semi-honest setting. A feasible two-server scheme DPF-PIR is presented, inspired by the original employment of the distributed point function. Without the need of downloading some “hint” about the database, DPF-PIR can achieve similar throughput results with the state-of-the-art single-server scheme, SimplePIR, and 25.5× faster than previous schemes. Meanwhile, the communication cost of DPF-PIR, which exhibits logarithmic complexity, is significantly lower compared to other schemes; for example, it is less than 2% of the communication cost of SimplePIR. We also present a variant of our scheme, PDPF-PIR, rendering the non-collusion assumption more acceptable in practice. Despite the decreased throughput due to heavier computational costs, PDPF-PIR is still at least 2× faster than previous single-server schemes.

Graphical abstract

Keywords

private information retrieval / ditributed point function / secure multi-party computation

References

[1] Ahmad I, Yang Y, Agrawal D, El Abbadi A, Gupta T. Addra: metadata-private voice communication over fully untrusted infrastructure. In: Proceedings of the 15th USENIX Symposium on Operating Systems Design and Implementation. 2021, 313−329

[2] Mughees M H, Chen H, Ren L. OnionPIR: response efficient single-server PIR. In: Proceedings of 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021, 2292−2306

[3] Hafiz S M, Henry R . A bit more than a bit is more than a bit better: faster (essentially) optimal-rate many-server PIR. Proceedings on Privacy Enhancing Technologies, 2019, 2019( 1): 112–131

[4] Chor B, Kushilevitz E, Goldreich O, Sudan M . Private information retrieval. Journal of the ACM, 1998, 45( 6): 965–981

[5] Goldreich O. Foundations of Cryptography - Volume 2: Basic Applications. Cambridge: Cambridge University Press, 2004

[6] Kushilevitz E, Ostrovsky R. Replication is not needed: single database, computationally-private information retrieval. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science. 1997, 364−373

[7] Mayberry T, Blass E O, Chan A H. Efficient private file retrieval by combining ORAM and PIR. In: Proceedings of the 21st Annual Network and Distributed System Security Symposium. 2014

[8] Gilboa N, Ishai Y. Distributed point functions and their applications. In: Proceedings of the 33rd Annual International Conference on the Advances in Cryptology. 2014, 640−658

[9] Boyle E, Gilboa N, Ishai Y. Function secret sharing: improvements and extensions. In: Proceedings of 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016, 1292−1303

[10] Boyle E, Gilboa N, Ishai Y, Kolobov V I. Programmable distributed point functions. In: Proceedings of the 42nd Annual International Cryptology Conference on Advances in Cryptology. 2022, 121−151

[11] Demmler D, Rindal P, Rosulek M, Trieu N . PIR-PSI: scaling private contact discovery. Proceedings on Privacy Enhancing Technologies, 2018, 2018( 4): 159–178

[12] Dauterman E, Feng E, Luo E, Popa R A, Stoica I. DORY: an encrypted search system with distributed trust. In: Proceedings of the 14th USENIX Conference on Operating Systems Design and Implementation. 2020, 62

[13] Doerner J, Shelat A. Scaling ORAM for secure computation. In: Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 523−535

[14] Servan-Schreiber S, Hogan K, Devadas S. AdVeil: a private targeted advertising ecosystem. Cryptology ePrint Archive, 2021

[15] Boneh D, Lewi K, Wu D J. Constraining pseudorandom functions privately. In: Proceedings of the 20th IACR International Conference on Practice and Theory in Public-Key Cryptography. 2017, 494−524

[16] Boneh D, Kim S, Montgomery H. Private puncturable PRFs from standard lattice assumptions. In: Proceedings of the 36th Annual International Conference on Advances in Cryptology. 2017, 415−445

[17] Boneh D, Waters B. Constrained pseudorandom functions and their applications. In: Proceedings of the 19th International Conference on Advances in Cryptology. 2013, 280−300

[18] Kiayias A, Papadopoulos S, Triandopoulos N, Zacharias T. Delegatable pseudorandom functions and applications. In: Proceedings of 2013 ACM SIGSAC Conference on Computer & Communications Security. 2013, 669−684

[19] Kirsch A, Mitzenmacher M, Wieder U . More robust hashing: cuckoo hashing with a stash. SIAM Journal on Computing, 2010, 39( 4): 1543–1561

[20] Li X, Andersen D G, Kaminsky M, Freedman M J. Algorithmic improvements for fast concurrent cuckoo hashing. In: Proceedings of the 9th European Conference on Computer Systems. 2014, 27

[21] Pinkas B, Schneider T, Zohner M . Scalable private set intersection based on OT extension. ACM Transactions on Privacy and Security, 2018, 21( 2): 1–35

[22] Kolesnikov V, Kumaresan R, Rosulek M, Trieu N. Efficient batched oblivious PRF with applications to private set intersection. In: Proceedings of 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016, 818−829

[23] bo-hub. Puncturable_PRF. See Github.com/bo-hub/Puncturable_PRF website, 2021

[24] Angel S, Chen H, Laine K, Setty S. PIR with compressed queries and amortized query processing. In: Proceedings of the IEEE Symposium on Security and Privacy. 2018, 962−979

[25] Lueks W, Goldberg I. Sublinear scaling for multi-client private information retrieval. In: Proceedings of the 19th International Conference on Financial Cryptography and Data Security. 2015, 168−186

[26] Boyle E, Ishai Y, Pass R, Wootters M. Can we access a database both locally and privately? In: Proceedings of the 15th International Conference on Theory of Cryptography. 2017, 662−693

[27] Zhou J, Ross K A. Implementing database operations using SIMD instructions. In: Proceedings of 2002 ACM SIGMOD International Conference on Management of Data. 2002, 145−156

[28] Nuzman D, Rosen I, Zaks A . Auto-vectorization of interleaved data for SIMD. ACM SIGPLAN Notices, 2006, 41( 6): 132–143

[29] Jeong H, Kim S, Lee W, Myung S H. Performance of SSE and AVX instruction sets. 2012, arXiv preprint arXiv: 1211.0820

[30] Lim R, Lee Y, Kim R, Choi J . An implementation of matrix–matrix multiplication on the Intel KNL processor with AVX-512. Cluster Computing, 2018, 21( 4): 1785–1795

[31] Aguilar-Melchor C, Barrier J, Fousse L, Killijian M O . XPIR: private information retrieval for everyone. Proceedings on Privacy Enhancing Technologies, 2016, 2016( 2): 155–174

[32] Menon S J, Wu D J. SPIRAL: fast, high-rate single-server PIR via FHE composition. In: Proceedings of the IEEE Symposium on Security and Privacy. 2022, 930−947

[33] Cao Q, Tran H, Dau S H, Yi X, Viterbo E, Feng C, Huang Y, Zhu J, Kruglik S, Kiah H M. Committed private information retrieval. In: Proceedings of the 28th European Symposium on Computer Security. 2024, 393−413

[34] de Castro L, Polychroniadou A. Lightweight, maliciously secure verifiable function secret sharing. In: Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2022, 150−179

[35] Kruglik S, Dau S H, Kiah H M, Wang H, Zhang L F. Verifiable information-theoretic function secret sharing. Cryptology ePrint Archive, 2024

[36] Beimel A, Stahl Y . Robust information-theoretic private information retrieval. Journal of Cryptology, 2007, 20( 3): 295–321

[37] Devet C, Goldberg I, Heninger N. Optimally robust private information retrieval. In: Proceedings of the 21th USENIX Conference on Security Symposium. 2012, 269−283

[38] Goldberg I. Improving the robustness of private information retrieval. In: Proceedings of 2007 IEEE Symposium on Security and Privacy. 2007, 131−148

[39] Bunn P, Kushilevitz E, Ostrovsky R. CNF-FSS and its applications. In: Proceedings of the 25th IACR International Conference on Practice and Theory of Public-Key Cryptography. 2022, 283−314

[40] Park A, Leong T, Maturana F, Zheng W, Rashmi K V. Communication-efficient, fault tolerant PIR over erasure coded storage. In: Proceedings of the IEEE Symposium on Security and Privacy. 2024, 4331−4347

[41] Demmler D, Herzberg A, Schneider T. RAID-PIR: practical multi-server PIR. In: Proceedings of the 6th Edition of the ACM Workshop on Cloud Computing Security. 2014, 45−56

[42] Eskandarian S, Corrigan-Gibbs H, Zaharia M, Boneh D. Express: lowering the cost of metadata-hiding communication with cryptographic privacy. In: Proceedings of the 30th USENIX Security Symposium. 2021, 1775−1792

[43] Wang F, Yun C, Goldwasser S, Vaikuntanathan V, Zaharia M. Splinter: practical private queries on public data. In: Proceedings of the 14th USENIX Symposium on Networked Systems Design and Implementation. 2017, 299−313

[44] Falk B H, Lu S, Ostrovsky R. DURASIFT: a robust, decentralized, encrypted database supporting private searches with complex policy controls. In: Proceedings of the 18th ACM Workshop on Privacy in the Electronic Society. 2019, 26−36

[45] Corrigan-Gibbs H, Boneh D, Mazieres D. Riposte: an anonymous messaging system handling millions of users. In: Proceedings of the IEEE Symposium on Security and Privacy. 2015, 321−338

RIGHTS & PERMISSIONS

Higher Education Press