On the nonlinearity of discrete logarithm in double-struck F2n

Risto M. Hakala, Kaisa Nyberg

    Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

    9 Sitaatiot (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.

    OtsikkoSequences and Their Applications, SETA 2010 - 6th International Conference, Proceedings
    DOI - pysyväislinkit
    TilaJulkaistu - 19 marraskuuta 2010
    OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
    TapahtumaInternational Conference on Sequences and Their Applications - Paris, Ranska
    Kesto: 13 syyskuuta 201017 syyskuuta 2010
    Konferenssinumero: 6


    NimiLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Vuosikerta6338 LNCS
    ISSN (painettu)0302-9743
    ISSN (elektroninen)1611-3349


    ConferenceInternational Conference on Sequences and Their Applications

    Sormenjälki Sukella tutkimusaiheisiin 'On the nonlinearity of discrete logarithm in double-struck F<sub>2n</sub>'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

    Siteeraa tätä