From at Least n/3 to at Most 3n: Correcting the Algebraic Immunity of the Hidden Weight Bit Function: Algebraic Immunity Upper Bounds on Weightwise Degree-d Functions and Their Implications

MEAUX, Pierrick

doi:10.1007/978-3-032-06754-8_13

Paper published in a book (Scientific congresses, symposiums and conference proceedings)

From at Least n/3 to at Most 3n: Correcting the Algebraic Immunity of the Hidden Weight Bit Function: Algebraic Immunity Upper Bounds on Weightwise Degree-d Functions and Their Implications

MEAUX, Pierrick

2026 • In Escudero, Daniel (Ed.) Progress in Cryptology – LATINCRYPT 2025 - 9th International Conference on Cryptology and Information Security in Latin America, Proceedings

Peer reviewed

Permalink
https://hdl.handle.net/10993/66319

DOI
10.1007/978-3-032-06754-8_13

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

WWdAI.pdf

Author postprint (367.27 kB)

Download

All documents in ORBilu are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Algebraic immunity; Boolean functions; HWBF; Symmetric functions; D-function; General upper bound; Hamming weights; Hidden weight bit function; Linear feedback shift registers; Property; Security parameters; Upper Bound; Theoretical Computer Science; Computer Science (all)

Abstract :

[en] Weightwise degree-d (WWdd) functions are Boolean functions that, on each set of fixed Hamming weight, coincide with a function of degree at most d. They generalize both symmetric functions and the Hidden Weight Bit Function (HWBF), which has been studied in cryptography for its favorable properties. In this work, we establish a general upper bound on the algebraic immunity of such functions, a key security parameter against algebraic attacks on stream ciphers like filtered Linear Feedback Shift Registers (LFSRs). We construct explicit low-degree annihilators for WWdd functions with small d, and show how to generalize these constructions. As an application, we prove that the algebraic immunity of the HWBF is upper bounded by 3n disproving a result from 2011 that claimed a lower bound of n/3. We then apply our technique to several generalizations of the HWBF proposed since 2021 for homomorphically friendly constructions and LFSR-based ciphers, refining or refuting results from six prior works.

Disciplines :

Mathematics

Author, co-author :

MEAUX, Pierrick ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Coron

External co-authors :

Language :

English

Title :

From at Least n/3 to at Most 3n: Correcting the Algebraic Immunity of the Hidden Weight Bit Function: Algebraic Immunity Upper Bounds on Weightwise Degree-d Functions and Their Implications

Publication date :

2026

Event name :

LATINCRYPT 2025

Event place :

Medellín, Colombia

Event date :

01-10-2025 => 03-10-2025

Audience :

International

Main work title :

Progress in Cryptology – LATINCRYPT 2025 - 9th International Conference on Cryptology and Information Security in Latin America, Proceedings

Editor :

Escudero, Daniel

Publisher :

Springer Science and Business Media Deutschland GmbH

ISBN/EAN :

978-3-03-206753-1

Peer reviewed :

Peer reviewed

Additional URL :

https://link.springer.com/content/pdf/10.1007/978-3-032-06754-8_13

Funders :

ERC - European Research Council

Funding number :

787390

Available on ORBilu :

since 11 November 2025

Statistics

Number of views

41 (0 by Unilu)

Number of downloads

33 (0 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Albrecht, M.R., Rechberger, C., Schneider, T., Tiessen, T., Zohner, M.: Ciphers for MPC and FHE. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 430–454. Springer, Heidelberg (2015). https://doi.org/10. 1007/978-3-662-46800-5_17
Bollig, B., Löbbing, M., Sauerhoff, M., Wegener, I.: On the complexity of the hidden weighted bit function for various BDD models. RAIRO Theor. Inform. Appl. 33(2), 103–116 (1999)
Braeken, A., Preneel, B.: On the algebraic immunity of symmetric Boolean functions. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds.) INDOCRYPT 2005. LNCS, vol. 3797, pp. 35–48. Springer, Heidelberg (2005). https://doi.org/10. 1007/11596219_4
Bryant, R.E.: On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication. IEEE Trans. Comput. 40(2), 205–213 (1991)
Canteaut, A., et al.: Stream ciphers: a practical solution for efficient homomorphic-ciphertext compression. In: Peyrin, T. (ed.) FSE 2016. LNCS, vol. 9783, pp. 313– 333. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-52993-5_16
Canteaut, A., Videau, M.: Symmetric Boolean functions. IEEE Trans. Inf. Theory 2791–2811 (2005)
Carlet, C.: On the degree, nonlinearity, algebraic thickness, and nonnormality of Boolean functions, with developments on symmetric functions. IEEE Trans. Inf. Theory 2178–2185 (2004)
Carlet, C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press (2021). https://doi.org/10.1017/9781108606806
Carlet, C.: A wide class of Boolean functions generalizing the hidden weight bit function. IEEE Trans. Inf. Theory 68(2), 1355–1368 (2022)
Carlet, C., Feng, K.: An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 425–440. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89255-7_26
Carlet, C., Méaux, P.: A complete study of two classes of Boolean functions: direct sums of monomials and threshold functions. IEEE Trans. Inf. Theory 1 (2021)
Carlet, C., Méaux, P., Rotella, Y.: Boolean functions with restricted input and their robustness; application to the FLIP cipher. IACR Trans. Symmetric Cryptol. 2017(3) (2017)
Carlet, C., Sarkar, P.: Constructions of efficiently implementable Boolean functions possessing high nonlinearity and good resistance to algebraic attacks. IACR Cryptol. ePrint Arch. 1305 (2024). https://eprint.iacr.org/archive/2024/1305/20240821:123900.5
Carlet, C., Sarkar, P.: The nonlinear filter model of stream cipher Redivivus. Cryptology ePrint Archive, Paper 2025/160 (2025). https://eprint.iacr.org/2025/160
Chacal, N., Méaux, P., AnonymousBeforeAcceptance: nostalgia cipher: can filtered lfsrs be secure again? ORBilu Archive (2025). https://hdl.handle.net/10993/64454
Chen, Y., Lu, P.: Two classes of symmetric Boolean functions with optimum algebraic immunity: construction and analysis. IEEE Trans. Inf. Theory 57(4), 2522– 2538 (2011). https://doi.org/10.1109/TIT.2011.2111810
Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 3–33. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_1
Cong, K., Das, D., Park, J., Pereira, H.V.: SortingHat: efficient private decision tree evaluation via homomorphic encryption and transciphering. In: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pp. 563–577. Association for Computing Machinery (2022).https://doi.org/10.1145/3548606.3560702
Courtois, N.T.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_11
Courtois, N.T., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_21
Dalai, D.K., Gupta, K.C., Maitra, S.: Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 98–111. Springer, Heidelberg (2005). https://doi.org/10.1007/11502760_7
Dalai, D.K., Mallick, K.: A class of weightwise almost perfectly balanced Boolean functions. Adv. Math. Commun. 18(2), 480–504 (2024)
Dobraunig, C., et al.: Rasta: a cipher with low ANDdepth and few ANDs per bit. In: Shacham, H ., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 662–692. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_22
Ducas, L., Micciancio, D.: FHEW: bootstrapping homomorphic encryption in less than a second. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 617–640. Springer, Heidelberg (2015). https://doi.org/10. 1007/978-3-662-46800-5_24
Fine, N.J.: Binomial coefficients modulo a prime. Am. Math. Monthly 54(10), 589–592 (1947). http://www.jstor.org/stable/2304500
Gini, A., Méaux, P.: On the weightwise nonlinearity of weightwise perfectly balanced functions. Discrete Appl. Math. 322, 320–341 (2022). https://doi.org/10. 1016/j.dam.2022.08.017
Hoffmann, C., Méaux, P., Ricosset, T.: Transciphering, using FiLIP and TFHE for an efficient delegation of computation. In: Bhargavan, K., Oswald, E., Prab-hakaran, M. (eds.) INDOCRYPT 2020. LNCS, vol. 12578, pp. 39–61. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-65277-7_3
Li, J., Su, S.: Construction of weightwise perfectly balanced Boolean functions with high weightwise nonlinearity. Discret. Appl. Math. 279, 218–227 (2020)
Liu, J., Mesnager, S.: Weightwise perfectly balanced functions with high weightwise nonlinearity profile. Des. Codes Cryptogr. 87(8), 1797–1813 (2019)
Mandujano, S., Ku Cauich, J.C., Lara, A.: Studying special operators for the application of evolutionary algorithms in the seek of optimal Boolean functions for cryptography. In: Pichardo Lagunas, O., Martínez-Miranda, J., Martínez Seis, B. (eds.) MICAI 2022. LNCS, vol. 13612, pp. 383–396. Springer, Cham (2022). https://doi. org/10.1007/978-3-031-19493-1_30
Mariot, L., Picek, S., Jakobovic, D., Djurasevic, M., Leporati, A.: Evolutionary construction of perfectly balanced Boolean functions. In: 2022 IEEE Congress on Evolutionary Computation (CEC), pp. 1–8. IEEE Press (2022)
Méaux, P.: On the fast algebraic immunity of majority functions. In: Schwabe, P., Thériault, N. (eds.) LATINCRYPT 2019. LNCS, vol. 11774, pp. 86–105. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30530-7_5
Méaux, P., Carlet, C., Journault, A., Standaert, F.-X.: Improved filter permutators for efficient FHE: better instances and implementations. In: Hao, F., Ruj, S., Sen Gupta, S. (eds.) INDOCRYPT 2019. LNCS, vol. 11898, pp. 68–91. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-35423-7_4
Méaux, P., Journault, A., Standaert, F.-X., Carlet, C.: Towards stream ciphers for efficient FHE with low-noise ciphertexts. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016, Part I. LNCS, vol. 9665, pp. 311–343. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_13
Méaux, P., Ozaim, Y.: On the cryptographic properties of weightwise affine and weightwise quadratic functions. Discret. Appl. Math. 355, 13–29 (2024)
Méaux, P., Park, J., Pereira, H.V.L.: Towards practical transciphering for FHE with setup independent of the plaintext space. IACR Commun. Cryptol. 1(1), 20 (2024). https://doi.org/10.62056/ANXRXRXQI
Méaux, P., Seuré, T., Tang, D.: The revisited hidden weight bit function. IACR Cryptol. ePrint Arch. 2022 (2024). https://eprint.iacr.org/2024/2022. To appear at Selected Areas in Cryptography – SAC 2025
Meier, W., Pasalic, E., Carlet, C.: Algebraic attacks and decomposition of Boolean functions. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 474–491. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_28
Mesnager, S., Su, S.: On constructions of weightwise perfectly balanced Boolean functions. Cryptogr. Commun. (2021)
Naehrig, M., Lauter, K., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop, CCSW 2011, pp. 113–124. Association for Computing Machinery, New York (2011)
Sarkar, P., Maitra, S.: Balancedness and correlation immunity of symmetric Bo olean functions. Discrete Math. 2351 – 2358 (2007)
Tang, D., Liu, J.: A family of weightwise (almost) perfectly balanced Boolean functions with optimal algebraic immunity. Cryptogr. Commun. 11(6), 1185–1197 (2019). https://doi.org/10.1007/s12095-019-00374-6
Wang, Q., Carlet, C., Stanica, P., Tan, C.H.: Cryptographic properties of the hidden weighted bit function. Discret. Appl. Math. 174, 1–10 (2014)
Wang, Q., Tan, C.H., Stanica, P.: Concatenations of the hidden weighted bit function and their cryptographic properties. Adv. Math. Commun. 8(2), 153–165 (2014)