On the algebraic immunity of direct sum constructions

Meaux, Pierrick

doi:10.1016/j.dam.2022.05.021

Download

Article (Scientific journals)

On the algebraic immunity of direct sum constructions

Meaux, Pierrick

2022 • In Discrete Applied Mathematics, 320, p. 223--234

Peer reviewed

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

DOI
10.1016/j.dam.2022.05.021

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

AIofDSfinal.pdf

Author preprint (332.49 kB)

Download

All documents in ORBilu are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Boolean Functions; Algebraic Immunity; , Direct Sum

Abstract :

[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 :

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 :

On the algebraic immunity of direct sum constructions

Publication date :

2022

Journal title :

Discrete Applied Mathematics

Volume :

320

Pages :

223--234

Peer reviewed :

Peer reviewed

Focus Area :

Security, Reliability and Trust

Additional URL :

https://doi.org/10.1016/j.dam.2022.05.021

Available on ORBilu :

since 25 October 2022

Statistics

Number of views

42 (3 by Unilu)

Number of downloads

20 (1 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

WoS citations^™

Bibliography

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.
Boyle, Elette, Couteau, Geoffroy, Gilboa, Niv, Ishai, Yuval, Kohl, Lisa, Scholl, Peter, Correlated pseudorandom functions from variable-density LPN. 61st FOCS, 2020, IEEE Computer Society Press.
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.
Hamann, Matthias, Krause, Matthias, Meier, Willi, LIZARD - A lightweight stream cipher for power-constrained devices. IACR Trans. Symmetric Cryptol. 2017:1 (2017), 45–79.
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.