Boolean Functions; Algebraic Immunity; , Direct Sum
Résumé :
[en] In this paper, we study sufficient conditions to improve the lower bound on the algebraic immunity of a direct sum of Boolean functions.
We exhibit three properties on the component functions such that satisfying one of them is sufficient to ensure that the algebraic immunity of their direct sum exceeds the maximum of their algebraic immunities.
These properties can be checked while computing the algebraic immunity and they allow to determine better the security provided by functions central in different cryptographic constructions such as stream ciphers, pseudorandom generators, and weak pseudorandom functions.
We provide examples for each property and determine the exact algebraic immunity of candidate constructions.
Disciplines :
Mathématiques
Auteur, co-auteur :
MEAUX, Pierrick ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Coron
Co-auteurs externes :
no
Langue du document :
Anglais
Titre :
On the algebraic immunity of direct sum constructions
Applebaum, Benny, Lovett, Shachar, Algebraic attacks against random local functions and their countermeasures. Wichs, Daniel, Mansour, Yishay, (eds.) 48th ACM STOC, 2016, ACM Press.
Armknecht, Frederik, Carlet, Claude, Gaborit, Philippe, Künzli, Simon, Meier, Willi, Ruatta, Olivier, Efficient computation of algebraic immunity for algebraic and fast algebraic attacks. Vaudenay, Serge, (eds.) EUROCRYPT 2006 LNCS, vol. 4004, 2006, Springer, Heidelberg.
Dan Boneh, Yuval Ishai, Alain Passelègue, Amit Sahai, David J. Wu, Exploring Crypto Dark Matter: - New Simple PRF Candidates and Their Applications, in: Theory of Cryptography - 16th International Conference, TCC 2018, Panaji, India, November 11-14, 2018, Proceedings, Part II, 2018, pp. 699–729.
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.
Carlet, Claude, On the higher order nonlinearities of algebraic immune functions. Dwork, Cynthia, (eds.) CRYPTO 2006 LNCS, vol. 4117, 2006, Springer, Heidelberg, 584–601.
Carlet, Claude, Boolean Functions for Cryptography and Coding Theory. 2021, Cambridge University Press, 10.1017/9781108606806.
Carlet, Claude, Méaux, Pierrick, Boolean functions for homomorphic-friendly stream ciphers. Algebra, Codes and Cryptology, 2019, 166–182.
Carlet, Claude, Méaux, Pierrick, A complete study of two classes of boolean functions: Direct sums of monomials and threshold functions. IEEE Trans. Inform. Theory, 2021.
Courtois, Nicolas, Meier, Willi, Algebraic attacks on stream ciphers with linear feedback. Biham, Eli, (eds.) EUROCRYPT 2003 LNCS, 2656, 2003, Springer, Heidelberg.
Deepak Kumar Dalai, Computing the Rank of Incidence Matrix and the Algebraic Immunity of Boolean Functions, Report 2013/273, 2013, Cryptology ePrint Archive.
Dalai, Deepak Kumar, Maitra, Subhamoy, Sarkar, Sumanta, Basic theory in construction of boolean functions with maximum possible annihilator immunity. Des. Codes Cryptogr., 2006.
Dillon, J., Elementary Hadamard Difference Sets. (Ph.D. thesis), 1976, University of Maryland, USA.
Gay, Romain, Jain, Aayush, Lin, Huijia, Sahai, Amit, Indistinguishability obfuscation from simple-to-state hard problems: New assumptions, new techniques, and simplification. 2020, 764 2020, IACR Cryptol. EPrint Arch., URL https://eprint.iacr.org/2020/764.
Goldreich, Oded, Foundations of Cryptography: Basic Tools, Vol. 1. 2001, Cambridge University Press, Cambridge, UK, xix + 372.
Lin Jiao, Bin Zhang, M. Wang, Revised algorithms for computing algebraic immunity against algebraic and fast algebraic attacks, in: ISC, 2014.
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.) EUROCRYPT 2016, Part I LNCS, vol. 9665, 2016, Springer, Heidelberg, 311–343.
Meier, Willi, Pasalic, Enes, Carlet, Claude, Algebraic attacks and decomposition of boolean functions. EUROCRYPT, Vol. 3027, 2004, Springer, 474–491.
Mesnager, Sihem, Improving the lower bound on the higher order nonlinearity of boolean functions with prescribed algebraic immunity. IEEE Trans. Inf. Theory 54:8 (2008), 3656–3662.
Naehrig, Michael, Lauter, Kristin E., Vaikuntanathan, Vinod, Can homomorphic encryption be practical?. Cachin, Christian, Ristenpart, Thomas, (eds.) ACM Cloud Computing Security Workshop, CCSW, 2011, ACM, 113–124.
Rizomiliotis, Panagiotis, Improving the high order nonlinearity lower bound for boolean functions with given algebraic immunity. Discrete Appl. Math. 158 (2010), 2049–2055.
Rothaus, O.S, On “bent” functions. J. Combin. Theory Ser. A 20:3 (1976), 300–305.
