Abstract
This paper proposes a general method to construct 1-resilient Boolean functions by modifying the Tu-Deng and Tang-Carlet-Tang functions. Cryptographic properties such as algebraic degree, nonlinearity and algebraic immunity are also considered. A sufficient condition of the modified functions with optimal algebraic degree in terms of the Siegenthaler bound is proposed. The authors obtain a lower bound on the nonlinearity of the Tang-Carlet-Tang functions, which is slightly better than the known result. If the authors do not break the “continuity” of the support and zero sets, the functions constructed in this paper have suboptimal algebraic immunity. Finally, four specific classes of 1-resilient Boolean functions constructed from this construction and with the mentioned good cryptographic properties are proposed. Experimental results show that there are many 1-resilient Boolean functions have higher nonlinearities than known 1-resilient functions modified by Tu-Deng and Tang-Carlet-Tang functions.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Carlet C, Boolean functions for cryptography and error correcting codes, The Monography Boolean Models and Methods in Mathematics, Computer Science, and Engineering (eds. by Hammer P and Crama Y), Cambridge University Press, 2010, 257–397.
Siegenthaler T, Correlation-immunity of nonlinear combining functions for cryptographic applications, IEEE Trans. Inf. Theory, 1984, 30(5): 776–780.
Xiao G and Massey J, A spectral characterization of correlation-immune combining functions, IEEE Trans. Inf. Theory, 1988, 34(3): 569–571.
Camion P, Carlet C, Charpin P, et al., On correlation-immune functions, CRYPTO’91, Lecture Notes in Computer Science, 1992, 576: 86–100.
Chee S, Lee S, Lee D, et al., On the correlation immune functions and their nonlinearity, ASIACRYPT’ 96, Lecture Notes in Computer Science, 1996, 1163: 232–243.
Filiol E and Fontaine C, Highly nonlinear balanced Boolean functions with a good correlationimmunity, EUROCRYPT 1998, Lecture Notes in Computer Science, 1998, 1403: 475–488.
Pasalic E and Johansson T, Further results on the relation between nonlinearity and resiliency for Boolean functions, Cryptography and Coding, Lecture Notes in Computer Science, 1999, 1746: 35–44.
Zhang W and Xiao G, Constructions of almost optimal resilient Boolean functions on large even number of variables, IEEE Trans. Inf. Theory, 2009, 55(12): 5822–5831.
Zhang W and Pasalic E, Generalized Maiorana-McFarland construction of resilient Boolean functions with high nonlinearity and good algebraic properties, IEEE Trans. Inf. Theory, 2014, 60(10): 6681–6695.
Courtois N and Meier W, Algebraic attacks on stream ciphers with linear feedback, EUROCRYPT 2003, Lecture Notes in Computer Science, 2003, 2656: 345–359.
Meier W, Pasalic E, and Carlet C, Algebraic attacks and decomposition of Boolean functions, EUROCRYPT 2004, Lecture Notes in Computer Science, 2004, 3027: 474–491.
Courtois N, Fast algebraic attacks on stream ciphers with linear feedback, CRYPTO 2003, Lecture Notes in Computer Science, 2003, 2729: 176–194.
Lobanov M, Tight bound between nonlinearity and algebraic immunity, Cryptology ePrint Archive, Report 2005/441, 2005.
Braeken A and Preneel B, On the algebraic immunity of symmetric Boolean functions, INDOCRYPT 2005, Lecture Notes in Computer Science, 2005, 3797: 35–48.
Carlet C, A method of construction of balanced functions with optimum algebraic immunity, Proceedings of the International Workshop on Coding and Cryptology, Coding Theory and Cryptology, 2008, 4: 25–43.
Carlet C, Dalai D, Gupta K, et al., Algebraic immunity for cryptographicly significant Boolean functions: analysis and construction, IEEE Trans. Inf. Theory, 2006, 52(7): 3105–3121.
Carlet C, Zeng X, Li C, et al., Further properties of several classes of Boolean functions with optimum algebraic immunity, Des. Codes Cryptogr., 2009, 52(3): 303–338.
Dalai D, Gupta K, and Maitra S, Cryptographicly significant Boolean functions: Construction and analysis in terms of algebraic immunity, FSE 2005, Lecture Notes in Computer Science, 2005, 3557: 98–111.
Dalai D, Maitra S, and Sarkar S, Basic theory in construction of Boolean functions with maximum possible annihilator immunity, Des. Codes Cryptogr., 2006, 40(1): 41–58.
Li N and Qi W, Construction and analysis of Boolean functions of 2t+1 variables with maximum algebraic immunity, ASIACRYPT 2006, Lecture Notes in Computer Science, 2006, 4284: 84–98.
Li N, Qu L, Qi W, et al., On the construction of Boolean functions with optimal algebraic immunity, IEEE Trans. Inf. Theory, 2008, 54(3): 1330–1334.
Carlet C and Feng K, An infinite class of balanced functions with optimal algebraic immunity, good immunity to fast algebraic attacks and good nonlinearity, ASIACRYPT 2008, Lecture Notes in Computer Science, 2008, 5350: 425–440.
Tu Z and Deng Y, A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity, Des. Codes Cryptogr., 2011, 60(1): 1–14.
Carlet C, On a weakness of the Tu-Deng function and its repair, Cryptology ePrint Archive, Report 2009/606, 2009.
Tang D, Carlet C, and Tang X, Highly nonlinear Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks, IEEE Trans. Inf. Theory, 2013, 59(1): 653–664.
Tu Z and Deng Y, A class of 1-resilient function with high nonlinearity and algebraic immunity, Cryptology ePrint Archive, Report 2010/179, 2010.
Tang D, Carlet C, and Tang X, A class of 1-resilient Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks, Int. J. Found. Comput. Sci., 2014, 25(6): 763–780.
Armknecht F, Carlet C, Gaborit P, et al., Efficient computation of algebraic immunity for algebraic and fast algebraic attacks, EUROCRYPT 2006, Lecture Notes in Computer Science, 2006, 4004: 147–164.
MacWilliams F and Sloane N, The Theory of Error-Correcting Codes, NorthHolland, Amsterdam, 1977.
Li J, Carlet C, Zeng X, et al., Two constructions of balanced Boolean functions with optimal algebraic immunity, high nonlinearity and good behavior against fast algebraic attacks, Des. Codes Cryptogr., 2015, 76(2): 279–305.
Cohen G and Flori J, On a generalized combinatorial conjecture involving addition mod 2k − 1, Cryptology ePrint Archive, Report 2011/400, 2011.
Cusick T, Li Y, and Stănică P, On a combinatorial conjecture, Cryptology ePrint Archive, Report 2009/554, 2009.
Flori J, Randriam H, Cohen G, et al., On a conjecture about binary strings distribution, SETA 2010, Lecture Notes in Computer Science, 2010, 6338: 346–358.
Flori J and Randriam H, On the number of carries occuring in an addition mod 2k−1, Cryptology ePrint Archive, Report 2011/245, 2011.
Tang D, Carlet C, and Tang X, Highly nonlinear Boolean functions with optimal algebraic immunity and good behavior against fast algebraic attacks, Cryptology ePrint Archive, Report 2011/366, 2011.
Liu M, Zhang Y, and Lin D, Perfect algberaic immune functions, ASIACRYPT 2012, Lecture Notes in Computer Science, 2012, 7658: 172–189.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was supported by the National Key Basic Research Program of China under Grant No. 2013CB834203, the National Natural Science Foundation of China under Grant Nos. 61472417 and 61472120, and the Research Council of Norway.
This paper was recommended for publication by Editor DENG Yingpu.
Rights and permissions
About this article
Cite this article
Shan, J., Hu, L., Zeng, X. et al. A Construction of 1-Resilient Boolean Functions with Good Cryptographic Properties. J Syst Sci Complex 31, 1042–1064 (2018). https://doi.org/10.1007/s11424-017-6177-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11424-017-6177-6