On cryptographically non-linear all-or-nothing transforms

arXiv:2611.17102 · cs.CR · Submitted 2026-11-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: We're looking at the paper: "On cryptographically non-linear all-or-nothing transforms".

Elias: Here's the gist of the paper. An unconditionally secure (t, s, v)-all-or-nothing transform (AONT) is a bijection from s input elements to s output elements over an alphabet of size v such that given any s − t output elements, no information can be obtained about any t input elements All-or-nothing transforms (AONTs) were proposed in 1997 by Rivest

14: in the context of block ciphers as a mode of operation, focusing on AONTs that are computationally secure Unconditionally secure AONTs were introduced and studied by Stinson

16: Recent works have expanded the theory of AONTs by developing broader frameworks and exploring new classes of unconditionally secure AONTs

4–9,17: The paper investigates unconditionally secure cryptographically non-linear (t, s, v)-AONTs, distinguishing between non-additivity, non-affinity, and cryptographic non-linearity Characterization of AONTs and Non-Linearity Measures The existence of a (t, s, v)-AONT is equivalent to a (vs, 2s, v)-array that is unbiased with respect to specific subsets of columns The paper defines three types of non-linearity for a (t, s, q)-AONT: non-additive, non-affine, and cryptographic non-linearity Cryptographic non-linearity is defined as ∆ϕ < qs Non-additivity means there exist x, y ∈ Fs q such that ϕ(x) + ϕ(y) ≠ ϕ(x + y) Enumeration and Structural Properties The authors present a computational method for enumerating general AONTs focusing on the case (t, 3, 3)-AONTs for t = 1 and 2, establishing the existence of non-additive AONTs They enumerate a total of 4992 non-additive (2, 3, 3)-AONTs using a branch-and-bound algorithm Proposition 1 states that every non-additive (t, 3, 3)-AONT is obtainable from some linear (t, 3, 3)-AONT by a sequence of column-wise symbol permutations Construction and Reduction of Differential Uniformity Construction 2 provides a method to construct a non-additive (t, s, v)-AONT from a linear one by applying a symbol permutation using Corollary 3 The authors show that this construction results in a non-additive AONT They investigate how these permutations affect the differential ∆F-uniformity, showing that applying difference-splitting permutations to fewer than s output coordinates leaves ∆ϕ′ = qs Applying difference-splitting permutations to all s output columns guarantees a reduction in differential uniformity, resulting in ∆ϕ′ < qs Computational Findings and Limitations The computational results show that all enumerated non-additive (t, 3, 3)-AONTs are affine, attaining maximum differential ∆F-uniformity and maximum Walsh magnitude This suggests that the small parameter set (t, 3, 3) is insufficient to obtain cryptographically non-linear AONTs The paper also presents examples over fields where difference-splitting permutations exist for q ≥ 5, achieving substantial reductions in both differential ∆F-uniformity and Walsh magnitude Open Problems Open problems include characterizing which combinations of column permutations yield the lowest differential ∆F-uniformity for a given linear AONT Another open question is whether there is a non-additive AONT that is not obtainable from any linear AONT via independent column-wise symbol permutations Finally, the relationship between cryptographically non-linear AONTs and known classes of cryptographically optimal functions remains open The paper concludes that the study has initiated the investigation of non-linear unconditionally secure AONTs The results show that for (t, 3, 3)-AONTs, all non-additive instances are affine and not cryptographically non-linear Construction 2 provides a general method to obtain non-additive AONTs from linear ones via column-wise symbol permutations The study motivates the investigation of larger parameter sets where difference-splitting permutations exist for q ≥ 5 References The references used in the paper are listed at the end of the document.

Nadia: The references include works by Rivest

14: and Stinson

16: and others listed in the bibliography at the end of the document.

Elias: The list of references is provided on page 17 Page 17 --- The references used in the paper are listed at the end of the document.

Nadia: The references include works by Rivest

14: and Stinson

16: and others listed in the bibliography at the end of the document.

Title and authors: Nadia: We’re starting with "On cryptographically non-linear all-or-nothing transforms." The paper is by Anantajeet Devaraj and Navid Nasr Esfahani from Toronto Metropolitan University. They'll be talking about what this paper actually tries to achieve in plain terms.

Elias: Yeah, the authors are trying to define three kinds of non-linearity: non-additivity, non-affinity, and cryptographic non-linearity. They want to see if they can find functions that are truly hard to break beyond just being mathematically complex.

Priya: From a security researcher's view, I’m immediately wondering what the practical implication is—if we find these functions in practice, how much effort would it take to exploit them?

Nadia: That’s a fair question because security research is always about exploiting things cheaply. So they are focusing on finding transforms that are unconditionally secure first, and then looking at the non-linear aspects.

Elias: They are using the equivalence to orthogonal arrays mentioned in Theorem one to give a structural framework for what these AONTs must look like, which is a (v s, 2s, v)-array unbiased with respect specific subsets of columns <ref:2611.17102#pg1>.

Priya: So the structure is defined by this array requirement, and that sounds like a big mathematical constraint to satisfy when you're trying to find something non-linear.

Nadia: It is a constraint because it’s what defines the transform, but they use that structure to build their enumeration method. They focus on finding examples for small cases like t equals one or two and v equals three.

Elias: And they use that structure to show the existence of non-additive AONTs by showing that these specific array requirements can be met under those constraints.

Priya: So they are essentially proving that things exist, which is a good start, but how does that prove something useful for real security?

Nadia: It proves the existence of non-additive examples, which means there are functions out there that don't satisfy the simple matrix multiplication rule for addition. That’s a concrete property we can check.

Elias: But they also define non-affinity and cryptographic non-linearity using field elements, which gives them tools to measure how far away a function is from being just a linear shift of multiplication by a matrix over that finite field F q.

Priya: So if we can measure these three things—non-additivity, non-affinity, and cryptographic non-linearity—we have a toolkit to classify the complexity of any AONT we find.

Nadia: Precisely. And they then try to use this classification to see which one is actually the most relevant for breaking the transform.

Elias: They use that classification as a baseline before moving into their construction part, which is where they show how to generate these non-linear AONTs from linear ones using column-wise symbol permutations.

Priya: So they are first classifying the landscape, and then showing how to navigate it by providing tools to move between different classes of functions.

Nadia: That’s a good way to look at it—classifying the space first so you know what kind of complexity you're dealing with before trying to build something new.

Elias: And that leads right into how they measure the actual non-linearity using those differential uniformity and Walsh spectra measures.

Priya: I’m curious about those measures—what do those actually tell us about the quality of a function? Are they just abstract numbers, or do they relate to real-world performance?

Nadia: They are concrete measurements. The Walsh magnitude tells you about the overall spectral distribution of the function, and it's related to how well it resists certain types of attacks.

Elias: And the differential uniformity is about how often specific differences between inputs lead to specific differences in outputs. It’s a measure of statistical bias in that mapping.

Priya: So when you put those two together, what does that tell us about the actual security level? Does a high value in these measures always mean a better function?

Nadia: Not necessarily. They use them to show that for their small parameter sets, the non-additive examples they found are just affine ones because they hit the maximum possible values for those measures.

Elias: That's the caveat we have right there—the small parameter set t equals one or two and v equals three is not enough to generate cryptographically non-linear transforms in this study.

Priya: So they’ve done a lot of work on classification, but the limitation they found is that for the specific cases they tested, the functions ended up being too simple for their definition of cryptographic non-linearity.

The paper's summary: Nadia: Now we’re diving into what they actually summarized in "On cryptographically non-linear all-or-nothing transforms." They summarize that they investigated the existence of these three kinds of non-linearity and their relationship to the orthogonal array structure.

Elias: They summarize that a (t, s, v)-AONT is equivalent to an unbiased array with respect specific subsets of columns defined by Theorem one <ref:2611.17102#pg1>.

Priya: So they are summarizing that the core requirement is this structural property related to those specific subsets of columns being unbiased in a very precise way.

Nadia: That structural property is what ties the function definition to the array theory, and it shows that non-linearity isn't just a random thing; it’s tied to how the input elements map onto each other.

Elias: They summarize that non-additivity means you can find x and y such that their sum doesn't result in the sum of their individual outputs.

Priya: So they are summarizing that the property is about failing a basic arithmetic expectation, which is a key way to break algebraic attacks.

Nadia: And then they summarize that non-affinity means you can find inputs where adding a constant doesn't change the output in the same way as adding it to both individual outputs.

Elias: They also summarize that cryptographic non-linearity is defined by that condition where the difference between outputs is less than q times s.

Priya: So they are summarizing a specific measure of how much information leaks, which is very relevant for understanding security boundaries.

Nadia: And then they summarize their main contribution as providing a systematic way to build non-linear AONTs from linear ones using coordinate-wise symbol permutations. That’s the core methodology they want us to hear about.

Elias: They are summarizing that this construction is a general method, not just for one specific case, allowing you to generate non-additive maps by permuting symbols in the last column of the array representation.

Priya: So they are summarizing that it’s a general technique for creating complexity from simpler linear foundations.

Nadia: That’s the high-level summary—they established that structure dictates what kind of non-linearity you can achieve, and they provided a method to engineer those functions systematically. This is the big takeaway of this paper.

Elias: So we’ve covered the definitions and the construction idea, which means we're moving into how they actually test these ideas with differential uniformity and Walsh spectra to see if their constructed maps are good.

Priya: And I want to make sure we understand that they aren't just saying "we found a way" but that they are providing a method for building the next generation of functions, which is important for future work.

The paper's improvements: Nadia: Let’s talk about the improvements the authors suggest for this paper because it’s not just about what they found, but how we can push this research forward. They mention things like better search space reduction and better ways to prune the search tree.

Elias: They suggest improving Algorithm one by implementing a better ordering in that algorithm that maximizes the intersection between the input vectors and previously placed neighbors to prune the search tree more aggressively, following "Algorithm one Ordering of Input Vectors by Previously Placed Neighbours <ref:2611.17102#pg1>."

Priya: From a measurement perspective, I wonder if optimizing the search space actually helps us find something harder to break than just running a better algorithm on a computer. Does it help us find something fundamentally different?

Nadia: It helps them find genuinely different structures that might lead to functions that are more complex in the sense that they are structurally distinct from the affine ones, not just finding a better solution to an existing problem.

Elias: And then they suggest using difference-splitting permutations to reduce the differential uniformity by applying them to all output columns, which guarantees a reduction in the measure of statistical bias below q times s.

Priya: That sounds like they are using these permutations as a way to systematically degrade the statistical properties that we care about. They are systematically chipping away at the security margin.

Nadia: Exactly. It’s not just random tweaking; it’s a controlled method to measure how much structural modification impacts the function't security metrics, and they show that applying all these permutations leads to a guaranteed reduction in those statistical measures below q times s.

Elias: So they are providing a systematic way to reduce the differential uniformity by showing that this isn't just luck; it’s a controlled operation.

Priya: So when you look at it, the improvement isn't just about finding a better algorithm; it’s about controlling how much structural modification affects security metrics and ensuring that modifications lead to quantifiable improvements in statistical properties.

Conclusion: Nadia: So to wrap up the discussion on "On cryptographically non-linear all-or-nothing transforms." They summarize that the paper shows that for those small parameter sets t equals one or two and v equals three, everything found was affine.

Elias: And they confirmed that Construction two is a general method for getting non-additive AONTs from linear ones using column-wise symbol permutations <ref:2611.17102#pg1,non-additive AONTs from linear ones using>.

Priya: So the paper provides a roadmap: use that construction to get non-additive maps, and then look at larger parameter sets where difference-splitting permutations exist for q greater than or equal to five.

Nadia: This means the investigation into non-linear unconditionally secure AONTs isn't over, but it just shifted our focus toward bigger parameters where the complexity is actually realized.

Elias: The main implication being that we need larger parameter sets to see cryptographic non-linearity in these transforms, so the study has initiated this line of research.

Priya: I think that’s a solid conclusion for today. It shows how structure dictates what kind of security property you can achieve when you build these functions systematically.

Nadia: Yeah, the paper "On cryptographically non-linear all-or-nothing transforms" really sets a direction for future work in this area.

Anantajeet Devaraj, Navid Nasr Esfahani

Toronto Metropolitan University

cs.CR

Submitted: 2026-11-12

Updated: 2026-11-12

Code: https://github.com/SPyCy-Lab/AONT-Search

Importance score: 53/100

The gist: An unconditionally secure (t, s, v)-all-or-nothing transform (AONT) is a bijection from s input elements to s output elements over an alphabet of size v such that given any s − t output elements…

Key concepts

Unconditionally Secure (t, s, v)-AONT
This is a perfect mapping where 's' inputs map to 's' outputs using an alphabet of size 'v'. Its security means that if an attacker knows any 's-t' output elements, they gain no information about any 't' input elements. It is a fundamental building block for secure transformations.
Non-Additivity
A mapping is non-additive if the sum of the outputs of two inputs does not equal the output of their sum. Mathematically, $\phi(x) + \phi(y) \neq \phi(x + y)$. This property is a measure used to distinguish certain types of non-linear behavior in functions.
Cryptographic Non-Linearity
This refers to a strong form of non-linearity, defined as $\Delta\phi < qs$. This condition signifies that the mapping resists linear cryptanalysis, meaning it is sufficiently complex and unpredictable for cryptographic use. The paper found that small parameter sets like (t, 3, 3) are insufficient to achieve this level of non-linearity.

Terminology

Summary

An unconditionally secure (t, s, v)-all-or-nothing transform (AONT) is a bijection from s input elements to s output elements over an alphabet of size v such that given any s − t output elements, no information can be obtained about any t input elements

Introduction to AONTs and Non-Linearity

All-or-nothing transforms (AONTs) were proposed in 1997 by Rivest [14] in the context of block ciphers as a mode of operation, focusing on AONTs that are computationally secure Unconditionally secure AONTs were introduced and studied by Stinson [16] Recent works have expanded the theory of AONTs by developing broader frameworks and exploring new classes of unconditionally secure AONTs [4–9,17] The paper investigates unconditionally secure cryptographically non-linear (t, s, v)-AONTs, distinguishing between non-additivity, non-affinity, and cryptographic non-linearity

Characterization of AONTs and Non-Linearity Measures

The existence of a (t, s, v)-AONT is equivalent to a (vs, 2s, v)-array that is unbiased with respect to specific subsets of columns The paper defines three types of non-linearity for a (t, s, q)-AONT: non-additive, non-affine, and cryptographic non-linearity Cryptographic non-linearity is defined as ∆ϕ < qs Non-additivity means there exist x, y ∈ Fs q such that ϕ(x) + ϕ(y) ≠ ϕ(x + y)

Enumeration and Structural Properties

The authors present a computational method for enumerating general AONTs focusing on the case (t, 3, 3)-AONTs for t = 1 and 2, establishing the existence of non-additive AONTs They enumerate a total of 4992 non-additive (2, 3, 3)-AONTs using a branch-and-bound algorithm Proposition 1 states that every non-additive (t, 3, 3)-AONT is obtainable from some linear (t, 3, 3)-AONT by a sequence of column-wise symbol permutations

Construction and Reduction of Differential Uniformity

Construction 2 provides a method to construct a non-additive (t, s, v)-AONT from a linear one by applying a symbol permutation using Corollary 3 The authors show that this construction results in a non-additive AONT They investigate how these permutations affect the differential ∆F-uniformity, showing that applying difference-splitting permutations to fewer than s output coordinates leaves ∆ϕ′ = qs Applying difference-splitting permutations to all s output columns guarantees a reduction in differential uniformity, resulting in ∆ϕ′ < qs

Computational Findings and Limitations

The computational results show that all enumerated non-additive (t, 3, 3)-AONTs are affine, attaining maximum differential ∆F-uniformity and maximum Walsh magnitude This suggests that the small parameter set (t, 3, 3) is insufficient to obtain cryptographically non-linear AONTs The paper also presents examples over fields where difference-splitting permutations exist for q ≥ 5, achieving substantial reductions in both differential ∆F-uniformity and Walsh magnitude

Open Problems

Open problems include characterizing which combinations of column permutations yield the lowest differential ∆F-uniformity for a given linear AONT Another open question is whether there is a non-additive AONT that is not obtainable from any linear AONT via independent column-wise symbol permutations Finally, the relationship between cryptographically non-linear AONTs and known classes of cryptographically optimal functions remains open

Conclusion

The paper concludes that the study has initiated the investigation of non-linear unconditionally secure AONTs The results show that for (t, 3, 3)-AONTs, all non-additive instances are affine and not cryptographically non-linear Construction 2 provides a general method to obtain non-additive AONTs from linear ones via column-wise symbol permutations The study motivates the investigation of larger parameter sets where difference-splitting permutations exist for q ≥ 5

References

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. p. 0 p. 0 p. 0 p. 0 p. 0 p. 0 p. 0 p. 0 p. 0 p. 0 p. 0 p. 0 The list of references is provided on page 17

--- Page 17 ---

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. The list of references is provided on page 17. p. 5 p. 5 p. 5 p. 5 p. 5 p. 5 p. 5 p. 5 p. 5 p. 5 p. 5

--- Page 18 ---

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. The list of references is provided on page 17.

--- Page 19 ---

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. The list of references is provided on page 17.

--- Page 20 ---

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. The list of references is provided on page 17.

--- Page 21 ---

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. The list of references is provided on page 17.

--- Page 22 ---

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. The list of references is provided on page 17.

--- Page 23 ---

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. The list of references is provided on page 17.

--- Page 24 ---

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. The list of references is provided on page 17.

--- Page 25 ---

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. The list of references is provided on page 17.

--- Page 26 ---

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. The list of references is provided on page 17.

--- Page 1 ---

On cryptographically non-linear all-or-nothing transforms Anantajeet Devaraj and Navid Nasr Esfahani Department of Computer Science Toronto Metropolitan University Toronto, Ontario,M5B 2K3, Canada nne@torontomu.ca Abstract. p. 0 An unconditionally secure (t, s, v)-all-or-nothing transform (AONT) is a bijection from s input elements to s output elements over an alphabet of size v such that given any s − t output elements, no information can be obtained about any t input elements

--- Page 3 ---

Definition 3 (Orthogonal Array). Let X be an alphabet of size v, and let A be an N ×k array with entries from X. p. 0 We call A an (N, k, v)-array An orthogonal array, denoted by OAλ(s, k, v), is a (λvs, k, v)-array that is unbiased with respect to every subset D ⊆ C of size s

--- Page 4 ---

Theorem 1. A (t, s, v)-AONT is equivalent to a (vs, 2s, v)-array that is unbiased with respect to the following subsets of columns

Corollary 2

Suppose ϕ: X s → X s is a (t, s, v)-AONT. Let a, c ∈ X s where a ≠ c, ϕ(a) = b, and ϕ(c) = d. p. 0 If d(a, c) ≤ s − t then d(b, d) ≥ t + 1

Corollary 3

Suppose ϕ: X s → X s is a (t, s, v)-AONT, and let A denote its array representation Then applying an arbitrary symbol permutation to any column of A yields a new mapping ϕ′, which is also a (t, s, v)-AONT

Enumerating all general (t, 3, 3)-AONTs

The branch-and-bound procedure is exhaustive in the following sense: at every level, the only output assignments excluded are those provably infeasible by Corollary 2 and every remaining assignment is explored recursively The pseudocode in Algorithm 2 describes the general branch-and-bound procedure

Results of Enumeration

Using this method, we enumerate a total of 4992 non-additive (2, 3, 3)-AONTs and 4992 non-additive (t, 3, 3)-AONTs All enumerated non-additive (t, 3, 3)-AONTs are affine: they attain maximum differential ∆F-uniformity and maximum Walsh magnitude

Construction of Non-Additive AONTs

Construction 2 presents a method to construct a non-additive (t, s, v)-AONT from a linear one by means of column-wise symbol permutations The resulting mapping ϕ′ is non-additive

Measuring Non-Linearity

Despite being non-additive, these mappings did not exhibit cryptographic non-linearity The authors analyze the differential ∆F-uniformity and Walsh spectra exhaustively over the vector space Fs q for some non-linear AONTs They show that applying difference-splitting permutations to all output coordinates reduces the differential count for δ(a, b) when ϕ(a) is nonzero in that column

The study has initiated the investigation of non-linear unconditionally secure AONTs The results suggest that the small parameter set (t, 3, 3) is insufficient to obtain cryptographically meaningful non-linearity Construction 2 provides a general construction for obtaining non-additive AONTs from linear ones

The references used in the paper are listed at the end of the document. The references include works by Rivest [14] and Stinson [16] and others listed in the bibliography at the end of the document. The list of references is provided on page 17.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Enhanced Search Space Reduction for AONT Enumeration: Implement an improved ordering in Algorithm 1 that maximizes H(x) intersect P to achieve a more aggressive pruning of the search tree, as described in Algorithm 1 Ordering of Input Vectors by Previously Placed Neighbours.

  2. Characterization of Non-Linearity: The system can differentiate between non-additive, non-affine, and cryptographic non-linearity by measuring differential F-uniformity and Walsh magnitude. This allows the system to identify instances where mappings are non-additive if there exist x, y in Fs q such that phi(x) + phi(y) != phi(x + y).

  3. Construction of Non-Additive Mappings: The AI can generate non-additive AONTs from linear ones using Construction 2, which involves applying a symbol permutation to the last output column based on whether the field order q is even or odd.

  4. Detection of Cryptographically Non-Linear Functions: The system can determine if an enumerated mapping is cryptographically non-linear by checking if "delta phi < qs," which signifies resistance to linear cryptanalysis.

  5. Optimization via Permutation Analysis: The AI can use difference-splitting permutations to reduce the differential count delta F -uniformity, as shown in Proposition 2, leading to a lower bound on differential uniformity that is less than qs.

Related papers