×

Concatenations of the hidden weighted bit function and their cryptographic properties. (English) Zbl 1300.94099

Summary: 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 R. E. Bryant [IEEE Trans. Comput. 40, No. 2, 205–213 (1991; Zbl 1220.68060)], seems to be the simplest function with exponential BDD size. In [Discrete Appl. Math. 174, 1–10 (2014; Zbl 1298.94110)], Q. Wan 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.

MSC:

94A60 Cryptography
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

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, 205 (1991) · Zbl 1220.68060 · doi:10.1109/12.73590
[2] C. Carlet, On the higher order nonlinearities of algebraic immune functions,, in Advances in Cryptology - CRYPTO 2006, 584 (2006) · Zbl 1129.94015 · doi:10.1007/11818175_35
[3] C. Carlet, Boolean functions for cryptography and error correcting codes,, in Boolean Models and Methods in Mathematics, 257 (2010) · Zbl 1209.94035
[4] C. Carlet, Algebraic immunity for cryptographically significant Boolean functions: analysis and construction,, IEEE Trans. Inf. Theory, 52, 3105 (2006) · Zbl 1192.94091 · doi:10.1109/TIT.2006.876253
[5] C. Carlet, 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, 425 (2008) · Zbl 1206.94060 · doi:10.1007/978-3-540-89255-7_26
[6] C. Carlet, An infinite class of balanced vectorial Boolean functions with optimum algebraic immunity and good nonlinearity,, in IWCC 2009, 1 (2009) · Zbl 1248.94060 · 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, 176 (2003) · Zbl 1122.94365 · doi:10.1007/978-3-540-45146-4_11
[8] N. Courtois, Algebraic attacks on stream ciphers with linear feedback,, in Advances in Cryptology - EUROCRYPT 2003, 345 (2003) · Zbl 1038.94525 · doi:10.1007/3-540-39200-9_21
[9] T. W. Cusick, <em>Cryptographic Boolean Functions and Applications</em>,, Elsevier-Academic Press (2009) · Zbl 1173.94002
[10] D. K. Dalai, Cryptographically significant Boolean functions: Construction and analysis in terms of algebraic immunity,, in Proceedings of FSE 2005, 98 (2005) · Zbl 1140.94334
[11] D. K. Dalai, Basic theory in construction of Boolean functions with maximum possible annihilator immunity,, Des. Codes Cryptogr., 40, 41 (2006) · Zbl 1202.94179 · doi:10.1007/s10623-005-6300-x
[12] P. Hawkes, Rewriting variables: the complexity of fast algebraic attacks on stream ciphers,, in Advances in Cryptology - CRYPTO 2004, 390 (2004) · Zbl 1104.94023 · doi:10.1007/978-3-540-28628-8_24
[13] D. E. Knuth, <em>The Art of Computer Programming: Bitwise Tricks & Techniques; Binary Decision Diagrams</em>,, Addison-Wesley Professional (2009) · Zbl 1178.68372
[14] M. Krause, BDD-based cryptanalysis of keystream generators,, in Advances in Cryptology - EUROCRYPT 2002, 222 (2002) · Zbl 1055.94018 · doi:10.1007/3-540-46035-7_15
[15] N. Li, Construction and analysis of Boolean functions of \(2t+1\) variables with maximum algebraic immunity,, in Advances in Cryptology - ASIACRYPT 2006, 84 (2006) · Zbl 1172.94584 · doi:10.1007/11935230_6
[16] N. Li, On the construction of Boolean functions with optimal algebraic immunity,, IEEE Trans. Inf. Theory, 54, 1330 (2008) · Zbl 1306.94070 · doi:10.1109/TIT.2007.915914
[17] M. S. Lobanov, Exact relation between nonlinearity and algebraic immunity,, Discrete Math. Appl., 16, 453 (2006) · Zbl 1121.94020 · doi:10.1515/156939206779238418
[18] M. S. Lobanov, Exact relations between nonlinearity and algebraic immunity,, J. Appl. Ind. Math., 3, 367 (2009) · Zbl 1249.94035 · doi:10.1134/S1990478909030077
[19] W. Meier, Algebraic attacks and decomposition of Boolean functions,, in Advances in Cryptology - EUROCRYPT 2004, 474 (2004) · Zbl 1122.94041 · doi:10.1007/978-3-540-24676-3_28
[20] W. Meier, Fast correlation attacks on stream ciphers,, in Advances in Cryptology - EUROCRYPT ’88, 301 (1988) · Zbl 0673.94010
[21] S. Mesnager, Improving the lower bound on the higher order nonlinearity of Boolean functions with prescribed algebraic immunity,, IEEE Trans. Inf. Theory, 54, 3656 (2008) · Zbl 1247.94028 · 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, 399 (2008) · Zbl 05531800 · 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, 4014 (2010) · Zbl 1366.94528 · doi:10.1109/TIT.2010.2050801
[24] O. S. Rothaus, On bent functions,, J. Comb. Theory Ser. A, 20, 300 (1976) · Zbl 0336.12012
[25] C. Tan, Several classes of even-variable balanced Boolean functions with optimal algebraic immunity,, IEICE Trans. Fund., E94.A, 165 (2011)
[26] D. Tang, Highly nonlinear Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks,, IEEE Trans. Inf. Theory, 59, 653 (2013) · Zbl 1364.94808 · doi:10.1109/TIT.2012.2217476
[27] Z. Tu, A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity,, Des. Codes Cryptogr., 60, 1 (2011) · Zbl 1226.94013 · doi:10.1007/s10623-010-9413-9
[28] Q. Wang, Cryptographic properties of the hidden weighted bit function,, Discrete Appl. Math. · Zbl 1298.94110 · doi:10.1016/j.dam.2014.01.010
[29] Q. Wang, Some results on fast algebraic attacks and higher-order non-linearities,, IET Inform. Secur., 6, 41 (2012)
[30] Q. Wang, Constructions of cryptographically significant Boolean functions using primitive polynomials,, IEEE Trans. Inf. Theory, 56, 3048 (2010) · Zbl 1366.94541 · doi:10.1109/TIT.2010.2046195
[31] Q. Wang, A new method to construct Boolean functions with good cryptographic properties,, Inform. Proc. Lett., 113, 567 (2013) · Zbl 1358.94117 · doi:10.1016/j.ipl.2013.04.017
[32] Q. Wang, Balanced Boolean functions with optimum algebraic degree, optimum algebraic immunity and very high nonlinearity,, Discrete Appl. Math., 1673, 25 (2014) · Zbl 1317.94172 · doi:10.1016/j.dam.2013.11.014
[33] A. F. Webster, On the design of S-boxes,, in Advances in Cryptology - CRYPTO ’85, 523 (1985)
[34] X. Zeng, More balanced Boolean functions with optimal algebraic immunity, and good nonlinearity and resistance to fast algebraic attacks,, IEEE Trans. Inf. Theory, 57, 6310 (2011) · Zbl 1365.94686 · doi:10.1109/TIT.2011.2109935
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.