1. bookVolume 2021 (2021): Issue 3 (July 2021)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Faster homomorphic comparison operations for BGV and BFV

Published Online: 27 Apr 2021
Page range: 246 - 264
Received: 30 Nov 2020
Accepted: 16 Mar 2021
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
Abstract

Fully homomorphic encryption (FHE) allows to compute any function on encrypted values. However, in practice, there is no universal FHE scheme that is effi-cient in all possible use cases. In this work, we show that FHE schemes suitable for arithmetic circuits (e.g. BGV or BFV) have a similar performance as FHE schemes for non-arithmetic circuits (TFHE) in basic comparison tasks such as less-than, maximum and minimum operations. Our implementation of the less-than function in the HElib library is up to 3 times faster than the prior work based on BGV/BFV. It allows to compare a pair of 64-bit integers in 11 milliseconds, sort 64 32-bit integers in 19 seconds and find the minimum of 64 32-bit integers in 9.5 seconds on an average laptop without multi-threading.

Keywords

[1] 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. Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Toronto, Canada, November 2018.Search in Google Scholar

[2] Martin R. Albrecht, Shi Bai, and Léo Ducas. A subfield lattice attack on overstretched NTRU assumptions - cryptanalysis of some FHE and graded encoding schemes. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part I, volume 9814 of LNCS, pages 153–178. Springer, Heidelberg, August 2016.Search in Google Scholar

[3] 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.Search in Google Scholar

[4] 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. IEEE Computer Society Press, May 2018.Search in Google Scholar

[5] Pascal Aubry, Sergiu Carpov, and Renaud Sirdey. Faster Homomorphic Encryption is not Enough: Improved Heuristic for Multiplicative Depth Minimization of Boolean Circuits. In Stanislaw Jarecki, editor, Topics in Cryptology – CT-RSA 2020, pages 345–363, Cham, 2020. Springer International Publishing.Search in Google Scholar

[6] J. Bajard, P. Martins, L. Sousa, and V. Zucca. Improving the Efficiency of SVM Classification With FHE. IEEE Transactions on Information Forensics and Security, 15:1709–1722, 2020.Search in Google Scholar

[7] Joppe W. Bos, Wouter Castryck, Ilia Iliashenko, and Fred-erik Vercauteren. Privacy-friendly forecasting for the smart grid using homomorphic encryption and the group method of data handling. In Marc Joye and Abderrahmane Nitaj, editors, Progress in Cryptology - AFRICACRYPT 2017, pages 184–201, Cham, 2017. Springer International Publishing.Search in Google Scholar

[8] Christina Boura, Nicolas Gama, Mariya Georgieva, and Dimitar Jetchev. Chimera: Combining ring-lwe-based fully homomorphic encryption schemes. Journal of Mathematical Cryptology, 14(1):316–338, 2020.Search in Google Scholar

[9] Florian Bourse, Michele Minelli, Matthias Minihold, and Pascal Paillier. Fast Homomorphic Evaluation of Deep Discretized Neural Networks. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, pages 483–512, Cham, 2018. Springer International Publishing.Search in Google Scholar

[10] Zvika Brakerski. Fully homomorphic encryption without modulus switching from classical GapSVP. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 868–886. Springer, Heidelberg, August 2012.Search in Google Scholar

[11] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, page 309–325, New York, NY, USA, 2012. Association for Computing Machinery.Search in Google Scholar

[12] Gizem S. Çetin, Yarkin Doröz, Berk Sunar, and Erkay Savas. Depth optimized efficient homomorphic sorting. In Kristin E. Lauter and Francisco Rodríguez-Henríquez, editors, LATIN-CRYPT 2015, volume 9230 of LNCS, pages 61–80. Springer, Heidelberg, August 2015.Search in Google Scholar

[13] J. H. Cheon, M. Kim, and M. Kim. Optimized Search-and-Compute Circuits and Their Application to Query Evaluation on Encrypted Data. IEEE Transactions on Information Forensics and Security, 11(1):188–199, 2016.Search in Google Scholar

[14] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. Homomorphic encryption for arithmetic of approximate numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, pages 409–437, Cham, 2017. Springer International Publishing.Search in Google Scholar

[15] Jung Hee Cheon, Dongwoo Kim, and Duhyeong Kim. Efficient homomorphic comparison methods with optimal complexity. Cryptology ePrint Archive, Report 2019/1234, 2019. https://eprint.iacr.org/2019/1234, to appear in ASIACRYPT 2020.Search in Google Scholar

[16] Jung Hee Cheon, Dongwoo Kim, Duhyeong Kim, Hun-Hee Lee, and Keewoo Lee. Numerical method for comparison on homomorphically encrypted numbers. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part II, volume 11922 of LNCS, pages 415–445. Springer, Heidelberg, December 2019.Search in Google Scholar

[17] Jung Hee Cheon, Miran Kim, and Myungsun Kim. Search-and-compute on encrypted data. In Michael Brenner, Nicolas Christin, Benjamin Johnson, and Kurt Rohloff, editors, Financial Cryptography and Data Security, pages 142–159, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.Search in Google Scholar

[18] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology – ASIACRYPT 2016, pages 3–33, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.Search in Google Scholar

[19] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part I, volume 10624 of LNCS, pages 377–408. Springer, Heidelberg, December 2017.Search in Google Scholar

[20] Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: Fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1):34–91, January 2020.Search in Google Scholar

[21] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009.Search in Google Scholar

[22] Léo Ducas and Daniele Micciancio. FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, pages 617–640, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg.Search in Google Scholar

[23] Thomas Espitau, Antoine Joux, and Natalia Kharchenko. On a hybrid approach to solve small secret LWE. Cryptology ePrint Archive, Report 2020/512, 2020. http://eprint.iacr.org/2020/512.Search in Google Scholar

[24] Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144, 2012. https://eprint.iacr.org/2012/144.Search in Google Scholar

[25] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, 41st ACM STOC, pages 169–178. ACM Press, May / June 2009.Search in Google Scholar

[26] Craig Gentry, Shai Halevi, and Nigel P. Smart. Fully Homomorphic Encryption with Polylog Overhead. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, pages 465–482, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.Search in Google Scholar

[27] HElib: An implementation of homomorphic encryption (2.0.0). https://github.com/homenc/HElib, January 2021. IBM.Search in Google Scholar

[28] Shizuo Kaji, Toshiaki Maeno, Koji Nuida, and Yasuhide Numata. Polynomial expressions of p-ary auction functions. Journal of Mathematical Cryptology, 13(2):69–80, 2019.Search in Google Scholar

[29] M. Kim, H. T. Lee, S. Ling, and H. Wang. On the Effi-ciency of FHE-Based Private Queries. IEEE Transactions on Dependable and Secure Computing, 15(2):357–363, 2018.Search in Google Scholar

[30] Miran Kim and Kristin Lauter. Private Genome Analysis Through Homomorphic Encryption. BMC medical informatics and decision making, 15, December 2015.Search in Google Scholar

[31] Rudolf Lidl and Harald Niederreiter. Introduction to finite fields and their applications. Cambridge University Press, 1986.Search in Google Scholar

[32] Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Howard J. Karloff and Toniann Pitassi, editors, 44th ACM STOC, pages 1219–1234. ACM Press, May 2012.Search in Google Scholar

[33] H. Narumanchi, D. Goyal, N. Emmadi, and P. Gauravaram. Performance analysis of sorting of fhe data: Integer-wise comparison vs bit-wise comparison. In 2017 IEEE 31st International Conference on Advanced Information Networking and Applications (AINA), pages 902–908, 2017.Search in Google Scholar

[34] Michael S Paterson and Larry J Stockmeyer. On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM Journal on Computing, 2(1):60–66, 1973.Search in Google Scholar

[35] Hayim Shaul, Dan Feldman, and Daniela Rus. Secure kish nearest neighbors classifier. Proceedings on Privacy Enhancing Technologies, 2020(3):42–61, 2020.Search in Google Scholar

[36] N. P. Smart and F. Vercauteren. Fully Homomorphic SIMD Operations. Des. Codes Cryptography, 71(1):57–81, April 2014.Search in Google Scholar

[37] B. H. M. Tan, H. T. Lee, H. Wang, S. Q. Ren, and A. M. M. Khin. Efficient private comparison queries over encrypted databases using fully homomorphic encryption with finite fields. IEEE Transactions on Dependable and Secure Computing, pages 1–1, 2020.Search in Google Scholar

[38] Mihai Togan, Luciana Morogan, and Cezar Plesca. Comparison-based applications for fully homomorphic encrypted data. Proceedings of the Romanian Academy-Series A: Mathematics, Physics, Technical Sciences, Information Science, 16:329, 2015.Search in Google Scholar

[39] Andrew C. Yao. Protocols for Secure Computations. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, SFCS ’82, page 160–164, USA, 1982. IEEE Computer Society.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo