Symbolic dynamics and rotation symmetric Boolean functions
Tóm tắt
We identify the weights wt(fn) of a family {fn} of rotation symmetric Boolean functions with the cardinalities of the sets of n-periodic points of a finite-type shift, recovering the second author’s result that said weights satisfy a linear recurrence. Similarly, the weights of idempotent functions fn defined on finite fields can be recovered as the cardinalities of curves over those fields and hence satisfy a linear recurrence as a consequence of the rationality of curves’ zeta functions. Weil’s Riemann hypothesis for curves then provides additional information about wt(fn). We apply our results to the case of quadratic functions and considerably extend the results in an earlier paper of ours.
Tài liệu tham khảo
Adams, C.M.: Constructing symmetric ciphers using the CAST design procedure. volume 12, pages 283–316. Selected areas in cryptography (Ottawa), ON, 1995 (1997)
Aubry, Y., Perret, M.: A Weil theorem for singular curves. In: Arithmetic, geometry and coding theory (Luminy, 1993), pages 1–7. de Gruyter, Berlin (1996)
Bileschi, M.L., Cusick, T.W., Padgett, D.: Weights of Boolean cubic monomial rotation symmetric functions. Cryptogr. Commun. 4(2), 105–130 (2012)
Blondeau, C., Nyberg, K.: Perfect nonlinear functions and cryptography. Finite Fields Appl. 32, 120–147 (2015)
Bowen R., Lanford III, O.E.: Zeta functions of restrictions of the shift transformation. In: In Global Analysis (Proc. Sympos. Pure Math., Vol. XIV, Berkeley, Calif., 1968), pp. 43–49. Amer. Math. Soc., Providence, R.I. (1970)
Brown, A., Cusick, T.W.: Recursive weights for some Boolean functions. J. Math Cryptol. 6(2), 105–135 (2012)
Claude Carlet: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2021)
Carlet, C., Gao, G., Liu, W.: A secondary construction and a transformation on rotation symmetric functions, and their action on bent and semi-bent functions. J. Combin. Theory Ser. A 127, 161–175 (2014)
Chirvasitu, A.: Affine equivalence for quadratic rotation symmetric Boolean functions. Des. Codes Cryptogr. 88(7), 1301–1329 (2020)
Cusick, T.W.: Finding Hamming weights without looking at truth tables. Cryptogr. Commun. 5(1), 7–18 (2013)
Cusick, T.W.: Weight recursions for any rotation symmetric Boolean functions. arXiv:1701.06648 (2017)
Cusick, T.W.: Weight recursions for any rotation symmetric Boolean functions. IEEE Trans. Inform. Theory 64(4, part 2), 2962–2968 (2018)
Cusick, T.W., Stănică, P.: Fast evaluation, weights and nonlinearity of rotation-symmetric functions. Discrete Math. 258(1-3), 289–301 (2002)
Cusick, T.W., Stănică, P.: Cryptographic Boolean Functions and Applications, 2nd. Elsevier/Academic Press, London (2017)
Deligne, P.: La conjecture de Weil. I. Inst. Hautes Études Sci. Publ. Math. (43):273–307 (1974)
Dwork, B.: On the rationality of the zeta function of an algebraic variety. Amer. J. Math. 82, 631–648 (1960)
Forré, R.: The strict avalanche criterion: spectral properties of Boolean functions and an extended definition. In: Advances in cryptology—CRYPTO ’88 (Santa Barbara, CA, 1988), volume 403 of Lecture Notes in Comput. Sci., pp 450–468. Springer, Berlin (1990)
Hardy, G.H., Wright, E.M.: An Introduction to the Theory of Numbers, 6th. Oxford University Press, Oxford (2008). Revised by Heath-Brown, D.R. and Silverman, J.H. With a foreword by Andrew Wiles
Hartshorne, R.: Algebraic geometry. Springer-Verlag, New York-Heidelberg. Graduate texts in mathematics, No. 52 (1977)
Jacobson, N.: Basic Algebra, 2nd. W. H. Freeman and Company, New York (1985)
Kim, H., Park, S.-M., Hahn, S.G.: On the weight and nonlinearity of homogeneous rotation symmetric Boolean functions of degree 2. Discrete Appl. Math. 157(2), 428–432 (2009)
Serge Lang. Algebraic number theory: Volume 110 of Graduate Texts in Mathematics, 2nd. Springer-Verlag, New York (1994)
Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995)
Nyberg, K.: Perfect nonlinear S-boxes. In: Advances in cryptology—EUROCRYPT ’91 (Brighton, 1991), volume 547 of Lecture Notes in Comput. Sci., pp 378–386. Springer, Berlin (1991)
Olsen, J.D., Scholtz, R.A., Welch, L.R.: Bent-function sequences. IEEE Trans. Inform. Theory 28(6), 858–864 (1982)
Pieprzyk, J., Qu, C.X.: Fast hashing and rotation-symmetric functions. J.UCS 5(1), 20–31 (1999)
Seberry, J., Zhang, X.M., Zheng, Y.: Nonlinearity and propagation characteristics of balanced Boolean functions. Inform. and Comput. 119(1), 1–13 (1995)
Serre, J.-P.: A Course in Arithmetic. Springer-Verlag, New York-Heidelberg (1973). Translated from the French, Graduate Texts in Mathematics, No. 7
Stănică, P., Maitra, S.: Rotation symmetric Boolean functions—count and cryptographic properties. Discrete Appl. Math. 156(10), 1567–1580 (2008)
Weil, A.: Sur les courbes algébriques et les variétés qui s’en déduisent. Actualités Sci. Ind., no. 1041 = Publ. Inst. Math. Univ. Strasbourg 7(1945). Hermann et Cie., Paris (1948)
Weil, A: Numbers of solutions of equations in finite fields. Bull. Amer. Math. Soc. 55, 497–508 (1949)