Algebraic nonlinearity and its applications to cryptography |
| |
Authors: | Luke O'Connor Andrew Klapper |
| |
Affiliation: | (1) Department of Computer Science, University of Waterloo, N2L 3G1, Ontario, Canada;(2) ISRC, QUT Gardens Point, 2 George Street, GPO Box 2434, 4001 Brisbane, Queensland, Australia;(3) Department of Computer Science, University of Kentucky, 40506-0027 Lexington, KY, USA;(4) Computer Science Department, University of Manitoba, R3T 2N2 Winnipeg, Manitoba, Canada |
| |
Abstract: | The algebraic nonlinearity of an n-bit boolean function is defined as the degree of the polynomial f(X) Z2[x1, x2,..., xn] that represents f. We prove that the average degree of an ANF polynomial for an n-bit function is n+o(1). Further, for a balanced n-bit function, any subfunction obtained by holding less than n-[log n]- 1 bits constant is also expected to be nonaffine. A function is partially linear if f(X) has some indeterminates that only occur in terms bounded by degree 1. Boolean functions which can be mapped to partially linear functions via a linear transformation are said to have a linear structure, and are a potentially weak class of functions for cryptography. We prove that the number of n-bit functions that have a linear structure is asymptotic .The author is presently employed by the Distributed System Technology Center, Brisbane, Australia.Project sponsored in part by NSERC operating Grant OGP0121648, and the National Security Agency under Grant Number MDA904-91-H-0012. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon. |
| |
Keywords: | Linearity Partial linearity Linear structures |
本文献已被 SpringerLink 等数据库收录! |
|