Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Gowers \(U_3\) norm of some classes of bent Boolean functions

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

The Gowers \(U_3\) norm of a Boolean function is a measure of its resistance to quadratic approximations. It is known that smaller the Gowers \(U_3\) norm for a Boolean function larger is its resistance to quadratic approximations. Here, we compute Gowers \(U_3\) norms for some classes of Maiorana–McFarland bent functions. In particular, we explicitly determine the value of the Gowers \(U_3\) norm of Maiorana–McFarland bent functions obtained by using APN permutations. We prove that this value is always smaller than the Gowers \(U_3\) norms of Maiorana–McFarland bent functions obtained by using differentially \(\delta \)-uniform permutations, for all \(\delta \ge 4\). We also compute the Gowers \(U_3\) norms for a class of cubic monomial functions, not necessarily bent, and show that for \(n=6\), these norm values are less than that of Maiorana–McFarland bent functions. Further, we computationally show that there exist 6-variable functions in this class which are not bent but achieve the maximum second-order nonlinearity for 6 variables.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Canteaut A., Charpin P.: Decomposing bent functions. IEEE Trans. Inf. Theory 49(8), 2004–2019 (2003).

    Article  MathSciNet  MATH  Google Scholar 

  2. Canteaut A., Charpin P., Kyureghyan G.M.: A new class of monomial bent functions. Finite Fields Appl. 14, 221–241 (2008).

    Article  MathSciNet  MATH  Google Scholar 

  3. Carlet C., Charpin P., Zinoviev V.: Codes, bent functions and permutations suitable for DES-like cryptosystems. Des. Codes Cryptogr. 15(2), 125–156 (1998).

    Article  MathSciNet  MATH  Google Scholar 

  4. Carlet C.: On cryptographic propagation criteria for Boolean functions. Inf. Comput. 151(1–2), 32–56 (1999).

    Article  MathSciNet  MATH  Google Scholar 

  5. Carlet C.: Recursive lower bounds on the nonlinearity profile of Boolean functions and their applications. IEEE Trans. Inf. Theory 54(3), 1262–1272 (2008).

    Article  MathSciNet  MATH  Google Scholar 

  6. Carlet C.: In: Crama Y., Hammer P.L. (eds.) Boolean Functions for Cryptography and Error Correcting Codes. Boolean Models and Methods in Mathematics, Computer Science, and Engineering, pp. 257–397. Cambridge University Press, New York (2010).

  7. Chen V.Y.-W.: The Gowers’ norm in the testing of Boolean functions. PhD Thesis, Massachusetts Institute of Technology (2009).

  8. Cusick T.W., Stănică P.: Cryptographic Boolean Functions and Applications, 2nd edn. Academic Press, San Diego (2017) (1st edn., 2009).

  9. Gangopadhyay S., Sarkar S., Telang R.: On the lower bounds of the second order nonlinearities of some Boolean functions. Inf. Sci. 180, 266–273 (2010).

    Article  MathSciNet  MATH  Google Scholar 

  10. Gangopadhyay S.: Affine inequivalence of cubic Maiorana–McFarland type bent functions. Discret. Appl. Math. 161(7–8), 1141–1146 (2013).

    Article  MathSciNet  MATH  Google Scholar 

  11. Gowers T.: A new proof of Szemerédi’s theorem. Geom. Funct. Anal. 11(3), 465–588 (2001).

    Article  MathSciNet  MATH  Google Scholar 

  12. Green B., Tao T.: An inverse theorem for the Gowers’ \(U^3(G)\) norm. arXiv:math/0503014 [math.NT] (2006).

  13. Rothaus O.S.: On bent functions. J. Combin. Theory Ser. A 20, 300–305 (1976).

    Article  MATH  Google Scholar 

  14. Tang D., Carlet C., Tang X.: On the second-order nonlinearities of some bent functions. Inf. Sci. 223, 322–330 (2013).

    Article  MathSciNet  MATH  Google Scholar 

  15. Tao T.: Structure and randomness in combinatorics. arXiv:0707.4269v2 [math.CO] (2007).

Download references

Acknowledgements

The authors thank Palash Sarkar for suggesting the problem and for several long discussions. We are also thankful for the useful comments of the reviewers that has immensely helped us to significantly improve both technical and editorial quality of the manuscript. Bimal Mandal acknowledges IIT Roorkee for supporting his research.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Indian Institute of Technology Roorkee, Roorkee, India

    Sugata Gangopadhyay

  2. Department of Mathematics, Indian Institute of Technology Roorkee, Roorkee, India

    Bimal Mandal

  3. Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA, 93943-5216, USA

    Pantelimon Stănică

Authors
  1. Sugata Gangopadhyay
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Bimal Mandal
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pantelimon Stănică
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Sugata Gangopadhyay.

Additional information

Communicated by C. Carlet.

Sections 1–2 were presented in Fq11, The 11th International Conference on Finite Fields and their Applications, Magdeburg, Germany, July 22–26, 2013.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Gangopadhyay, S., Mandal, B. & Stănică, P. Gowers \(U_3\) norm of some classes of bent Boolean functions. Des. Codes Cryptogr. 86, 1131–1148 (2018). https://doi.org/10.1007/s10623-017-0383-z

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-017-0383-z

Keywords

Mathematics Subject Classification

Search

Navigation