Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Nonlinearity Bounds and Constructions of Resilient Boolean Functions

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 1880))

Included in the following conference series:

Abstract

In this paper we investigate the relationship between the nonlinearity and the order of resiliency of a Boolean function. We first prove a sharper version of McEliece theorem for Reed-Muller codes as applied to resilient functions, which also generalizes the well known Xiao-Massey characterization. As a consequence, a nontrivial upper bound on the nonlinearity of resilient functions is obtained. This result coupled with Siegenthaler’s inequality leads to the notion of best possible trade-off among the parameters: number of variables, order of resiliency, nonlinearity and algebraic degree. We further show that functions achieving the best possible trade-off can be constructed by the Maiorana-McFarland like technique. Also we provide constructions of some previously unknown functions.

Similar content being viewed by others

Keywords

References

  1. P. Camion, C. Carlet, P. Charpin, and N. Sendrier. On correlation immune functions. InAdvances in Cryptology-CRYPTO’91, pages 86–100. Springer-Verlag, 1992.

    Google Scholar 

  2. C. Carlet. More correlation immune and resilient functions over Galois fields and Galois rings. InAdvances in Cryptology-EUROCRYPT’97, pages 422–433. Springer-Verlag, May 1997.

    Google Scholar 

  3. S. Chee, S. Lee, D. Lee, and S. H. Sung. On the correlation immune functions and their nonlinearity. InAdvances in Cryptology, Asiacrypt 96, number 1163 in Lecture Notes in Computer Science, pages 232–243. Springer-Verlag, 1996.

    Chapter  Google Scholar 

  4. C. Ding, G. Xiao, and W. Shan.The Stability Theory of Stream Ciphers. Number 561 in Lecture Notes in Computer Science. Springer-Verlag, 1991.

    MATH  Google Scholar 

  5. E. Filiol and C. Fontaine. Highly nonlinear balanced Boolean functions with a good correlation-immunity. InAdvances in Cryptology-EUROCRYPT’98. Springer-Verlag, 1998.

    Google Scholar 

  6. X. Guo-Zhen and J. Massey. A spectral characterization of correlation immune combining functions.IEEE Transactions on Information Theory, 34(3):569–571, May 1988.

    Google Scholar 

  7. X. Hou. Covering radius of the Reed-Muller codeR(1, 7)-a simpler proof.Journal of Combinatorial Theory, Series A, 74(3):337–341, 1996.

    Article MATH MathSciNet  Google Scholar 

  8. X. Hou. On the covering radius ofR(1,m) inR(3,m).IEEE Transactions on Information Theory, 42(3):1035–1037, 1996.

    Article MATH  Google Scholar 

  9. X. Hou. On the norm and covering radius of the first order Reed-Muller codes.IEEE Transactions on Information Theory, 43(3):1025–1027, 1997.

    Article MATH  Google Scholar 

  10. T. Johansson and F. Jonsson. Fast correlation attacks based on turbo code techniques. InAdvances in Cryptology-CRYPTO’99, number 1666 in Lecture Notes in Computer Science, pages 181–197. Springer-Verlag, August 1999.

    Google Scholar 

  11. T. Johansson and F. Jonsson. Improved fast correlation attacks on stream ciphers via convolutional codes. InAdvances in Cryptology-EUROCRYPT’99, number 1592 in Lecture Notes in Computer Science, pages 347–362. Springer-Verlag, May 1999.

    Google Scholar 

  12. F. J. MacWillams and N. J. A. Sloane.The Theory of Error Correcting Codes. North Holland, 1977.

    Google Scholar 

  13. S. Maitra and P. Sarkar. Highly nonlinear resilient functions optimizing Siegen-thaler’s inequality. InAdvances in Cryptology-CRYPTO’99, number 1666 in Lecture Notes in Computer Science, pages 198–215. Springer Verlag, August 1999.

    Google Scholar 

  14. W. Meier and O. Staffelbach. Fast correlation attack on stream ciphers. InAdvances in Cryptology-EUROCRYPT’88, volume 330, pages 301–314. Springer-Verlag, May 1988.

    Google Scholar 

  15. S. Palit and B. K. Roy. Cryptanalysis of LFSR-encrypted codes with unknown combining functions. InAdvances in Cryptology-ASIACRYPT’99, number 1716 in Lecture Notes in Computer Science, pages 306–320. Springer Verlag, November 1999.

    Google Scholar 

  16. E. Pasalic and T. Johansson. Further results on the relation between nonlinearity and resiliency of Boolean functions. InIMA Conference on Cryptography and Coding, number 1746 in Lecture Notes in Computer Science, pages 35–45. Springer-Verlag, 1999.

    Chapter  Google Scholar 

  17. R. A. Rueppel.Analysis and Design of Stream Ciphers. Springer Verlag, 1986.

    Google Scholar 

  18. R. A. Rueppel and O. J. Staffelbach. Products of linear recurring sequences with maximum complexity.IEEE Transactions on Information Theory, IT-33:124–131, January 1987.

    Google Scholar 

  19. P. Sarkar and S. Maitra. Construction of nonlinear Boolean functions with important cryptographic properties. InAdvances in Cryptology-EUROCRYPT 2000, number 1807 in Lecture Notes in Computer Science, pages 491–512. Springer Verlag, 2000.

    Chapter  Google Scholar 

  20. J. Seberry, X. M. Zhang, and Y. Zheng. Nonlinearly balanced Boolean functions and their propagation characteristics. InAdvances in Cryptology-CRYPTO’93, pages 49–60. Springer-Verlag, 1994.

    Google Scholar 

  21. J. Seberry, X. M. Zhang, and Y. Zheng. On constructions and nonlinearity of correlation immune Boolean functions. InAdvances in Cryptology-EUROCRYPT’93, pages 181–199. Springer-Verlag, 1994.

    Google Scholar 

  22. T. Siegenthaler. Correlation-immunity of nonlinear combining functions for cryptographic applications.IEEE Transactions on Information Theory, IT-30(5):776–780, September 1984.

    Google Scholar 

  23. T. Siegenthaler. Decrypting a class of stream ciphers using ciphertext only.IEEE Transactions on Computers, C-34(1):81–85, January 1985.

    Google Scholar 

  24. Y. V. Tarannikov. On resilient Boolean functions with maximum possible nonlinearity.Cryptology ePrint Archive, eprint.iacr.org, No. 2000/005, 2000.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Applied Statistics Unit, Indian Statistical Institute, 203, B T Road, Calcutta, 700 035, India

    Palash Sarkar

  2. Computer and Statistical Service Center, Indian Statistical Institute, 203, B T Road, Calcutta, 700 035, India

    Subhamoy Maitra

Authors
  1. Palash Sarkar

    You can also search for this author inPubMed Google Scholar

  2. Subhamoy Maitra

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science and Engineering, University of California, 0114 9500 Gilman Drive, La Jolla, CA, 92093, USA

    Mihir Bellare

Rights and permissions

Copyright information

© 2000 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Sarkar, P., Maitra, S. (2000). Nonlinearity Bounds and Constructions of Resilient Boolean Functions. In: Bellare, M. (eds) Advances in Cryptology — CRYPTO 2000. CRYPTO 2000. Lecture Notes in Computer Science, vol 1880. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44598-6_32

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp