License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06111.18
URN: urn:nbn:de:0030-drops-6044
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/604/
Go to the corresponding Portal

Carlet, Claude

The complexity of Boolean functions from cryptographic viewpoint

pdf-format:
06111.CarletClaude.Paper.604.pdf (0.3 MB)

Abstract

Cryptographic Boolean functions must be complex to satisfy Shannon's principle of confusion. But the cryptographic viewpoint on complexity is not the same as in circuit complexity.
The two main criteria evaluating the cryptographic complexity of Boolean functions on $F_2^n$ are the nonlinearity (and more generally the $r$-th order nonlinearity, for every positive $r< n$) and the algebraic degree. Two other criteria have also been considered: the algebraic thickness and the non-normality. After recalling the definitions of these criteria and why, asymptotically, almost all Boolean functions are deeply non-normal and have high algebraic degrees, high ($r$-th order) nonlinearities and high algebraic thicknesses, we study the relationship between the $r$-th order nonlinearity and a recent cryptographic criterion called the algebraic immunity. This relationship strengthens the reasons why the algebraic immunity can be considered as a further cryptographic complexity criterion.

BibTeX - Entry

@InProceedings{carlet:DagSemProc.06111.18,
  author =	{Carlet, Claude},
  title =	{{The complexity of Boolean functions from cryptographic viewpoint}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--15},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2006/604},
  URN =		{urn:nbn:de:0030-drops-6044},
  doi =		{10.4230/DagSemProc.06111.18},
  annote =	{Keywords: Boolean function, nonlinearity, Reed-Muller code}
}

Keywords: Boolean function, nonlinearity, Reed-Muller code
Collection: 06111 - Complexity of Boolean Functions
Issue Date: 2006
Date of publication: 09.10.2006

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI