Shift-invariant functions and almost liftings

• URL: http://arxiv.org/abs/2407.11931v2
• Date: Fri, 08 Nov 2024 16:23:20 GMT
• Title: Shift-invariant functions and almost liftings
• Authors: Jan Kristian Haugland, Tron Omland,
• Abstract summary: We investigate shift-invariant vectorial Boolean functions on $n$ bits that are induced from Boolean functions on $k$ bits, for $kleq n$. We find that if a function with diameter $k$ is an almost lifting, the maximum number of collisions of its induced functions is $2k-1$ for any $n$. We search for functions in the class of almost liftings that have good cryptographic properties and for which the non-bijectivity does not cause major security weaknesses.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate shift-invariant vectorial Boolean functions on $n$ bits that are induced from Boolean functions on $k$ bits, for $k\leq n$. We consider such functions that are not necessarily permutations, but are, in some sense, almost bijective, and their cryptographic properties. In this context, we define an almost lifting as a Boolean function for which there is an upper bound on the number of collisions of its induced functions that does not depend on $n$. We show that if a Boolean function with diameter $k$ is an almost lifting, then the maximum number of collisions of its induced functions is $2^{k-1}$ for any $n$. Moreover, we search for functions in the class of almost liftings that have good cryptographic properties and for which the non-bijectivity does not cause major security weaknesses. These functions generalize the well-known map $\chi$ used in the Keccak hash function.

Related papers

• On Counts and Densities of Homogeneous Bent Functions: An Evolutionary Approach [60.00535100780336]
  This paper examines the use of Evolutionary Algorithms (EAs) to evolve homogeneous bent Boolean functions.<n>We introduce the notion of density of homogeneous bent functions, facilitating the algorithmic design that results in finding quadratic and cubic bent functions in different numbers of variables.
  arXiv  Detail & Related papers  (2025-11-16T15:33:40Z)
• An Elementary Characterization of Bargmann Invariants [0.3779860024918729]
  We give a complete characterization of the set $B_n$ of complex values that $n$-th order invariants can take.<n>We show that both ranges are equal to the $n$-th power of the complex unit $n$-gon, and are therefore convex.
  arXiv  Detail & Related papers  (2025-06-20T16:33:41Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We show that the rank of a function $f$ corresponds to the minimum number of Chain of Thought steps required by a single-layer transformer decoder. We also analyze the problem of identifying the position of the $k$-th occurrence of 1 in a Boolean sequence, proving that it requires $k$ CoT steps.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• New classes of reversible cellular automata [0.0]
  A shift-invariant vectorial Boolean function $F$ induces a proper lifting for every $ngeq k$. We construct new families of such liftings for arbitrary large $k$ and discuss whether all have been identified for $kleq 6$.
  arXiv  Detail & Related papers  (2024-11-01T16:33:53Z)
• Crooked indifferentiability of the Feistel Construction [53.572703605492904]
  The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks.
  arXiv  Detail & Related papers  (2024-04-15T04:29:24Z)
• Learning to Understand: Identifying Interactions via the Möbius Transform [18.987216240237483]
  We use the M"obius transform to find interpretable representations of learned functions. A robust version of this algorithm withstands noise and maintains this complexity. In several examples, we observe that representations generated via the M"obius transform are up to twice as faithful to the original function.
  arXiv  Detail & Related papers  (2024-02-04T22:47:34Z)
• Look into the Mirror: Evolving Self-Dual Bent Boolean Functions [35.305121158674964]
  This paper experiments with evolutionary algorithms with the goal of evolving (anti-)self-dual bent Boolean functions. We successfully construct self-dual bent functions for each dimension. We also tried evolving secondary constructions for self-dual bent functions, but this direction provided no successful results.
  arXiv  Detail & Related papers  (2023-11-20T16:20:16Z)
• Embeddings between Barron spaces with higher order activation functions [1.0999592665107414]
  We study embeddings between Barron spaces with different activation functions. An activation function of particular interest is the rectified power unit ($operatornameRePU$) given by $operatornameRePU_s(x)=max(0,x)s$.
  arXiv  Detail & Related papers  (2023-05-25T08:31:59Z)
• Efficiently Computing Sparse Fourier Transforms of $q$-ary Functions [12.522202946750157]
  We develop a sparse Fourier transform algorithm specifically for $q$-ary functions of length $n$ sequences. We show that for fixed $q$, a robust version of $q$-SFT has a sample complexity of $O(Sn2)$ and a computational complexity of $O(Sn3)$ with the same guarantees.
  arXiv  Detail & Related papers  (2023-01-15T22:04:53Z)
• On Symmetric Pseudo-Boolean Functions: Factorization, Kernels and Applications [0.0]
  We prove that any symmetric pseudo-Boolean function can be equivalently expressed as a power series or factorized. We use these results to analyze symmetric pseudo-Boolean functions appearing in the literature of spin glass energy functions, quantum information and tensor networks.
  arXiv  Detail & Related papers  (2022-09-29T18:00:07Z)
• Dueling Convex Optimization with General Preferences [85.14061196945599]
  We address the problem of emph optimization with dueling feedback, where the goal is to minimize a convex function given a weaker form of emphilonling feedback. Our main contribution is an efficient algorithm with convergence $smashwidetilde O(epsilon-4p)$ for a smooth convex objective function, and an efficient $smashwidetilde O(epsilon-2p) when the objective is smooth and convex.
  arXiv  Detail & Related papers  (2022-09-27T11:10:41Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• Convexity of a certain operator trace functional [1.1470070927586014]
  In this article the operator trace function $ Lambda_r,s(A)[K, M] := operatornametr(K*Ar M Ar K)s$ is introduced and its convexity and concavity properties are investigated. This function has a direct connection to several well-studied operator trace functions that appear in quantum information theory.
  arXiv  Detail & Related papers  (2021-09-23T17:51:46Z)
• 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)
• Neural networks with superexpressive activations and integer weights [91.3755431537592]
  An example of an activation function $sigma$ is given such that networks with activations $sigma, lfloorcdotrfloor$, integer weights and a fixed architecture is given. The range of integer weights required for $varepsilon$-approximation of H"older continuous functions is derived.
  arXiv  Detail & Related papers  (2021-05-20T17:29:08Z)
• Size and Depth Separation in Approximating Natural Functions with Neural Networks [52.73592689730044]
  We show the benefits of size and depth for approximation of natural functions with ReLU networks. We show a complexity-theoretic barrier to proving such results beyond size $O(d)$. We also show an explicit natural function, that can be approximated with networks of size $O(d)$.
  arXiv  Detail & Related papers  (2021-01-30T21:30:11Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
  arXiv  Detail & Related papers  (2020-02-23T22:51:52Z)

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.