Sălăgean2020_Article_DiscreteAntiderivativesForFunc.pdf (330.18 kB)
Download file

Discrete antiderivatives for functions over Fpn

Download (330.18 kB)
journal contribution
posted on 03.01.2020, 13:50 authored by Ana SalageanAna Salagean
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.

History

School

  • Science

Department

  • Computer Science

Published in

Designs, Codes and Cryptography

Volume

88

Issue

3

Pages

471-486

Publisher

Springer

Version

VoR (Version of Record)

Rights holder

© The Author

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/

Acceptance date

03/10/2019

Publication date

2019-11-12

Copyright date

2020

ISSN

0925-1022

eISSN

1573-7586

Language

en

Depositor

Dr Ana Salagean. Deposit date: 3 January 2020