nach oben

Designs, Codes and Cryptography

Erschienen in:

10.10.2017

Boolean functions with maximum algebraic immunity: further extensions of the Carlet–Feng construction

verfasst von: Konstantinos Limniotis, Nicholas Kolokotronis

Erschienen in: Designs, Codes and Cryptography | Ausgabe 8/2018

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The algebraic immunity of Boolean functions is studied in this paper. More precisely, having the prominent Carlet–Feng construction as a starting point, we propose a new method to construct a large number of functions with maximum algebraic immunity. The new method is based on deriving new properties of minimal codewords of the punctured Reed–Muller code \(\mathrm{RM}^{\star }(\lfloor \frac{n-1}{2}\rfloor ,n)\) for any n, allowing—if n is odd—for efficiently generating large classes of new functions that cannot be obtained by other known constructions. It is shown that high nonlinearity, as well as good behavior against fast algebraic attacks, is also attainable.

Vorheriger Artikel Chosen ciphertext secure keyed-homomorphic public-key cryptosystems

Nächster Artikel Self-reciprocal polynomials and coterm polynomials

Canteaut A.: Open problems related to algebraic attacks on stream ciphers. In: International Workshop on Coding and Cryptography (WCC), pp. 1–11 (2005).

Carlet C.: Boolean functions for cryptography and error correcting codes. Chapter of the monography. In: Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 257–397. Cambridge University Press, Cambridge. http://www-roc.inria.fr/secret/Claude.Carlet/pubs.html (2010).

Carlet C., Dalai D.K., Gupta K.C., Maitra S.: Algebraic immunity for cryptographically significant Boolean functions: analysis and construction. IEEE Trans. Inf. Theory 52, 3105–3121 (2006).MathSciNetCrossRefMATH

Carlet C.: Constructing balanced functions with optimum algebraic immunity. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 451–455 (2007).

Carlet C., Feng K.: An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity. In: Asiacrypt 2008. Lecture Notes in Computer Science, vol. 5350, pp. 425–440 . Springer, Heidelberg (2008).

Carlet C. and Gaborit P.: On the construction of balanced Boolean functions with a good algebraic immunity. In: Proceedings of the IEEE International Symposium on Information Theory (ISIT), pp. 1101–1105 (2005).

Carlet C., Zeng X., Li C., Hu L.: Further properties of several classes of Boolean functions with optimum algebraic immunity. Des. Codes Cryptogr. 52, 303–338 (2009).MathSciNetCrossRefMATH

Carlet C.: Comments on “Constructions of cryptographically significant Boolean functions using primitive polynomials”. IEEE Trans. Inf. Theory 57, 4852–4853 (2011).MathSciNetCrossRefMATH

Chen Y., Lu P.: Two classes of symmetric Boolean functions with optimum algebraic immunity: construction and analysis. IEEE Trans. Inf. Theory 57, 2522–2538 (2011).MathSciNetCrossRefMATH

10.

Courtois N., Meier W.: Algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology—Eurocrypt 2003. Lecture Notes in Computer Science, vol. 2656, pp. 345–359. Springer, Heidelberg (2003).

11.

Courtois N. : Fast algebraic attacks on stream ciphers with linear feedback. In: Advances in Cryptology—Crypto 2003. Lecture Notes in Computer Science, vol. 2729, pp. 176–194. Springer, Heidelberg (2003).

12.

Dalai D.K., Maitra S., Sarkar S.: Basic theory in construction of Boolean functions with maximum possible annihilator immunity. Des. Codes Cryptogr. 40, 41–58 (2006).MathSciNetCrossRefMATH

13.

Li N., Qi W.: Construction and analysis of Boolean functions of \(2t + 1\) variables with maximum algebraic immunity. In: Advances in Cryptology—Asiacrypt 2006, vol. 4284, pp. 84–98. Lecture Notes in Computer Science. Springer, Heidelberg (2006).

14.

Li J., Carlet C., Zeng X., Li C., Hu L., Shan J.: Two constructions of balanced Boolean functions with optimal algebraic immunity, high nonlinearity and good behavior against fast algebraic attacks. Des. Codes Cryptogr. 76, 279–305 (2015).MathSciNetCrossRefMATH

15.

Lidl R., Niederreiter H.: Finite Fields, 2nd edn. Encyclopedia of Mathematics and Its Applications, vol. 20. Cambridge University Press, Cambridge (1996).

16.

Limniotis K., Kolokotronis N., Kalouptsidis N.: Constructing Boolean functions in odd number of variables with maximum algebraic immunity. In: IEEE International Symposium on Information Theory (ISIT), pp. 2686–2690 (2011).

17.

Limniotis K., Kolokotronis N., Kalouptsidis N.: Secondary constructions of Boolean functions with maximum algebraic immunity. Cryptogr. Comm. 5, 179–199 (2013).MathSciNetCrossRefMATH

18.

Limniotis K., Kolokotronis N.: Boolean functions with maximum algebraic immunity based on properties of punctured Reed–Muller codes. In: BalkanCryptSec 2015. Lecture Notes in Computer Science, vol. 9540, pp. 3–16. Springer, Heidelberg (2016).

19.

Liu M., Zhang Y., Lin D.: Perfect algebraic immune functions. In: Advances in Cryptology—Asiacrypt 2012. Lecture Notes in Computer Science, vol. 7658, pp. 172–189. Springer, Heidelberg (2012).

20.

Liu M., Lin D.: Fast algebraic attacks and decomposition of symmetric Boolean functions. IEEE Trans. Inf. Theory 57, 4817–4821 (2011).MathSciNetCrossRefMATH

21.

Liu M., Lin D.: Almost perfect algebraic immune functions with good nonlinearity. IEEE International Symposium on Information Theory, pp. 1837–1841 (2014).

22.

MacWilliams F., Sloane N.: The Theory of Error Correcting Codes. North-Holland, Amsterdam (1977).MATH

23.

Meier W., Pasalic E., Carlet C.: Algebraic attacks and decomposition of Boolean functions. In: Advances in Cryptology—Eurocrypt 2004. Lecture Notes in Computer Science, vol. 3027, pp. 474–491. Springer, Heidelberg (2004).

24.

Mesnager S.: Bent and hyper-bent functions in polynomial form and their link with some exponential sums and Dickson polynomials. IEEE Trans. Inf. Theory 57, 5996–6009 (2011).MathSciNetCrossRefMATH

25.

Mesnager S., Cohen G.: Cyclic codes and algebraic immunity of Boolean functions. ITW 2015, 1–5 (2015).

26.

Pasalic E.: Almost fully optimized infinitive classes of Boolean functions resistant to (fast) algebraic cryptanalysis. ICISC 2008. Lecture Notes in Computer Science, vol. 5461, pp. 399–414. Springer, Heidelberg (2008).

27.

Qu L., Feng K., Liu F., Wang L.: Constructing symmetric Boolean functions with maximum algebraic immunity. IEEE Trans. Inf. Theory 55, 2406–2412 (2009).MathSciNetCrossRefMATH

28.

Rizomiliotis P.: On the resistance of Boolean functions against algebraic attacks using univariate polynomial representation. IEEE Trans. Inf. Theory 56, 4014–4024 (2010).MathSciNetCrossRefMATH

29.

Sarkar S., Maitra S.: Construction of rotation symmetric Boolean functions on odd number of variables with maximum algebraic immunity. AAECC 2007. Lecture Notes in Computer Science, vol. 4851, pp. 271–280. Springer, Heidelberg (2007).

30.

Su S., Tang X., Zeng X.: A systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of the Reed-Muller code. Des. Codes Cryptogr. 72, 653–673 (2014).MathSciNetCrossRefMATH

31.

Su S., Tang X.: Construction of rotation symmetric Boolean functions with optimal algebraic immunity and high nonlinearity. Des. Codes Cryptogr. 71, 183–199 (2014).MathSciNetCrossRefMATH

32.

Tang D., Carlet C., Tang X.: Highly nonlinear Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks. IEEE Trans. Inf. Theory 59, 653–664 (2013).MathSciNetCrossRefMATH

33.

Tang D., Carlet C., Tang X., Zhou Z.: Construction of highly nonlinear \(1\)-Resilient Boolean functions with optimal algebraic immunity and provably high fast algebraic immunity. IEEE Trans. Inf. Theory 63, 6113–6125 (2017).MathSciNetMATH

34.

Tu Z., Deng Y.: A conjecture on binary string and its applications on constructing Boolean functions of optimal algebraic immunity. Des. Codes Cryptogr. 60, 1–14 (2011).MathSciNetCrossRefMATH

35.

Wang Q., Peng J., Kan H.: Constructions of cryptographically significant Boolean functions using primitive polynomials. IEEE Trans. Inf. Theory 56, 3048–3053 (2010).MathSciNetCrossRefMATH

36.

Wang Q., Tan C.H.: Properties of a family of cryptographic Boolean functions. Sequences and Their Applications (SETA) 2014. Lecture Notes in Computer Science, vol. 8865, pp. 34–46 . Springer, Heidelberg (2014).

37.

Zeng X., Carlet C., Shan J., Hu L.: More balanced Boolean functions with optimal algebraic immunity and good nonlinearity and resistance to fast algebraic attacks. IEEE Trans. Inf. Theory 57, 6310–6320 (2011).MathSciNetCrossRefMATH

Titel: Boolean functions with maximum algebraic immunity: further extensions of the Carlet–Feng construction
verfasst von: Konstantinos Limniotis
Nicholas Kolokotronis
Publikationsdatum: 10.10.2017
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 8/2018
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-017-0418-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 8/2018

On the (in)efficiency of non-interactive secure multiparty computation

Generalized Gabidulin codes over fields of any characteristic

New upper bounds for parent-identifying codes and traceability codes

Rank metric codes and zeta functions

Flag-transitive point-primitive automorphism groups of non-symmetric 2-(v, k, 3) designs

On a conjecture of differentially 8-uniform power functions