access icon free Constructions of involutions with optimal minimum degree

The minimum degree (resp. algebraic degree) of a Boolean permutation is the minimum (resp. maximum) algebraic degree of all the non-zero linear combinations of its coordinate functions. In this study, the authors concentrate on the design of Boolean permutations with optimal minimum degree. First, they present a novel method for optimising the minimum degrees of known Boolean permutations. Second, they show that the Boolean permutations, which are obtained by optimising Boolean permutations without optimal algebraic degree, have optimal minimum degree. At last, it is shown that their method generates an infinite class of involutions with optimal minimum degree.

Inspec keywords: Boolean functions; optimisation

Other keywords: nonzero linear combinations; Boolean permutations; involutions; optimal minimum degree; coordinate functions; minimum algebraic degree; Boolean function

Subjects: Optimisation techniques; Algebra; Formal logic

References

    1. 1)
      • 9. Carlet, C., Zhang, F., Hu, Y.: ‘Secondary constructions of bent functions and their enforcements’, Adv. Math. Commun., 2012, 6, (3), pp. 305314.
    2. 2)
      • 6. Charpin, P., Mesnager, S., Sarkar, S.: ‘Dickson polynomials that are involutions’. Available at https://www.eprint.iacr.org/2015/434.pdf, accessed 6 May 2015.
    3. 3)
      • 22. Yu, Y., Wang, M., Li, Y.: ‘Constructing differential 4-uniform permutations from known ones’, Chin. J. Electron., 2013, 22, (3), pp. 495499.
    4. 4)
      • 21. Li, Y., Wang, M.: ‘Constructing differentially 4-uniform permutations over GF22m from quadratic APN permutations over GF22m+1’, Des. Codes Cryptogr., 2014, 72, (2), pp. 249264.
    5. 5)
      • 14. Mesnager, S.: ‘Bent functions from spreads’, J. Am. Math. Soc., 2015, 632, pp. 295316.
    6. 6)
      • 3. Borghoff, J., Canteaut, A., Güneysu, T., et al: ‘PRINCE – a low-latency block cipher for pervasive computing applications’. Proc. of the 18th Int. Conf. on the Theory and Application of Cryptology and Information Security, Beijing, 2012, pp. 208225.
    7. 7)
      • 16. Zhang, F., Carlet, C., Hu, Y., et al: ‘New secondary constructions of bent functions’, Appl. Algebra Eng. Commun. Comput., 2016, 27, (5), pp. 413434.
    8. 8)
      • 13. Mesnager, S.: ‘Several new infinite families of bent functions and their duals’, IEEE Trans. Inf. Theory, 2014, 60, (7), pp. 43974407.
    9. 9)
      • 24. Siegenthaler, T.: ‘Correlation-immunity of nonlinear combining functions for cryptographic applications’, IEEE Trans. Inf. Theory, 1984, 30, (5), pp. 776780.
    10. 10)
      • 10. Li, N., Helleseth, T., Tang, X., et al: ‘Several new classes of bent functions from Dillon exponents’, IEEE Trans. Inf. Theory, 2013, 59, (3), pp. 18181831.
    11. 11)
      • 25. Kyureghyan, G.M.: ‘Constructing permutations of finite fields via linear translators’, J. Comb. Theory A, 2011, 118, (3), pp. 10521061.
    12. 12)
      • 20. Zha, Z., Hu, L., Sun, S.: ‘Constructing new differentially 4-uniform permutations from the inverse function’, Finite Fields Appl., 2014, 25, pp. 6478.
    13. 13)
      • 18. Fuller, J.E.: ‘Analysis of affine equivalent Boolean functions for cryptography’. PhD thesis, Queensland University of Technology, 2003.
    14. 14)
      • 17. Mesnager, S.: ‘A note on constructions of bent functions from involutions’. Available at https://www.eprint.iacr.org/2015/982.pdf, accessed 13 October 2015.
    15. 15)
      • 5. Canteaut, A., Roué, J.: ‘On the behaviors of affine equivalent S-boxes regarding differential and linear attacks’. Proc. of the 34th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 2015, pp. 4574.
    16. 16)
      • 11. Mandal, B., Stanica, P., Gangopadhyay, S., et al: ‘An analysis of the C class of bent functions’. Available at http://www.eprint.iacr.org/2015/588.pdf, accessed 14 June 2015.
    17. 17)
      • 15. Zhang, F., Wei, Y., Pasalic, E.: ‘Constructions of bent-negabent functions and their relation to the completed Maiorana–McFarland class’, IEEE Trans. Inf. Theory, 2015, 61, (3), pp. 14961506.
    18. 18)
      • 1. Carlet, C.: ‘Vectorial Boolean functions for cryptography’, in Crama, Y., Hammer, P. (EDs.): ‘Boolean models and methods in mathematics, computer science, and engineering’ (Cambridge University Press, Cambridge, 2010), pp. 398469.
    19. 19)
      • 8. Carlet, C.: ‘On the secondary constructions of resilient and bent functions’. Proc. of Coding, Cryptography and Combinatorics, Progress in Computer Science and Applied Logic, Basel, 2004, pp. 328.
    20. 20)
      • 23. Pasalic, E.: ‘Maiorana–McFarland class: degree optimization and algebraic properties’, IEEE Trans. Inf. Theory, 2006, 52, pp. 45814594.
    21. 21)
      • 4. Gallager, R.G.: ‘Low density parity check codes’ (MIT Press, Cambridge, Massachusetts, 1963).
    22. 22)
      • 7. Charpin, P., Mesnager, S., Sarkar, S.: ‘Involutions over the Galois field F2n’, IEEE Trans. Inf. Theory, 2016, 62, (4), pp. 22662276.
    23. 23)
      • 19. Qu, L., Tan, Y., Tan, C., et al: ‘Constructing differentially 4-uniform permutations over F22k via the switching method’, IEEE Trans. Inf. Theory, 2013, 59, (7), pp. 46754686.
    24. 24)
      • 2. http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf, accessed November 2001.
    25. 25)
      • 12. Mesnager, S.: ‘Bent and hyper-bent functions in polynomial form and their link with some exponential sums and Dickson polynomials’, IEEE Trans. Inf. Theory, 2011, 57, (9), pp. 59966009.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2016.0437
Loading

Related content

content/journals/10.1049/iet-ifs.2016.0437
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading