On the nonlinearity of discrete logarithm in double-struck F2n

Risto M. Hakala, Kaisa Nyberg

    Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

    9 Sitaatiot (Scopus)

    Abstrakti

    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.

    AlkuperäiskieliEnglanti
    OtsikkoSequences and Their Applications, SETA 2010 - 6th International Conference, Proceedings
    Sivut333-345
    Sivumäärä13
    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

    Julkaisusarja

    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

    Conference

    ConferenceInternational Conference on Sequences and Their Applications
    LyhennettäSETA
    MaaRanska
    KaupunkiParis
    Ajanjakso13/09/201017/09/2010

    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ä