ML p(r)ior | Progress Towards the Conjecture on APN Functions and Absolutely Irreducible Polynomials

Progress Towards the Conjecture on APN Functions and Absolutely Irreducible Polynomials

2016-01-30
1602.02576 | math.NT
Almost Perfect Nonlinear (APN) functions are very useful in cryptography, when they are used as S-Boxes, because of their good resistance to differential cryptanalysis. An APN function $f:\mathbb{F}_{2^n}\rightarrow\mathbb{F}_{2^n}$ is called exceptional APN if it is APN on infinitely many extensions of $\mathbb{F}_{2^n}$. Aubry, McGuire and Rodier conjectured that the only exceptional APN functions are the Gold and the Kasami-Welch monomial functions. They established that a polynomial function of odd degree is not exceptional APN provided the degree is not a Gold number $(2^k+1)$ or a Kasami-Welch number $(2^{2k}-2^k+1)$. When the degree of the polynomial function is a Gold number, several partial results have been obtained [1, 7, 8, 10, 17]. One of the results in this article is a proof of the relatively primeness of the multivariate APN polynomial conjecture, in the Gold degree case. This helps us extend substantially previous results. We prove that Gold degree polynomials of the form $x^{2^k+1}+h(x)$, where $deg(h)$ is any odd integer (with the natural exceptions), can not be exceptional APN. We also show absolute irreducibility of several classes of multivariate polynomials over finite fields and discuss their applications.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2019-05-30

In this paper we define a notion of partial APNness and find various characterizations and construct… show more
PDF

Highlights - Most important sentences from the article

2018-04-22

We propose an algebraic approach to proving circuit lower bounds for ACC0 by defining and studying t… show more
PDF

Highlights - Most important sentences from the article

2018-11-27

To determine the dimension of null space of any given linearized polynomial is one of vital problems… show more
PDF

Highlights - Most important sentences from the article

2018-11-04
1811.01351 | cs.CC

We show that if a system of degree-$k$ polynomial constraints on~$n$ Boolean variables has a Sums-of… show more
PDF

Highlights - Most important sentences from the article

2019-04-12
1904.06245 | math.CO

We prove Sylvester-Gallai type theorems for quadratic polynomials. Specifically, we prove that if a … show more
PDF

Highlights - Most important sentences from the article

2018-05-08
1805.03097 | math.NT

Let $q$ be a prime power, $\mathbb F_q$ be the finite field of order $q$ and $\mathbb F_q(x)$ be the… show more
PDF

Highlights - Most important sentences from the article

2018-11-07
1811.03491 | cs.LG

The degree-$d$ Chow parameters of a Boolean function $f: \{-1,1\}^n \to \mathbb{R}$ are its degree a… show more
PDF

Highlights - Most important sentences from the article

2017-06-26
1706.08447 | math.NT

In this paper we characterize the set of polynomials $f\in\mathbb F_q[X]$ satisfying the following p… show more
PDF

Highlights - Most important sentences from the article

2019-03-05
1903.02112 | math.CO

In this paper we construct planar polynomials of the type $f_{A,B}(x)=x(x^{q^2}+Ax^{q}+x)\in \mathbb… show more
PDF

Highlights - Most important sentences from the article

2018-03-05
1803.01877 | math.OC

We prove that if a homogeneous, continuously differentiable vector field is asymptotically stable, t… show more
PDF

Highlights - Most important sentences from the article

2018-12-17
1812.06828 | cs.CC

The existence of string functions, which are not polynomial time computable, but whose graph is chec… show more
PDF

Highlights - Most important sentences from the article

2018-09-10
1809.03089 | math.CO

The Friedgut-Kalai-Naor (FKN) theorem states that if $f$ is a Boolean function on the Boolean cube w… show more
PDF

Highlights - Most important sentences from the article

2012-06-19

We present an algorithm which computes the multilinear factors of bivariate lacunary polynomials. It… show more
PDF

Highlights - Most important sentences from the article

2013-11-22

We present a deterministic polynomial-time algorithm which computes the multilinear factors of multi… show more
PDF

Highlights - Most important sentences from the article

2016-07-19

In this paper we study sums of powers of affine functions in (mostly) one variable. Although quite s… show more
PDF

Highlights - Most important sentences from the article

2015-04-15
1504.03761 | math.OC

We show that for any positive integer $d$, there are families of switched linear systems---in fixed … show more
PDF

Highlights - Most important sentences from the article