Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/3470496.3527433acmconferencesArticle/Chapter ViewAbstractPublication PagesiscaConference Proceedingsconference-collections
research-article
Open access

INSPIRE: in-storage private information retrieval via protocol and architecture co-design

Published: 11 June 2022 Publication History

Abstract

Private Information Retrieval (PIR) plays a vital role in secure, database-centric applications. However, existing PIR protocols explore a massive working space containing hundreds of GiBs of query and database data. As a consequence, PIR performance is severely bounded by storage communication, making it far from practical for real-world deployment.
In this work, we describe INSPIRE, an accelerator for IN-Storage Private Information REtrieval. INSPIRE follows a protocol and architecture co-design approach. We first design the INSPIRE protocol with a multi-stage filtering mechanism, which achieves a constant PIR query size. For a 1-billion-entry database of size 288GiB, INSPIRE's protocol reduces the query size from 27GiB to 3.6MiB. Further, we propose the INSPIRE hardware, a heterogeneous in-storage architecture, which integrates our protocol across the SSD hierarchy. Together with the INSPIRE protocol, the INSPIRE hardware reduces the query time from 28.4min to 36s, relative to the the state-of-the-art FastPIR scheme.

References

[1]
Ishtiyaque Ahmad, Yuntian Yang, Divyakant Agrawal, Amr El Abbadi, and Trinabh Gupta. 2021. Addra: Metadata-private voice communication over fully untrusted infrastructure. In USENIX Symposium on Operating Systems Design and Implementation (OSDI).
[2]
Junwhan Ahn, Sungpack Hong, Sungjoo Yoo, Onur Mutlu, and Kiyoung Choi. 2015. A scalable processing-in-memory accelerator for parallel graph processing. In Annual International Symposium on Computer Architecture. 105--117.
[3]
Martin R Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin E Lauter, et al. 2019. Homomorphic Encryption Standard. IACR Cryptol. ePrint Arch. 2019 (2019), 939.
[4]
Sebastian Angel, Hao Chen, Kim Laine, and Srinath Setty. 2018. PIR with compressed queries and amortized query processing. In IEEE symposium on security and privacy (SP). 962--979.
[5]
Sebastian Angel and Srinath Setty. 2016. Unobservable communication over fully untrusted infrastructure. In USENIX Symposium on Operating Systems Design and Implementation (OSDI). 551--569.
[6]
Hadi Asghari-Moghaddam, Young Hoon Son, Jung Ho Ahn, and Nam Sung Kim. 2016. Chameleon: Versatile and practical near-DRAM acceleration architecture for large memory systems. In IEEE/ACM international symposium on Microarchitecture (MICRO). IEEE, 1--13.
[7]
Amos Beimel, Yuval Ishai, Eyal Kushilevitz, and J-F Raymond. 2002. Breaking the O(n/sup 1/(2k-1)/) barrier for information-theoretic private information retrieval. In IEEE Symposium on Foundations of Computer Science. IEEE, 261--270.
[8]
Amos Beimel, Yuval Ishai, and Tal Malkin. 2000. Reducing the servers computation in private information retrieval: PIR with preprocessing. In Annual International Cryptology Conference. Springer, 55--73.
[9]
Zvika Brakerski. 2012. Fully homomorphic encryption without modulus switching from classical GapSVP. In Annual Cryptology Conference. Springer, 868--886.
[10]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2014. (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT) 6, 3 (2014), 1--36.
[11]
Yan-Cheng Chang. 2004. Single database private information retrieval with logarithmic communication. In Australasian Conference on Information Security and Privacy. Springer, 50--61.
[12]
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2017. Homomorphic encryption for arithmetic of approximate numbers. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 409--437.
[13]
Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. 1995. Private information retrieval. In IEEE Annual Foundations of Computer Science. 41--50.
[14]
Daniel Demmler, Amir Herzberg, and Thomas Schneider. 2014. RAID-PIR: Practical multi-server pir. In ACM Workshop on Cloud Computing Security. 45--56.
[15]
Casey Devet, Ian Goldberg, and Nadia Heninger. 2012. Optimally robust private information retrieval. In USENIX Security Symposium (SEC). 269--283.
[16]
Jaeyoung Do, Yang-Suk Kee, Jignesh M Patel, Chanik Park, Kwanghyun Park, and David J DeWitt. 2013. Query processing on smart SSDs: Opportunities and challenges. In ACM SIGMOD International Conference on Management of Data. 1221--1230.
[17]
Changyu Dong and Liqun Chen. 2014. A fast single server private information retrieval protocol with low communication cost. In European symposium on research in computer security. Springer, 380--399.
[18]
Junfeng Fan and Frederik Vercauteren. 2012. Somewhat practical fully homomorphic encryption. IACR Cryptol. ePrint Arch. (2012).
[19]
Harvey L Garner. 1959. The residue number system. In Papers presented at the the March 3--5, 1959, western joint computer conference. 146--153.
[20]
Craig Gentry. 2009. A fully homomorphic encryption scheme. Stanford university.
[21]
Matthew Green, Watson Ladd, and Ian Miers. 2016. A protocol for privately reporting ad impressions at scale. In ACM SIGSAC Conference on Computer and Communications Security (CCS). 1591--1601.
[22]
Peng Gu, Xinfeng Xie, Shuangchen Li, Dimin Niu, Hongzhong Zheng, Krishna T Malladi, and Yuan Xie. 2020. DLUX: a LUT-based Near-Bank Accelerator for Data Center Deep Learning Training Workloads. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2020).
[23]
Trinabh Gupta, Natacha Crooks, Whitney Mulhern, Srinath Setty, Lorenzo Alvisi, and Michael Walfish. 2016. Scalable and private media consumption with Popcorn. In USENIX Symposium on Networked Systems Design and Implementation (NSDI). 91--107.
[24]
Ryan Henry, Femi Olumofin, and Ian Goldberg. 2011. Practical PIR for electronic commerce. In ACM SIGSAC Conference on Computer and communications security (CCS). 677--690.
[25]
Jonmichael Hands 2021. Endurance of NVMe, SAS, and SATA SSDs. snia.org/sites/default/files/SSSI/NVMe_SAS_SATA_Endurance_White_Paper.pdf.
[26]
Yangwook Kang, Yang-suk Kee, Ethan L Miller, and Chanik Park. 2013. Enabling cost-effective data processing with smart SSD. In 2013 IEEE 29th symposium on mass storage systems and technologies (MSST). IEEE, 1--12.
[27]
Roman Kaplan, Leonid Yavits, and Ran Ginosar. 2018. Prins: Processing-in-storage acceleration of machine learning. IEEE Transactions on Nanotechnology 17, 5 (2018), 889--896.
[28]
Chad D Kersey, Hyesoon Kim, and Sudhakar Yalamanchili. 2017. Lightweight SIMT core designs for intelligent 3D stacked DRAM. In Proceedings of the International Symposium on Memory Systems. 49--59.
[29]
Aggelos Kiayias, Nikos Leonardos, Helger Lipmaa, Kateryna Pavlyk, and Qiang Tang. 2015. Optimal Rate Private Information Retrieval from Homomorphic Encryption. Privacy Enhancing Technologies 2015, 2 (2015), 222--243.
[30]
Gwangsun Kim, Niladrish Chatterjee, Mike O'Connor, and Kevin Hsieh. 2017. Toward standardized near-data processing with unrestricted data placement for GPUs. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. 1--12.
[31]
Shine Kim, Yunho Jin, Gina Sohn, Jonghyun Bae, Tae Jun Ham, and Jae W Lee. 2021. Behemoth: A Flash-centric Training Accelerator for Extreme-scale DNNs. In USENIX Conference on File and Storage Technologies (FAST). 371--385.
[32]
Albert Hyukjae Kwon, David Lazar, Srinivas Devadas, and Bryan Ford. 2015. Riffle: An efficient communication system with strong anonymity. (2015).
[33]
Young-Cheon Kwon, Suk Han Lee, Jaehoon Lee, Sang-Hyuk Kwon, Je Min Ryu, Jong-Pil Son, O Seongil, Hak-Soo Yu, Haesuk Lee, Soo Young Kim, Youngmin Cho, Jin Guk Kim, Jongyoon Choi, Hyun-Sung Shin, Jin Kim, BengSeng Phuah, HyoungMin Kim, Myeong Jun Song, Ahn Choi, Daeho Kim, SooYoung Kim, Eun-Bong Kim, David Wang, Shinhaeng Kang, Yuhwan Ro, Seungwoo Seo, JoonHo Song, Jaeyoun Youn, Kyomin Sohn, and NamSung Kim. 2021. 25.4 A20nm6GB Function-In-Memory DRAM, Based on HBM2 with a 1.2TFLOPS Programmable Computing Unit Using Bank-Level Parallelism, for Machine Learning Applications. In IEEE International Solid- State Circuits Conference (ISSCC), Vol. 64. 350--352.
[34]
Jinho Lee, Heesu Kim, Sungjoo Yoo, Kiyoung Choi, H Peter Hofstee, Gi-Joon Nam, Mark R Nutter, and Damir Jamsek. 2017. Extrav: boosting graph processing near storage with a coherent accelerator. Proceedings of the VLDB Endowment 10, 12 (2017), 1706--1717.
[35]
Feifei Li. 2019. Cloud-Native Database Systems at Alibaba: Opportunities and Challenges. Proc. VLDB Endow. 12, 12 (Aug. 2019), 2263--2272.
[36]
Jilan Lin, Shuangchen Li, Yufei Ding, and Yuan Xie. 2021. Overcoming the Memory Hierarchy Inefficiencies in Graph Processing Applications. In 2021 IEEE/ACM International Conference On Computer Aided Design (ICCAD). IEEE, 1--9.
[37]
Helger Lipmaa. 2005. An oblivious transfer protocol with log-squared communication. In International Conference on Information Security. Springer, 314--328.
[38]
Liu Liu, Jilan Lin, Zheng Qu, Yufei Ding, and Yuan Xie. 2021. ENMC: Extreme Near-Memory Classification via Approximate Screening. In MICRO-54: 54th Annual IEEE/ACM International Symposium on Microarchitecture. 1309--1322.
[39]
Travis Mayberry, Erik-Oliver Blass, and Agnes Hui Chan. 2014. Efficient Private File Retrieval by Combining ORAM and PIR. In NDSS. Citeseer.
[40]
Carlos Aguilar Melchor, Joris Barrier, Laurent Fousse, and Marc-Olivier Killijian. 2016. XPIR: Private information retrieval for everyone. Proceedings on Privacy Enhancing Technologies 2016 (2016), 155--174.
[41]
Coskun Mermer, Donglok Kim, and Yongmin Kim. 2003. Efficient 2D FFT implementation on mediaprocessors. Parallel Comput. 29, 6 (2003), 691--709.
[42]
Ahmet Can Mert, Erdinç Öztürk, and Erkay Savaş. 2019. Design and implementation of a fast and scalable NTT-based polynomial multiplier architecture. In 2019 22nd Euromicro Conference on Digital System Design (DSD). IEEE, 253--260.
[43]
Vincent Migliore, Maria Mendez Real, Vianney Lapotre, Arnaud Tisserand, Caroline Fontaine, and Guy Gogniat. 2016. Hardware/software co-design of an accelerator for FV homomorphic encryption scheme using Karatsuba algorithm. IEEE Trans. Comput. 67, 3 (2016), 335--347.
[44]
Prateek Mittal, Femi G Olumofin, Carmela Troncoso, Nikita Borisov, and Ian Goldberg. 2011. PIR-Tor: Scalable Anonymous Communication Using Private Information Retrieval. In USENIX Security Symposium (SEC).
[45]
Peter L Montgomery. 1985. Modular multiplication without trial division. Mathematics of computation 44, 170 (1985), 519--521.
[46]
Lifeng Nai, Ramyad Hadidi, He Xiao, Hyojong Kim, Jaewoong Sim, and Hyesoon Kim. 2018. CoolPIM: Thermal-aware source throttling for efficient PIM instruction offloading. In 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 680--689.
[47]
Erdinç Öztürk, Yarkin Doröz, Erkay Savaş, and Berk Sunar. 2016. A custom accelerator for homomorphic encryption applications. IEEE Trans. Comput. 66, 1 (2016), 3--16.
[48]
Brandon Reagen, Wooseok Choi, Yeongil Ko, Vincent Lee, Gu-Yeon Wei, Hsien-Hsin S Lee, and David Brooks. 2020. Cheetah: Optimizations and methods for PrivacyPreserving inference via homomorphic encryption. arXiv e-prints (2020), arXiv-2006.
[49]
Dayane Reis, Jonathan Takeshita, Taeho Jung, Michael Niemier, and Xiaobo Sharon Hu. 2020. Computing-in-Memory for Performance and Energy-Efficient Homomorphic Encryption. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 28, 11 (2020), 2300--2313.
[50]
Sahand Salamat, Armin Haj Aboutalebi, Behnam Khaleghi, Joo Hwan Lee, Yang Seok Ki, and Tajana Rosing. 2021. NASCENT: Near-Storage Acceleration of Database Sort on SmartSSD. In The 2021 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays. 262--272.
[51]
Nikola Samardzic, Axel Feldmann, Aleksandar Krastev, Srinivas Devadas, Ronald Dreslinski, Christopher Peikert, and Daniel Sanchez. 2021. F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption. In IEEE/ACM International Symposium on Microarchitecture (MICRO). 238--252.
[52]
SEAL 2020. Microsoft SEAL (release 3.6). https://github.com/Microsoft/SEAL. Microsoft Research, Redmond, WA.
[53]
Julien P Stern. 1998. A new and efficient all-or-nothing disclosure of secrets protocol. In International conference on the theory and application of cryptology and information security. Springer, 357--371.
[54]
Yang Su, Bailong Yang, Chen Yang, and Luogeng Tian. 2020. FPGA-based hardware accelerator for leveled Ring-LWE fully homomorphic encryption. IEEE Access 8 (2020), 168008--168025.
[55]
Muhammad Talha, Mishal Sohail, and Hajar Hajji. 2020. Analysis of research on amazon AWS cloud computing seller data security. International Journal of Research in Engineering and Innovation 4, 3 (2020), 131--136.
[56]
Arash Tavakkol, Juan Gómez-Luna, Mohammad Sadrosadati, Saugata Ghose, and Onur Mutlu. 2018. Mqsim: A framework for enabling realistic studies of modern multi-queue SSD devices. In USENIX Conference on File and Storage Technologies (FAST). 49--66.
[57]
Furkan Turan, Sujoy Sinha Roy, and Ingrid Verbauwhede. 2020. Heaws: An accelerator for homomorphic encryption on the Amazon AWS FPGA. IEEE Trans. Comput. 69, 8 (2020), 1185--1196.
[58]
Jianguo Wang, Dongchul Park, Yang-Suk Kee, Yannis Papakonstantinou, and Steven Swanson. 2016. SSD in-storage computing for list intersection. In Proceedings of the 12th International Workshop on Data Management on New Hardware. 1--7.
[59]
Jianguo Wang, Dongchul Park, Yannis Papakonstantinou, and Steven Swanson. 2016. Ssd in-storage computing for search engines. IEEE Trans. Comput. (2016).
[60]
Shiyuan Wang, Divyakant Agrawal, and Amr El Abbadi. 2010. Generalizing PIR for practical private retrieval of public data. In IFIP Annual Conference on Data and Applications Security and Privacy. Springer, 1--16.
[61]
Wei Wang, Xinming Huang, Niall Emmart, and Charles Weems. 2013. VLSI design of a large-number multiplier for fully homomorphic encryption. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 22, 9 (2013), 1879--1887.
[62]
Mark Wilkening, Udit Gupta, Samuel Hsia, Caroline Trippel, Carole-Jean Wu, David Brooks, and Gu-Yeon Wei. 2021. RecSSD: near data processing for solid state drive based recommendation inference. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. 717--729.
[63]
Amir Yazdanbakhsh, Choungki Song, Jacob Sacks, Pejman Lotfi-Kamran, Hadi Esmaeilzadeh, and Nam Sung Kim. 2018. In-dram near-data approximate acceleration for GPUs. In International Conference on Parallel Architectures and Compilation Techniques. 1--14.

Cited By

View all
  • (2024)SoK: Fully Homomorphic Encryption AcceleratorsACM Computing Surveys10.1145/367695556:12(1-32)Online publication date: 5-Jul-2024
  • (2024)GPU-based Private Information Retrieval for On-Device Machine Learning InferenceProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3617232.3624855(197-214)Online publication date: 27-Apr-2024
  • (2024)Flagger: Cooperative Acceleration for Large-Scale Cross-Silo Federated Learning Aggregation2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00071(915-930)Online publication date: 29-Jun-2024
  • Show More Cited By

Index Terms

  1. INSPIRE: in-storage private information retrieval via protocol and architecture co-design

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      ISCA '22: Proceedings of the 49th Annual International Symposium on Computer Architecture
      June 2022
      1097 pages
      ISBN:9781450386104
      DOI:10.1145/3470496
      This work is licensed under a Creative Commons Attribution International 4.0 License.

      Sponsors

      In-Cooperation

      • IEEE CS TCAA: IEEE CS technical committee on architectural acoustics

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 11 June 2022

      Check for updates

      Author Tags

      1. in-storage computing
      2. private information retrieval (PIR)

      Qualifiers

      • Research-article

      Funding Sources

      • National Science Foundation

      Conference

      ISCA '22
      Sponsor:

      Acceptance Rates

      ISCA '22 Paper Acceptance Rate 67 of 400 submissions, 17%;
      Overall Acceptance Rate 543 of 3,203 submissions, 17%

      Upcoming Conference

      ISCA '25

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)700
      • Downloads (Last 6 weeks)64
      Reflects downloads up to 28 Sep 2024

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)SoK: Fully Homomorphic Encryption AcceleratorsACM Computing Surveys10.1145/367695556:12(1-32)Online publication date: 5-Jul-2024
      • (2024)GPU-based Private Information Retrieval for On-Device Machine Learning InferenceProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3617232.3624855(197-214)Online publication date: 27-Apr-2024
      • (2024)Flagger: Cooperative Acceleration for Large-Scale Cross-Silo Federated Learning Aggregation2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00071(915-930)Online publication date: 29-Jun-2024
      • (2024)NDSEARCH: Accelerating Graph-Traversal-Based Approximate Nearest Neighbor Search through Near Data Processing2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00035(368-381)Online publication date: 29-Jun-2024
      • (2024)PreSto: An In-Storage Data Preprocessing System for Training Recommendation Models2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00033(340-353)Online publication date: 29-Jun-2024
      • (2024)FlashGNN: An In-SSD Accelerator for GNN Training2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00035(361-378)Online publication date: 2-Mar-2024
      • (2023)SPG: Structure-Private Graph Database via SqueezePIRProceedings of the VLDB Endowment10.14778/3587136.358713816:7(1615-1628)Online publication date: 1-Mar-2023
      • (2023)Abakus: Accelerating k-mer Counting with Storage TechnologyACM Transactions on Architecture and Code Optimization10.1145/363295221:1(1-26)Online publication date: 21-Nov-2023
      • (2023)Designing In-Storage Computing for Low Latency and High Throughput Homomorphic Encrypted Execution2023 IEEE 8th International Conference on Big Data Analytics (ICBDA)10.1109/ICBDA57405.2023.10104970(127-136)Online publication date: 3-Mar-2023

      View Options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Get Access

      Login options

      Media

      Figures

      Other

      Tables

      Share

      Share

      Share this Publication link

      Share on social media