{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:28:52Z","timestamp":1778128132962,"version":"3.51.4"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030360320","type":"print"},{"value":"9783030360337","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-36033-7_17","type":"book-chapter","created":{"date-parts":[[2019,11,22]],"date-time":"2019-11-22T21:03:34Z","timestamp":1574456614000},"page":"438-464","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":68,"title":["Compressible FHE with Applications to PIR"],"prefix":"10.1007","author":[{"given":"Craig","family":"Gentry","sequence":"first","affiliation":[]},{"given":"Shai","family":"Halevi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,11,22]]},"reference":[{"issue":"2","key":"17_CR1","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1515\/popets-2016-0010","volume":"2016","author":"C Aguilar-Melchor","year":"2016","unstructured":"Aguilar-Melchor, C., Barrier, J., Fousse, L., Killijian, M.-O.: XPIR: private information retrieval for everyone. Proc. Priv. Enhancing Technol. 2016(2), 155\u2013174 (2016)","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"17_CR2","unstructured":"Albrecht, M., et al.: Homomorphic encryption standard, November 2018. http:\/\/homomorphicencryption.org\/. Accessed Feb 2019"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Angel, S., Chen, H., Laine, K., Setty, S.: PIR with compressed queries and amortized query processing. In: 2018 IEEE Symposium on Security and Privacy (SP), pp. 962\u2013979. IEEE (2018)","DOI":"10.1109\/SP.2018.00062"},{"key":"17_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/978-3-642-03356-8_35","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"B Applebaum","year":"2009","unstructured":"Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595\u2013618. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03356-8_35"},{"key":"17_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-22006-7_34","volume-title":"Automata, Languages and Programming","author":"S Arora","year":"2011","unstructured":"Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 403\u2013415. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22006-7_34"},{"key":"17_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-319-70700-6_10","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2017","author":"S Badrinarayanan","year":"2017","unstructured":"Badrinarayanan, S., Garg, S., Ishai, Y., Sahai, A., Wadia, A.: Two-message witness indistinguishability and\u00a0secure computation in the plain model from new assumptions. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10626, pp. 275\u2013303. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70700-6_10"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., D\u00f6ttling, N., Garg, S., Malavolta, G.: Leveraging linear decryption: Rate-1 fully-homomorphic encryption and time-lock puzzles. Private communications (2019)","DOI":"10.1007\/978-3-030-36033-7_16"},{"key":"17_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-36362-7_1","volume-title":"Public-Key Cryptography \u2013 PKC 2013","author":"Z Brakerski","year":"2013","unstructured":"Brakerski, Z., Gentry, C., Halevi, S.: Packed ciphertexts in LWE-based homomorphic encryption. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 1\u201313. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36362-7_1"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Gentry, C., Vaikuntanathan, V.: Fully homomorphic encryption without bootstrapping. In: Innovations in Theoretical Computer Science (ITCS 2012) (2012). http:\/\/eprint.iacr.org\/2011\/277","DOI":"10.1145\/2090236.2090262"},{"issue":"2","key":"17_CR10","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1137\/120868669","volume":"43","author":"Z Brakerski","year":"2014","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput. 43(2), 831\u2013871 (2014)","journal-title":"SIAM J. Comput."},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Vaikuntanathan, V.: Lattice-based FHE as secure as PKE. In: Naor, M. (ed.) Innovations in Theoretical Computer Science, ITCS 2014, pp. 1\u201312. ACM (2014)","DOI":"10.1145\/2554797.2554799"},{"key":"17_CR12","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: Proceedings, 36th Annual Symposium on Foundations of Computer Science 1995, pp. 41\u201350. IEEE (1995)"},{"key":"17_CR13","unstructured":"Crypto++ 5.6.0, pentium 4 benchmarks (2009). https:\/\/www.cryptopp.com\/benchmarks-p4.html. Accessed Feb 2019"},{"key":"17_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/3-540-44586-2_9","volume-title":"Public Key Cryptography","author":"I Damg\u00e5rd","year":"2001","unstructured":"Damg\u00e5rd, I., Jurik, M.: A generalisation, a simpli.cation and some applications of paillier\u2019s probabilistic public-key system. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119\u2013136. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44586-2_9"},{"key":"17_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-26954-8_1","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"N D\u00f6ttling","year":"2019","unstructured":"D\u00f6ttling, N., Garg, S., Ishai, Y., Malavolta, G., Mour, T., Ostrovsky, R.: Trapdoor hash functions and their applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 3\u201332. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26954-8_1"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197\u2013206. ACM (2008)","DOI":"10.1145\/1374376.1374407"},{"key":"17_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-40041-4_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"C Gentry","year":"2013","unstructured":"Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 75\u201392. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40041-4_5"},{"key":"17_CR18","unstructured":"Green, M., Hohenberger, S., Waters, B.: Outsourcing the decryption of ABE ciphertexts. In: Proceedings 20th USENIX Security Symposium, San Francisco, CA, USA, 8\u201312 August 2011. USENIX Association (2011)"},{"key":"17_CR19","series-title":"Information Security and Cryptography","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-319-57048-8_5","volume-title":"Tutorials on the Foundations of Cryptography","author":"S Halevi","year":"2017","unstructured":"Halevi, S.: Homomorphic encryption. Tutorials on the Foundations of Cryptography. ISC, pp. 219\u2013276. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57048-8_5"},{"issue":"1","key":"17_CR20","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1587\/transfun.E99.A.73","volume":"99","author":"R Hiromasa","year":"2016","unstructured":"Hiromasa, R., Abe, M., Okamoto, T.: Packing messages and optimizing bootstrapping in gsw-fhe. IEICE TRANS. Fundam. Electron. Commun. Comput. Sci. 99(1), 73\u201382 (2016)","journal-title":"IEICE TRANS. Fundam. Electron. Commun. Comput. Sci."},{"issue":"2","key":"17_CR21","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1515\/popets-2015-0016","volume":"2015","author":"A Kiayias","year":"2015","unstructured":"Kiayias, A., Leonardos, N., Lipmaa, H., Pavlyk, K., Tang, Q.: Optimal rate private information retrieval from homomorphic encryption. Proc. Priv. Enhancing Technol. 2015(2), 222\u2013243 (2015)","journal-title":"Proc. Priv. Enhancing Technol."},{"issue":"11","key":"17_CR22","doi-asserted-by":"publisher","first-page":"6989","DOI":"10.1109\/TIT.2012.2210752","volume":"58","author":"D Klinc","year":"2012","unstructured":"Klinc, D., Hazay, C., Jagmohan, A., Krawczyk, H., Rabin, T.: On compression of data encrypted with block ciphers. IEEE Trans. Inf. Theory 58(11), 6989\u20137001 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"17_CR23","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is not needed: Single database, computationally-private information retrieval. In: Proceedings, 38th Annual Symposium on Foundations of Computer Science 1997, pp. 364\u2013373. IEEE (1997)"},{"issue":"1","key":"17_CR24","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1090\/S0002-9904-1976-13988-2","volume":"82","author":"JD Laderman","year":"1976","unstructured":"Laderman, J.D.: A noncommutative algorithm for multiplying $$3 \\times 3$$ matrices using 23 multiplications. Bull. Amer. Math. Soc. 82(1), 126\u2013128 (1976)","journal-title":"Bull. Amer. Math. Soc."},{"key":"17_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/978-3-319-70972-7_35","volume-title":"Financial Cryptography and Data Security","author":"H Lipmaa","year":"2017","unstructured":"Lipmaa, H., Pavlyk, K.: A simpler rate-optimal CPIR protocol. In: Kiayias, A. (ed.) FC 2017. LNCS, vol. 10322, pp. 621\u2013638. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70972-7_35"},{"issue":"6","key":"17_CR26","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1145\/2535925","volume":"60","author":"V Lyubashevsky","year":"2013","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. J. ACM 60(6), 43 (2013). Early version in EUROCRYPT 2010","journal-title":"J. ACM"},{"key":"17_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1007\/978-3-642-29011-4_41","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"D Micciancio","year":"2012","unstructured":"Micciancio, D., Peikert, C.: Trapdoors for lattices: simpler, tighter, faster, smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700\u2013718. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-29011-4_41"},{"key":"17_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-27576-0_13","volume-title":"Financial Cryptography and Data Security","author":"F Olumofin","year":"2012","unstructured":"Olumofin, F., Goldberg, I.: Revisiting the computational practicality of private information retrieval. In: Danezis, G. (ed.) FC 2011. LNCS, vol. 7035, pp. 158\u2013172. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-27576-0_13"},{"key":"17_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/3-540-48910-X_16","volume-title":"Advances in Cryptology \u2014 EUROCRYPT \u201999","author":"P Paillier","year":"1999","unstructured":"Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223\u2013238. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48910-X_16"},{"key":"17_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/978-3-540-85174-5_31","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"C Peikert","year":"2008","unstructured":"Peikert, C., Vaikuntanathan, V., Waters, B.: A framework for efficient and composable oblivious transfer. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 554\u2013571. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85174-5_31"},{"issue":"6","key":"17_CR31","doi-asserted-by":"publisher","first-page":"34:1","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O Regev","year":"2009","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34:1\u201334:40 (2009)","journal-title":"J. ACM"},{"key":"17_CR32","unstructured":"Schmid, P., Roos, A.: AES-NI performance analyzed; limited to 32nm core i5 CPUs (2010). https:\/\/www.tomshardware.com\/reviews\/clarkdale-aes-ni-encryption,2538.html. Accessed Feb 2019"},{"key":"17_CR33","unstructured":"Sion, R., Carbunar, B.: On the practicality of private information retrieval. In: Proceedings of the Network and Distributed System Security Symposium, NDSS 2007, San Diego, California, USA, 28 February\u20132nd March 2007 (2007)"},{"issue":"1","key":"17_CR34","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10623-012-9720-4","volume":"71","author":"NP Smart","year":"2014","unstructured":"Smart, N.P., Vercauteren, F.: Fully homomorphic SIMD operations. Des. Codes Crypt. 71(1), 57\u201381 (2014). Early verion at http:\/\/eprint.iacr.org\/2011\/133","journal-title":"Des. Codes Crypt."},{"key":"17_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/3-540-49649-1_28","volume-title":"Advances in Cryptology \u2014 ASIACRYPT\u201998","author":"JP Stern","year":"1998","unstructured":"Stern, J.P.: A new and efficient all-or-nothing disclosure of secrets protocol. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 357\u2013371. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/3-540-49649-1_28"},{"key":"17_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1007\/978-3-642-13190-5_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"M van Dijk","year":"2010","unstructured":"van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24\u201343. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13190-5_2"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-36033-7_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,22]],"date-time":"2022-11-22T03:06:48Z","timestamp":1669086408000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-36033-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030360320","9783030360337"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-36033-7_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"22 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nuremberg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 December 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 December 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Review software by Shai Halevi","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"147","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"29% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.35","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"15","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}