nach oben

Designs, Codes and Cryptography

Erschienen in:

01.09.2014

A systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of the Reed–Muller code

verfasst von: Sihong Su, Xiaohu Tang, Xiangyong Zeng

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2014

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

Because of the recent algebraic attacks, optimal algebraic immunity is now an absolutely necessary (but not sufficient) property for Boolean functions used in stream ciphers. In this paper, we firstly determine the concrete coefficients in the linear expression of the column vectors with respect to a given basis of the generator matrix of Reed–Muller code, which is an important tool for constructing Boolean functions with optimal algebraic immunity. Secondly, as applications of the determined coefficients, we provide simpler and direct proofs for two known constructions. Further, we construct new Boolean functions on odd variables with optimal algebraic immunity based on the generator matrix of Reed–Muller code. Most notably, the new constructed functions possess the highest nonlinearity among all the constructions based on the generator matrix of Reed–Muller code, although which is not as good as the nonlinearity of Carlet–Feng function. Besides, the ability of the new constructed functions to resist fast algebraic attacks is also checked for the variable \(n=11,13\) and 15.

Vorheriger Artikel 1-Overlap cycles for Steiner triple systems

Nächster Artikel The Ubiquity of the Orders of Fractional Semifields of Even Characteristic

Armknecht F.: Improving fast algebraic attacks. In: Fast Software Encryption 2004. Lecture Notes in Computer Science, vol. 3017. Springer, Berlin, pp. 65–82 (2004).

Canteaut A.: Open problems related to algebraic attacks on stream ciphers. In: Workshop on Coding and Cryptography 2005. Lecture Notes in Computer Science, vol. 3969. Springer, Berlin, pp. 120–134 (2006).

Carlet C.: A method of construction of balanced functions with optimum algebraic immunity. In: International Workshop on Coding and Cryptology, pp. 25–43, 2007.

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

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

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

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

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).

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

10.

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

11.

Dalai D., Maitra S.: Reducing the number of homogeneous linear equations in finding annihilators. In: Sequences and Their Applications 2006. Lecture Notes in Computer Science, vol. 4086. Springer, Berlin, pp. 376–390 (2006).

12.

Dalai D., Gupta K., Maitra S.: Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity. In: Workshop on Fast Software Encryption, FSE 2005. Lecture Notes in Computer Science, vol. 3557. Springer, Berlin, pp. 98–111 (2005).

13.

Dalai D., Gupta K., Maitra S.: Notion of algebraic immunity and its evaluation related to fast algebraic attacks. In: Second International Workshop on Boolean Functions: Cryptography and Applications, BFCA 2006, Cryptology ePrint Archive, Report 2006/018. http://eprint.iacr.org/2006/018.pdf.

14.

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

15.

Ding C., Xiao G., Shan W.: The Stability Theory of Stream Ciphers. Springer, Berlin (1991).

16.

Dong D., Fu S., Qu L., Li C.: A new construction of Boolean functions with maximum algebraic immunity. In: ISC 2009. Lecture Notes in Computer Science, vol. 5735. Springer, Berlin, pp. 177–185 (2009).

17.

Feng K., Liao Q., Yang J.: Maximal values of generalized algebraic immunity. Des. Codes Cryptogr. 50, 243–252 (2009).

18.

Hawkes P., Rose G.: Rewriting variables: The complexity of fast algebraic attacks on stream ciphers. In: Advances in Cryptology-CRYPTO 2004. Lecture Notes in Computer Science, vol. 3152. Springer, Berlin, pp. 390–406 (2004).

19.

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

20.

Lobanov M.: Tight bound between nonlinearity and algebraic immunity. In: Cryptology ePrint Archive, Report 2005/441. http://eprint.iacr.org/2005/441.pdf.

21.

Meier W., Staffelbach O.: Fast correlation attacks on stream ciphers. In: Advances in Cryptology-EUROCRYPT 1988. Lecture Notes in Computer Science, vol. 330. Springer, Berlin, pp. 301–314 (1988).

22.

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. Springer, Berlin, pp. 474–491 (2004).

23.

Muller D.: Application of Boolean algebra to switching circuit design and to error detection. IEEE Trans. Comput. 3, 6–12 (1954).

24.

Peng J., Wu Q., Kan H.: On symmetric Boolean functions with high algebraic immunity on even number of variables. IEEE Trans. Inf. Theory, 57, 7205–7220 (2011).

25.

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

26.

Reed S.: A class of multiple-error-correcting codes and the decoding scheme. IEEE Trans. Inf. Theory 4, 38–49 (1954).

27.

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

28.

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, to be published (2012).

29.

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).

Titel: A systematic method of constructing Boolean functions with optimal algebraic immunity based on the generator matrix of the Reed–Muller code
verfasst von: Sihong Su
Xiaohu Tang
Xiangyong Zeng
Publikationsdatum: 01.09.2014
Verlag: Springer US
Erschienen in: Designs, Codes and Cryptography / Ausgabe 3/2014
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-013-9801-z

Springer Professional

Abstract

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

Weitere Artikel der Ausgabe 3/2014

Codes over an infinite family of rings with a Gray map

Skeleton simplicial evaluation codes

A class of 1-generator repeated root quasi-cyclic codes

List decoding of number field codes

On the sharpness of Bruen’s bound for intersection sets in Desarguesian affine spaces

The structure of quaternary quantum caps