On the number of rotation symmetric Boolean functions | Science China Information Sciences Skip to main content
Springer Nature Link
Log in

On the number of rotation symmetric Boolean functions

  • Research Papers
  • Published:
Science China Information Sciences Aims and scope Submit manuscript

Abstract

Rotation symmetric Boolean functions (RSBFs) have been used as components of different cryptosystems. This class of functions are invariant under circular translation of indices. In this paper, we investigated balanced RSBFs and 1st order correlation immune RSBFs. Based on constructive techniques, we give an accurate enumeration formula for n-variable balanced RSBFs when n is a power of a prime. Furthermore, an original and efficient method to enumerate all n-variable (n prime) 1st order correlation-immune functions is presented. The exact number of 1st order correlation immune RSBFs with 11 variables is 6925047156550478825225250374129764511077684773805520800 and the number of 13 variables has 189 digits. Then for more variables, we also provide a significant lower bound on the number of 1st order correlation immune RSBFs.

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. Clark J, Jacob J, Stepney S, et al. Evolving Boolean functions satisfying multiple criteria. In: INDOCRYPT 2002, LNCS, vol. 2551. Berlin: Springer-Verlag, 2002. 246–259

    Chapter  Google Scholar 

  2. Clark J, Jacob J, Maitra S, et al. Almost Boolean functions: The design of Boolean functions by spectral inversion. In: the 2003 Congress on Evolutionary Computation (CEC 2003), Vol. 3. Newport Beach, California, USA, 2003. 2173–2180

    Article  Google Scholar 

  3. Maitra S, Pasalic E. Further constructions of resilient Boolean functions with very high nonlinearity. IEEE Trans Inf Theory, 2002, 48: 1825–1834

    Article  MATH  MathSciNet  Google Scholar 

  4. Filiol E, Fontaine C. Highly nonlinear balanced Boolean functions with a good correlation-immunity. In: Advances in Cryptology-EUROCRYPT 98, LNCS, Vol. 1403. Berlin: Springer-Verlag, 1998. 475–488

    Chapter  Google Scholar 

  5. Stanica P, Maitra S. Rotation symmetric Boolean functions-count and cryptographic properties. Discrete Math Appl, 2008, 156: 1567–1580

    Article  MATH  MathSciNet  Google Scholar 

  6. Stanica P, Maitra S. A constructive count of rotation symmetric functions. Inf Process Lett, 2003, 88: 299–304

    Article  MATH  MathSciNet  Google Scholar 

  7. Stanica P, Maitra S, Clark J. Results on rotation symmetric bent and correlation immune Boolean functions. In: Fast Software Encryption Workshop (FSE 2004), LNCS, Vol. 3017. Berlin: Springer-Verlag, 2004. 161–177

    Google Scholar 

  8. Maximov A, Hell M, Maitra S. Plateaued rotation symmetric Boolean functions on odd number of variables. In: First Workshop on Boolean Functions: Cryptography and Applications, BFCA 05, Rouen, France, 2005. 83–104

  9. Dalai D K, Maitra S, Sarkar S. Results on rotation symmetric bent functions. In: Second International Workshop on Boolean Functions: Cryptography and Applications, BFCA 06, Rouen, France, 2006. 137–156

  10. Pieprzyk J, Qu C X. Fast hashing and rotation-symmetric runctions. J Univ Comput Sci, 1999, 5: 20–31

    MathSciNet  Google Scholar 

  11. Cusick T W, Stanica P. Fast evaluation, weights and nonlinearity of rotation-symmetric functions. Discrete Math, 2002, 258: 289–301

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Science College of National University of Defense Technology, Changsha, 410073, China

    ShaoJing Fu, Chao Li & LongJiang Qu

  2. State Key Laboratory of Information Security, Beijing, 100039, China

    Chao Li

  3. National Mobile Communications Research Laboratory, Southeast University, Nanjing, 210096, China

    LongJiang Qu

Authors
  1. ShaoJing Fu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chao Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. LongJiang Qu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to ShaoJing Fu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Fu, S., Li, C. & Qu, L. On the number of rotation symmetric Boolean functions. Sci. China Inf. Sci. 53, 537–545 (2010). https://doi.org/10.1007/s11432-010-0045-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11432-010-0045-5

Keywords

Search

Navigation