Variation on correlation immune Boolean and vectorial functions

Jian  Liu; Sihem  Mesnager; Lusheng  Chen

doi:10.3934/amc.2016048

Article Contents

2016, Volume 10, Issue 4: 895-919. Doi: 10.3934/amc.2016048

This issue Previous Article On group violations of inequalities in five subgroups Next Article On the duality and the direction of polycyclic codes

Variation on correlation immune Boolean and vectorial functions

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

Received: March 2015

Revised: September 2015

Published: November 2016

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 06E30; Secondary: 94A60.

Citation:

Related Papers

Cited by

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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[13]	G. Cohen, I. Honkala , S. Litsyn and A. Lobstein, Covering Codes, North-Holland, Amsterdam, 1997.
[14]	J. F. Dillon, Elementary Hadamard Difference Sets, Ph.D. thesis, Univ. Maryland, 1974.
[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.
[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.
[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.
[18]	P. Lacharme, Analysis and construction of correctors, IEEE Trans. Inform. Theory, 55 (2009), 4742-4748.doi: 10.1109/TIT.2009.2027483.
[19]	J. Liu, L. Chen and X. Guang, Highly nonlinear resilient functions without linear structures, IEICE Trans. Fundam., E97-A (2014), 1405-1417.
[20]	F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland, Amsterdam, 1977.
[21]	W. Meier and O. Staffelbach, Fast correlation attacks on stream ciphers, in Adv. Crypt. - EUROCRYPT'88, Springer-Verlag, Berlin, 1988, 301-314.
[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.
[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.
[24]	T. Siegenthaler, Decrypting a class of stream ciphers using ciphertext only, IEEE Trans. Comp., C-34 (1985), 81-85.
[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.
[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.
[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.
[28]	X.-M. Zhang and Y. Zheng, Cryptographically resilient functions, IEEE Trans. Inform. Theory, 43 (1997), 1740-1747.doi: 10.1109/18.623184.