[en] Weightwise degree-d functions are Boolean functions that take the values of a function of degree at most d on each set of fixed Hamming weight.
The class of weightwise affine functions encompasses both the symmetric functions and the Hidden Weight Bit Function (HWBF).
The good cryptographic properties of the HWBF, except for the nonlinearity, motivates to investigate a larger class with functions that share the good properties and have a better nonlinearity.
Additionally, the homomorphic friendliness of symmetric functions exhibited in the context of hybrid homomorphic encryption and the recent results on homomorphic evaluation of Boolean functions make this class of functions appealing for efficient privacy-preserving protocols.
In this article we realize the first study on weightwise degree-d functions, focusing on weightwise affine and weightwise quadratic functions.
We show some properties on these new classes of functions, in particular on the subclass of cyclic weightwise functions. We provide balanced constructions and prove nonlinearity upper bounds for all cyclic weightwise affine functions and for a family of weightwise quadratic functions. We complement our work with experimental results, they show that other cyclic weightwise linear functions than the HWBF have better cryptographic parameters, and considering weightwise quadratic functions allows to reach higher algebraic immunity and substantially better nonlinearity.
Disciplines :
Mathématiques
Auteur, co-auteur :
MEAUX, Pierrick ✱; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Coron
OZAIM, Yassine
✱ Ces auteurs ont contribué de façon équivalente à la publication.
Co-auteurs externes :
yes
Langue du document :
Anglais
Titre :
On the cryptographic properties of weightwise affine and weightwise quadratic functions
Titre original :
[en] On the cryptographic properties of weightwise affine and weightwise quadratic functions
Albrecht, Martin R., Rechberger, Christian, Schneider, Thomas, Tiessen, Tyge, Zohner, Michael, Ciphers for MPC and FHE. Advances in Cryptology – EUROCRYPT 2015, 2015, Springer Berlin Heidelberg, 430–454.
Thibault Balenbois, Jean-Baptiste Orfila, Nigel Smart, Trivial Transciphering With Trivium and TFHE, in: Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, 2023, pp. 69–78.
Bendoukha, Adda-Akram, Clet, Pierre-Emmanuel, Boudguiga, Aymen, Sirdey, Renaud, Optimized stream-cipher-based transciphering by means of functional-bootstrapping. Atluri, Vijayalakshmi, Ferrara, Anna Lisa, (eds.) Data and Applications Security and Privacy XXXVII, 2023, Springer Nature Switzerland, Cham, 91–109.
Bendoukha, Adda-Akram, Stan, Oana, Sirdey, Renaud, Quero, Nicolas, Freitas, Luciano, Practical homomorphic evaluation of block-Cipher-based hash functions with applications. 2023 Cryptology ePrint Archive, Paper 2023/480.
Bollig, Beate, Löbbing, Martin, Sauerhoff, Martin, Wegener, Ingo, On the complexity of the hidden weighted bit function for various BDD models. RAIRO - Theoret. Inform. Appl. 33:2 (1999), 103–116.
Bon, Nicolas, Pointcheval, David, Rivain, Matthieu, Optimized homomorphic evaluation of Boolean functions. 2023 Cryptology ePrint Archive, Paper 2023/1589.
An Braeken, Bart Preneel, On the Algebraic Immunity of Symmetric Boolean Functions, in: Progress in Cryptology - INDOCRYPT 2005, 6th International Conference on Cryptology in India, Bangalore, India, December 10-12, 2005, Proceedings, 2005, pp. 35–48.
Bryant, Randal E., On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication. IEEE Trans. Comput. 40:2 (1991), 205–213.
Canteaut, Anne, Carpov, Sergiu, Fontaine, Caroline, Lepoint, Tancrède, Naya-Plasencia, María, Paillier, Pascal, Sirdey, Renaud, Stream Ciphers: A practical solution for efficient homomorphic-Ciphertext compression. Fast Software Encryption, 2016, 313–333.
Carlet, Claude, On the degree, nonlinearity, algebraic thickness, and nonnormality of Boolean functions, with developments on symmetric functions. IEEE Trans. Inform. Theory, 2004, 2178–2185.
Carlet, Claude, Boolean Functions for Cryptography and Coding Theory. 2021, Cambridge University Press.
Carlet, Claude, A wide class of Boolean functions generalizing the hidden weight bit function. IEEE Trans. Inf. Theory 68:2 (2022), 1355–1368.
Carlet, Claude, Méaux, Pierrick, A complete study of two classes of Boolean functions: Direct sums of monomials and threshold functions. IEEE Trans. Inf. Theory 68:5 (2022), 3404–3425.
Carlet, Claude, Méaux, Pierrick, Rotella, Yann, Boolean functions with restricted input and their robustness; application to the FLIP Cipher. IACR Trans. Symmetric Cryptol., 2017(3), 2017.
Chen, Yindong, Lu, Peizhong, Two classes of symmetric Boolean functions with optimum algebraic immunity: Construction and analysis. IEEE Trans. Inform. Theory 57:4 (2011), 2522–2538.
Chillotti, Ilaria, Gama, Nicolas, Georgieva, Mariya, Izabachène, Malika, Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. Cheon, Jung Hee, Takagi, Tsuyoshi, (eds.) Advances in Cryptology – ASIACRYPT 2016, 2016, 3–33.
Cong, Kelong, Das, Debajyoti, Park, Jeongeun, Pereira, Hilder V.L., SortingHat: Efficient private decision tree evaluation via homomorphic encryption and transciphering. Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022, Association for Computing Machinery, 563–577.
Dalai, Deepak Kumar, Maitra, Subhamoy, Sarkar, Sumanta, Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Des. Codes Cryptogr., 2006.
Dobraunig, Christoph, Eichlseder, Maria, Grassi, Lorenzo, Lallemand, Virginie, Leander, Gregor, List, Eik, Mendel, Florian, Rechberger, Christian, Rasta: A Cipher with low ANDdepth and few ANDs per bit. CRYPTO 2018, 2018, 662–692.
Ducas, Léo, Micciancio, Daniele, FHEW: Bootstrapping homomorphic encryption in less than a second. Oswald, Elisabeth, Fischlin, Marc, (eds.) Advances in Cryptology – EUROCRYPT 2015, 2015, 617–640.
Gini, Agnese, Méaux, Pierrick, On the weightwise nonlinearity of weightwise perfectly balanced functions. Discrete Appl. Math. 322 (2022), 320–341.
Gini, Agnese, Méaux, Pierrick, On the algebraic immunity of weightwise perfectly balanced functions. Aly, Abdelrahaman, Tibouchi, Mehdi, (eds.) Progress in Cryptology - LATINCRYPT 2023 - 8th International Conference on Cryptology and Information Security in Latin America, LATINCRYPT 2023, Quito, Ecuador, October 3-6, 2023, Proceedings Lecture Notes in Computer Science, vol. 14168, 2023, Springer, 3–23.
Hoffmann, Clément, Méaux, Pierrick, Ricosset, Thomas, Transciphering, using FiLIP and TFHE for an efficient delegation of computation. Bhargavan, Karthikeyan, Oswald, Elisabeth, Prabhakaran, Manoj, (eds.) Progress in Cryptology - INDOCRYPT 2020 - 21st International Conference on Cryptology in India, Bangalore, India, December 13-16, 2020, Proceedings Lecture Notes in Computer Science, vol. 12578, 2020, Springer, 39–61.
Liu, Jian, Mesnager, Sihem, Weightwise perfectly balanced functions with high weightwise nonlinearity profile. Des. Codes Cryptogr. 87:8 (2019), 1797–1813.
MacWilliams, Jessie, Sloane, Niels, The Theory of Error-Correcting Codes. Second ed., 1978, North-holland Publishing Company.
Mandujano, Sara, Ku Cauich, Juan Carlos, Lara, Adriana, Studying special operators for the application of evolutionary algorithms in the seek of optimal Boolean functions for cryptography. Pichardo Lagunas, Obdulia, Martínez-Miranda, Juan, Martínez Seis, Bella, (eds.) Advances in Computational Intelligence, 2022, Springer Nature Switzerland, Cham, 383–396.
Méaux, Pierrick, On the fast algebraic immunity of majority functions. Schwabe, Peter, Thériault, Nicolas, (eds.) Progress in Cryptology - LATINCRYPT LNCS, vol. 11774, 2019, Springer, 86–105.
Méaux, Pierrick, On the fast algebraic immunity of threshold functions. Cryptogr. Commun. 13:5 (2021), 741–762.
Méaux, Pierrick, Carlet, Claude, Journault, Anthony, Standaert, François-Xavier, Improved filter permutators for efficient FHE: Better instances and implementations. Hao, Feng, Ruj, Sushmita, Gupta, Sourav Sen, (eds.) Progress in Cryptology - INDOCRYPT LNCS, vol. 11898, 2019, Springer, 68–91.
Méaux, Pierrick, Journault, Anthony, Standaert, François-Xavier, Carlet, Claude, Towards stream Ciphers for efficient FHE with low-noise Ciphertexts. Fischlin, Marc, Coron, Jean-Sébastien, (eds.) Advances in Cryptology – EUROCRYPT 2016, 2016, 311–343.
Méaux, Pierrick, Park, Jeongeun, Pereira, Hilder V.L., Towards practical transciphering for FHE with setup independent of the plaintext space. 2023 Cryptology ePrint Archive, Paper 2023/1531.
Meier, Willi, Pasalic, Enes, Carlet, Claude, Algebraic attacks and decomposition of Boolean functions. Cachin, Christian, Camenisch, Jan L., (eds.) Advances in Cryptology - EUROCRYPT 2004, 2004, Springer Berlin Heidelberg, Berlin, Heidelberg, 474–491.
Mesnager, Sihem, Su, Sihong, Li, Jingjing, On concrete constructions of weightwise perfectly balanced functions with optimal algebraic immunity and high weightwise nonlinearity. Bool. Funct. Appl., 2021.
Naehrig, Michael, Lauter, Kristin, Vaikuntanathan, Vinod, Can homomorphic encryption be practical?. Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop, CCSW ’11, 2011, Association for Computing Machinery, New York, NY, USA, 113–124.
Sarkar, Palash, Maitra, Subhamoy, Balancedness and correlation immunity of symmetric Boolean functions. Discrete Math., 2007, 2351–2358.
Tang, Deng, Liu, Jian, A family of weightwise (almost) perfectly balanced Boolean functions with optimal algebraic immunity. Cryptogr. Commun. 11:6 (2019), 1185–1197.
Daphné Trama, Pierre-Emmanuel Clet, Aymen Boudguiga, Renaud Sirdey, A Homomorphic AES Evaluation in Less than 30 Seconds by Means of TFHE, in: Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, 2023, pp. 79–90.
Wang, Qichun, Carlet, Claude, Stanica, Pantelimon, Tan, Chik How, Cryptographic properties of the hidden weighted bit function. Discrete Appl. Math. 174 (2014), 1–10.
Wang, Qichun, Tan, Chik How, Stanica, Pantelimon, Concatenations of the hidden weighted bit function and their cryptographic properties. Adv. Math. Commun. 8:2 (2014), 153–165.
Yan, Lili, Cui, Jingyi, Liu, Jian, Xu, Guangquan, Han, Lidong, Jolfaei, Alireza, Zheng, Xi, IGA: An improved genetic algorithm to construct weightwise (almost) perfectly balanced Boolean functions with high weightwise nonlinearity. Proceedings of the 2023 ACM Asia Conference on Computer and Communications Security ASIA CCS ’23, 2023, Association for Computing Machinery, New York, NY, USA, 638–648.
Zhao, Qinglan, Li, Mengran, Chen, Zhixiong, Qin, Baodong, Zheng, Dong, A unified construction of weightwise perfectly balanced Boolean functions. 2023 Cryptology ePrint Archive, Paper 2023/460.
