🔢 mathematics

Minimal Binary Linear Codes of Dimension n+4 from Partial Spreads and Their Dual Access Structures

This paper presents a generic construction of minimal binary linear codes with dimension $n+4$ derived from partial spreads and special Boolean functions, explicitly determining their weight distributions and demonstrating that they violate the Ashikhmin-Barg condition, thereby offering valuable resources for secret sharing and cryptographic applications.

Original authors: Apurba Sarkar, Kalyan Hansda, Makhan Maji

Published 2026-08-06

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Apurba Sarkar, Kalyan Hansda, Makhan Maji

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 send a secret message to a group of friends, but you know some of them might be spies, or the channel might be full of static noise. In the world of digital communication, we use "codes" to fix errors and keep secrets safe. Think of a code like a special language where every message is padded with extra clues. If a few letters get scrambled, the receiver can use those clues to fix the message. But there's a deeper game: Secret Sharing. Imagine a vault that needs a specific combination of keys to open. You don't want just any group of friends to open it; you want only specific, authorized teams to succeed. This is where "minimal linear codes" come in. They are the mathematical blueprints that decide exactly which groups of people can unlock the secret and which cannot. For a long time, mathematicians had a strict rule of thumb (called the Ashikhmin-Barg condition) that said, "To make a good secret-sharing code, the smallest group of clues must be more than half the size of the largest group." This rule made the system very rigid, like a lock that only opens if you have exactly 51% of the keys, no more, no less.

Now, enter a team of mathematicians who asked: "What if we can build a lock that breaks this rule? What if we can have a system where the smallest group is actually smaller than half the largest, yet it still works perfectly?" This paper, titled "Minimal Binary Linear Codes of Dimension n + 4 from Partial Spreads and Their Dual Access Structures," dives into exactly that challenge. The authors, Apurba Sarkar, Kalyan Hansda, and Makhan Maji, have constructed a brand new family of these secret codes. They didn't just tweak an old design; they built a complex structure using a geometric concept called "partial spreads" (think of it as arranging non-overlapping rooms in a giant building) and combined four different "layers" of logic. Their big discovery is that they created codes that are mathematically proven to be "minimal" (meaning they are the most efficient, smallest possible keys for the job) even though they break the old "half-size" rule. This means they can create secret-sharing systems that are far more flexible, allowing for a much wider variety of team sizes to unlock secrets, which is a huge deal for secure communication and cryptography.

The Story of the Four-Layer Lock

To understand what these researchers did, let's picture a giant, invisible building made of binary blocks (zeros and ones). Inside this building, there are many rooms, but they are arranged in a very specific way so that no two rooms share any space except for the very center point. Mathematicians call this a "partial spread." The authors took this geometric arrangement and used it to build a "code."

Usually, when building these codes, researchers would stack just one, two, or three layers of these rooms together. But this paper says, "Let's go bigger." They stacked four distinct layers of these rooms together. They called this their "dimension n + 4" construction. Why four? Because when you mix four different layers of logic, you create a complex web of 15 different possible combinations (since $2^4 - 1 = 15$ ). It's like having four different colored lights; you can turn on any combination of them to create a unique signal.

The team proved that if they arranged these four layers correctly (following a set of strict geometric rules they called C1, C2, and C3), the resulting code would be "minimal." In plain English, this means that every single valid key in their system is unique and essential. You can't take a smaller piece of the key and still open the lock. This is crucial for secret sharing because it ensures that no group of people can accidentally unlock the secret unless they have the exact right combination of shares.

Breaking the "Half-Size" Rule

Here is the most exciting part of their discovery. For decades, the "Ashikhmin-Barg condition" was the gold standard. It was a safety rule that said: "To be safe, the smallest group of people needed to open the vault must be more than half the size of the largest possible group." If you followed this rule, your secret-sharing system was rigid. You couldn't have a small team of 10 people and a large team of 100 people both being valid; the math just wouldn't allow it.

The authors proved that their new "four-layer" codes break this rule. They showed that they can create a system where the smallest team is actually less than half the size of the largest team, yet the system remains perfectly secure and minimal. They didn't just guess this; they used rigorous math (involving something called Walsh-Hadamard transforms, which is like a special way of checking the "frequency" of the code) to prove it.

They demonstrated this with a concrete example using a field size of $n=8$ . In this scenario, they built a code with a length of 255 and a dimension of 12.

The smallest team needed to unlock the secret had a size corresponding to a weight of 60.
The largest team had a size corresponding to a weight of 140.
The ratio is $60/140$ , which is roughly 0.43.

Since 0.43 is less than 0.5 (the old rule), they successfully violated the Ashikhmin-Barg condition. This isn't a bug; it's a feature. It means their system is more flexible.

Why This Matters: The Super-Unlock

So, what does breaking the rule actually get you? The paper highlights three major superpowers for this new code:

Quadruple the Keys: In their new system, the number of possible "minimal access sets" (the unique teams that can unlock the secret) jumps to $2^{n+3}$ . For their example, that's $2^{11} = 2048$ different valid teams. This is four times more than previous similar codes. It's like having a vault with thousands of different valid key combinations instead of just a few.
A Wider Range of Teams: Because they broke the "half-size" rule, the difference between the smallest team and the largest team is huge. In their example, the "operational span" (the difference in team sizes) is at least 131. This allows for a "multi-threshold" system. You could have a small, elite team of 10 people who can open the vault, and a massive team of 140 people who can also open it, and the system handles both gracefully. This is perfect for complex organizations where different levels of authority need different access rights.
Better Speed and Security: The authors calculated that their system improves the "throughput" (how much information you can send efficiently) by about 20% compared to older methods. Furthermore, they proved that if a group of spies tries to guess the secret without having the right number of keys, their chance of guessing correctly is exactly 50% (like flipping a coin). This is the best possible security; it means the spies learn absolutely nothing from their failed attempts.

The Verdict

The authors didn't just suggest this might work; they provided a proof. They established necessary and sufficient conditions (rules that must be met) for these codes to exist and be minimal. They showed that for any even number $n$ greater than or equal to 8, you can build these codes.

They also looked at the "dual" of their code, which is the mathematical mirror image used to actually run the secret sharing. They found that this mirror image creates a perfect, ideal secret sharing scheme. The paper concludes by suggesting that while they have cracked the code for four layers, there might be even more layers to explore in the future, perhaps using different types of number systems. But for now, they have handed us a new, more flexible, and more powerful tool for keeping our digital secrets safe, proving that sometimes, breaking the old rules is the only way to build a better lock.

Technical Summary: Minimal Binary Linear Codes of Dimension $n+4$ from Partial Spreads and Their Dual Access Structures

Problem Statement
Minimal linear codes are fundamental to secret sharing schemes (SSS) and secure multi-party computation, as their dual codes dictate minimal access structures. Historically, verifying code minimality relied on the Ashikhmin–Barg (AB) sufficient condition, which requires the ratio of minimum to maximum weight ( $w_{min}/w_{max}$ ) to exceed $1/2$ . While effective, this condition restricts the weight distribution to a narrow cluster, resulting in rigid access structures with limited operational flexibility. Recent research has sought to construct minimal codes that violate the AB condition ( $w_{min}/w_{max} \le 1/2$ ) by leveraging geometric properties of partial spreads. However, existing constructions using Boolean functions supported on partial spreads have been largely confined to lower-dimensional extensions ( $K = n+1, n+2, n+3$ ). The challenge addressed in this paper is to extend these constructions to a higher dimension ( $K = n+4$ ) while ensuring minimality and overcoming the combinatorial saturation inherent in increasing the number of basis functions.

Methodology
The authors propose a generic construction of binary linear codes $M(\psi_a)$ of length $N = 2^n - 1$ and dimension $K = n+4$ . The construction utilizes a linear span $\mathcal{F}$ of four Boolean functions $\{\psi_1, \psi_2, \psi_3, \psi_4\}$ defined over $\mathbb{F}_2^n$ . These functions are derived from a partial spread of order $\kappa$ in $\mathbb{F}_2^n$ , where the spread consists of pairwise disjoint $m$ -dimensional subspaces ( $m = n/2$ ). Each $\psi_a$ is a sum of indicator functions corresponding to specific subsets of these subspaces.

The core of the methodology involves:

Code Definition: The codewords are generated by evaluating linear combinations of the four basis functions plus a linear term $\beta \cdot x$ over all non-zero vectors in $\mathbb{F}_2^n$ .
Weight Distribution Analysis: The authors derive the explicit weight distribution and weight enumerator using Walsh-Hadamard transforms. They analyze the character sums over the orthogonal complements of the partial spread subspaces to determine the exact multiplicities of codeword weights.
Minimality Criteria: Instead of relying solely on the AB condition, the paper establishes necessary and sufficient conditions for minimality based on the non-containment of supports. This is translated into constraints on the Walsh-Hadamard coefficients of the functions in $\mathcal{F}$ .
Combinatorial Constraints: To ensure the code is minimal at dimension $n+4$ , the authors define specific geometric and combinatorial constraints (Conditions C1–C3) on the index sets defining the basis functions. These conditions prevent improper support containment among the $2^4 - 1 = 15$ non-zero linear combinations of the basis functions.

Key Contributions and Results
The paper presents the following specific contributions:

Dimensional Expansion: The construction successfully achieves a dimension of $K = n+4$ , expanding upon previous works limited to $n+3$ . This requires managing $2^4 - 1 = 15$ non-zero Boolean combinations, necessitating a proof of non-containment across $15 \times 15 = 225$ function pair interactions.
Violation of Ashikhmin–Barg Condition: The authors prove that for $n \ge 8$ , the constructed codes can strictly violate the AB condition ( $w_{min}/w_{max} \le 1/2$ ) while remaining minimal. This is achieved through a "combinatorial non-containment design" that acts as a geometric sieve, ensuring minimality independent of global weight bounds.
Explicit Weight Distributions: The paper provides exact weight distributions and enumerators for the codes, parameterized by the cardinalities of the symmetric differences of the index sets ( $\sigma_{ab}, \sigma_{abc}, \sigma_{1234}$ ).
Theoretical Bounds: Theorems 4 and 5 establish that the Walsh-Hadamard combinations strictly satisfy the minimality criteria for $n \ge 8$ . Theorem 6 confirms that if the minimum intersection parameter $\theta \le 2^{m-2}$ , the code is minimal and violates the AB condition.

Significance and Applications
The paper claims significant implications for cryptographic secret sharing schemes (SSS) based on Massey's framework:

Expanded Authorization Density: The $K = n+4$ construction yields $|\Gamma| = 2^{n+3}$ minimal access sets, which is four times the number available in $(n+2)$ -dimensional schemes and double that of $(n+3)$ -dimensional schemes.
Multi-Threshold Flexibility: By violating the AB condition, the codes induce a "multi-threshold access spectrum" with a broad operational span ( $\Delta \ge 2^{n-1} + 2^{m-2} - 1$ ). This allows for flexible, multi-tiered authorization hierarchies, contrasting with the rigid, clustered access structures of AB-compliant codes.
Throughput and Efficiency: The scheme achieves a relative information rate enhancement of $2/(n+2)$ over standard $(n+2)$ -dimensional constructions. For $n=8$ , this represents a 20% throughput gain.
Security Properties: The dual access structures provide information-theoretic immunity against unauthorized collusion (unauthorized probability $P_{unauthorized} = 1/2$ ) and statistical share approximation attacks, as the variance in access set cardinalities is strictly positive.
Overlap Bounds: The paper derives tight upper bounds on participant overlaps between distinct minimal access sets, guaranteeing that no two coalitions share a dominant majority of participants.

Conclusion
The paper concludes that the proposed family of minimal binary linear codes offers a robust solution for advanced communication systems requiring flexible and secure multi-party access structures. By leveraging partial spreads and four-component Boolean functions, the authors have successfully navigated the combinatorial complexities of higher dimensions to produce codes that are structurally minimal yet violate traditional weight-ratio constraints. Future work suggested includes generalizing the construction to non-binary fields and designing multi-secret sharing protocols.

The Story of the Four-Layer Lock

Breaking the "Half-Size" Rule

Why This Matters: The Super-Unlock

The Verdict

More like this