Fast evaluation, weights and nonlinearity of rotation-symmetric functions (Q1850065)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Fast evaluation, weights and nonlinearity of rotation-symmetric functions
scientific article

    Statements

    Fast evaluation, weights and nonlinearity of rotation-symmetric functions (English)
    0 references
    0 references
    0 references
    2 December 2002
    0 references
    The paper is devoted to some properties of the rotation-symmetric functions, namely to their weights and nonlinearity. The authors also discuss efficiency of evaluation of the truth table of the mentioned functions. In the first two sections, the authors present motivation for their research and some necessary definitions. The third section deals with the second degree rotation-symmetric function (\(f_2\)). First, some previous results on properties of the function are reviewed. Then the authors evaluate the nonlinearity of \(f_2\) in an even number of variables. Using their result they are able to display the truth table of the function with a significantly smaller number of operations than using the normal form of the function. Finally, they evaluate the weight of \(f_2\) for any dimension \(n\). In the fourth section, the third degree rotation-symmetric function (\(f_3\)) is discussed. The authors calculate the number of operations necessary to display the truth table of the function, and they evaluate the weight of the function. At the end of the section they present a conjecture about the nonlinearity of \(f_3\).
    0 references
    0 references
    Boolean functions
    0 references
    nonlinearity
    0 references
    bent
    0 references
    semi-bent
    0 references
    hash functions
    0 references
    rotation-symmetric functions
    0 references
    0 references
    0 references