Concatenations of the hidden weighted bit function and their cryptographic properties

Qichun Wang; Chik How Tan; Pantelimon Stănică

doi:10.3934/amc.2014.8.153

Article Contents

2014, Volume 8, Issue 2: 153-165. Doi: 10.3934/amc.2014.8.153

This issue Previous Article On Abelian group representability of finite groups Next Article Algebraic space-time codes based on division algebras with a unitary involution

Concatenations of the hidden weighted bit function and their cryptographic properties

1.
Temasek Laboratories, National University of Singapore, 117411
2.
Department of Applied Mathematics, Naval Postgraduate School, Monterey, CA 93943-5216

Received: December 31, 2012

Revised: August 31, 2013

Published: April 2014

Abstract Related Papers Cited by

Abstract

To resist Binary Decision Diagrams (BDD) based attacks, a Boolean function should have a high BDD size. The hidden weighted bit function (HWBF), introduced by Bryant in 1991, seems to be the simplest function with exponential BDD size. In [28], Wang et al. investigated the cryptographic properties of the HWBF and found that it is a very good candidate for being used in real ciphers. In this paper, we modify the HWBF and construct two classes of functions with very good cryptographic properties (better than the HWBF). The new functions are balanced, with almost optimum algebraic degree and satisfy the strict avalanche criterion. Their nonlinearity is higher than that of the HWBF. We investigate their algebraic immunity, BDD size and their resistance against fast algebraic attacks, which seem to be better than those of the HWBF too. The new functions are simple, can be implemented efficiently, have high BDD sizes and rather good cryptographic properties. Therefore, they might be excellent candidates for constructions of real-life ciphers.

Keywords:

Mathematics Subject Classification: 11T71.

Citation:

Related Papers

Cited by

References

[1]	R. E. Bryant, On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication, IEEE Trans. Comput., 40 (1991), 205-213.doi: 10.1109/12.73590.
[2]	C. Carlet, On the higher order nonlinearities of algebraic immune functions, in Advances in Cryptology - CRYPTO 2006, Springer-Verlag, 2006, 584-601.doi: 10.1007/11818175_35.
[3]	C. Carlet, Boolean functions for cryptography and error correcting codes, in Boolean Models and Methods in Mathematics, Computer Science, and Engineering, Cambridge Univ. Press, 2010, 257-397.
[4]	C. Carlet, D. K. Dalai, K. C. Gupta and S. Maitra, Algebraic immunity for cryptographically significant Boolean functions: analysis and construction, IEEE Trans. Inf. Theory, 52 (2006), 3105-3121.doi: 10.1109/TIT.2006.876253.
[5]	C. Carlet and K. Feng, An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity, in Advances in Cryptology - ASIACRYPT 2008, Springer-Verlag, 2008, 425-440.doi: 10.1007/978-3-540-89255-7_26.
[6]	C. Carlet and K. Feng, An infinite class of balanced vectorial Boolean functions with optimum algebraic immunity and good nonlinearity, in IWCC 2009, Springer-Verlag, 2009, 1-11.doi: 10.1007/978-3-642-01877-0_1.
[7]	N. Courtois, Fast algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology - CRYPTO 2003, Springer-Verlag, 2003, 176-194.doi: 10.1007/978-3-540-45146-4_11.
[8]	N. Courtois and W. Meier, Algebraic attacks on stream ciphers with linear feedback, in Advances in Cryptology - EUROCRYPT 2003, Springer-Verlag, 2003, 345-359.doi: 10.1007/3-540-39200-9_21.
[9]	T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and Applications, Elsevier-Academic Press, New York, 2009.
[10]	D. K. Dalai, K. C. Maitra and S. Maitra, Cryptographically significant Boolean functions: Construction and analysis in terms of algebraic immunity, in Proceedings of FSE 2005, Springer-Verlag, 2005, 98-111.
[11]	D. K. Dalai, S. Maitra and S. Sarkar, Basic theory in construction of Boolean functions with maximum possible annihilator immunity, Des. Codes Cryptogr., 40 (2006), 41-58.doi: 10.1007/s10623-005-6300-x.
[12]	P. Hawkes and G. G. Rose, Rewriting variables: the complexity of fast algebraic attacks on stream ciphers, in Advances in Cryptology - CRYPTO 2004, Springer-Verlag, 2004, 390-406.doi: 10.1007/978-3-540-28628-8_24.
[13]	D. E. Knuth, The Art of Computer Programming: Bitwise Tricks & Techniques; Binary Decision Diagrams, Addison-Wesley Professional, Boston, 2009.
[14]	M. Krause, BDD-based cryptanalysis of keystream generators, in Advances in Cryptology - EUROCRYPT 2002, Springer-Verlag, 2002, 222-237.doi: 10.1007/3-540-46035-7_15.
[15]	N. Li and W. F. Qi, Construction and analysis of Boolean functions of $2t+1$ variables with maximum algebraic immunity, in Advances in Cryptology - ASIACRYPT 2006, Springer-Verlag, 2006, 84-98.doi: 10.1007/11935230_6.
[16]	N. Li, L. Qu, W. Qi, G. Feng, C. Li and D. Xie, On the construction of Boolean functions with optimal algebraic immunity, IEEE Trans. Inf. Theory, 54 (2008), 1330-1334.doi: 10.1109/TIT.2007.915914.
[17]	M. S. Lobanov, Exact relation between nonlinearity and algebraic immunity, Discrete Math. Appl., 16 (2006), 453-460.doi: 10.1515/156939206779238418.
[18]	M. S. Lobanov, Exact relations between nonlinearity and algebraic immunity, J. Appl. Ind. Math., 3 (2009), 367-376.doi: 10.1134/S1990478909030077.
[19]	W. Meier, E. Pasalic and C. Carlet, Algebraic attacks and decomposition of Boolean functions, in Advances in Cryptology - EUROCRYPT 2004, Springer-Verlag, 2004, 474-491.doi: 10.1007/978-3-540-24676-3_28.
[20]	W. Meier and O. Staffelbach, Fast correlation attacks on stream ciphers, in Advances in Cryptology - EUROCRYPT '88, Springer-Verlag, 1988, 301-314.
[21]	S. Mesnager, Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity, IEEE Trans. Inf. Theory, 54 (2008), 3656-3662.doi: 10.1109/TIT.2008.926360.
[22]	E. Pasalic, Almost fully optimized infinite classes of Boolean functions resistant to (fast) algebraic cryptanalysis, in Proceedings of ICISC 2008, Springer-Verlag, 2009, 399-414.doi: 10.1007/978-3-642-00730-9_25.
[23]	P. Rizomiliotis, On the resistance of Boolean functions against algebraic attacks using univariate polynomial representation, IEEE Trans. Inf. Theory, 56 (2010), 4014-4024.doi: 10.1109/TIT.2010.2050801.
[24]	O. S. Rothaus, On bent functions, J. Comb. Theory Ser. A, 20 (1976), 300-305.
[25]	C. Tan and S. Goh, Several classes of even-variable balanced Boolean functions with optimal algebraic immunity, IEICE Trans. Fund., E94.A (2011), 165-171.
[26]	D. Tang, C. Carlet and X. Tang, Highly nonlinear Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks, IEEE Trans. Inf. Theory, 59 (2013), 653-664.doi: 10.1109/TIT.2012.2217476.
[27]	Z. Tu and Y. Deng, A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity, Des. Codes Cryptogr., 60 (2011), 1-14.doi: 10.1007/s10623-010-9413-9.
[28]	Q. Wang, C. Carlet, P. Stănică and C. Tan, Cryptographic properties of the hidden weighted bit function, Discrete Appl. Math., to appear. doi: 10.1016/j.dam.2014.01.010.
[29]	Q. Wang, T. Johansson and H. Kan, Some results on fast algebraic attacks and higher-order non-linearities, IET Inform. Secur., 6 (2012), 41-46.
[30]	Q. Wang, J. Peng, H. Kan and X. Xue, Constructions of cryptographically significant Boolean functions using primitive polynomials, IEEE Trans. Inf. Theory, 56 (2010), 3048-3053.doi: 10.1109/TIT.2010.2046195.
[31]	Q. Wang and C. H. Tan, A new method to construct Boolean functions with good cryptographic properties, Inform. Proc. Lett., 113 (2013), 567-571.doi: 10.1016/j.ipl.2013.04.017.
[32]	Q. Wang and C. H. Tan, Balanced Boolean functions with optimum algebraic degree, optimum algebraic immunity and very high nonlinearity, Discrete Appl. Math., 1673 (2014), 25-32.doi: 10.1016/j.dam.2013.11.014.
[33]	A. F. Webster and S. E. Tavares, On the design of S-boxes, in Advances in Cryptology - CRYPTO '85, Springer-Verlag, 1985, 523-534.
[34]	X. Zeng, C. Carlet, J. Shan and L. Hu, More balanced Boolean functions with optimal algebraic immunity, and good nonlinearity and resistance to fast algebraic attacks, IEEE Trans. Inf. Theory, 57 (2011), 6310-6320.doi: 10.1109/TIT.2011.2109935.