Skip to Main content Skip to Navigation

Algebraic Immunities of functions over finite fields

Gwénolé Ars 1 Jean-Charles Faugère 2, 1
2 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : A general mathematical definition for a function from $GF(q)^n$ to $GF(q)^m$ to resist to cryptanalytic attacks is developed. It generalize the definition of Algebraic Immunity for Stream Cipher to any finite field and also Block Cipher. This algebraic immunity correspond to equations with low leading term according a monomial ordering. We give properties of this Algebraic Immunity and also compute explicit and asymptotic bounds. We extended the definitions of Algebraic Immunity to functions with memory but they depend on the number of consecutive outputs we look at. We show that all the results obtained for memoryless function give similarly results on memory functions by a change of variables. And then, we prove that, for a memory function f with memory size l and only one output, if there is no relation which not depend on memory for l consecutive output, than we can construct a polynomial that generate all relations without memories. We apply this theorem to the summation generator and compute explicitly the Algebraic Immunity.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 8:36:28 PM
Last modification on : Tuesday, January 12, 2021 - 9:36:03 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:18:12 PM


  • HAL Id : inria-00070475, version 1


Gwénolé Ars, Jean-Charles Faugère. Algebraic Immunities of functions over finite fields. [Research Report] RR-5532, INRIA. 2005, pp.17. ⟨inria-00070475⟩



Record views


Files downloads