Finding Balance in Unbalanced PSI: A New Construction from Single-Server PIR
Authors
Chengyu Lin, Zeyu Liu, Peihan Miao, Max Tromanhauser
Abstract
Private set intersection (PSI) enables two parties to jointly compute the intersection of their private sets without revealing any extra information to each other. In this work, we focus on the unbalanced setting where one party (a powerful server) holds a significantly larger set than the other party (a resource-limited client). We present a new protocol for this setting that achieves a better balance between low client-side storage and efficient online processing.
We first formalize a general framework to transform Private Information Retrieval (PIR) into PSI with techniques used in prior works. Building upon recent advancements in Private Information Retrieval (PIR), specifically the SimplePIR construction (Henzinger et al., USENIX Security'23), combined with our tailored techniques, our construction shows a great improvement in online efficiency. Concretely, when the client holds a single element, our protocol achieves more than $100\times$ faster computation and over $4\times$ lower communication compared to the state-of-the-art unbalanced PSI based on leveled fully homomorphic encryption (Chen et al., CCS'21). The client-side storage is only in the order of tens of megabytes, even for a gigabyte-sized set on the server. Moreover, since the framework is generic, any future improvement in PIR can further improve our construction.
References
[ABFK16]
Carlos Aguilar-Melchor, Joris Barrier, Laurent Fousse, and Marc-Olivier Killijian. XPIR: Private Information Retrieval for Everyone. PoPETs, 2016(2):155–174, April 2016.
[ACLS18]
Sebastian Angel, Hao Chen, Kim Laine, and Srinath T. V. Setty. PIR with Compressed Queries and Amortized Query Processing. In 2018 IEEE Symposium on Security and Privacy, pages 962–979. May 2018. IEEE Computer Society Press. DOI: 10.1109/SP.2018.00062
[Ali18]
Junade Ali. Validating Leaked Passwords with k-Anonymity. https://blog.cloudflare.com/validating-leaked-passwords-with-k-anonymity/. 2018.
[ALP+21a]
Asra Ali, Tancrède Lepoint, Sarvar Patel, Mariana Raykova, Phillipp Schoppmann, Karn Seth, and Kevin Yeo. Communication-Computation Trade-offs in PIR. In Michael Bailey and Rachel Greenstadt, editors, USENIX Security 2021, pages 1811–1828. August 2021. USENIX Association.
[ALP+21b]
Asra Ali, Tancrède Lepoint, Sarvar Patel, Mariana Raykova, Phillipp Schoppmann, Karn Seth, and Kevin Yeo. Communication–Computation Trade-offs in PIR. In 30th USENIX Security Symposium (USENIX Security 21), pages 1811–1828. August 2021. USENIX Association.
[APP21]
Password Monitoring – Apple Platform Security. https://support.apple.com/en-al/guide/security/sec78e79fc3b/web. 2021.
[APS15]
Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology, 9(3):169–203, 2015. DOI: doi:10.1515/jmc-2015-0016
[BGV14]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3):1–36, 2014.
[BIM00]
Amos Beimel, Yuval Ishai, and Tal Malkin. Reducing the Servers Computation in Private Information Retrieval: PIR with Preprocessing. In Mihir Bellare, editor, CRYPTO 2000, volume 1880 of LNCS, pages 55–73. August 2000. Springer, Heidelberg. DOI: 10.1007/3-540-44598-6_4
[BIPW17]
Elette Boyle, Yuval Ishai, Rafael Pass, and Mary Wootters. Can We Access a Database Both Locally and Privately?. In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part II, volume 10678 of LNCS, pages 662–693. November 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-70503-3_22
[BPSW07]
Justin Brickell, Donald E. Porter, Vitaly Shmatikov, and Emmett Witchel. Privacy-preserving remote diagnostics. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson, editors, ACM CCS 2007, pages 498–507. October 2007. ACM Press. DOI: 10.1145/1315245.1315307
[Bra12]
Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical GapSVP. In Annual Cryptology Conference, pages 868–886. 2012. Springer.
[BV11]
Zvika Brakerski and Vinod Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In Rafail Ostrovsky, editor, 52nd FOCS, pages 97–106. October 2011. IEEE Computer Society Press. DOI: 10.1109/FOCS.2011.12
[CCF+20]
Justin Chan, Landon P. Cox, Dean P. Foster, Shyam Gollakota, Eric Horvitz, Joseph Jaeger, Sham M. Kakade, Tadayoshi Kohno, John Langford, Jonathan Larson, Puneet Sharma, Sudheesh Singanamalla, Jacob E. Sunshine, and Stefano Tessaro. PACT: Privacy-Sensitive Protocols And Mechanisms for Mobile Contact Tracing. IEEE Data Eng. Bull., 2020.
[CD24]
Sofía Celi and Alex Davidson. Call Me By My Name: Simple, Practical Private Information Retrieval for Keyword Queries. CCS'24. 2024.
[CGKS95]
Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private Information Retrieval. In 36th FOCS, pages 41–50. October 1995. IEEE Computer Society Press. DOI: 10.1109/SFCS.1995.492461
[CGN98]
Benny Chor, Niv Gilboa, and Moni Naor. Private Information Retrieval by Keywords. https://eprint.iacr.org/1998/003. Cryptology ePrint Archive, Report 1998/003. 1998.
[CHK22]
Henry Corrigan-Gibbs, Alexandra Henzinger, and Dmitry Kogan. Single-Server Private Information Retrieval with Sublinear Amortized Time. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part II, volume 13276 of LNCS, pages 3–33. 2022. Springer, Heidelberg. DOI: 10.1007/978-3-031-07085-3_1
[CHLR18]
Hao Chen, Zhicong Huang, Kim Laine, and Peter Rindal. Labeled PSI from Fully Homomorphic Encryption with Malicious Security. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018, pages 1223–1237. October 2018. ACM Press. DOI: 10.1145/3243734.3243836
[CHR17]
Ran Canetti, Justin Holmgren, and Silas Richelson. Towards Doubly Efficient Private Information Retrieval. In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part II, volume 10678 of LNCS, pages 694–726. November 2017. Springer, Heidelberg. DOI: 10.1007/978-3-319-70503-3_23
[CK20]
Henry Corrigan-Gibbs and Dmitry Kogan. Private Information Retrieval with Sublinear Online Time. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part I, volume 12105 of LNCS, pages 44–75. May 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-45721-1_3
[CLR17]
Hao Chen, Kim Laine, and Peter Rindal. Fast Private Set Intersection from Homomorphic Encryption. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 1243–1255. 2017. ACM Press. DOI: 10.1145/3133956.3134061
[CM20]
Melissa Chase and Peihan Miao. Private Set Intersection in the Internet Setting from Lightweight Oblivious PRF. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part III, volume 12172 of LNCS, pages 34–63. August 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-56877-1_2
[CMdG+21]
Kelong Cong, Radames Cruz Moreno, Mariana Botelho da Gama, Wei Dai, Ilia Iliashenko, Kim Laine, and Michael Rosenberg. Labeled PSI from Homomorphic Encryption with Reduced Computation and Communication. In Giovanni Vigna and Elaine Shi, editors, ACM CCS 2021, pages 1135–1150. November 2021. ACM Press. DOI: 10.1145/3460120.3484760
[CNCG+23]
Simone Colombo, Kirill Nikitin, Henry Corrigan-Gibbs, David J. Wu, and Bryan Ford. Authenticated private information retrieval. Usenix Security'23. 2023.
[DC14]
Changyu Dong and Liqun Chen. A Fast Single Server Private Information Retrieval Protocol with Low Communication Cost. In Miroslaw Kutylowski and Jaideep Vaidya, editors, ESORICS 2014, Part I, volume 8712 of LNCS, pages 380–399. September 2014. Springer, Heidelberg. DOI: 10.1007/978-3-319-11203-9_22
[dCL24]
Leo de Castro and Keewoo Lee. VeriSimplePIR: Verifiability in SimplePIR at No Online Cost for Honest Servers. Usenix Security'24. 2024.
[DM15]
Léo Ducas and Daniele Micciancio. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 617–640. April 2015. Springer, Heidelberg. DOI: 10.1007/978-3-662-46800-5_24
[DPC23]
Alex Davidson, Gonçalo Pestana, and Sofía Celi. FrodoPIR: Simple, Scalable, Single-Server Private Information Retrieval. PoPETs, 2023(1):365–383, January 2023. DOI: 10.56553/popets-2023-0022
[DRRT18]
Daniel Demmler, Peter Rindal, Mike Rosulek, and Ni Trieu. PIR-PSI: Scaling Private Contact Discovery. PoPETs, 2018(4):159–178, October 2018. DOI: 10.1515/popets-2018-0037
[FAKM14]
Bin Fan, Dave G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher. Cuckoo Filter: Practically Better Than Bloom. In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, pages 75–88, New York, NY, USA. 2014. Association for Computing Machinery. DOI: 10.1145/2674005.2674994
[FIPR05]
Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold. Keyword Search and Oblivious Pseudorandom Functions. In Joe Kilian, editor, TCC 2005, volume 3378 of LNCS, pages 303–324. February 2005. Springer, Heidelberg. DOI: 10.1007/978-3-540-30576-7_17
[FLLP24]
Ben Fisch, Arthur Lazzaretti, Zeyu Liu, and Charalampos Papamanthou. ThorPIR: Single Server PIR via Homomorphic Thorp Shuffles. In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, pages 1448–1462, New York, NY, USA. 2024. Association for Computing Machinery. DOI: 10.1145/3658644.3690326
[FV12]
Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Paper 2012/144. 2012.
[GH19]
Craig Gentry and Shai Halevi. Compressible FHE with Applications to PIR. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part II, volume 11892 of LNCS, pages 438–464. December 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-36033-7_17
[GLM16]
Matthew Green, Watson Ladd, and Ian Miers. A Protocol for Privately Reporting Ad Impressions at Scale. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 1591–1601. October 2016. ACM Press. DOI: 10.1145/2976749.2978407
[GPR+21]
Gayathri Garimella, Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. Oblivious Key-Value Stores and Amplification for Private Set Intersection. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part II, volume 12826 of LNCS, pages 395–425, Virtual Event. August 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-84245-1_14
[HFH99]
Bernardo A. Huberman, Matthew K. Franklin, and Tad Hogg. Enhancing privacy and trust in electronic communities. In Stuart I. Feldman and Michael P. Wellman, editors, Proceedings of the First ACM Conference on Electronic Commerce (EC-99), Denver, CO, USA, November 3-5, 1999, pages 78–86. 1999. ACM. DOI: 10.1145/336992.337012
[HHCG+23]
Alexandra Henzinger, Matthew M. Hong, Henry Corrigan-Gibbs, Sarah Meiklejohn, and Vinod Vaikuntanathan. One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval. In 32nd USENIX Security Symposium (USENIX Security 23), pages 3889–3905, Anaheim, CA. August 2023. USENIX Association.
[HL08]
Carmit Hazay and Yehuda Lindell. Efficient Protocols for Set Intersection and Pattern Matching with Security Against Malicious and Covert Adversaries. In Ran Canetti, editor, TCC 2008, volume 4948 of LNCS, pages 155–175. March 2008. Springer, Heidelberg. DOI: 10.1007/978-3-540-78524-8_10
[HSW23]
Laura Hetz, Thomas Schneider, and Christian Weinert. Scaling Mobile Private Contact Discovery toBillions of Users. In Computer Security – ESORICS 2023: 28th European Symposium on Research in Computer Security, The Hague, The Netherlands, September 25–29, 2023, Proceedings, Part I, pages 455–476, Berlin, Heidelberg. 2023. Springer-Verlag. DOI: 10.1007/978-3-031-50594-2_23
[HWS+21]
Christoph Hagen, Christian Weinert, Christoph Sendner, Alexandra Dmitrienko, and Thomas Schneider. All the Numbers are US: Large-scale Abuse of Contact Discovery in Mobile Messengers. In NDSS 2021. February 2021. The Internet Society.
[IKN+20]
Mihaela Ion, Ben Kreuter, Ahmet Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, Mariana Raykova, David Shanahan, and Moti Yung. On Deploying Secure Computing: Private Intersection-Sum-with-Cardinality. In IEEE European Symposium on Security and Privacy, EuroS&P 2020, Genoa, Italy, September 7-11, 2020, pages 370–389. 2020. IEEE. DOI: 10.1109/EuroSP48549.2020.00031
[JL10]
Stanislaw Jarecki and Xiaomin Liu. Fast Secure Computation of Set Intersection. In Juan A. Garay and Roberto De Prisco, editors, SCN 10, volume 6280 of LNCS, pages 418–435. September 2010. Springer, Heidelberg. DOI: 10.1007/978-3-642-15317-4_26
[KC21]
Dmitry Kogan and Henry Corrigan-Gibbs. Private Blocklist Lookups with Checklist. In Michael Bailey and Rachel Greenstadt, editors, USENIX Security 2021, pages 875–892. August 2021. USENIX Association.
[KKRT16]
Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. Efficient Batched Oblivious PRF with Applications to Private Set Intersection. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016, pages 818–829. October 2016. ACM Press. DOI: 10.1145/2976749.2978381
[KLL+15]
Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk, and Qiang Tang. Optimal Rate Private Information Retrieval from Homomorphic Encryption. PoPETs, 2015(2):222–243, April 2015. DOI: 10.1515/popets-2015-0016
[KLS+17]
Ágnes Kiss, Jian Liu, Thomas Schneider, N. Asokan, and Benny Pinkas. Private Set Intersection for Unequal Set Sizes with Mobile Applications. PoPETs, 2017(4):177–197, October 2017. DOI: 10.1515/popets-2017-0044
[KO97]
Eyal Kushilevitz and Rafail Ostrovsky. Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. In 38th FOCS, pages 364–373. October 1997. IEEE Computer Society Press. DOI: 10.1109/SFCS.1997.646125
[KRS+19]
Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, and Christian Weinert. Mobile Private Contact Discovery at Scale. In Nadia Heninger and Patrick Traynor, editors, USENIX Security 2019, pages 1447–1464. August 2019. USENIX Association.
[Lin16]
Yehuda Lindell. How To Simulate It - A Tutorial on the Simulation Proof Technique. Electron. Colloquium Comput. Complex., TR17, 2016. DOI: 10.1007/978-3-319-57048-8_6
[LKLM21]
Kristin Lauter, Sreekanth Kannepalli, Kim Laine, and Radames Cruz Moreno. Password monitor: Safeguarding passwords in microsoft edge. https://www.microsoft.com/en-us/research/blog/password-monitor-safeguarding-passwords-in-microsoft-edge/. 2021.
[LLM22]
Chengyu Lin, Zeyu Liu, and Tal Malkin. XSPIR: Efficient Symmetrically Private Information Retrieval from Ring-LWE. In Vijayalakshmi Atluri, Roberto Di Pietro, Christian Damsgaard Jensen, and Weizhi Meng, editors, ESORICS 2022, Part I, volume 13554 of LNCS, pages 217–236. September 2022. Springer, Heidelberg. DOI: 10.1007/978-3-031-17140-6_11
[LMP22]
Zeyu Liu, Daniele Micciancio, and Yuriy Polyakov. Large-Precision Homomorphic Sign Evaluation Using FHEW/TFHE Bootstrapping. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part II, volume 13792 of LNCS, pages 130–160. December 2022. Springer, Heidelberg. DOI: 10.1007/978-3-031-22966-4_5
[LMW23]
Wei-Kai Lin, Ethan Mook, and Daniel Wichs. Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 595–608, New York, NY, USA. 2023. Association for Computing Machinery. DOI: 10.1145/3564246.3585175
[LP22]
Arthur Lazzaretti and Charalampos Papamanthou. Near-Optimal Private Information Retrieval with Preprocessing. Cryptology ePrint Archive, Paper 2022/830. 2022.
[LP23]
Arthur Lazzaretti and Charalampos Papamanthou. TreePIR: Sublinear-Time and Polylog-Bandwidth Private Information Retrieval from DDH. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, pages 284–314, Cham. 2023. Springer Nature Switzerland. DOI: 10.1007/978-3-031-38545-2_10
[LPR+20]
Tancrède Lepoint, Sarvar Patel, Mariana Raykova, Karn Seth, and Ni Trieu. Private Join and Compute from PIR with Default. Cryptology ePrint Archive, Paper 2020/1011. 2020.
[Mar14]
Moxie Marlinspike. The Difficulty Of Private Contact Discovery. https://signal.org/blog/contact-discovery/. A company blog post (2014). 2014.
[MCR21]
Muhammad Haris Mughees, Hao Chen, and Ling Ren. OnionPIR: Response Efficient Single-Server PIR. In Giovanni Vigna and Elaine Shi, editors, ACM CCS 2021, pages 2292–2306. November 2021. ACM Press. DOI: 10.1145/3460120.3485381
[MPR+20]
Peihan Miao, Sarvar Patel, Mariana Raykova, Karn Seth, and Moti Yung. Two-Sided Malicious Security for Private Intersection-Sum with Cardinality. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part III, volume 12172 of LNCS, pages 3–33. August 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-56877-1_1
[MW22]
Samir Jordan Menon and David J. Wu. SPIRAL: Fast, High-Rate Single-Server PIR via FHE Composition. In 2022 IEEE Symposium on Security and Privacy, pages 930–947. May 2022. IEEE Computer Society Press. DOI: 10.1109/SP46214.2022.9833700
[NR97]
Moni Naor and Omer Reingold. Number-theoretic Constructions of Efficient Pseudo-random Functions. In 38th FOCS, pages 458–467. October 1997. IEEE Computer Society Press. DOI: 10.1109/SFCS.1997.646134
[OPPW23]
Hiroki Okada, Rachel Player, Simon Pohmann, and Christian Weinert. Towards Practical Doubly-Efficient Private Information Retrieval. Financial Cryptography and Data Security 2024. Cryptology ePrint Archive, Paper 2023/1510. 2023.
[PR04]
Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. J. Algorithms, 2004. DOI: 10.1016/j.jalgor.2003.12.002
[PRTY19]
Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. SpOT-Light: Lightweight Private Set Intersection from Sparse OT Extension. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part III, volume 11694 of LNCS, pages 401–431. August 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-26954-8_13
[PRTY20]
Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. PSI from PaXoS: Fast, Malicious Private Set Intersection. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part II, volume 12106 of LNCS, pages 739–767. May 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-45724-2_25
[PSSW09]
Benny Pinkas, Thomas Schneider, Nigel P. Smart, and Stephen C. Williams. Secure Two-Party Computation Is Practical. In Mitsuru Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 250–267. December 2009. Springer, Heidelberg. DOI: 10.1007/978-3-642-10366-7_15
[PSTY19]
Benny Pinkas, Thomas Schneider, Oleksandr Tkachenko, and Avishay Yanai. Efficient Circuit-Based PSI with Linear Communication. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part III, volume 11478 of LNCS, pages 122–153. May 2019. Springer, Heidelberg. DOI: 10.1007/978-3-030-17659-4_5
[PSWW18]
Benny Pinkas, Thomas Schneider, Christian Weinert, and Udi Wieder. Efficient Circuit-Based PSI via Cuckoo Hashing. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part III, volume 10822 of LNCS, pages 125–157. 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-78372-7_5
[PSY23]
Sarvar Patel, Joon Young Seo, and Kevin Yeo. Don’t be Dense: Efficient Keyword PIR for Sparse Databases. In 32nd USENIX Security Symposium (USENIX Security 23), pages 3853–3870, Anaheim, CA. August 2023. USENIX Association.
[PT20]
Jeongeun Park and Mehdi Tibouchi. SHECS-PIR: Somewhat Homomorphic Encryption-Based Compact and Scalable Private Information Retrieval. In Liqun Chen, Ninghui Li, Kaitai Liang, and Steve A. Schneider, editors, ESORICS 2020, Part II, volume 12309 of LNCS, pages 86–106. September 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-59013-0_5
[PVW08]
Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. A Framework for Efficient and Composable Oblivious Transfer. In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 554–571. August 2008. Springer, Heidelberg. DOI: 10.1007/978-3-540-85174-5_31
[RA18]
Amanda C. Davi Resende and Diego F. Aranha. Faster Unbalanced Private Set Intersection. In Sarah Meiklejohn and Kazue Sako, editors, FC 2018, volume 10957 of LNCS, pages 203–221. 2018. Springer, Heidelberg. DOI: 10.1007/978-3-662-58387-6_11
[RR17]
Peter Rindal and Mike Rosulek. Malicious-Secure Private Set Intersection via Dual Execution. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017, pages 1229–1242. 2017. ACM Press. DOI: 10.1145/3133956.3134044
[RS21]
Peter Rindal and Phillipp Schoppmann. VOLE-PSI: Fast OPRF and Circuit-PSI from Vector-OLE. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part II, volume 12697 of LNCS, pages 901–930. October 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-77886-6_31
[SACM21]
Elaine Shi, Waqar Aqeel, Balakrishnan Chandrasekaran, and Bruce M. Maggs. Puncturable Pseudorandom Sets and Private Information Retrieval with Near-Optimal Online Bandwidth and Time. In Tal Malkin and Chris Peikert, editors, CRYPTO 2021, Part IV, volume 12828 of LNCS, pages 641–669, Virtual Event. August 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-84259-8_22
[TKC07]
Juan Ramón Troncoso-Pastoriza, Stefan Katzenbeisser, and Mehmet Celik. Privacy preserving error resilient dna searching through oblivious automata. In Peng Ning, Sabrina De Capitani di Vimercati, and Paul F. Syverson, editors, ACM CCS 2007, pages 519–528. October 2007. ACM Press. DOI: 10.1145/1315245.1315309
[TPY+19]
Kurt Thomas, Jennifer Pullman, Kevin Yeo, Ananth Raghunathan, Patrick Gage Kelley, Luca Invernizzi, Borbala Benko, Tadek Pietraszek, Sarvar Patel, Dan Boneh, and Elie Bursztein. Protecting accounts from credential stuffing with password breach alerting. In Proceedings of the 28th USENIX Conference on Security Symposium, pages 1555–1571, USA. 2019. USENIX Association.
[TSS+20]
Ni Trieu, Kareem Shehata, Prateek Saxena, Reza Shokri, and Dawn Song. Epione: Lightweight Contact Tracing with Strong Privacy. IEEE Data Eng. Bull., 2020.
[Yao86]
Andrew Chi-Chih Yao. How to Generate and Exchange Secrets (Extended Abstract). In 27th FOCS, pages 162–167. October 1986. IEEE Computer Society Press. DOI: 10.1109/SFCS.1986.25
[ZLTS23]
Mingxun Zhou, Wei-Kai Lin, Yiannis Tselekounis, and Elaine Shi. Optimal Single-Server Private Information Retrieval. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part I, volume 14004 of LNCS, pages 395–425. April 2023. Springer, Heidelberg. DOI: 10.1007/978-3-031-30545-0_14
[ZPSZ23]
Mingxun Zhou, Andrew Park, Elaine Shi, and Wenting Zheng. Piano: Extremely Simple, Single-Server PIR with Sublinear Server Computation. Cryptology ePrint Archive, Paper 2023/452. 2023.
PDF
History
Submitted: 2025-01-13
Accepted: 2025-03-11
Published: 2025-04-08
Accepted: 2025-03-11
Published: 2025-04-08
How to cite
Chengyu Lin, Zeyu Liu, Peihan Miao, and Max Tromanhauser, Finding Balance in Unbalanced PSI: A New Construction from Single-Server PIR. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/angy4fvtw.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.