American Institute of Mathematical Sciences

Advanced
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

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.  Google Scholar

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

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

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

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

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

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

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

[9]

T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and Applications, Elsevier-Academic Press, New York, 2009.  Google Scholar

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

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

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

[13]

D. E. Knuth, The Art of Computer Programming: Bitwise Tricks & Techniques; Binary Decision Diagrams, Addison-Wesley Professional, Boston, 2009.  Google Scholar

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

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

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

[17]

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

[18]

M. S. Lobanov, Exact relations between nonlinearity and algebraic immunity, J. Appl. Ind. Math., 3 (2009), 367-376. doi: 10.1134/S1990478909030077.  Google Scholar

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

[20]

W. Meier and O. Staffelbach, Fast correlation attacks on stream ciphers, in Advances in Cryptology - EUROCRYPT '88, Springer-Verlag, 1988, 301-314. Google Scholar

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

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

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

[24]

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

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

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

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

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

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

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

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

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

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

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

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.  Google Scholar

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

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

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

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

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

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

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

[9]

T. W. Cusick and P. Stănică, Cryptographic Boolean Functions and Applications, Elsevier-Academic Press, New York, 2009.  Google Scholar

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

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

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

[13]

D. E. Knuth, The Art of Computer Programming: Bitwise Tricks & Techniques; Binary Decision Diagrams, Addison-Wesley Professional, Boston, 2009.  Google Scholar

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

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

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

[17]

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

[18]

M. S. Lobanov, Exact relations between nonlinearity and algebraic immunity, J. Appl. Ind. Math., 3 (2009), 367-376. doi: 10.1134/S1990478909030077.  Google Scholar

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

[20]

W. Meier and O. Staffelbach, Fast correlation attacks on stream ciphers, in Advances in Cryptology - EUROCRYPT '88, Springer-Verlag, 1988, 301-314. Google Scholar

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

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

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

[24]

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

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

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

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

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

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

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

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

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

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

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

[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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - B, 2007, 8 (4) : 1007-1020. doi: 10.3934/dcdsb.2007.8.1007
[16]

Maolin Cheng, Mingyin Xiang. Application of a modified CES production function model based on improved firefly algorithm. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1571-1584. doi: 10.3934/jimo.2019018
[17]

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

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

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

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

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy