A Complete Study of Two Classes of Boolean Functions: Direct Sums of Monomials and Threshold Functions

[en] In this paper, we make a comprehensive study of two classes of Boolean functions whose interest originally comes from hybrid symmetric-FHE encryption (with stream ciphers like FiLIP), but which also present much interest for general stream ciphers. The functions in these two classes are cheap and easy to implement, and they allow the resistance to all classical attacks and to their guess and determine variants as well. We determine exactly all the main cryptographic parameters (algebraic degree, resiliency order, nonlinearity, algebraic immunity) for all functions in these two classes, and we give close bounds for the others (fast algebraic immunity, the dimension of the space of annihilators of minimal degree). This is the first time that this is done for all functions in large classes of cryptographic interest.

Disciplines :

Mathematics

Author, co-author :

Carlet, Claude

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

External co-authors :

yes

Language :

English

Title :

A Complete Study of Two Classes of Boolean Functions: Direct Sums of Monomials and Threshold Functions

Publication date :

2022

Journal title :

IEEE Transactions on Information Theory

Volume :

Issue :

Pages :

3404--3425

Peer reviewed :

Peer reviewed

Focus Area :

Security, Reliability and Trust

Additional URL :

https://doi.org/10.1109/TIT.2021.3139804

Available on ORBilu :

since 25 October 2022

Statistics

Number of views

87 (3 by Unilu)

Number of downloads

77 (3 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

WoS citations^™

Bibliography

P. Méaux, A. Journault, F.-X. Standaert, and C. Carlet, "Towards stream ciphers for efficient FHE with low-noise ciphertexts," in Proc. EUROCRYPT, in Lecture Notes in Computer Science, vol. 9665, M. Fischlin and J.-S. Coron, Eds. Heidelberg, Germany: Springer, May 2016, pp. 311-343.
P. Méaux, C. Carlet, A. Journault, and F.-X. Standaert, "Improved filter permutators for efficient FHE: Better instances and implementations," in Proc. 20th Int. Conf. Cryptol. India, in Lecture Notes in Computer Science, Hyderabad, India, vol. 11898, F. Hao, S. Ruj, and S. S. Gupta, Eds. Springer, Dec. 2019, pp. 68-91, doi: 10.1007/978-3-030-35423-7_4.
C. Gentry, "Fully homomorphic encryption using ideal lattices," in Proc. 41st Annu. ACM Symp. Theory Comput., M. Mitzenmacher, Ed. New York, NY, USA: ACM Press, 2009, pp. 169-178.
M. Naehrig, K. E. Lauter, and V. Vaikuntanathan, "Can homomorphic encryption be practical?" in Proc. 3rd ACM Cloud Comput. Secur. Workshop (CCSW), Chicago, IL, USA, C. Cachin and T. Ristenpart, Eds., Oct. 2011, pp. 113-124. [Online]. Available: https://dl.acm.org/citation. cfm?id=2046682
M. R. Albrecht, C. Rechberger, T. Schneider, T. Tiessen, and M. Zohner, "Ciphers for MPC and FHE," in Proc. IACR Cryptol. ePrint Arch., 2016, p. 687.
A. Canteaut et al., "Stream ciphers: A practical solution for efficient homomorphic-ciphertext compression," in Proc. FSE, in Lecture Notes in Computer Science, vol. 9783, T. Peyrin, Ed. Heidelberg, Germany: Springer, Mar. 2016, pp. 313-333.
C. Dobraunig et al., "Rasta: A cipher with low ANDdepth and few ANDs per bit," in Proc. CRYPTO, 2018, pp. 662-692.
C. Carlet and P. Méaux, "Boolean functions for homomorphic-friendly stream ciphers," in Proc. Conf. Algebra, Codes Cryptol. (A2C). Cham, Switzerland: Springer, 2019, pp. 166-182.
C. Carlet, Boolean Functions for Cryptography Coding Theory. Cambridge, U.K.: Cambridge Univ. Press, 2021.
D. K. Dalai, S. Maitra, and S. Sarkar, "Basic theory in construction of Boolean functions with maximum possible annihilator immunity," Des., Codes Cryptogr., vol. 40, no. 1, pp. 41-58, 2006.
C. Carlet and S. Mesnager, "Four decades of research on bent functions," Des., Codes Cryptogr., vol. 78, no. 1, pp. 5-50, Jan. 2016.
S. Mesnager, Bent Functions-Fundamentals and Results. Springer, 2016, doi: 10.1007/978-3-319-32595-8.
C. Carlet, "On the degree, nonlinearity, algebraic thickness, and nonnormality of Boolean functions, with developments on symmetric functions," IEEE Trans. Inf. Theory, vol. 50, no. 9, pp. 2178-2185, Sep. 2004.
A. Canteaut and M. Videau, "Symmetric Boolean functions," IEEE Trans. Inf. Theory, vol. 51, no. 8, pp. 2791-2811, Aug. 2005.
L. Qu, C. Li, and K. Feng, "A note on symmetric Boolean functions with maximum algebraic immunity in odd number of variables," IEEE Trans. Inf. Theory, vol. 53, no. 8, pp. 2908-2910, Aug. 2007.
P. Sarkar and S. Maitra, "Balancedness and correlation immunity of symmetric Boolean functions," Discrete Math., vol. 307, nos. 19-20, pp. 2351-2358, Sep. 2007.
L. Qu, K. Feng, F. Liu, and L. Wang, "Constructing symmetric Boolean functions with maximum algebraic immunity," IEEE Trans. Inf. Theory, vol. 55, no. 5, pp. 2406-2412, May 2009.
B. Applebaum and S. Lovett, "Algebraic attacks against random local functions and their countermeasures," in Proc. 48th ACM STOC, D. Wichs and Y. Mansour, Eds. New York, NY, USA: ACM Press, Jun. 2016, pp. 1087-1100.
C. Carlet, P. Méaux, and Y. Rotella, "Boolean functions with restricted input and their robustness; application to the FLIP cipher," IACR Trans. Symmetric Cryptol., vol. 2017, no. 3, pp. 192-227, 2017.
A. Braeken and B. Preneel, "On the algebraic immunity of symmetric Boolean functions," in Proc. 6th Int. Conf. Cryptol. India, Bangalore, India, Dec. 2005, pp. 35-48.
D. Tang, R. Luo, and X. Du, "The exact fast algebraic immunity of two subclasses of the majority function," IEICE Trans. Fundam. Electron., Commun. Comput. Sci., vol. E99.A, no. 11, pp. 2084-2088, 2016.
G. Couteau, A. Dupin, P. Méaux, M. Rossi, and Y. Rotella, "On the concrete security of Goldreich's pseudorandom generator," in Proc. ASIACRYPT, in Lecture Notes in Computer Science, vol. 11273, T. Peyrin and S. D. Galbraith, Eds. Springer, 2018, pp. 96-124.