Towards Efficient FHE Based cPIR Schemes and Their Parameter Selection
ARES '22: Proceedings of the 17th International Conference on Availability, Reliability and Security
Article No.: 136, Pages 1 - 11
Abstract
Private Information Retrieval (PIR) protocols enables fetching an arbitrary data from a server without revealing any information to the server about the data. In this paper, we construct three computational PIR (cPIR) protocols which we call P-cPIR and Recursive P-cPIR version I and II. We construct our cPIR protocols on a well known Fully Homomorphic Encryption scheme (FHE), BFVrns. For n = 220, 240, P-cPIR and Recursive P-cPIR version I provide at least ∼ 214 × computational improvement over other prominent cPIR protocols. Recursive P-cPIR version II proposes the same query and half response cost as OnionPIR (lower communication cost in total) and less than other protocols such as SealPIR, SHECS-PIR, XPIR. It also proposes at least ∼ 23 × less computational cost than other proposed protocols by stating the best performance in these protocols for both cases. We also provide a parameter selection method for the proposed cPIR protocols that takes the burden of parameter selection from the users and makes it more usable for real-life applications.
References
[1]
Carlos Aguilar-Melchor and Philippe Gaborit. 2007. A lattice-based computationally-efficient private information retrieval protocol. Cryptol. ePrint Arch., Report 446 (2007).
[2]
Martin Albrecht, Melissa Chase, Hao Chen, Jintai Ding, Shafi Goldwasser, Sergey Gorbunov, Shai Halevi, Jeffrey Hoffstein, Kim Laine, Kristin Lauter, Satya Lokam, Daniele Micciancio, Dustin Moody, Travis Morrison, Amit Sahai, and Vinod Vaikuntanathan. 2018. Homomorphic Encryption Security Standard. Technical Report. HomomorphicEncryption.org, Toronto, Canada.
[3]
Martin R Albrecht, Rachel Player, and Sam Scott. 2015. On the concrete hardness of learning with errors. Journal of Mathematical Cryptology 9, 3 (2015), 169–203.
[4]
Sebastian Angel, Hao Chen, Kim Laine, and Srinath Setty. 2018. PIR with compressed queries and amortized query processing. In 2018 IEEE symposium on security and privacy (SP). IEEE, 962–979.
[5]
Sanjeev Arora and Rong Ge. 2011. New algorithms for learning in presence of errors. In International Colloquium on Automata, Languages, and Programming. Springer, 403–415.
[6]
Jean-Claude Bajard, Julien Eynard, M Anwar Hasan, and Vincent Zucca. 2016. A full RNS variant of FV like somewhat homomorphic encryption schemes. In International Conference on Selected Areas in Cryptography. Springer, 423–442.
[7]
Jingguo Bi, Mingjie Liu, and Xiaoyun Wang. 2012. Cryptanalysis of a homomorphic encryption scheme from ISIT 2008. In 2012 IEEE International Symposium on Information Theory Proceedings. IEEE, 2152–2156.
[8]
Zvika Brakerski. 2012. Fully homomorphic encryption without modulus switching from classical GapSVP. In Annual Cryptology Conference. Springer, 868–886.
[9]
Zvika Brakerski and Vinod Vaikuntanathan. 2011. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In Annual cryptology conference. Springer, 505–524.
[10]
Yan-Cheng Chang. 2004. Single database private information retrieval with logarithmic communication. In Australasian Conference on Information Security and Privacy. Springer, 50–61.
[11]
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. 2020. TFHE: fast fully homomorphic encryption over the torus. Journal of Cryptology 33, 1 (2020), 34–91.
[12]
B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. 1995. Private information retrieval. In Proceedings of IEEE 36th Annual Foundations of Computer Science. 41–50. https://doi.org/10.1109/SFCS.1995.492461
[13]
Don Coppersmith and Madhu Sudan. 2003. Reconstructing curves in three (and higher) dimensional space from noisy data. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing. 136–142.
[14]
Junfeng Fan and Frederik Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144. https://eprint.iacr.org/2012/144.
[15]
Craig Gentry 2009. Fully homomorphic encryption using ideal lattices. In Stoc. 169–178.
[16]
Craig Gentry and Shai Halevi. 2019. Compressible FHE with applications to PIR. In Theory of Cryptography Conference. Springer, 438–464.
[17]
Shai Halevi, Yuriy Polyakov, and Victor Shoup. 2019. An improved RNS variant of the BFV homomorphic encryption scheme. In Cryptographers’ Track at the RSA Conference. Springer, 83–105.
[18]
Eyal Kushilevitz and Rafail Ostrovsky. 1997. Replication is not needed: Single database, computationally-private information retrieval. In Proceedings 38th annual symposium on foundations of computer science. IEEE, 364–373.
[19]
Eyal Kushilevitz and Rafail Ostrovsky. 2000. One-way trapdoor permutations are sufficient for non-trivial single-server private information retrieval. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 104–121.
[20]
Helger Lipmaa. 2005. An oblivious transfer protocol with log-squared communication. In International Conference on Information Security. Springer, 314–328.
[21]
Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2010. On ideal lattices and learning with errors over rings. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 1–23.
[22]
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.
[23]
Carlos Aguilar Melchor, Benoit Crespin, Philippe Gaborit, Vincent Jolivet, and Pierre Rousseau. 2008. High-speed private information retrieval computation on gpu. In 2008 Second International Conference on Emerging Security Information, Systems and Technologies. IEEE, 263–272.
[24]
Carlos Aguilar Melchor and Philippe Gaborit. 2008. A fast private information retrieval protocol. In 2008 IEEE International Symposium on Information Theory. 1848–1852. https://doi.org/10.1109/ISIT.2008.4595308
[25]
Muhammad Haris Mughees, Hao Chen, and Ling Ren. 2021. OnionPIR: Response Efficient Single-Server PIR. In Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2292–2306.
[26]
Jeongeun Park and Mehdi Tibouchi. 2020. SHECS-PIR: Somewhat Homomorphic Encryption-Based Compact and Scalable Private Information Retrieval. In European Symposium on Research in Computer Security. Springer, 86–106.
[27]
Yuriy Polyakov, Kurt Rohloff, and Gerard W Ryan. 2018. PALISADE lattice cryptography library. https://palisade-crypto.org/
[28]
Oded Regev. 2005. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing (Baltimore, MD, USA) (STOC ’05). ACM, New York, NY, USA, 84–93. https://doi.org/10.1145/1060590.1060603
[29]
Ronald L Rivest, Len Adleman, Michael L Dertouzos, 1978. On data banks and privacy homomorphisms. Foundations of secure computation 4, 11 (1978), 169–180.
[30]
Radu Sion and Bogdan Carbunar. 2007. On the computational practicality of private information retrieval. In Proceedings of the Network and Distributed Systems Security Symposium. Internet Society, 2006–06.
[31]
Nigel P Smart and Frederik Vercauteren. 2014. Fully homomorphic SIMD operations. Designs, codes and cryptography 71, 1 (2014), 57–81.
[32]
StataCorp. 2013. Stata Statistical Software: Release 13. https://www.stata.com
[33]
Damien Stehlé and Ron Steinfeld. 2010. Faster Fully Homomorphic Encryption. In Proceedings of ASIACRYPT 2010. 377–394.
[34]
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. 2009. Efficient public key encryption based on ideal lattices. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 617–635.
[35]
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.
[36]
Jonathan Trostle and Andy Parrish. 2010. Efficient computationally private information retrieval from anonymity or trapdoor groups. In International Conference on Information Security. Springer, 114–128.
[37]
Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. 2010. Fully Homomorphic Encryption over the Integers. EUROCRYPT 2010 (2010), 24.
[38]
Cavidan Yakupoglu and Kurt Rohloff. 2022. Parameter Selection for Computationally Efficient Use of the BFVrns FHE Scheme. World Academy of Science, Engineering and Technology International Journal of Computer and Information Engineering 16, 07 (2022).
Index Terms
- Towards Efficient FHE Based cPIR Schemes and Their Parameter Selection
Recommendations
XSPIR: Efficient Symmetrically Private Information Retrieval from Ring-LWE
Computer Security – ESORICS 2022AbstractPrivate Information Retrieval (PIR) allows a client to retrieve one entry from a database held by a server, while hiding from the server which entry has been retrieved. Symmetrically Private Information Retrieval (SPIR) additionally protects the ...
Communication-efficient distributed oblivious transfer
Distributed oblivious transfer (DOT) was introduced by Naor and Pinkas (2000) [31], and then generalized to (k,@__ __)-DOT-(n1) by Blundo et al. (2007) [8] and Nikov et al. (2002) [34]. In the generalized setting, a (k,@__ __)-DOT-(n1) allows a sender to ...
On the Black-box Use of Somewhat Homomorphic Encryption in NonInteractive Two-Party Protocols
In this work, we develop a methodology for determining the communication required to implement various two-party functionalities noninteractively. In the particular setting on which we focus, the protocols are based upon somewhat homomorphic encryption, and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
August 2022
1371 pages
ISBN:9781450396707
DOI:10.1145/3538969
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 23 August 2022
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- DARPA and the US Navy SPAWAR Systems Center Pacific (SSCPAC)
Conference
ARES 2022
ARES 2022: The 17th International Conference on Availability, Reliability and Security
August 23 - 26, 2022
Vienna, Austria
Acceptance Rates
Overall Acceptance Rate 228 of 451 submissions, 51%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 80Total Downloads
- Downloads (Last 12 months)23
- Downloads (Last 6 weeks)4
Reflects downloads up to 03 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format