Sălăgean2020_Article_DiscreteAntiderivativesForFunc.pdf (330.18 kB)

# Discrete antiderivatives for functions over Fpn

journal contribution
posted on 2020-01-03, 13:50 authored by
In the design of cryptographic functions, the properties of their discrete derivatives have to be carefully considered, as many cryptographic attacks exploit these properties. One can therefore attempt to first construct derivatives with the desired properties and then recover the function itself. Recently Suder developed an algorithm for reconstructing a function (also called antiderivative) over the finite field F2n given its discrete derivatives in up to n linearly independent directions. Pasalic et al. also presented an algorithm for determining a function over Fpn given one of its derivatives. Both algorithms involve solving a pn×pn system of linear equations; the functions are represented as univariate polynomials over Fpn. We show that this apparently high computational complexity is not intrinsic to the problem, but rather a consequence of the representation used. We describe a simpler algorithm, with quasilinear complexity, provided we work with a different representation of the functions. Namely they are polynomials in n variables over Fp in algebraic normal form (for p>2, additionally, we need to use the falling factorial polynomial basis) and the directions of the derivatives are the canonical basis of Fpn. Algorithms for other representations (the directions of the derivatives not being the canonical basis vectors or the univariate polynomials over Fpn mentioned above) can be obtained by combining our algorithm with converting between representations. However, the complexity of these conversions is, in the worst case, exponential. As an application, we develop a method for constructing new quadratic PN (Perfect Nonlinear) functions. We use an approach similar to the one of Suder, who used antiderivatives to give an alternative formulation of the methods of Weng et al. and Yu et al. for searching for new quadratic APN (Almost Perfect Nonlinear) functions.

• Science

## Department

• Computer Science

## Published in

Designs, Codes and Cryptography

88

3

471-486

Springer

## Version

• VoR (Version of Record)

## Publisher statement

This is an Open Access Article. It is published by Springer under the Creative Commons Attribution 4.0 International Licence (CC BY 4.0). Full details of this licence are available at: https://creativecommons.org/licenses/by/4.0/

2019-10-03

2019-11-12

2020

0925-1022

1573-7586

• en

## Depositor

Dr Ana Salagean. Deposit date: 3 January 2020
figshare. credit for all your research.