Maximal values of generalized algebraic immunity | Designs, Codes and Cryptography Skip to main content
Springer Nature Link
Log in

Maximal values of generalized algebraic immunity

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

Abstract

The notion of algebraic immunity of Boolean functions has been generalized in several ways to vector-valued functions and/or over arbitrary finite fields and reasonable upper bounds for such generalized algebraic immunities has been proved in Armknecht and Krause (Proceedings of ICALP 2006, LNCS, vol. 4052, pp 180–191, 2006), Ars and Faugere (Algebraic immunity of functions over finite fields, INRIA, No report 5532, 2005) and Batten (Canteaut, Viswanathan (eds.) Progress in Cryptology—INDOCRYPT 2004, LNCS, vol. 3348, pp 84–91, 2004). In this paper we show that the upper bounds can be reached as the maximal values of algebraic immunities for most of generalizations by using properties of Reed–Muller codes.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Armknecht F.: Improving fast algebraic attacks. In: Roy B., Meier W. (eds.) FSE 2004, LNCS, vol. 3017, pp. 65–82 (2004).

  2. Armknecht F., Krause M.: Algebraic attacks on combiners with memory. In: Boneh D. (ed.) Advances in Cryptology—Crypto 2003, LNCS, vol. 2729, pp. 162–176 (2003).

  3. Armknecht F., Krause M.: Constructing single- and multi-output Boolean functions with maximal algebraic immunity. In: Proceedings of ICALP 2006, LNCS, vol. 4052, pp. 180–191 (2006).

  4. Ars G., Faugere J.-C.: Algebraic immunity of functions over finite fields, INRIA, No report 5532 (2005).

  5. Assmus E.F., Key J.D. Jr.: Designs and their Codes. Cambridge University Press (1992).

  6. Batten L.M.: Algebraic attacks over GF(q). In: Canteaut A., Viswanathan K. (eds.) Progress in Cryptology—INDOCRYPT 2004, LNCS, vol. 3348, pp. 84–91 (2004).

  7. Courtois N.: Fast algebraic attacks over GF(q). In: Boneh D. (ed.) Advances in Cryptology—Crypto 2003, LNCS, vol. 2729, pp. 176–194 (2003).

  8. Meier W., Pasalic E., Carlet C.: Algebraic attacks and decomposition of Boolean functions. In: Cachin C. Camenisch J. (eds.) Advances in Cryptology—EUROCRYPT 2004, LNCS, vol. 3207, pp. 474–491 (2004).

Download references

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, Tsinghua University, Beijing, 100084, China

    Keqin Feng, Qunying Liao & Jing Yang

  2. College of Mathematics and Software Science, Sichuan Normal University, Chengdu, 610066, China

    Qunying Liao

Authors
  1. Keqin Feng
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Qunying Liao
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Jing Yang
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Jing Yang.

Additional information

Communicated by C. Cid.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Feng, K., Liao, Q. & Yang, J. Maximal values of generalized algebraic immunity. Des. Codes Cryptogr. 50, 243–252 (2009). https://doi.org/10.1007/s10623-008-9228-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-008-9228-0

Keywords

Mathematics Subject Classification (2000)