Abstract
The correlation immune functions have a rich history of research. Balanced correlation immune Boolean functions with high nonlinearity and algebraic degree are important in the design of stream cipher systems. In this paper we mainly outline the development in the field of constructing such functions. We also briefly survey related issues in this area.
This draft for the invited lecture has been prepared in collaboration with Dr. Subhamoy Maitra of Indian Statistical Institute.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C. H. Bennet, G. Brassard, and J. M. Robert. Privacy amplification by by public discussion. SIAM Journal on Computing, 17:210–229, 1988.
J. Bierbrauer, K. Gopalakrishnan, and D. R Stinson. Bounds on resilient functions and orthogonal arrays. In Advances in Cryptology-CRYPTO’94, number 839 in Lecture Notes in Computer Science, pages 247–256. Springer Verlag, 1994.
P. Camion, C. Carlet, P. Charpin, and N. Sendrier. On correlation immune functions. In Advances in Cryptology-CRYPTO’91, number 576 in Lecture Notes in Computer Science, pages 86–100. Springer-Verlag, 1992.
P. Camion and A. Canteaut. Correlation-Immune and Resilient Functions Over a Finite Alphabet and Their Applications in Cryptography. Designs, Codes and Cryptography, 16(2): 121–149, 1999.
A. Canteaut, C. Carlet, P. Charpin and C. Fontaine. Propagation characteristics and correlation immunity of highly nonlinear Boolean functions. In Advances in Cryptology-EUROCRYPT’00, pages 507–522. Springer-Verlag, LNCS 1807, 2000.
C. Carlet. More Correlation-Immune and Resilient Functions over Galois Fields and Galois Rings. In Advances in Cryptology-Eurocrypt’ 97, number 1233 in Lecture Notes in Computer Science, pages 422–433. Springer-Verlag, 1997.
C. Carlet. On the coset weight divisibility and nonlinearity of resilient and correlation immune functions. In Sequences and Their Applications-SETA 2001, Discrete Mathematics and Theoretical Computer Science, pages 131–144. Springer Verlag, 2001.
C. Carlet and P. Sarkar. Spectral domain analysis of correlation immune and resilient Boolean functions. Accepted in Finite Fields and Its Applications, 2001.
S. Chee, S. Lee, D. Lee, and S. H. Sung. On the correlation immune functions and their nonlinearity. In Advances in Cryptology-ASIACRYPT’ 96, number 1163 in Lecture Notes in Computer Science, pages 232–243. Springer-Verlag, 1996.
J. H. Cheon and S. Chee. Elliptic Curves and Resilient Functions. In ICISC 2000, number 2015 in Lecture Notes in Computer Science, pages 64–72. Springer Verlag, 2000.
J. H. Cheon. Nonlinear Vector Resilient Functions. In Advances in Cryptology-CRYPTO 2001, Lecture Notes in Computer Science. Springer Verlag, 2001.
B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, and R. Smolensky. The bit extraction problem or t-resilient functions. In 26th IEEE Symposium on Foundations of Computer Science, pages 396–407, 1985.
J. Clark, J. Jacob, W. Millan, and S. Maitra. Evolution of Boolean Functions Satisfying Multiple Criteria with Simulated Annealing. Preprint, 2002.
E. Dawson and C. K. Wu. Construction of correlation immune Boolean functions. In Information and Communications Security, Lecture Notes in Computer Science, pages 170–180. Springer-Verlag, 1997.
C. Ding, G. Xiao, and W. Shan. The Stability Theory of Stream Ciphers. Number 561 in Lecture Notes in Computer Science. Springer-Verlag, 1991.
O. V. Denisov. An asymptotic formula for the number of correlation-immune of order k Boolean functions. Discrete Mathematics and Applications, 2(4):407–426, 1992.
M. Fedorova and Y. V. Tarannikov. On the constructing of highly nonlinear resilient Boolean functions by means of special matrices. In Progress in Cryptology-INDOCRYPT 2001, number 2247 in Lecture Notes in Computer Science, pages 254–266. Springer Verlag, 2001.
E. Filiol and C. Fontaine. Highly nonlinear balanced Boolean functions with a good correlation-immunity. In Advances in Cryptology-EUROCRYPT’98, number 1403 in Lecture Notes in Computer Science, pages 475–488. Springer-Verlag, 1998.
J. Friedman. On the bit extraction problem. In 33rd IEEE Symposium on Foundations of Computer Science, pages 314–319, 1982.
K. Gopalakrisnan, D. G. Hoffman, and D. R. Stinson. A note on a conjecture concerning symmetric resilient functions. Information Processing Letters, 47(3):139–143, 1993.
K. Gopalakrishnan. A study of Correlation-immune, resilient and related cryptographic functions. PhD thesis, University of Nebraska, 1994.
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.
T. Johansson and E. Pasalic, A construction of resilient functions with high nonlinearity, In IEEE International Symposium on Information Theory, ISIT, June 2000, full version available at Cryptology ePrint Archive, eprint.iacr.org, No.2000/053.
K. Kurosawa, T. Satoh, and K. Yamamoto Highly nonlinear t-Resilient functions. Journal of Universal Computer Science, vol. 3, no. 6, pp. 721–729, Springer Publishing Company, 1997.
S. Maitra and P. Sarkar. Enumeration of correlation immune Boolean functions. In 4th Australasian Conference on Information, Security and Privacy, number 1587 in Lecture Notes in Computer Science, pages 12–25. Springer Verlag, April 1999.
S. Maitra and P. Sarkar. Highly nonlinear resilient functions optimizing Siegenthaler’s inequality. In Advances in Cryptology-CRYPTO’99, number 1666 in Lecture Notes in Computer Science, pages 198–215. Springer Verlag, August 1999.
S. Maitra and P. Sarkar. Hamming weights of correlation immune Boolean functins. Information Processing Letters, 71(3–4):149–153, 1999.
S. Maitra. Correlation immune Boolean functions with very high nonlinearity. Cryptology ePrint Archive, eprint.iacr.org, No. 2000/054, October 27, 2000.
S. Maitra. Autocorrelation Properties of correlation immune Boolean functions. INDOCRYPT 2001, number 2247 Lecture Notes in Computer Science. Pages 242–253. Springer Verlag, December 2001.
S. Maitra. Boolean Functions with Important Cryptographic Properties. PhD Thesis, Indian Statistical Institute, 2001.
S. Maitra and P. Sarkar. Cryptographically significant Boolean functions with five valued Walsh spectra. Theoretical Computer Science, To be published in 2002.
S. Maitra and E. Pasalic. Further constructions of resilient Boolean functions with very high nonlinearity. IEEE Transactions on Information Theory, To be published in July 2002.
W. Millan, A. Clark, and E. Dawson. Heuristic design of cryptographically strong balanced Boolean functions. In Advances in Cryptology-EUROCRYPT’98. Springer-Verlag, 1998.
C. J. Mitchell. Enumerating Boolean functions of cryptographic significance. Journal of Cryptology, 2(3):155–170, 1990.
P. Sung Mo, L. Sangjin, S. Soo Hak, and K. Kwangjo. Improving bounds for the number of correlation immune Boolean functions. Information Processing Letters, 61(4):209–212, 1997.
J. J. Mykkeltveit. The covering radius of the (128, 8) Reed-Muller code is 56. IEEE Transactions on Information Theory, IT-26(3):358–362, 1983.
E. Pasalic and T. Johansson. Further results on the relation between nonlinearity and resiliency of Boolean functions. In IMA Conference on Cryptography and Coding, number 1746 in Lecture Notes in Computer Science, pages 35–45. Springer-Verlag, 1999.
E. Pasalic, S. Maitra, T. Johansson and P. Sarkar. New constructions of resilient and correlation immune Boolean functions achieving upper bounds on nonlinearity. In Workshop on Coding and Cryptography-WCC 2001, Paris, January 8–12, 2001. Electronic Notes in Discrete Mathematics, Volume 6, Elsevier Science, 2001.
E. Pasalic and S. Maitra. Linear codes in constructing resilient functions with high nonlinearity. In Selected Areas in Cryptography-SAC 2001, number 2259 in Lecture Notes in Computer Science. Pages 60–74, Springer Verlag, August 2001. (An extended version of this paper contains further improved results.)
N. J. Patterson and D. H. Wiedemann. The covering radius of the (215,16) Reed-Muller code is at least 16276. IEEE Transactions on Information Theory, IT-29(3):354–356, 1983.
N. J. Patterson and D. H. Wiedemann. Correction to-the covering radius of the (215,16) Reed-Muller code is at least 16276. IEEE Transactions on Information Theory, IT-36(2):443, 1990.
O. S. Rothaus. On bent functions. Journal of Combinatorial Theory, Series A, 20:300–305, 1976.
P. Sarkar and S. Maitra. Construction of nonlinear Boolean functions with important cryptographic properties. In Advances in Cryptology-EUROCRYPT 2000, number 1807 in Lecture Notes in Computer Science, pages 485–506. Springer Verlag, 2000.
P. Sarkar and S. Maitra. Nonlinearity bounds and constructions of resilient Boolean functions. In Advances in Cryptology-CRYPTO 2000, number 1880 in Lecture Notes in Computer Science, pages 515–532. Springer Verlag, 2000.
P. Sarkar. A note on the spectral characterization of correlation immune Boolean functions. Information Processing Letters, 74(5–6):191–195, 2000.
P. Sarkar and S. Maitra. Cross-correlation analysis of cryptographically useful Boolean functions and S-boxes. Theory of Computing Systems, to be published in 2002.
P. Sarkar and S. Maitra. Balancedness and Correlation Immunity of Symmetric Boolean Functions. Preprint, 2000.
M. Schneider. On the construction and upper bounds of balanced and correlation immune functions. In SAC’97, January 1997.
J. Seberry, X. M. Zhang, and Y. Zheng. On constructions and nonlinearity of correlation immune Boolean functions. In Advances in Cryptology-EUROCRYPT’93, number 765 in Lecture Notes in Computer Science, pages 181–199. Springer-Verlag, 1994.
W. Shan. The structure and the construction of correlation immune functions. MS Thesis, NTE Institute, Xian, 1987.
T. Siegenthaler. Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE Transactions on Information Theory, IT-30(5):776–780, September 1984.
T. Siegenthaler. Decrypting a class of stream ciphers using ciphertext only. IEEE Transactions on Computers, C-34(1):81–85, January 1985.
D. R. Stinson. Resilient functions and large sets of orthogonal arrays. Congressus Numerantium, 92:105–110, 1993.
D. R. Stinson and J. L. Massey. An infinite class of counterexamples to a conjecture concerning non-linear resilient functions. Journal of Cryptology, 8(3):167–173, 1995.
Y. V. Tarannikov. On resilient Boolean functions with maximum possible nonlinearity. In Progress in Cryptology-INDOCRYPT 2000, number 1977 in Lecture Notes in Computer Science, pages 19–30. Springer Verlag, 2000.
Y. V. Tarannikov. New constructions of resilient Boolean functions with maximal nonlinearity. In Fast Software Encryption-FSE 2001, pages 70–81 in preproceedings, 2001.
Y. V. Tarannikov, P. Korolev and A. Botev. Autocorrelation coefficients and correlation immunity of Boolean functions. In ASIACRYPT 2001, Lecture Notes in Computer Science. Springer Verlag, 2001.
Y. X. Yang and B. Guo. Further enumerating Boolean functions of cryptographic significance. Journal of Cryptology, 8(3):115–122, 1995.
X. M. Zhang and Y. Zheng. Cryptographically resilient functions. IEEE Transactions on Information Theory, 43(5):1740–1747, 1997.
Y. Zheng and X. M. Zhang. Improved upper bound on the nonlinearity of high order correlation immune functions. In Selected Areas in Cryptography-SAC 2000, number 2012 in Lecture Notes in Computer Science, pages 264–274. Springer Verlag, 2000.
Y. Zheng and X. M. Zhang. On relationships among propagation degree, nonlinearity and correlation immunity. In Advances in Cryptology-ASIACRYPT’00, Lecture Notes in Computer Science. Springer Verlag, 2000.
Y. Zheng and X. M. Zhang. New results on correlation immune functions. In International Conference on Information Security and Cryptology-ICISC 2000, number 2015 in Lecture Notes in Computer Science, pages 49–63. Springer Verlag, 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Roy, B. (2002). A Brief Outline of Research on Correlation Immune Functions. In: Batten, L., Seberry, J. (eds) Information Security and Privacy. ACISP 2002. Lecture Notes in Computer Science, vol 2384. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45450-0_29
Download citation
DOI: https://doi.org/10.1007/3-540-45450-0_29
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43861-8
Online ISBN: 978-3-540-45450-2
eBook Packages: Springer Book Archive