On the nonlinearity of discrete logarithm in double-struck F2n

Risto M. Hakala, Kaisa Nyberg

    Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

    9 Citations (Scopus)


    In this paper, we derive a lower bound to the nonlinearity of the discrete logarithm function in double-struck F2n extended to a bijection in double-struck F2 n. This function is closely related to a family of S-boxes from double-struck F2 n to double-struck F2 m proposed recently by Feng, Liao, and Yang, for which a lower bound on the nonlinearity was given by Carlet and Feng. This bound decreases exponentially with m and is therefore meaningful and proves good nonlinearity only for S-boxes with output dimension m logarithmic to n. By extending the methods of Brandstätter, Lange, and Winterhof we derive a bound that is of the same magnitude. We computed the true nonlinearities of the discrete logarithm function up to dimension n = 11 to see that, in reality, the reduction seems to be essentially smaller. We suggest that the closing of this gap is an important problem and discuss prospects for its solution.

    Original languageEnglish
    Title of host publicationSequences and Their Applications, SETA 2010 - 6th International Conference, Proceedings
    Number of pages13
    Publication statusPublished - 19 Nov 2010
    MoE publication typeA4 Article in a conference publication
    EventInternational Conference on Sequences and Their Applications - Paris, France
    Duration: 13 Sep 201017 Sep 2010
    Conference number: 6

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume6338 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    ConferenceInternational Conference on Sequences and Their Applications
    Abbreviated titleSETA


    • Boolean functions
    • discrete logarithm
    • nonlinearity
    • S-boxes
    • Symmetric cryptography


    Dive into the research topics of 'On the nonlinearity of discrete logarithm in double-struck F<sub>2n</sub>'. Together they form a unique fingerprint.

    Cite this