Abstract
Given a Boolean function f on n-variables, we find a reduced set of homogeneous linear equations by solving which one can decide whether there exist annihilators at degree d or not. Using our method the size of the associated matrix becomes \(\nu_f \times (\sum_{i=0}^{d} \binom{n}{i} -- \mu_f)\), where, ν f = |{x | wt(x) > d, f(x) = 1}| and μ f = |{x | wt(x) ≤d, f(x) = 1}| and the time required to construct the matrix is same as the size of the matrix. This is a preprocessing step before the exact solution strategy (to decide on the existence of the annihilators) that requires to solve the set of homogeneous linear equations (basically to calculate the rank) and this can be improved when the number of variables and the number of equations are minimized. As the linear transformation on the input variables of the Boolean function keeps the degree of the annihilators invariant, our preprocessing step can be more efficiently applied if one can find an affine transformation over f(x) to get h(x) = f(Bx+b) such that μ h = |{x | h(x) = 1, wt(x) ≤d}| is maximized (and in turn ν h is minimized too). We present an efficient heuristic towards this. Our study also shows for what kind of Boolean functions the asymptotic reduction in the size of the matrix is possible and when the reduction is not asymptotic but constant.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Armknecht, F., Carlet, C., Gaborit, P., Künzli, S., Meier, W., Ruatta, O.: Efficient computation of algebraic immunity for algebraic and fast algebraic attacks. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 147–164. Springer, Heidelberg (2006)
Armknecht, F.: Improving Fast Algebraic Attacks. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 65–82. Springer, Heidelberg (2004)
Ars, G., Faugére, J.: Algebraic Immunities of functions over finite fields. INRIA report (2005)
Batten, L.M.: Algebraic Attacks over GF(q). In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 84–91. Springer, Heidelberg (2004)
Botev, A., Tarannikov, Y.: Lower bounds on algebraic immunity for recursive constructions of nonlinear filters. Preprint (2004)
Braeken, A., Preneel, B.: Probabilistic algebraic attacks. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 290–303. Springer, Heidelberg (2005)
Braeken, A., Preneel, B.: On the Algebraic Immunity of Symmetric Boolean Functions. In: Maitra, S., Veni Madhavan, C.E., Venkatesan, R. (eds.) INDOCRYPT 2005. LNCS, vol. 3797, pp. 35–48. Springer, Heidelberg (2005), http://eprint.iacr.org/
Braeken, A., Lano, J., Preneel, B.: Evaluating the Resistance of Stream Ciphers with Linear Feedback Against Fast Algebraic Attacks. In: Batten, L.M., Safavi-Naini, R. (eds.) ACISP 2006. LNCS, vol. 4058, pp. 40–51. Springer, Heidelberg (2006)
Canteaut, A.: Open problems related to algebraic attacks on stream ciphers. In: Ytrehus, Ø. (ed.) WCC 2005. LNCS, vol. 3969, pp. 120–134. Springer, Heidelberg (2006)
Carlet, C.: Improving the algebraic immunity of resilient and nonlinear functions and constructing bent functions. IACR ePrint server, (2004/276), http://eprint.iacr.org
Cheon, J.H., Lee, D.H.: Resistance of S-boxes against Algebraic Attacks. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 83–94. Springer, Heidelberg (2004)
Cho, J.Y., Pieprzyk, J.: Algebraic Attacks on SOBER-t32 and SOBER-t16 without Stuttering. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 49–64. Springer, Heidelberg (2004)
Courtois, N., Pieprzyk, J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 267–287. Springer, Heidelberg (2002)
Courtois, N., Meier, W.: Algebraic attacks on stream ciphers with linear feedback. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 345–359. Springer, Heidelberg (2003)
Courtois, N.: Fast algebraic attacks on stream ciphers with linear feedback. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 176–194. Springer, Heidelberg (2003)
Courtois, N.T., Debraize, B., Garrido, E.: On Exact Algebraic [Non-]Immunity of S-Boxes Based on Power Functions. In: Batten, L.M., Safavi-Naini, R. (eds.) ACISP 2006. LNCS, vol. 4058, pp. 76–86. Springer, Heidelberg (2006)
Dalai, D.K., Gupta, K.C., Maitra, S.: Results on Algebraic Immunity for Cryptographically Significant Boolean Functions. In: Canteaut, A., Viswanathan, K. (eds.) INDOCRYPT 2004. LNCS, vol. 3348, pp. 92–106. Springer, Heidelberg (2004)
Dalai, D.K., Gupta, K.C., Maitra, S.: Cryptographically Significant Boolean functions: Construction and Analysis in terms of Algebraic Immunity. In: Gilbert, H., Handschuh, H. (eds.) FSE 2005. LNCS, vol. 3557, pp. 98–111. Springer, Heidelberg (2005)
Dalai, D.K., Maitra, S., Sarkar, S.: Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity. Cryptology ePrint Archive, No. 2005/229 (July 15, 2005), http://eprint.iacr.org/
Didier, F., Tillich, J.-P.: Computing the Algebraic Immunity Efficiently. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 359–374. Springer, Heidelberg (2006)
Lee, D.H., Kim, J., Hong, J., Han, J.W., Moon, D.: Algebraic Attacks on Summation Generators. In: Roy, B., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 34–48. Springer, Heidelberg (2004)
Meier, W., Pasalic, E., Carlet, C.: Algebraic attacks and decomposition of Boolean functions. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 474–491. Springer, Heidelberg (2004)
Nawaz, Y., Gong, G., Gupta, K.C.: Upper Bounds on Algebraic Immunity of Boolean Power Functions. In: Robshaw, M.J.B. (ed.) FSE 2006. LNCS, vol. 4047, pp. 375–389. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dalai, D.K., Maitra, S. (2006). Reducing the Number of Homogeneous Linear Equations in Finding Annihilators. In: Gong, G., Helleseth, T., Song, HY., Yang, K. (eds) Sequences and Their Applications – SETA 2006. SETA 2006. Lecture Notes in Computer Science, vol 4086. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11863854_33
Download citation
DOI: https://doi.org/10.1007/11863854_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44523-4
Online ISBN: 978-3-540-44524-1
eBook Packages: Computer ScienceComputer Science (R0)