A generalization of the map chi

summary

The gist

The mapping χn: Fn squared → Fn squared defined by y = χn(x) with yi = xi + xi+1xi+2 + xi+2, where the indices are computed modulo n…

In short

The paper generalizes a specific mapping called $\chi_n$ to create new shift-invariant permutations for lightweight cryptography. It introduces mappings like $\chi_{n,v}$ and $\chi_{n,-2v}$ that can permute the space $F_n^2$ even when $n$ is even. The authors fully characterize these permutations, showing they are related to the original map and have low algebraic degrees.

Key concepts

$\chi_n$
The original mapping studied, $\chi_n$, is a specific type of function used in cryptography. It maps vectors in $F_n^2$ to other vectors by performing additions and shifts based on indices modulo $n$. It is important because it forms the basis for many low-latency cryptographic primitives.
Shift-invariant permutations
These are specific types of functions that remain the same even if you shift the input vector by a fixed amount. The paper focuses on characterizing all such permutations of algebraic degree 2, which are important because they can be used to build new cryptographic systems.
$P(x) = (x ext{ } lacktriangleright u) + (x ext{ } lacktriangleright v) \cdot (x + a)$
This is a generalized form of the mapping being studied. It uses bitwise right shifts ($\gg$) and multiplication by another vector, combined with an addition term. Analyzing this specific structure allows researchers to determine exactly when it acts as a permutation over $F_n^2$.
Algebraic Degree 2
This refers to a mathematical property of the mapping's complexity. An algebraic degree of 2 is considered low, which makes these mappings attractive for lightweight cryptography because they offer good security properties while maintaining low computational latency.

Terminology used across episodes

This episode discusses

The paper

A generalization of the map chi · Read on arXiv

Chinese Academy of Sciences · Carleton University

The mapping χ n: F 2 n to F 2 n defined by y=χ n(x) with y i = x i + x i+1x i+2 + x i+2, where the indices are computed modulo n, has been widely studied for its application in lightweight cryptography. In this paper, we generalize this mapping and completely characterize all these shift-invariant permutations of the form y i=x i+u+x i+v(x i+w+a i), where 0 at most u, v, w<n and a i in F 2, 1 at most i at most n. We also determine their compositional inverses explicitly.

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "A generalization of the map chi".

Jane: Here's the gist of the paper. The mapping χn: Fn squared → Fn squared defined by y = χn(x) with yi = xi + xi+1xi+2 + xi+2, where the indices are computed modulo n, has been widely studied for its application in lightweight cryptography In this paper, we generalize this mapping and completely characterize all these shift-invariant permutations of algebraic degree 2.

Tom: Generalization of the Chi-map The authors introduce two new classes of nonlinear mappings, χn,v and χn,-2v, which induce permutations of Fn squared where n can be even.

Jane: The original mapping χn is a special case of χn,v when v = 1.

Tom: These new mappings have a latency lower than the recent generalization introduced by Lyu et al.

Title and authors: Jane: Now that we know the basics of the paper's focus, let’s talk about what they actually called this work: "A generalization of the map chi."

Tom: Yeah, it’s just a title, but it tells you immediately that they are taking something known—the original map chi n—and generalizing it.

Lu: The point is that the original map chi n is what we have been studying for a long time because of its use in things like Keccak-f and ASCON, which is what we started with.

Meng: So they’re taking that existing structure and exploring how much you can change it while keeping the algebraic degree low.

Jane: Right, and the generalization part is key here because they are looking for more flexibility in how we define these mappings, especially when n is even.

Tom: They specifically mention that their new classes of mappings induce permutations for even n, which is a major extension beyond the original work where it was known to be bijective only when n was odd.

Lu: That’s what they’re setting up, so they are opening the door to explore permutations in dimensions where we previously had trouble finding them.

Meng: So they are broadening the scope from just odd dimensions to even ones, and that sounds like a lot of new possibilities for cryptographic primitives.

Jane: And what makes it interesting is that they show these generalizations have a low algebraic degree, which is still just two, matching the original mapping.

Tom: That’s the takeaway for me; they aren't introducing something fundamentally new in terms of complexity class; they are just finding a different way to write and analyze existing structures.

The paper's summary: Jane: So what is this paper summarizing? Basically, it’s summarizing their process of studying all these shift-invariant mappings of algebraic degree two.

Lu: They studied every single mapping defined by chi n u v w, which is where you have that definition involving y being the sum over i from one to n of x+u + x+v(x+w + a) i equals zero.

Meng: That definition sounds complicated; they are looking at how every single coordinate of the resulting vector relates to the input coordinates.

Tom: They are essentially trying to find out exactly when this mapping P is a permutation by checking for solutions to an equation on x that starts with (x plus some delta) versus the original mapping.

Jane: So they reformulate it as checking if any non-zero difference delta has a solution to that equation, and this leads them to the simplified equation number three.

Lu: That simplification is where the real mathematical heavy lifting happens because it moves us from analyzing all n squared possibilities down to analyzing those specific linear subsystems E zero through E tau minus one <ref:2609.19548#pg1>.

Meng: So they are using this system of equations to filter out the non-permutations efficiently, which is smart for scaling.

Tom: And the summary points out that if you focus on just one subsystem E j, you can look at several cases, like when there are no zero entries in the difference vector.

Jane: That’s a practical way to handle the complexity; they aren't trying to solve every single equation simultaneously.

The paper's improvements: Tom: So what are the actual improvements they propose over what was there before? They focus on how they characterize permutations.

Lu: Their main improvement is stating that a mapping chi n u v w permutes F n squared if and only if those specific conditions involving v, w, and the differences between them hold, plus the parameter one condition.

Meng: So it moves from just being a complex definition to having a clear set of necessary and sufficient conditions for permutation.

Jane: That’s a big deal because it gives us a concrete rule—a checklist—to use when designing or verifying these functions.

Tom: And they also show that essentially all permutations they find are shift equivalent to either chi n v or chi n minus two v, which is a major simplification for classification.

Lu: That means instead of studying a huge space, we only need to study those two representative forms.

Meng: If we can confirm that our desired mapping belongs to one of those two categories, the verification becomes much faster than checking everything else.

Jane: It gives us a way to classify these low-latency permutations based on their algebraic degree and structure, which is really valuable for understanding the landscape.

Conclusion: Tom: So, to wrap up, this paper "A generalization of the map chi" shows that even though we generalized the mapping by adding parameters u, v, and w, it doesn't actually open up a whole new class of complex functions.

Jane: It confirms that the resulting permutations are highly constrained; they are essentially just variations of those two core forms, chi n v and chi n minus two v.

Lu: The real contribution is providing a complete characterization for these shift-invariant permutations, which is what gives us the theoretical foundation to study them fully.

Meng: From an engineering standpoint, it means we can build verification tools that are much more efficient because we know exactly what properties to test for.

Tom: Yeah, so the implication is that if you need a low-latency permutation of algebraic degree two, you should look at the constraints they established for v and w.

Jane: This paper gives us a clear framework for analyzing these mappings without having to check every single possibility.

Lu: It’s a nice way to connect the abstract algebra directly back to practical integer parameters.

Tom: We’ll see what happens when we try to build something using these specific rules, but this characterization is a strong starting point for designing those primitives.

More episodes

← Home