Non-interactive Private Multivariate Function Evaluation using Homomorphic Table Lookup
Authors
Ruixiao Li, Hayato Yamana
Ruixiao Li
Waseda University, Tokyo, Japan
liruixiao at yama dot info dot waseda dot ac dot jp
liruixiao at yama dot info dot waseda dot ac dot jp
Hayato Yamana
Waseda University, Tokyo, Japan
yamana at yama dot info dot waseda dot ac dot jp
yamana at yama dot info dot waseda dot ac dot jp
Abstract
To address security issues in cloud computing, fully homomorphic encryption (FHE) enables a third party to evaluate functions using ciphertexts that do not leak information to the cloud server. The remaining problems of FHE include high computational costs and limited arithmetic operations, only evaluating additions and multiplications. Arbitrary functions can be evaluated using a precomputed lookup table (LUT), which is one of the solutions for those problems. Previous studies proposed LUT-enabled computation methods 1) with bit-wise FHE and 2) with word-wise FHE. The performance of LUT-enabled computation with bit-wise FHE drops quickly when evaluating BigNum functions because of the complexity being O(s·2^d·m), where m represents the number of inputs, d and s represent the bit lengths of the inputs and outputs, respectively. Thus, LUT-enabled computation with word-wise FHE, which handles a set of bits with one operation, has also been proposed; however, previous studies are limited in evaluating multivariate functions within two inputs and cannot speed up the evaluation when the domain size of the integer exceeds 2N, where N is the number of elements packed into a single ciphertext. In this study, we propose a non-interactive model, in which no decryption is required, to evaluate arbitrary multivariate functions using homomorphic table lookup with word-wise FHE. The proposed LUT-enabled computation method 1) decreases the complexity to O(2^d·m/l), where l is the element size of FHE packing; 2) extends the input and output domain sizes to evaluate multivariate functions over two inputs; and 3) adopts a multidimensional table for enabling multithreading to reduce latency. The experimental results demonstrate that evaluating a 10-bit two-input function and a 5-bit three-input function takes approximately 90.5 and 105.5 s with 16-thread, respectively. Our proposed method achieves 3.2x and 23.1x speedup to evaluate two-bit and three-bit 3-input functions compared with naive LUT-enabled computation with bit-wise FHE.
References
[BBB+22]
Ahmad Al Badawi, Jack Bates, Flávio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Ian Quah, Yuriy Polyakov, R. V. Saraswathy, Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. OpenFHE: Open-Source Fully Homomorphic Encryption Library. In Michael Brenner, Anamaria Costache, and Kurt Rohloff, editors, Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Los Angeles, CA, USA, 7 November 2022, pages 53–63. 2022. ACM. DOI: 10.1145/3560827.3563379
[BGGJ20]
Christina Boura, Nicolas Gama, Mariya Georgieva, and Dimitar Jetchev. CHIMERA: Combining Ring-LWE-based Fully Homomorphic Encryption Schemes. J. Math. Cryptol., 14(1):316–338, 2020. DOI: 10.1515/JMC-2019-0026
[BGH13]
Zvika Brakerski, Craig Gentry, and Shai Halevi. Packed Ciphertexts in LWE-Based Homomorphic Encryption. In Kaoru Kurosawa and Goichiro Hanaoka, editors, PKC 2013: 16th International Conference on Theory and Practice of Public Key Cryptography, volume 7778 of Lecture Notes in Computer Science, pages 1–13, Nara, Japan. 2013. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-642-36362-7_1
[BGV14]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Trans. Comput. Theory, 6(3):13:1–13:36, 2014. DOI: 10.1145/2633600
[BPTG15]
Raphael Bost, Raluca Ada Popa, Stephen Tu, and Shafi Goldwasser. Machine Learning Classification over Encrypted Data. In ISOC Network and Distributed System Security Symposium – NDSS 2015, San Diego, CA, USA. 2015. The Internet Society. DOI: 10.14722/ndss.2015.23241
[Bra12]
Zvika Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology – CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 868–886, Santa Barbara, CA, USA. 2012. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-642-32009-5_50
[CBK+20]
Mahawaga Arachchige Pathum Chamikara, Peter Bertók, Ibrahim Khalil, Dongxi Liu, and Seyit Camtepe. Privacy Preserving Face Recognition Utilizing Differential Privacy. Comput. Secur., 97:101951, 2020. DOI: 10.1016/J.COSE.2020.101951
[CBL+18]
Edward Chou, Josh Beal, Daniel Levy, Serena Yeung, Albert Haque, and Li Fei-Fei. Faster CryptoNets: Leveraging Sparsity for Real-World Encrypted Inference. CoRR, abs/1811.09953, 2018.
[CDH+19]
Martine De Cock, Rafael Dowsley, Caleb Horst, Raj S. Katti, Anderson C. A. Nascimento, Wing-Sea Poon, and Stacey Truex. Efficient and Private Scoring of Decision Trees, Support Vector Machines and Logistic Regression Models Based on Pre-Computation. IEEE Trans. Dependable Secur. Comput., 16(2):217–230, 2019. DOI: 10.1109/TDSC.2017.2679189
[CdWM+17]
Hervé Chabanne, Amaury de Wargny, Jonathan Milgram, Constance Morel, and Emmanuel Prouff. Privacy-Preserving Classification on Deep Neural Network. Cryptology ePrint Archive, Report 2017/035. 2017.
[CFLW17]
Jingwei Chen, Yong Feng, Yang Liu, and Wenyuan Wu. Faster binary arithmetic operations on encrypted integers. In The 7th International Workshop on Computer Science and Engineering, Beijing, 25-27 June, 2017, Proceedings, pages 956–960. 2017. DOI: 10.18178/wcse.2017.06.166
[CG15]
Yao Chen and Guang Gong. Integer arithmetic over ciphertext and homomorphic data aggregation. In 2015 IEEE Conference on Communications and Network Security, CNS 2015, Florence, Italy, September 28-30, 2015, pages 628–632. 2015. IEEE. DOI: 10.1109/CNS.2015.7346877
[CGGI20]
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. DOI: 10.1007/s00145-019-09319-x
[CGH+18]
Jack L. H. Crawford, Craig Gentry, Shai Halevi, Daniel Platt, and Victor Shoup. Doing Real Work with FHE: The Case of Logistic Regression. In Michael Brenner and Kurt Rohloff, editors, Proceedings of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC@CCS 2018, Toronto, ON, Canada, October 19, 2018, pages 1–12. 2018. ACM. DOI: 10.1145/3267973.3267974
[CIM19]
Sergiu Carpov, Malika Izabachène, and Victor Mollimard. New Techniques for Multi-value Input Homomorphic Evaluation and Applications. In Mitsuru Matsui, editor, Topics in Cryptology – CT-RSA 2019, volume 11405 of Lecture Notes in Computer Science, pages 106–126, San Francisco, CA, USA. 2019. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-12612-4_6
[CKKS17]
Jung Hee Cheon, Andrey Kim, Miran Kim, and Yong Soo Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology – ASIACRYPT 2017, Part I, volume 10624 of Lecture Notes in Computer Science, pages 409–437, Hong Kong, China. 2017. Springer, Cham, Switzerland. DOI: 10.1007/978-3-319-70694-8_15
[CKP22]
Jung Hee Cheon, Wootae Kim, and Jai Hyun Park. Efficient Homomorphic Evaluation on Large Intervals. IEEE Trans. Inf. Forensics Secur., 17:2553–2568, 2022. DOI: 10.1109/TIFS.2022.3188145
[CMTB16]
Henry Carter, Benjamin Mood, Patrick Traynor, and Kevin R. B. Butler. Secure outsourced garbled circuit evaluation for mobile devices. J. Comput. Secur., 24(2):137–180, 2016. DOI: 10.3233/JCS-150540
[CT12]
Michael A. Cohen and Can Ozan Tan. A polynomial approximation for arbitrary functions. Appl. Math. Lett., 25(11):1947–1952, 2012. DOI: 10.1016/J.AML.2012.03.007
[DCW13]
Changyu Dong, Liqun Chen, and Zikai Wen. When private set intersection meets big data: an efficient and scalable protocol. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013: 20th Conference on Computer and Communications Security, pages 789–800, Berlin, Germany. 2013. ACM Press. DOI: 10.1145/2508859.2516701
[DM15]
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, Part I, volume 9056 of Lecture Notes in Computer Science, pages 617–640, Sofia, Bulgaria. 2015. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-662-46800-5_24
[FV12]
Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive, Report 2012/144. 2012.
[GCH+18]
Chong-zhi Gao, Qiong Cheng, Pei He, Willy Susilo, and Jin Li. Privacy-preserving Naive Bayes classifiers secure against the substitution-then-comparison attack. Inf. Sci., 444:72–88, 2018. DOI: 10.1016/J.INS.2018.02.058
[GDL+16]
Ran Gilad-Bachrach, Nathan Dowlin, Kim Laine, Kristin E. Lauter, Michael Naehrig, and John Wernsing. CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy. In Maria-Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 201–210. 2016. JMLR.org.
[Gen09]
Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, 41st Annual ACM Symposium on Theory of Computing, pages 169–178, Bethesda, MD, USA. 2009. ACM Press. DOI: 10.1145/1536414.1536440
[GSW13]
Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013, Part I, volume 8042 of Lecture Notes in Computer Science, pages 75–92, Santa Barbara, CA, USA. 2013. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-642-40041-4_5
[HS14]
Shai Halevi and Victor Shoup. Algorithms in HElib. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology – CRYPTO 2014, Part I, volume 8616 of Lecture Notes in Computer Science, pages 554–571, Santa Barbara, CA, USA. 2014. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-662-44371-2_31
[HTG19]
Ehsan Hesamifard, Hassan Takabi, and Mehdi Ghasemi. Deep Neural Networks Classification over Encrypted Data. In Gail-Joon Ahn, Bhavani Thuraisingham, Murat Kantarcioglu, and Ram Krishnan, editors, Proceedings of the Ninth ACM Conference on Data and Application Security and Privacy, CODASPY 2019, Richardson, TX, USA, March 25-27, 2019, pages 97–108. 2019. ACM. DOI: 10.1145/3292006.3300044
[jLHH+21]
Wen-jie Lu, Zhicong Huang, Cheng Hong, Yiping Ma, and Hunter Qu. PEGASUS: Bridging Polynomial and Non-polynomial Evaluations in Homomorphic Encryption. In 2021 IEEE Symposium on Security and Privacy, pages 1057–1073, San Francisco, CA, USA. 2021. IEEE Computer Society Press. DOI: 10.1109/SP40001.2021.00043
[KSW+18]
Miran Kim, Yongsoo Song, Shuang Wang, Yuhou Xia, and Xiaoqian Jiang. Secure Logistic Regression Based on Homomorphic Encryption: Design and Evaluation. JMIR Med Inform, 6(2):e19, April 2018. DOI: 10.2196/medinform.8805
[LBDY22]
Ruixiao Li, Shameek Bhattacharjee, Sajal K. Das, and Hayato Yamana. Look-Up Table based FHE System for Privacy Preserving Anomaly Detection in Smart Grids. In 2022 IEEE International Conference on Smart Computing, SMARTCOMP 2022, Helsinki, Finland, June 20-24, 2022, pages 108–115. 2022. IEEE. DOI: 10.1109/SMARTCOMP55677.2022.00030
[LDL15]
Hongwei Li, Yuanshun Dai, and Xiaodong Lin. Efficient e-health data release with consistency guarantee under differential privacy. In 17th International Conference on E-health Networking, Application & Services, HealthCom 2015, Boston, MA, USA, October 14-17, 2015, pages 602–608. 2015. IEEE. DOI: 10.1109/HEALTHCOM.2015.7454576
[LLNK22]
Eunsang Lee, Joon-Woo Lee, Jong-Seon No, and Young-Sik Kim. Minimax Approximation of Sign Function by Composite Polynomial for Homomorphic Comparison. IEEE Trans. Dependable Secur. Comput., 19(6):3711–3727, 2022. DOI: 10.1109/TDSC.2021.3105111
[LY21]
Ruixiao Li and Hayato Yamana. Fast and Accurate Function Evaluation with LUT over Integer-Based Fully Homomorphic Encryption. In Leonard Barolli, Isaac Woungang, and Tomoya Enokido, editors, Advanced Information Networking and Applications - Proceedings of the 35th International Conference on Advanced Information Networking and Applications (AINA-2021), Toronto, ON, Canada, 12-14 May, 2021, Volume 2, volume 226 of Lecture Notes in Networks and Systems, pages 620–633. 2021. Springer. DOI: 10.1007/978-3-030-75075-6_51
[LY24]
Ruixiao Li and Hayato Yamana. Privacy Preserving Function Evaluation using Lookup Tables with Word-Wise FHE. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E107-A(8):1–15, 2024. DOI: 10.1587/transfun.2023EAP1114
[MMN22]
Daisuke Maeda, Koki Morimura, and Takashi Nishide. Efficient Homomorphic Evaluation of Arbitrary Bivariate Integer Functions. In Michael Brenner, Anamaria Costache, and Kurt Rohloff, editors, Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Los Angeles, CA, USA, 7 November 2022, pages 13–22. 2022. ACM. DOI: 10.1145/3560827.3563378
[MP21]
Daniele Micciancio and Yuriy Polyakov. Bootstrapping in FHEW-like Cryptosystems. In WAHC '21: Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Virtual Event, Korea, 15 November 2021, pages 17–28. 2021. WAHC@ACM. DOI: 10.1145/3474366.3486924
[MRVW21]
Eleftheria Makri, Dragos Rotaru, Frederik Vercauteren, and Sameer Wagh. Rabbit: Efficient Comparison for Secure Multi-Party Computation. In Nikita Borisov and Claudia Díaz, editors, FC 2021: 25th International Conference on Financial Cryptography and Data Security, Part I, volume 12674 of Lecture Notes in Computer Science, pages 249–270, Virtual Event. 2021. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-662-64322-8_12
[OCHK18]
Hiroki Okada, Carlos Cid, Seira Hidano, and Shinsaku Kiyomoto. Linear Depth Integer-Wise Homomorphic Division. In Olivier Blazy and Chan Yeob Yeun, editors, Information Security Theory and Practice - 12th IFIP WG 11.2 International Conference, WISTP 2018, Brussels, Belgium, December 10-11, 2018, Revised Selected Papers, volume 11469 of Lecture Notes in Computer Science, pages 91–106. 2018. Springer. DOI: 10.1007/978-3-030-20074-9_8
[SV14]
Nigel P. Smart and Frederik Vercauteren. Fully homomorphic SIMD operations. Designs, Codes and Cryptography, 71(1):57–81, 2014. DOI: 10.1007/s10623-012-9720-4
[XBF+14]
Pengtao Xie, Misha Bilenko, Tom Finley, Ran Gilad-Bachrach, Kristin E. Lauter, and Michael Naehrig. Crypto-Nets: Neural Networks over Encrypted Data. CoRR, abs/1412.6181, 2014.
[XCWF16]
Chen Xu, Jingwei Chen, Wenyuan Wu, and Yong Feng. Homomorphically Encrypted Arithmetic Operations Over the Integer Ring. In Feng Bao, Liqun Chen, Robert H. Deng, and Guojun Wang, editors, Information Security Practice and Experience - 12th International Conference, ISPEC 2016, Zhangjiajie, China, November 16-18, 2016, Proceedings, volume 10060 of Lecture Notes in Computer Science, pages 167–181. 2016. DOI: 10.1007/978-3-319-49151-6_12
[Yao82]
Andrew Chi-Chih Yao. Protocols for Secure Computations (Extended Abstract). In 23rd Annual Symposium on Foundations of Computer Science, pages 160–164, Chicago, Illinois. 1982. IEEE Computer Society Press. DOI: 10.1109/SFCS.1982.38
[ZC20]
Xu Zheng and Zhipeng Cai. Privacy-Preserved Data Sharing Towards Multiple Parties in Industrial IoTs. IEEE J. Sel. Areas Commun., 38(5):968–979, 2020. DOI: 10.1109/JSAC.2020.2980802
[ZTG+19]
Maede Zolanvari, Marcio Andrey Teixeira, Lav Gupta, Khaled M. Khan, and Raj Jain. Machine Learning-Based Network Vulnerability Analysis of Industrial Internet of Things. IEEE Internet Things J., 6(4):6822–6834, 2019. DOI: 10.1109/JIOT.2019.2912022
PDF
History
Submitted: 2024-07-07
Accepted: 2024-09-02
Published: 2024-10-07
Accepted: 2024-09-02
Published: 2024-10-07
How to cite
Ruixiao Li and Hayato Yamana, Non-interactive Private Multivariate Function Evaluation using Homomorphic Table Lookup. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/andkmp-3y.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.