💻 computer science

SBN Explorer: An Empirical Study of Cryptographic Boolean Networks

This paper formalizes the design space of cryptographic Boolean systems into 64 distinct architectural classes based on six structural constraints and systematically evaluates their resistance to differential, linear, and algebraic attacks, revealing that optimal security arises from specific, sparse combinations of these constraints.

Original authors: Arnaud Valence

Published 2026-05-01

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Arnaud Valence

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build the ultimate lock for a digital safe. For decades, locksmiths have relied on a very specific, rigid blueprint: a series of alternating layers where one layer scrambles the data (confusion) and the next layer spreads it out (diffusion). This is like building a house with a strict rule: "Every room must be followed by a hallway, then another room, then another hallway." It works well, but it limits your creativity.

This paper, titled "SBN Explorer," asks a bold question: What if we throw away that strict blueprint? What if we treat the design of a cryptographic lock not as a fixed recipe, but as a giant playground of possibilities?

Here is the story of the paper, broken down into simple concepts.

1. The Playground: 64 Different "Architectures"

The authors created a digital sandbox called Synchronous Boolean Networks (SBNs). Think of this as a giant Lego set where you can build circuits that don't just flow in one direction (like a river) but can also loop back on themselves (like a racetrack).

To explore this sandbox, they defined six simple "rules" (or constraints) that a circuit could either follow or ignore:

Stratification (S): Does the circuit strictly alternate between "scrambling" layers and "spreading" layers? (The classic SPN rule).
Acyclicity (A): Is the circuit a one-way street with no loops, or does it allow feedback loops?
Regularity (R): Do all paths through the circuit take exactly the same amount of time to travel? (Like a highway where every lane has the same speed limit).
Interleaving (I): Do different parts of the circuit mix freely, or are they kept in separate, isolated boxes?
Homogeneity (H): Does every part of the circuit use the exact same "scrambling" rule, or are they all different?
Locality (L): Do connections only happen between neighbors, or can they jump across the whole circuit?

By turning these six switches on or off, they created 64 distinct architectural styles (2 to the power of 6). It's like having 64 different blueprints for a lock, ranging from the classic, rigid designs to wild, looping, irregular structures.

2. The Test: Three Types of Attackers

To see which of these 64 designs were the best, they didn't just look at them; they put them through a gauntlet. They simulated three types of digital burglars trying to crack the locks:

The Differential Burglar: Tries to find patterns by seeing how small changes in the input change the output.
The Linear Burglar: Tries to find straight-line relationships between inputs and outputs.
The Algebraic Burglar: Tries to solve the lock using complex math equations.

They used a computer program (a "Genetic Algorithm") to evolve millions of circuits within each of the 64 styles to see which ones could best resist these attacks.

3. The Big Surprise: The "Regularity" Rule

The most shocking discovery was about Regularity (Rule #3).

In the world of classic cryptography, the "Stratification" rule (alternating layers) is considered the golden standard. The authors expected this to be the most important factor. Instead, they found that Regularity was the true hero.

The Finding: The best-performing locks always had the "Regularity" rule turned on. This means that for a lock to be strong, every path the data takes through the circuit must be the same length. If some paths are short and others are long, the lock becomes weak, no matter how fancy the other rules are.
The Analogy: Imagine a relay race. If some runners have to run 100 meters and others only 10 meters, the team is unbalanced and easy to predict. The best teams are those where every runner runs the exact same distance.

4. The Unexpected Conflict: The "Feud" Between Rules

The paper also discovered a fascinating conflict between the two most famous rules: Stratification (S) and Regularity (R).

The Conflict: When you try to use both the classic "alternating layers" rule (S) and the "equal path length" rule (R) together, they fight each other. It's like trying to build a house where every room is a different size (Stratification) but also requires every room to be exactly the same distance from the front door (Regularity). You can't really do both perfectly.
The Result: The classic SPN design (which uses Stratification) actually performs worse at resisting differential attacks than some of the weird, non-standard designs that ignored Stratification but kept Regularity.

5. The "Sparse" Secret

The authors found that the best locks weren't the ones with all the rules turned on. In fact, having too many rules made the design worse.

The winning designs were sparse. They used a very small, specific combination of rules.

The Winner: The best design for resisting "Differential" attacks was a simple combination: No Loops (Acyclic) + Equal Paths (Regularity) + Local Connections (Locality).
The Lesson: You don't need a complex, over-engineered blueprint. You need a few key structural principles that work well together without fighting each other.

6. What About the Classics?

The paper tested the two most famous real-world designs:

Feistel Networks: These performed surprisingly poorly in this specific test. They are great for building full ciphers (because they are easy to reverse), but as a single "scrambling block," they weren't very strong against these specific attacks.
SPN (Substitution-Permutation Networks): These did well at resisting linear attacks but struggled with differential attacks because of the "feud" between their alternating layers and the need for equal path lengths.

Summary

This paper is a massive experiment in "design space exploration." It proves that:

We are too stuck in our ways. We have been designing cryptographic locks using a narrow set of rules for too long.
Structure matters more than we thought. The physical shape of the circuit (specifically, making sure all paths are the same length) is more important for security than the specific "scrambling" layers we usually focus on.
Less is often more. The strongest designs are simple, regular, and avoid mixing conflicting rules.

The authors didn't build a new cipher to sell; they built a map to show us that the territory of cryptographic design is much wider and stranger than we thought, and the "best" path isn't the one we've been walking for decades.

1. Problem Statement

Symmetric cryptography relies heavily on Boolean circuits (BCs) to implement confusion and diffusion. However, the design space of these circuits has historically been confined to a few canonical paradigms, primarily Substitution-Permutation Networks (SPN) and Feistel networks. These paradigms impose specific structural constraints (e.g., acyclicity, strict layering, alternating linear/nonlinear operators) that act as "quasi-defaults."

The paper identifies three critical limitations in existing research:

Bias toward Acyclicity: Classical designs assume acyclic graphs, excluding potentially secure recurrent (feedback-based) systems.
Rigid Architectural Templates: The alternation of linear and nonlinear layers is treated as a fundamental law rather than a design choice, ignoring other structural possibilities.
Lack of Systematic Exploration: Existing studies compare isolated, hand-designed ciphers rather than systematically exploring the combinatorial space of architectural constraints to understand how global topology influences cryptographic robustness.

Core Research Question: To what extent is cryptographic quality (resistance to differential, linear, and algebraic attacks) intrinsically tied to conventional architectural principles, and can superior or comparable security emerge from non-standard structural organizations?

2. Methodology

The authors propose a unified framework based on Synchronous Boolean Networks (SBNs), a general model that encompasses both acyclic combinational circuits and recurrent dynamical systems.

A. The Design Space: 64 Architectures

The study defines a design space generated by six independent binary structural constraints. These constraints form a hypercube of $2^6 = 64$ distinct architectural classes:

Stratification (S): Alternating layers of nonlinear (S) and linear (P) operators (SPN-like structure).
Acyclicity (A): Absence of directed cycles (feed-forward only).
Regularity (R): All input-to-output minimal propagation paths have equal length (uniform depth).
Interleaving (I): Existence of dependencies crossing predefined block boundaries (cross-coupling).
Homogeneity (H): All nodes within a layer use the same local rule (up to input permutation).
Locality (L): All interactions stay within a fixed geometric radius.

The authors prove these constraints are logically independent, ensuring the 64 classes are distinct and cover the full Boolean hypercube.

B. Evaluation Framework

The study employs a Genetic Algorithm (GA) to evolve Boolean networks within each of the 64 architectural classes. The evolution is guided by three generic cryptanalytic fitness objectives:

Differential Resistance: Minimizing differential uniformity.
Linear Resistance: Maximizing nonlinearity (minimizing linear approximation bias).
Algebraic Resistance: Maximizing algebraic degree and complexity.

C. Five-Stage Analysis Pipeline

To interpret the results, the authors use a sophisticated statistical and structural analysis pipeline:

Multi-Level Discretization: Categorizing architectures into "Elite" (top 10-20%) and binary performance groups.
Hypercube Edge Analysis: Calculating marginal effects of each constraint across all contexts.
Epistasis Matrix: Quantifying pairwise interactions (synergy vs. antagonism) between constraints.
Formal Concept Analysis (FCA): Extracting minimal structural patterns (rules) that define high-performance regions.
Spectral Variance Decomposition: Using Walsh-Hadamard decomposition to attribute variance in fitness to additive effects, pairwise interactions, and higher-order couplings.

3. Key Contributions

Formalization of a General Design Space: The paper introduces the first systematic framework to treat cryptographic Boolean circuits as points in a 64-dimensional hypercube defined by independent structural constraints, moving beyond specific cipher templates.
Identification of "Regularity" (R) as a Universal Driver: The study empirically demonstrates that Regularity (uniform propagation depth) is the single most critical constraint for cryptographic robustness, acting as a necessary condition for elite performance across all three attack models.
Discovery of Structural Antagonisms: The research reveals deep conflicts between constraints. Most notably, Stratification (S) and Regularity (R) are found to be strongly antagonistic. While S (alternating layers) is the hallmark of SPNs, it actively degrades differential resistance when combined with R.
Epistatic Nature of Cryptographic Design: The paper establishes that cryptographic security is a fundamentally epistatic problem. The fitness of a constraint depends heavily on the presence or absence of other constraints; no single constraint guarantees security in isolation.
Re-evaluation of Classical Architectures: The study quantifies the performance of standard Feistel and SPN architectures within this new space, revealing that they occupy sub-optimal regions for specific criteria (e.g., SPN is excellent for linear resistance but mediocre for differential resistance due to the S-R conflict).

4. Key Results

Differential Resistance

Dominant Driver: Regularity (R) is the only constraint with a stable, positive individual effect. It is a mandatory condition for elite architectures (100% of top performers contain R).
Major Antagonism: The combination S + R is highly detrimental. Stratification (alternating layers) conflicts with the uniform depth required by Regularity.
Top Architecture: A + R + L (Acyclic + Regular + Local) achieves the highest score (1.000).
Role of Locality (L): L is neutral alone but acts as a synergist when combined with R.

Linear Resistance

Dominant Driver: Homogeneity (H) is the primary positive driver, though its effect is context-dependent.
Key Interaction: S + R + H forms a strong synergistic trio, suggesting that while S and R conflict individually, their conflict is mediated by H in the context of linear resistance.
Negative Drivers: Stratification (S) and Locality (L) act as inhibitors individually but show compensatory synergy when paired.

Algebraic Resistance

Universal Necessity: Regularity (R) is again the sole necessary condition for top-tier performance.
Surprising Synergy: The pair S + A (Stratification + Acyclicity) shows a strong positive synergy, which was not observed in other fitness models.
Destructive Pair: H + L is highly antagonistic.

Performance of Standard Architectures

Feistel (A + I): Ranks poorly across all three metrics (bottom 12% for differential/algebraic). It prioritizes invertibility over single-pass cryptographic strength.
SPN (S + A + R + I + H): Ranks 3rd for Linear Resistance (due to S+H synergy) but drops to 21st for Differential Resistance. This highlights the intrinsic trade-off in SPN design caused by the S-R antagonism.

5. Significance and Implications

Beyond Shannon: While Shannon's principle of alternating confusion and diffusion (Stratification) is validated for linear/algebraic resistance, the paper identifies Regularity (uniform path depth) as a deeper, previously overlooked structural principle essential for differential security.
Design Philosophy Shift: The results suggest that cryptographic design should not be about "accumulating" constraints (more rules = better security). Instead, it requires identifying sparse, mutually compatible combinations of constraints. Activating too many constraints often triggers antagonisms that degrade performance.
New Topologies: The study proves that non-standard topologies (e.g., recurrent systems, irregular depths) can achieve elite cryptographic status if they satisfy the Regularity constraint, challenging the dogma that acyclicity and strict layering are prerequisites for security.
Future Directions: The authors propose extending this framework to multi-objective optimization (Pareto frontiers), larger bit-widths (32/64-bit), and iterated round structures to bridge the gap between S-box optimization and full cipher design.

In conclusion, SBN Explorer provides a rigorous, data-driven map of the cryptographic Boolean landscape, demonstrating that global topology is a determining factor in security and that the "best" architecture depends heavily on the specific cryptanalytic threat model, often requiring trade-offs that classical design paradigms fail to navigate.