On the algebraic degree stability of vectorial Boolean functions when restricted to affine subspaces

• URL: http://arxiv.org/abs/2504.03307v1
• Date: Fri, 04 Apr 2025 09:33:03 GMT
• Title: On the algebraic degree stability of vectorial Boolean functions when restricted to affine subspaces
• Authors: Claude Carlet, Serge Feukoua, Ana Salagean,
• Abstract summary: We study the behaviour of the degree of vectorial Boolean functions when their inputs are restricted to an affine subspace of their domain.<n>This behaviour is particularly interesting for cryptographic applications.
• Score: 23.743046820103057
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the behaviour of the algebraic degree of vectorial Boolean functions when their inputs are restricted to an affine subspace of their domain. Functions which maintain their degree on all subspaces of as high a codimension as possible are particularly interesting for cryptographic applications. For functions which are power functions $x^d$ in their univariate representation, we fully characterize the exponents $d$ for which the algebraic degree of the function stays unchanged when the input is restricted to spaces of codimension 1 or 2. For codimensions $k\ge 3$, we give a sufficient condition for the algebraic degree to stay unchanged. We apply these results to the multiplicative inverse function, as well as to the Kasami functions. We define an optimality notion regarding the stability of the degree on subspaces, and determine a number of optimal functions, including the multiplicative inverse function and the quadratic APN functions. We also give an explicit formula for counting the functions that keep their algebraic degree unchanged when restricted to hyperplanes.

Related papers

• Degree is Important: On Evolving Homogeneous Boolean Functions [32.90791284928444]
  This paper investigates the use of Evolutionary Algorithms to design homogeneous bent Boolean functions.<n>While EAs manage to find quadratic homogeneous bent functions, none of the approaches result in cubic homogeneous bent functions.
  arXiv  Detail & Related papers  (2025-01-30T15:04:14Z)
• Use of Simple Arithmetic Operations to Construct Efficiently Implementable Boolean functions Possessing High Nonlinearity and Good Resistance to Algebraic Attacks [28.8640336189986]
  We show that there are functions in the family achieving a combination of nonlinearity and (fast) algebraic immunity.<n>The main novelty of our approach is to apply a judicious combination of simple integer and binary field arithmetic to Boolean function construction.
  arXiv  Detail & Related papers  (2024-08-21T12:46:50Z)
• Piecewise Polynomial Regression of Tame Functions via Integer Programming [2.2499166814992435]
  We consider tame functions, nonsmooth functions with all common activations, value functions of mixed-integer programs, or wave functions of small molecules.
  arXiv  Detail & Related papers  (2023-11-22T17:37:42Z)
• Axiomatic characterization of pointwise Shapley decompositions [0.0]
  A common problem in various applications is the additive decomposition of the output of a function with respect to its input variables. In this paper, axioms are developed which fully preserve functional structures and lead to unique decompositions for all Borel measurable functions.
  arXiv  Detail & Related papers  (2023-03-14T10:24:48Z)
• Special functions in quantum phase estimation [61.12008553173672]
  We focus on two special functions. One is prolate spheroidal wave function, which approximately gives the maximum probability that the difference between the true parameter and the estimate is smaller than a certain threshold. The other is Mathieu function, which exactly gives the optimum estimation under the energy constraint.
  arXiv  Detail & Related papers  (2023-02-14T08:33:24Z)
• Inference on Strongly Identified Functionals of Weakly Identified Functions [71.42652863687117]
  We study a novel condition for the functional to be strongly identified even when the nuisance function is not. We propose penalized minimax estimators for both the primary and debiasing nuisance functions.
  arXiv  Detail & Related papers  (2022-08-17T13:38:31Z)
• Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions [63.21838830509772]
  We develop a framework for extending set functions onto low-dimensional continuous domains. Our framework subsumes many well-known extensions as special cases. We convert low-dimensional neural network bottlenecks into representations in high-dimensional spaces.
  arXiv  Detail & Related papers  (2022-08-08T10:58:02Z)
• The role of cohomology in quantum computation with magic states [0.0]
  A web of cohomological facts relates quantum error correction, measurement-based quantum computation, symmetry protected topological order and contextuality. We extend this web to quantum computation with magic states. In this scheme, the negativity of certain quasiprobability functions is an indicator for quantumness.
  arXiv  Detail & Related papers  (2021-10-22T07:39:15Z)
• Submodular + Concave [53.208470310734825]
  It has been well established that first order optimization methods can converge to the maximal objective value of concave functions. In this work, we initiate the determinant of the smooth functions convex body $$F(x) = G(x) +C(x)$. This class of functions is an extension of both concave and continuous DR-submodular functions for which no guarantee is known.
  arXiv  Detail & Related papers  (2021-06-09T01:59:55Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Concave Aspects of Submodular Functions [0.0]
  Submodular functions generalize several information-theoretic quantities such as entropy and mutual information. Submodular functions also show signs of concavity. We characterize the super-differentials and polyhedra associated with upper bounds and provide optimality conditions for submodular using the differentials.
  arXiv  Detail & Related papers  (2020-06-27T17:06:24Z)
• Space of Functions Computed by Deep-Layered Machines [74.13735716675987]
  We study the space of functions computed by random-layered machines, including deep neural networks and Boolean circuits. Investigating the distribution of Boolean functions computed on the recurrent and layer-dependent architectures, we find that it is the same in both models.
  arXiv  Detail & Related papers  (2020-04-19T18:31:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.