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

Concatenations of the hidden weighted bit function and their cryptographic properties

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

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.
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. doi: 10.1109/12.73590.

[2]

C. Carlet, On the higher order nonlinearities of algebraic immune functions,, in Advances in Cryptology - CRYPTO 2006, (2006), 584. doi: 10.1007/11818175_35.

[3]

C. Carlet, Boolean functions for cryptography and error correcting codes,, in Boolean Models and Methods in Mathematics, (2010), 257.

[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. 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, (2008), 425. 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, (2009), 1. 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, (2003), 176. 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, (2003), 345. doi: 10.1007/3-540-39200-9_21.

[9]

T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and Applications,, Elsevier-Academic Press, (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, (2005), 98.

[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. 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, (2004), 390. 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, (2009).

[14]

M. Krause, BDD-based cryptanalysis of keystream generators,, in Advances in Cryptology - EUROCRYPT 2002, (2002), 222. 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, (2006), 84. 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. doi: 10.1109/TIT.2007.915914.

[17]

M. S. Lobanov, Exact relation between nonlinearity and algebraic immunity,, Discrete Math. Appl., 16 (2006), 453. doi: 10.1515/156939206779238418.

[18]

M. S. Lobanov, Exact relations between nonlinearity and algebraic immunity,, J. Appl. Ind. Math., 3 (2009), 367. 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, (2004), 474. 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, (1988), 301.

[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. 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, (2008), 399. 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. doi: 10.1109/TIT.2010.2050801.

[24]

O. S. Rothaus, On bent functions,, J. Comb. Theory Ser. A, 20 (1976), 300.

[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.

[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. 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. 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., (). 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.

[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. 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. 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. 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, (1985), 523.

[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. 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. doi: 10.1109/12.73590.

[2]

C. Carlet, On the higher order nonlinearities of algebraic immune functions,, in Advances in Cryptology - CRYPTO 2006, (2006), 584. doi: 10.1007/11818175_35.

[3]

C. Carlet, Boolean functions for cryptography and error correcting codes,, in Boolean Models and Methods in Mathematics, (2010), 257.

[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. 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, (2008), 425. 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, (2009), 1. 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, (2003), 176. 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, (2003), 345. doi: 10.1007/3-540-39200-9_21.

[9]

T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and Applications,, Elsevier-Academic Press, (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, (2005), 98.

[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. 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, (2004), 390. 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, (2009).

[14]

M. Krause, BDD-based cryptanalysis of keystream generators,, in Advances in Cryptology - EUROCRYPT 2002, (2002), 222. 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, (2006), 84. 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. doi: 10.1109/TIT.2007.915914.

[17]

M. S. Lobanov, Exact relation between nonlinearity and algebraic immunity,, Discrete Math. Appl., 16 (2006), 453. doi: 10.1515/156939206779238418.

[18]

M. S. Lobanov, Exact relations between nonlinearity and algebraic immunity,, J. Appl. Ind. Math., 3 (2009), 367. 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, (2004), 474. 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, (1988), 301.

[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. 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, (2008), 399. 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. doi: 10.1109/TIT.2010.2050801.

[24]

O. S. Rothaus, On bent functions,, J. Comb. Theory Ser. A, 20 (1976), 300.

[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.

[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. 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. 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., (). 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.

[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. 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. 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. 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, (1985), 523.

[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. 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]

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

[3]

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 & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783

[4]

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 & Optimization, 2011, 1 (2) : 225-244. doi: 10.3934/naco.2011.1.225

[5]

Martin Gugat, Günter Leugering, Ke Wang. Neumann boundary feedback stabilization for a nonlinear wave equation: A strict $H^2$-lyapunov function. Mathematical Control & Related Fields, 2017, 7 (3) : 419-448. doi: 10.3934/mcrf.2017015

[6]

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

[7]

Minvydas Ragulskis, Zenonas Navickas. Hash function construction based on time average moiré. Discrete & Continuous Dynamical Systems - B, 2007, 8 (4) : 1007-1020. doi: 10.3934/dcdsb.2007.8.1007

[8]

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

[9]

Liuyang Yuan, Zhongping Wan, Qiuhua Tang. A criterion for an approximation global optimal solution based on the filled functions. Journal of Industrial & Management Optimization, 2016, 12 (1) : 375-387. doi: 10.3934/jimo.2016.12.375

[10]

Liming Wang. A passivity-based stability criterion for reaction diffusion systems with interconnected structure. Discrete & Continuous Dynamical Systems - B, 2012, 17 (1) : 303-323. doi: 10.3934/dcdsb.2012.17.303

[11]

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

[12]

Robert Baier, Lars Grüne, Sigurđur Freyr Hafstein. Linear programming based Lyapunov function computation for differential inclusions. Discrete & Continuous Dynamical Systems - B, 2012, 17 (1) : 33-56. doi: 10.3934/dcdsb.2012.17.33

[13]

Maolin Cheng, Mingyin Xiang. Application of a modified CES production function model based on improved firefly algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019018

[14]

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

[15]

Mohamed Baouch, Juan Antonio López-Ramos, Blas Torrecillas, Reto Schnyder. An active attack on a distributed Group Key Exchange system. Advances in Mathematics of Communications, 2017, 11 (4) : 715-717. doi: 10.3934/amc.2017052

[16]

Abdelwahab Bensouilah, Van Duong Dinh, Mohamed Majdoub. Scattering in the weighted $ L^2 $-space for a 2D nonlinear Schrödinger equation with inhomogeneous exponential nonlinearity. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2735-2755. doi: 10.3934/cpaa.2019122

[17]

Santanu Sarkar. Analysis of Hidden Number Problem with Hidden Multiplier. Advances in Mathematics of Communications, 2017, 11 (4) : 805-811. doi: 10.3934/amc.2017059

[18]

Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems & Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925

[19]

Deepak Kumar, Ahmad Jazlan, Victor Sreeram, Roberto Togneri. Partial fraction expansion based frequency weighted model reduction for discrete-time systems. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 329-337. doi: 10.3934/naco.2016015

[20]

Shuhua Xu, Fei Gao. Weighted two-phase supervised sparse representation based on Gaussian for face recognition. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1385-1400. doi: 10.3934/dcdss.2015.8.1385

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]