Top

Designs, Codes and Cryptography

Published in:

27-10-2018

A trigonometric sum sharp estimate and new bounds on the nonlinearity of some cryptographic Boolean functions

Authors: Qichun Wang, Pantelimon Stănică

Published in: Designs, Codes and Cryptography | Issue 8/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In this paper, we give a sharp estimate of a trigonometric sum which has several applications in cryptography and sequence theory. Using this estimate, we deduce new lower bounds on the nonlinearity of Carlet–Feng function, which has very good cryptographic properties with its nonlinearity bound being improved in numerous papers, as well as the function proposed by Tang–Carlet–Tang.

previous article Polynomial time bounded distance decoding near Minkowski’s bound in discrete logarithm lattices

next article Codes with the rank metric and matroids

Available only for authorised users

Berlekamp E.R., Welch L.R.: Weight distributions of the cosets of the (32, 6) Reed-Muller code. IEEE Trans. Inf. Theory 18(1), 203–207 (1972).MathSciNetMATHCrossRef

Braeken A., Preneel B.: On the algebraic immunity of symmetric Boolean functions. In: Progress in Cryptology-Indocrypt 2005, LNCS 3797, pp. 35–48. Springer, New York (2005).

Carlet C.: The complexity of Boolean functions from cryptographic viewpoint (2006). http://dblp.uni-trier.de/db/conf/dagstuhl/P6111.html.

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 (2010). http://www-roc.inria.fr/secret/Claude.Carlet/pubs.html.

Carlet C.: Comments on constructions of cryptographically significant boolean functions using primitive polynomials. IEEE Trans. Inf. Theory 57(7), 4852–4853 (2011).MATHCrossRef

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, LNCS 5350, pp. 425–440. Springer, New York (2008).

Carlet C., Mesnager S.: Improving the upper bounds on the covering radii of binary Reed-Muller codes. IEEE Trans. Inf. Theory 53(1), 162–173 (2007).MathSciNetMATHCrossRef

Carlet C., Mesnager S.: Four decades of research on bent functions. Des. Codes Cryptogr. 78(1), 5–50 (2016).MathSciNetMATHCrossRef

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(7), 3105–3121 (2006).MathSciNetMATHCrossRef

10.

Cohen G., Honkala I., Litsyn S., Lobstein A.: Covering Codes. North-Holland, Amsterdam (1997).MATH

11.

Cusick T.W., Stănică P.: Cryptographic Boolean Functions and Applications, 2nd edn. Elsevier, New York (2017).MATH

12.

Dalai D.K., Maitra K.C., Maitra S.: Cryptographically significant Boolean functions: construction and analysis in terms of algebraic immunity. In: Proceedings of FSE 2005, LNCS 3557, pp. 98–111. Springer, New York (2005)

13.

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

14.

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

15.

Gangopadhyay S., Mandal B., Stănică P.: Gowers \(U_3\) norm of some classes of bent Boolean functions. Des. Codes Cryptogr. 86(5), 1131–1148 (2018).MathSciNetMATHCrossRef

16.

Golić J.D.: Linear cryptanalysis of stream ciphers. In: Fast Software Encryption—FSE 1994, LNCS 1008, pp. 154–169. Springer, New York (1994).

17.

Hakala R.M., Nyberg K.: On the nonlinearity of the discrete logarithm in \(\mathbb{F}_2^n\). In: SEquences and Their Applications–SETA 2010, LNCS 6338, pp. 333–345. Springer, New York (2010).

18.

Hou X.D.: Covering radius of the Reed-Muller code \(R(1, 7)\)—a simpler proof. J. Comb. Theory Ser. A 74(2), 337–341 (1996).MathSciNetMATHCrossRef

19.

Hou X.D.: On the covering radius of \(R(1, m)\) in \(R(3, m)\). IEEE Trans. Inf. Theory 42(3), 1035–1037 (1996).MathSciNetMATHCrossRef

20.

Hou X.D.: The Covering Radius of \(R(1, 9)\) in \(R(4, 9)\). Des. Codes Cryptogr. 8(3), 285–292 (1996).MathSciNetMATHCrossRef

21.

Hou X.D.: On the norm and covering radius of the first order Reed-Muller codes. IEEE Trans. Inf. Theory 43(3), 1025–1027 (1997).MathSciNetMATHCrossRef

22.

Kavut S., Yücel M.D.: 9-variable Boolean functions with nonlinearity 242 in the generalized rotation symmetric class. Inf. Comput. 208(4), 341–350 (2010).MathSciNetMATHCrossRef

23.

Kavut S., Maitra S., Yücel M.D.: Search for Boolean functions with excellent profiles in the rotation symmetric class. IEEE Trans. Inf. Theory 53(5), 1743–1751 (2007).MathSciNetMATHCrossRef

24.

Li N., Qi W.F.: Construction and analysis of Boolean functions of \(2t+1\) variables with maximum algebraic immunity. In: Advances in Cryptology–ASIACRYPT 2006, LNCS 4284, pp. 84–98. Springer, New York (2006).

25.

Li N., Qu L., Qi W., Feng G., Li C., Xie D.: On the construction of Boolean functions with optimal algebraic immunity. IEEE Trans. Inf. Theory 54(3), 1330–1334 (2008).MathSciNetMATHCrossRef

26.

Lidl R., Niederreiter H.: Introduction to Finite Fields and Their Applications. Cambridge University Press, Cambridge (1986).MATH

27.

Liu M., Zhang Y., Lin D.: Perfect algebraic immune functions. Advances in Cryptology–ASIACRYPT 2012, LNCS 7658, pp. 172–189. Springer, New York (2012).

28.

Meier W., Staffelbach O.: Fast correlation attacks on stream ciphers. In: Advances in Cryptology–EUROCRYPT ’88, LNCS 330, pp. 301–314. Springer, New York (1988).

29.

Mykkeltveit J.J.: The covering radius of the (128, 8) Reed-Muller code is 56. IEEE Trans. Inf. Theory 26(3), 359–362 (1980).MathSciNetMATHCrossRef

30.

Pasalic, E.: Almost fully optimized infinite classes of Boolean functions resistant to (Fast) algebraic cryptanalysis. In: Proceedings of ICISC 2008, LNCS 5461, pp. 399–414. Springer, New York (2009).

31.

Patterson N.J., Wiedemann D.H.: The covering radius of the (215, 16) Reed-Muller code is at least 16276. IEEE Trans. Inf. Theory 29(3), 354–356 (1983).MATHCrossRef

32.

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

33.

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

34.

Tan C., Goh S.: Several classes of even-variable balanced Boolean functions with optimal algebraic immunity. Trans. Fundam. Electron. Commun. Comput. Sci. 94(1), 165–171 (2011).CrossRef

35.

Tang D., Maitra S.: Construction of \(n\)-variable \((n \equiv 2 \text{mod}4)\) balanced Boolean functions with maximum absolute value in autocorrelation spectra \(< 2^{n/2}\). IEEE Trans. Inf. Theory 64(1), 393–402 (2018).

36.

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(1), 653–664 (2013).MathSciNetMATHCrossRef

37.

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

38.

Wang Q., Stănică P.: New bounds on the covering radius of the second order Reed–Muller code of length 128. Cryptogr. Commun. (2018). https://doi.org/10.1007/s12095-018-0289-2.

39.

Wang Q., Tan C.H.: Properties of a family of cryptographic Boolean functions. In: SEquences and Their Applications–SETA 2014, LNCS 8865, pp. 34–46. Springer, New York (2012).

40.

Wang Q., Tan C.H.: Proof of a conjecture and a bound on the imbalance properties of LFSR subsequences. Discret. Appl. Math. 211, 217–221 (2016).MathSciNetMATHCrossRef

41.

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

42.

Wang Q., Tan C.H., Prabowo T.F.: On the covering radius of the third order Reed-Muller code \(RM(3, 7)\). Des. Codes Cryptogr. 86(1), 151–159 (2018).MathSciNetMATHCrossRef

43.

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(9), 6310–6320 (2011).MathSciNetMATHCrossRef

Title: A trigonometric sum sharp estimate and new bounds on the nonlinearity of some cryptographic Boolean functions
Authors: Qichun Wang
Pantelimon Stănică
Publication date: 27-10-2018
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 8/2019
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-018-0574-2

Springer Professional

A trigonometric sum sharp estimate and new bounds on the nonlinearity of some cryptographic Boolean functions

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 8/2019

Additive perfect codes in Doob graphs

At most three-weight binary linear codes from generalized Moisio’s exponential sums

Cameron–Liebler sets of k-spaces in

Correction to: Improved Singleton bound on frequency hopping sequences and optimal constructions

Weightwise perfectly balanced functions with high weightwise nonlinearity profile

Transitive PSL(2,11)-invariant k-arcs in PG(4,q)

Premium Partner