# American Institute of Mathematical Sciences

November  2016, 10(4): 895-919. doi: 10.3934/amc.2016048

## Variation on correlation immune Boolean and vectorial functions

 1 School of Computer Software, Tianjin University, Tianjin 300072, China 2 Department of Mathematics, University of Paris VIII, CNRS, UMR 7539 LAGA and Telecom ParisTech, Paris, France 3 School of Mathematical Sciences, Nankai University, Tianjin 300071, China

Received  March 2015 Revised  September 2015 Published  November 2016

Correlation immune functions were introduced to protect some shift register based stream ciphers against correlation attacks. For cryptographic applications, relaxing the concept of correlation immunity has been highlighted and proved to be more appropriate in several cryptographic situations. Various weakened notions of correlation immunity and resiliency have been widely introduced for cryptographic functions, but those notions are difficult to handle.
As a variation, we focus on the notion of $\varphi$-correlation immunity which is closely related to (fast) correlation attacks on stream ciphers based on nonlinear combiner model. In particular, we exhibit new connections between $\varphi$-correlation immunity and $\epsilon$-almost resiliency, which are two distinct approaches for characterizing relaxed resiliency. We also extend the concept of $\varphi$-correlation immunity introduced by Carlet et al. in 2006 for Boolean functions to vectorial functions and study the main cryptographic parameters of $\varphi$-correlation immune functions. Moreover, we provide new primary constructions of $\varphi$-resilient functions with good designed immunity profile. Specially, we propose a new recursive method to construct $\varphi$-resilient functions with high nonlinearity, high algebraic degree, and monotone increasing immunity profile.
Citation: Jian Liu, Sihem Mesnager, Lusheng Chen. Variation on correlation immune Boolean and vectorial functions. Advances in Mathematics of Communications, 2016, 10 (4) : 895-919. doi: 10.3934/amc.2016048
##### References:
 [1] C. H. Bennett, G. Brassard and J. M. Robert, Privacy amplification by public discussion, SIAM J. Comp., 17 (1988), 210-229. doi: 10.1137/0217014.  Google Scholar [2] A. Braeken, V. Nikov, S. Nikova and B. Preneel, On Boolean functions with generalized cryptographic properties, in Progr. Crypt. - INDOCRYPT 2004, Springer-Verlag, Berlin, 2005, 120-135. doi: 10.1007/978-3-540-30556-9_11.  Google Scholar [3] A. Canteaut, On the correlations between a combining functions and functions of fewer variables, in Proc. Inform. Theory Workshop 2002, IEEE, 2002, 78-81. Google Scholar [4] A. Canteaut and M. Trabbia, Improved fast correlation attacks using parity-check equations of weight $4$ and $5$, in Adv. Crypt. - EUROCRYPT 2000, Springer-Verlag, Berlin, 2000, 573-588. Google Scholar [5] C. Carlet, More correlation-immune and resilient functions over Galois fields and Galois rings, in Adv. Crypt. - EUROCRYPT'97, Springer-Verlag, Berlin, 1997, 422-433. doi: 10.1007/3-540-69053-0_29.  Google Scholar [6] C. Carlet, On the coset weight divisibility and nonlinearity of resilient and correlation-immune functions, in Proc. SETA'01 Seq. Appl., Springer-Verlag, London, 2002, 131-144.  Google Scholar [7] C. Carlet, Boolean functions for cryptography and error correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge Univ. Press, London, 2010, 257-397. Google Scholar [8] C. Carlet, Vectorial Boolean functions for cryptography, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge Univ. Press, London, 2010, 398-469. Google Scholar [9] C. Carlet, P. Guilot and S. Mesnager, On immunity profile of Boolean functions, in Proc Seq. Appl. - SETA 2006, Springer-Verlag, Berlin, 2006, 364-375. doi: 10.1007/11863854_32.  Google Scholar [10] C. Carlet and P. Sarkar, Spectral domain analysis of correlation immune and resilient Boolean functions, Finite Fields Appl., 8 (2002), 120-130. doi: 10.1006/ffta.2001.0332.  Google Scholar [11] V. V. Chepyzhov, T. Johansson and B. Smeets, A simple algorithm for fast correlation attacks on stream ciphers, in Fast Software Encryption, FSE 2000, Springer-Verlag, Berlin, 2001, 181-195. Google Scholar [12] B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich and R. Smolensky, The bit extraction problem or $t$-resilient functions, in 26th IEEE Symp. Found. Comp. Sci., 1985, 396-407. Google Scholar [13] G. Cohen, I. Honkala , S. Litsyn and A. Lobstein, Covering Codes, North-Holland, Amsterdam, 1997.  Google Scholar [14] J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D. thesis, Univ. Maryland, 1974.  Google Scholar [15] T. Johansson and E. Pasalic, A construction of resilient functions with high nonlinearity, IEEE Trans. Inform. Theory, 49 (2003), 494-501. doi: 10.1109/TIT.2002.807297.  Google Scholar [16] K. Kurosawa, T. Johansson and D. Stinson, Almost $k$-wise independent sample spaces and their cryptologic applications, J. Crypt., 14 (2001), 301-324. doi: 10.1007/3-540-69053-0_28.  Google Scholar [17] K. Kurosawa and R. Matsumoto, Almost security of cryptographic Boolean functions, IEEE Trans. Inform. Theory, 50 (2004), 2572-2761. doi: 10.1109/TIT.2004.836684.  Google Scholar [18] P. Lacharme, Analysis and construction of correctors, IEEE Trans. Inform. Theory, 55 (2009), 4742-4748. doi: 10.1109/TIT.2009.2027483.  Google Scholar [19] J. Liu, L. Chen and X. Guang, Highly nonlinear resilient functions without linear structures, IEICE Trans. Fundam., E97-A (2014), 1405-1417. Google Scholar [20] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977. Google Scholar [21] W. Meier and O. Staffelbach, Fast correlation attacks on stream ciphers, in Adv. Crypt. - EUROCRYPT'88, Springer-Verlag, Berlin, 1988, 301-314. Google Scholar [22] P. Sarkar and S. Maitra, Nonlinearity bounds and constructions of resilient Boolean functions, in Adv. Crypt. - CRYPTO 2000, Springer-Verlag, Berlin, 2000, 515-532. doi: 10.1007/3-540-44598-6_32.  Google Scholar [23] T. Siegenthaler, Correlation immunity of nonlinear combining functions for cryptographic applications, IEEE Trans. Inform. Theory, 30 (1984), 776-780. doi: 10.1109/TIT.1984.1056949.  Google Scholar [24] T. Siegenthaler, Decrypting a class of stream ciphers using ciphertext only, IEEE Trans. Comp., C-34 (1985), 81-85. Google Scholar [25] Y. V. Tarannikov, New constructions of resilient Boolean functions with maximum nonlinearity, in Proc. 8th Int. Workshop FSE 2001, Springer-Verlag, Berlin, 2001, 66-77. Google Scholar [26] G. Z. Xiao and J. L. Massey, A spectral characterization of correlation-immune combining functions, IEEE Trans. Inform. Theory, 34 (1988), 569-571. doi: 10.1109/18.6037.  Google Scholar [27] W. Zhang and E. Pasalic, Constructions of resilient S-boxes with strictly almost optimal nonlinearity through disjoint linear codes, IEEE Trans. Inform. Theory, 60 (2014), 1638-1651. doi: 10.1109/TIT.2014.2300067.  Google Scholar [28] X.-M. Zhang and Y. Zheng, Cryptographically resilient functions, IEEE Trans. Inform. Theory, 43 (1997), 1740-1747. doi: 10.1109/18.623184.  Google Scholar

show all references

##### References:
 [1] C. H. Bennett, G. Brassard and J. M. Robert, Privacy amplification by public discussion, SIAM J. Comp., 17 (1988), 210-229. doi: 10.1137/0217014.  Google Scholar [2] A. Braeken, V. Nikov, S. Nikova and B. Preneel, On Boolean functions with generalized cryptographic properties, in Progr. Crypt. - INDOCRYPT 2004, Springer-Verlag, Berlin, 2005, 120-135. doi: 10.1007/978-3-540-30556-9_11.  Google Scholar [3] A. Canteaut, On the correlations between a combining functions and functions of fewer variables, in Proc. Inform. Theory Workshop 2002, IEEE, 2002, 78-81. Google Scholar [4] A. Canteaut and M. Trabbia, Improved fast correlation attacks using parity-check equations of weight $4$ and $5$, in Adv. Crypt. - EUROCRYPT 2000, Springer-Verlag, Berlin, 2000, 573-588. Google Scholar [5] C. Carlet, More correlation-immune and resilient functions over Galois fields and Galois rings, in Adv. Crypt. - EUROCRYPT'97, Springer-Verlag, Berlin, 1997, 422-433. doi: 10.1007/3-540-69053-0_29.  Google Scholar [6] C. Carlet, On the coset weight divisibility and nonlinearity of resilient and correlation-immune functions, in Proc. SETA'01 Seq. Appl., Springer-Verlag, London, 2002, 131-144.  Google Scholar [7] C. Carlet, Boolean functions for cryptography and error correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge Univ. Press, London, 2010, 257-397. Google Scholar [8] C. Carlet, Vectorial Boolean functions for cryptography, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge Univ. Press, London, 2010, 398-469. Google Scholar [9] C. Carlet, P. Guilot and S. Mesnager, On immunity profile of Boolean functions, in Proc Seq. Appl. - SETA 2006, Springer-Verlag, Berlin, 2006, 364-375. doi: 10.1007/11863854_32.  Google Scholar [10] C. Carlet and P. Sarkar, Spectral domain analysis of correlation immune and resilient Boolean functions, Finite Fields Appl., 8 (2002), 120-130. doi: 10.1006/ffta.2001.0332.  Google Scholar [11] V. V. Chepyzhov, T. Johansson and B. Smeets, A simple algorithm for fast correlation attacks on stream ciphers, in Fast Software Encryption, FSE 2000, Springer-Verlag, Berlin, 2001, 181-195. Google Scholar [12] B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich and R. Smolensky, The bit extraction problem or $t$-resilient functions, in 26th IEEE Symp. Found. Comp. Sci., 1985, 396-407. Google Scholar [13] G. Cohen, I. Honkala , S. Litsyn and A. Lobstein, Covering Codes, North-Holland, Amsterdam, 1997.  Google Scholar [14] J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D. thesis, Univ. Maryland, 1974.  Google Scholar [15] T. Johansson and E. Pasalic, A construction of resilient functions with high nonlinearity, IEEE Trans. Inform. Theory, 49 (2003), 494-501. doi: 10.1109/TIT.2002.807297.  Google Scholar [16] K. Kurosawa, T. Johansson and D. Stinson, Almost $k$-wise independent sample spaces and their cryptologic applications, J. Crypt., 14 (2001), 301-324. doi: 10.1007/3-540-69053-0_28.  Google Scholar [17] K. Kurosawa and R. Matsumoto, Almost security of cryptographic Boolean functions, IEEE Trans. Inform. Theory, 50 (2004), 2572-2761. doi: 10.1109/TIT.2004.836684.  Google Scholar [18] P. Lacharme, Analysis and construction of correctors, IEEE Trans. Inform. Theory, 55 (2009), 4742-4748. doi: 10.1109/TIT.2009.2027483.  Google Scholar [19] J. Liu, L. Chen and X. Guang, Highly nonlinear resilient functions without linear structures, IEICE Trans. Fundam., E97-A (2014), 1405-1417. Google Scholar [20] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977. Google Scholar [21] W. Meier and O. Staffelbach, Fast correlation attacks on stream ciphers, in Adv. Crypt. - EUROCRYPT'88, Springer-Verlag, Berlin, 1988, 301-314. Google Scholar [22] P. Sarkar and S. Maitra, Nonlinearity bounds and constructions of resilient Boolean functions, in Adv. Crypt. - CRYPTO 2000, Springer-Verlag, Berlin, 2000, 515-532. doi: 10.1007/3-540-44598-6_32.  Google Scholar [23] T. Siegenthaler, Correlation immunity of nonlinear combining functions for cryptographic applications, IEEE Trans. Inform. Theory, 30 (1984), 776-780. doi: 10.1109/TIT.1984.1056949.  Google Scholar [24] T. Siegenthaler, Decrypting a class of stream ciphers using ciphertext only, IEEE Trans. Comp., C-34 (1985), 81-85. Google Scholar [25] Y. V. Tarannikov, New constructions of resilient Boolean functions with maximum nonlinearity, in Proc. 8th Int. Workshop FSE 2001, Springer-Verlag, Berlin, 2001, 66-77. Google Scholar [26] G. Z. Xiao and J. L. Massey, A spectral characterization of correlation-immune combining functions, IEEE Trans. Inform. Theory, 34 (1988), 569-571. doi: 10.1109/18.6037.  Google Scholar [27] W. Zhang and E. Pasalic, Constructions of resilient S-boxes with strictly almost optimal nonlinearity through disjoint linear codes, IEEE Trans. Inform. Theory, 60 (2014), 1638-1651. doi: 10.1109/TIT.2014.2300067.  Google Scholar [28] X.-M. Zhang and Y. Zheng, Cryptographically resilient functions, IEEE Trans. Inform. Theory, 43 (1997), 1740-1747. doi: 10.1109/18.623184.  Google Scholar

2020 Impact Factor: 0.935