Cloud security; encrypted number comparison; homomorphic encryption; polynomial approximation; privacy-preserving; Approximation methods; Cloud securities; Cloud-computing; Encrypted number comparison; Ho-momorphic encryptions; Homomorphic-encryptions; Privacy preserving; Public keys; Computer Science (all); Materials Science (all); Engineering (all); General Engineering; General Materials Science; General Computer Science; Electrical and Electronic Engineering
Résumé :
[en] The security issues that arise in public cloud environments raise several concerns about privacy-preserving. Conventional security practices successfully protect stored and transmitted data by encryption, but not during data processing where the data value extraction requires decryption. It creates critical exposure points for sensitive sectors like healthcare, pharmaceutical, genomics, government, and financial, among many others that cause hesitation to use these third-party services and prevent widespread practical adoption of cloud solutions. Homomorphic Encryption (HE) emerges as a mechanism for expanding the scope of public cloud services for sensitive data processing. However, high-demand solutions such as artificial intelligence and machine learning require efficient operations beyond HE additions and multiplications. In this paper, we analyze the current homomorphic comparison methods across their strengths and weaknesses and present theoretical concepts, state-of-the-art techniques, challenges, opportunities, and open problems. We theoretically prove the limits of the representability of sign and comparison functions in polynomial forms for HE schemes. We show that both functions can be represented as polynomials over the Galois field and cannot be represented over a residue ring with zero divisors. We compare the efficiency, accuracy, and computational complexity of different homomorphic comparison approaches. The experimental results demonstrate that Newton-Raphson is the fastest method for generating polynomial approximations and evaluating comparisons, and the Fourier method is the most accurate considering the L1, L2, L∞ norms and R2 measure. The bi-objective analysis presents the performance compromise between complexity and accuracy.
Disciplines :
Sciences informatiques
Auteur, co-auteur :
Pulido-Gaytan, Bernardo ; CICESE Research Center, Department of Computer Science, Ensenada, Mexico
Tchernykh, Andrei ; CICESE Research Center, Department of Computer Science, Ensenada, Mexico
LEPREVOST, Franck ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
BOUVRY, Pascal ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Goldman, Alfredo ; Institute of Mathematics and Statistics, University of São Paulo, São Paulo, Brazil
J. H. Cheon, D. Kim, D. Kim, H. H. Lee, and K. Lee, "Numerical method for comparison on homomorphically encrypted numbers, " in Advances in Cryptology ASIACRYPT 2019. Cham, Switzerland: Springer., 2019, pp. 415-445.
Z. Brakerski, C. Gentry, and V. Vaikuntanathan, "(Leveled) fully homomorphic encryption without bootstrapping, " in Proc. 3rd Innov. Theor. Comput. Sci. Conf., Jan. 2012, pp. 309-325.
Z. Brakerski, "Fully homomorphic encryption without modulus switching from classical GapSVP, " in Proc. CRYPTO, 2012, pp. 868-886.
J. Fan and F. Vercauteren, "Somewhat practical fully homomorphic encryption, " IACR Cryptol. ePrint Arch., vol. 144, Mar. 2012. [Online]. Available: https://eprint.iacr.org/2012/144
J. H. Cheon, A. Kim, M. Kim, and Y. Song, "Homomorphic encryption for arithmetic of approximate numbers, " in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur., 2017, pp. 409-437.
B. H. M. Tan, H. T. Lee, H. Wang, S. Ren, and K. M. M. Aung, "Efficient private comparison queries over encrypted databases using fully homomorphic encryption with finite fields, " IEEE Trans. Depend. Secure Comput., vol. 18, no. 6, pp. 2861-2874, Nov. 2021, doi: 10.1109/TDSC.2020.2967740.
M. Babenko, A. Tchernykh, N. Chervyakov, V. Kuchukov, V. Miranda-López, R. Rivera-Rodriguez, Z. Du, and E.-G. Talbi, "Positional characteristics for efficient number comparison over the homomorphic encryption, " Program. Comput. Softw., vol. 45, no. 8, pp. 532-543, Dec. 2019, doi: 10.1134/S0361768819080115.
E. Lee, J.-W. Lee, J.-S. No, and Y.-S. Kim, "Minimax approximation of sign function by composite polynomial for homomorphic comparison, " IEEE Trans. Depend. Secure Comput., vol. 19, no. 6, pp. 3711-3727, Nov. 2022, doi: 10.1109/TDSC.2021.3105111.
H. C. Tanuwidjaja, R. Choi, and K. Kim, "A survey on deep learning techniques for privacy-preserving, " in Machine Learning for Cyber Security. Cham, Switzerland: Springer, 2019, pp. 29-46.
A. C.-C. Yao, "Howto generate and exchange secrets, " in Proc. 27th Annu. Symp. Found. Comput. Sci. (SFCS), Oct. 1986, pp. 162-167.
Q. Zhang, C. Xin, and H. Wu, "SecureTrain: An approximation-free and computationally efficient framework for privacy-preserved neural network training, " IEEE Trans. Netw. Sci. Eng., vol. 9, no. 1, pp. 187-202, Jan. 2022, doi: 10.1109/TNSE.2020.3040704.
O. Goldreich, S. Micali, and A. Wigderson, "How to play ANY mental game, " in Proc. 19th Annu. ACM Conf. Theory Comput. (STOC), 1987, pp. 218-229.
C. Dwork, F. McSherry, K. Nissim, and A. Smith, "Calibrating noise to sensitivity in private data analysis, " in Theory of Cryptography. Berlin, Germany: Springer, 2006, pp. 265-284.
D. Boneh, A. Sahai, and B. Waters, "Functional encryption: Definitions and challenges, " in Theory Cryptography. Berlin, Germany: Springer, 2011, pp. 253-273.
C. Gentry, "A fully homomorphic encryption scheme, " Ph.D. Thesis, Dept. Comput. Sci., Stanford Univ., Stanford, CA, USA, 2009.
B. Pulido-Gaytan, A. Tchernykh, J. M. Cortés-Mendoza, M. Babenko, G. Radchenko, A. Avetisyan, and A. Y. Drozdov, "Privacy-preserving neural networks with homomorphic encryption: Challenges and opportunities, " Peer Peer Netw. Appl., vol. 14, no. 3, pp. 1666-1691, May 2021, doi: 10.1007/s12083-021-01076-8.
C. Gentry, A. Sahai, and B.Waters, "Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attributebased, " in Proc. CRYPTO, Santa Barbara, CA, USA, 2013, pp. 75-92.
J. W. Bos, K. Lauter, J. Loftus, and M. Naehrig, "Improved security for a ring-based fully homomorphic encryption scheme, " in Proc. Int. Conf. Cryptogr., 2013, pp. 45-64.
J. Hoffstein, J. Pipher, and J. H. Silverman, "NTRU: A ring-based public key cryptosystem, " in Algorithmic Number Theory. Berlin, Germany: Springer, 1998, pp. 267-288.
A. López-Alt, E. Tromer, and V. Vaikuntanathan, "On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption, " in Proc. 44th Annu. ACM Symp. Theory Comput., May 2012, pp. 1219-1234.
R. Podschwadt, D. Takabi, P. Hu, M. H. Rafiei, and Z. Cai, "A survey of deep learning architectures for privacy-preserving machine learning with fully homomorphic encryption, " IEEE Access, vol. 10, pp. 117477-117500, 2022, doi: 10.1109/ACCESS.2022.3219049.
S. Obla, X. Gong, A. Aloufi, P. Hu, and D. Takabi, "Effective activation functions for homomorphic evaluation of deep neural networks, " IEEE Access, vol. 8, pp. 153098-153112, 2020, doi: 10.1109/ACCESS.2020.3017436.
N. Dowlin, R. Gilad-Bachrach, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing, "CryptoNets: Applying neural networks to encrypted data with high throughput and accuracy, " in Proc. 33rd Int. Conf. Mach. Learn., 2016, pp. 201-210.
M. Kim, Y. Song, S. Wang, Y. Xia, and X. Jiang, "Secure logistic regression based on homomorphic encryption: Design and evaluation, " JMIR Med. Informat., vol. 6, no. 2, Apr. 2018, Art. no. e8805, doi: 10.2196/medinform. 8805.
H. Chabanne, A. De Wargny, J. Milgram, C. Morel, and E. Prouff, "Privacy-preserving classification on deep neural network, " IACR Cryptol. ePrint Arch, vol. 35, Mar. 2017. [Online]. Available: https://eprint.iacr.org/2017/035
C. Bonte and F. Vercauteren, "Privacy-preserving logistic regression training, " BMC Med. Genomics, vol. 11, pp. 13-21, Oct. 2018, doi: 10.1186/s12920-018-0398-y.
A. Kim, Y. Song, M. Kim, K. Lee, and J. H. Cheon, "Logistic regression model training based on the approximate homomorphic encryption, " BMC Med. Genomics, vol. 11, pp. 23-31, Oct. 2018, doi: 10.1186/s12920-018-0401-7.
H. Chen, I. Chillotti, and Y. Song, "Improved bootstrapping for approximate homomorphic encryption, " in Advances in Cryptology EUROCRYPT 2019. Cham, Switzerland: Springer, 2019, pp. 34-54.
K. Han and D. Ki, "Better bootstrapping for approximate homomorphic encryption, " in Topics in Cryptology CT-RSA. Cham, Switzerland: Springer, 2020, pp. 364-390.
A. Al Badawi, C. Jin, J. Lin, C. F. Mun, S. J. Jie, B. H. M. Tan, X. Nan, K. M. M. Aung, and V. R. Chandrasekhar, "Towards the AlexNet moment for homomorphic encryption: HCNN, the first homomorphic CNN on encrypted data with GPUs, " IEEE Trans. Emerg. Topics Comput., vol. 9, no. 3, pp. 1330-1343, Jul. 2021, doi: 10.1109/TETC.2020.3014636.
O.-A. Kwabena, Z. Qin, T. Zhuang, and Z. Qin, "MSCryptoNet: Multi-scheme privacy-preserving deep learning in cloud computing, " IEEE Access, vol. 7, pp. 29344-29354, 2019, doi: 10.1109/ACCESS. 2019.2901219.
J. M. Cortés-Mendoza, "Privacy-preserving logistic regression as a cloud service based on residue number system, " in Russian Supercomputing Days. Cham, Switzerland: Springer, 2020, pp. 598-610.
M. Babenko, A. Tchernykh, B. Pulido-Gaytan, A. Avetisyan, S. Nesmachnow, X. Wang, and F. Granelli, "Towards the sign function best approximation for secure outsourced computations and control, " Mathematics, vol. 10, no. 12, p. 2006, Jun. 2022, doi: 10.3390/math10122006.
M. Kim, H. T. Lee, S. Ling, and H.Wang, "On the efficiency of FHE-based private queries, " IEEE Trans. Depend. Secure Comput., vol. 15, no. 2, pp. 357-363, Mar. 2018, doi: 10.1109/TDSC.2016.2568182.
A. Al Badawi, Y. Polyakov, K. M. M. Aung, B. Veeravalli, and K. Rohloff, "Implementation and performance evaluation of RNS variants of the BFV homomorphic encryption scheme, " IEEE Trans. Emerg. Topics Comput., vol. 9, no. 2, pp. 941-956, Apr. 2021, doi: 10.1109/TETC.2019.2902799.
A. Barenghi, N. Mainardi, and G. Pelosi, "Comparison-based attacks against noise-free fully homomorphic encryption schemes, " in Information and Communications Security. Cham, Switzerland: Springer, 2018, pp. 177-191.
I. Iliashenko and V. Zucca, "Faster homomorphic comparison operations for BGV and BFV, " in Proceedings on Privacy Enhancing Technologies. Lyon, France: HAL Open Science, 2021, pp. 246-264.
J. M. Cortés-Mendoza, G. Radchenko, A. Tchernykh, B. Pulido-Gaytan, M. Babenko, A. Avetisyan, P. Bouvry, and A. Zomaya, "LR-GDRNS: Enhanced privacy-preserving logistic regression algorithms for secure deployment in untrusted environments, " in Proc. IEEE/ACM 21st Int. Symp. Cluster, Cloud Internet Comput. (CCGrid), May 2021, pp. 770-775.
S. Bi andW. J. Gross, "The mixed-radix Chinese remainder theorem and its applications to residue comparison, " IEEE Trans. Comput., vol. 57, no. 12, pp. 1624-1632, Dec. 2008, doi: 10.1109/TC.2008.126.
N. I. Chervyakov, A. S. Molahosseini, P. A. Lyakhov, M. G. Babenko, and M. A. Deryabin, "Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem, " Int. J. Comput. Math., vol. 94, no. 9, pp. 1833-1849, Sep. 2017, doi: 10.1080/00207160.2016.1247439.
T. Van Vu, "Efficient implementations of the Chinese remainder theorem for sign detection and residue decoding, " IEEE Trans. Comput., vol. C-34, no. 7, pp. 646-651, Jul. 1985, doi: 10.1109/TC.1985.1676602.
G. Dimauro, S. Impedovo, and G. Pirlo, "A new technique for fast number comparison in the residue number system, " IEEE Trans. Comput., vol. 42, no. 5, pp. 608-612, May 1993, doi: 10.1109/12.223680.
G. Pirlo and D. Impedovo, "A new class of monotone functions of the residue number system, " Int. J. Math. Models Methods Appl. Sci, vol. 7, no. 9, pp. 803-809, 2013.
M. Babenko, M. Deryabin, S. J. Piestrak, P. Patronik, N. Chervyakov, A. Tchernykh, and A. Avetisyan, "RNS number comparator based on a modified diagonal function, " Electronics, vol. 9, no. 11, p. 1784, Oct. 2020, doi: 10.3390/electronics9111784.
J.-W. Lee, H. Kang, Y. Lee, W. Choi, J. Eom, M. Deryabin, E. Lee, J. Lee, D. Yoo, Y.-S. Kim, and J.-S. No, "Privacy-preserving machine learning with fully homomorphic encryption for deep neural network, " IEEE Access, vol. 10, pp. 30039-30054, 2022, doi: 10.1109/ACCESS.2022.3159694.
P.-A. Fouque, J. Stern, and G.-J. Wackers, "CryptoComputing with rationals, " in Financial Cryptography. Berlin, Germany: Springer, 2003, pp. 136-146.
N. Dowlin, R. Gilad-Bachrach, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing, "Manual for using homomorphic encryption for bioinformatics, " Proc. IEEE, vol. 105, no. 3, pp. 552-567, Mar. 2017, doi: 10.1109/JPROC.2016.2622218.
S. Arita and S. Nakasato, "Fully homomorphic encryption for point numbers, " in Information Security and Cryptology. Cham, Switzerland: Springer, 2017, pp. 253-270.
C. Bonte, C. Bootland, J. W. Bos, W. Castryck, I. Iliashenko, and F. Vercauteren, "Faster homomorphic function evaluation using nonintegral base encoding, " in Cryptographic Hardware and Embedded Systems CHES. Cham, Switzerland: Springer, 2017, pp. 579-600.
A. Jäschke and F. Armknecht, "Accelerating homomorphic computations on rational numbers, " in Applied Cryptography and Network Security. Cham, Switzerland: Springer, 2016, pp. 405-423.
H. Chung and M. Kim, "Encoding of rational numbers and their homomorphic computations for FHE-based applications, " Int. J. Found. Comput. Sci., vol. 29, no. 06, pp. 1023-1044, Sep. 2018, doi: 10.1142/S0129054118500193.
A. Costache, N. P. Smart, S. Vivek, and A.Waller, "Fixed-point arithmetic in SHE schemes, " in Selected Areas in Cryptography SAC 2016. Cham, Switzerland: Springer, 2017, pp. 401-422.
H. Chung, M. Kim, A. A. Badawi, K. M. M. Aung, and B. Veeravalli, "Homomorphic comparison for point numbers with user-controllable precision and its applications, " Symmetry, vol. 12, no. 5, p. 788, May 2020, doi: 10.3390/sym12050788.
S. Meftah, B. H. M. Tan, C. F. Mun, K. M. M. Aung, B. Veeravalli, and V. Chandrasekhar, "DOReN: Toward efficient deep convolutional neural networks with fully homomorphic encryption, " IEEE Trans. Inf. Forensics Security, vol. 16, pp. 3740-3752, 2021, doi: 10.1109/TIFS.2021. 3090959.
N. Zhang, Q. Qin, Z. Hou, B. Yang, S. Yin, S. Wei, and L. Liu, "Efficient comparison and addition for FHE with weighted computational complexity model, " IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 40, no. 9, pp. 1896-1908, Sep. 2021, doi: 10.1109/TCAD.2020.3031266.
R. T. Gregory and E. V. Krishnamurthy, Methods and Applications of Error-Free Computation. Cham, Switzerland: Springer, 2012.
J. H. Cheon, D. Kim, and D. Kim, "Efficient homomorphic comparison methods with optimal complexity, " in Advances in Cryptology ASIACRYPT 2020. Cham, Switzerland: Springer, 2020, pp. 221-256.
J. H. Cheon, M. Kim, and M. Kim, "Search-and-compute on encrypted data, " in Financial Cryptography Data Security. Berlin, Germany: Springer, 2015, pp. 142-159.
Y. Nakatsukasa, Z. Bai, and F. Gygi, "Optimizing Halley's iteration for computing the matrix polar decomposition, " SIAM J. Matrix Anal. Appl., vol. 31, no. 5, pp. 2700-2720, Jan. 2010, doi: 10.1137/090774999.
A. R. Soheili, F. Toutounian, and F. Soleymani, "A fast convergent numerical method for matrix sign function with application in SDEs, " J. Comput. Appl. Math., vol. 282, pp. 167-178, Jul. 2015, doi: 10.1016/j.cam.2014.12.041.
A. Cordero, F. Soleymani, J. R. Torregrosa, and M. Z. Ullah, "Numerically stable improved Chebyshev-Halley type schemes for matrix sign function, " J. Comput. Appl. Math., vol. 318, pp. 189-198, Jul. 2017, doi: 10.1016/j.cam.2016.10.025.
N. J. Higham, Functions of Matrices: Theory and Computation. Philadelphia, PA, USA: SIAM, 2008.
C. S. Kenney and A. J. Laub, "The matrix sign function, " IEEE Trans. Autom. Control, vol. AC-40, no. 8, pp. 1330-1348, Aug. 1995, doi: 10.1109/9.402226.
R. E. Goldschmidt, "Applications of division by convergence, " Ph.D. Thesis, Dept. Elect. Eng., Massachusetts Inst. Technol., Cambridge, MA, USA, 1964.
C. Boura, N. Gama, M. Georgieva, and D. Jetchev, "CHIMERA: Combining ring-LWE-based fully homomorphic encryption schemes, " J. Math. Cryptol., vol. 14, no. 1, pp. 316-338, Aug. 2020, doi: 10.1515/jmc-2019-0026.
D. Chialva and A. Dooms, "Conditionals in homomorphic encryption and machine learning applications, " 2018, arXiv:1810.12380.
M. Babenko, A. Tchernykh, B. Pulido-Gaytan, E. Golimblevskaia, J. M. Cortés-Mendoza, and A. Avetisyan, "Experimental evaluation of homomorphic comparison methods, " in Proc. Ivannikov Ispras Open Conf. (ISPRAS), Dec. 2020, pp. 69-74.
E. Y. Remez, "Sur la determination des polynomes d'approximation de degre donnee, " Commun. Soc. Math. Kharkov, vol. 10, no. 196, pp. 41-63, 1934.
E. Lee, J.-W. Lee, Y.-S. Kim, and J.-S. No, "Optimization of homomorphic comparison algorithm on RNS-CKKS scheme, " IEEE Access, vol. 10, pp. 26163-26176, 2022, doi: 10.1109/ACCESS.2022.3155882.
J.-C. Bajard, P. Martins, L. Sousa, and V. Zucca, "Improving the efficiency of SVM classification with FHE, " IEEE Trans. Inf. Forensics Security, vol. 15, pp. 1709-1722, 2020, doi: 10.1109/TIFS.2019.2946097.
Microsoft Research, "Simple encrypted arithmetic library, " Redmond, WA, USA, Apr. 2020. [Online]. Available: https://github.com/Microsoft/SEAL
Homomorphic Encryption Security Standard, Open Ind., Government, Acad. Consortium Advance Secure Comput., Toronto, ON, Canada, 2018. [Online]. Available: HomomorphicEncryption.org
