Concatenations of the hidden weighted bit function and their cryptographic properties

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

May 2014, 8(2): 153-165. doi: 10.3934/amc.2014.8.153

Concatenations of the hidden weighted bit function and their cryptographic properties

Qichun Wang ^1, , Chik How Tan ^1, and Pantelimon Stănică ^2,

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

Received January 2013 Revised September 2013 Published May 2014

Abstract
Related Papers

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: Hidden weighted bit function, strict avalanche criterion, nonlinearity, BDD-based attack., algebraic immunity.

Mathematics Subject Classification: 11T7.

Citation: Qichun Wang, Chik How Tan, Pantelimon Stănică. Concatenations of the hidden weighted bit function and their cryptographic properties. Advances in Mathematics of Communications, 2014, 8 (2) : 153-165. doi: 10.3934/amc.2014.8.153

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.

show all references

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.

[1]	Sihem Mesnager, Gérard Cohen. Fast algebraic immunity of Boolean functions. Advances in Mathematics of Communications, 2017, 11 (2) : 373-377. doi: 10.3934/amc.2017031
[2]	Deng Tang. A note on the fast algebraic immunity and its consequences on modified majority functions. Advances in Mathematics of Communications, 2020, 14 (1) : 111-125. doi: 10.3934/amc.2020009
[3]	Claude Carlet, Brahim Merabet. Asymptotic lower bound on the algebraic immunity of random balanced multi-output Boolean functions. Advances in Mathematics of Communications, 2013, 7 (2) : 197-217. doi: 10.3934/amc.2013.7.197
[4]	T. V. Anoop, Nirjan Biswas, Ujjal Das. Admissible function spaces for weighted Sobolev inequalities. Communications on Pure and Applied Analysis, 2021, 20 (9) : 3259-3297. doi: 10.3934/cpaa.2021105
[5]	Markus Dick, Martin Gugat, Günter Leugering. A strict $H^1$-Lyapunov function and feedback stabilization for the isothermal Euler equations with friction. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 225-244. doi: 10.3934/naco.2011.1.225
[6]	Martin Gugat, Günter Leugering, Ke Wang. Neumann boundary feedback stabilization for a nonlinear wave equation: A strict $H^2$-lyapunov function. Mathematical Control and Related Fields, 2017, 7 (3) : 419-448. doi: 10.3934/mcrf.2017015
[7]	Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks and Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783
[8]	Cai-Tong Yue, Jing Liang, Bo-Fei Lang, Bo-Yang Qu. Two-hidden-layer extreme learning machine based wrist vein recognition system. Big Data & Information Analytics, 2017, 2 (1) : 59-68. doi: 10.3934/bdia.2017008
[9]	Grégory Berhuy. Algebraic space-time codes based on division algebras with a unitary involution. Advances in Mathematics of Communications, 2014, 8 (2) : 167-189. doi: 10.3934/amc.2014.8.167
[10]	Bingzheng Li, Zhengzhan Dai. Error analysis on regularized regression based on the Maximum correntropy criterion. Mathematical Foundations of Computing, 2020, 3 (1) : 25-40. doi: 10.3934/mfc.2020003
[11]	Murat Arcak, Eduardo D. Sontag. A passivity-based stability criterion for a class of biochemical reaction networks. Mathematical Biosciences & Engineering, 2008, 5 (1) : 1-19. doi: 10.3934/mbe.2008.5.1
[12]	Ting Hu. Kernel-based maximum correntropy criterion with gradient descent method. Communications on Pure and Applied Analysis, 2020, 19 (8) : 4159-4177. doi: 10.3934/cpaa.2020186
[13]	Liuyang Yuan, Zhongping Wan, Qiuhua Tang. A criterion for an approximation global optimal solution based on the filled functions. Journal of Industrial and Management Optimization, 2016, 12 (1) : 375-387. doi: 10.3934/jimo.2016.12.375
[14]	Liming Wang. A passivity-based stability criterion for reaction diffusion systems with interconnected structure. Discrete and Continuous Dynamical Systems - B, 2012, 17 (1) : 303-323. doi: 10.3934/dcdsb.2012.17.303
[15]	Minvydas Ragulskis, Zenonas Navickas. Hash function construction based on time average moiré. Discrete and Continuous Dynamical Systems - B, 2007, 8 (4) : 1007-1020. doi: 10.3934/dcdsb.2007.8.1007
[16]	Chandan Dey, Sumit Kumar Pandey, Tapabrata Roy, Santanu Sarkar. Differential faultt attack on DEFAULT. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022035
[17]	Maolin Cheng, Mingyin Xiang. Application of a modified CES production function model based on improved firefly algorithm. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1571-1584. doi: 10.3934/jimo.2019018
[18]	Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete and Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33
[19]	Mohammad Bolbolian Ghalibaf. Stress-strength reliability with dependent variables based on copula function. Journal of Dynamics and Games, 2022 doi: 10.3934/jdg.2022014
[20]	Roderick V.N. Melnik, Ningning Song, Per Sandholdt. Dynamics of torque-speed profiles for electric vehicles and nonlinear models based on differential-algebraic equations. Conference Publications, 2003, 2003 (Special) : 610-617. doi: 10.3934/proc.2003.2003.610

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Qichun Wang Chik How Tan Pantelimon Stănică
on Google Scholar
Qichun Wang Chik How Tan Pantelimon Stănică

[Back to Top]