Abstract
A novel type of functions called biregular irreducible functions is introduced and applied as security components (instead of, e.g., universal hash functions) in seeded modular wiretap coding schemes, whose second component is an error-correcting code. These schemes are called modular BRI schemes. An upper bound on the semantic security information leakage of modular BRI schemes in a one-shot setting is derived which separates the effects of the biregular irreducible function on the one hand and the error-correcting code plus the channel on the other hand. The effect of the biregular irreducible function is described by the second-largest eigenvalue of an associated stochastic matrix. A characterization of biregular irreducible functions is given in terms of connected edge-disjoint biregular graphs. It allows for the construction of new biregular irreducible functions from families of edge-disjoint Ramanujan graphs, which are shown to exist. A concrete and frequently used arithmetic universal hash function can be converted into a biregular irreducible function for certain parameters. Sequences of Ramanujan biregular irreducible functions are constructed which exhibit an optimal trade-off between the size of the regularity set and the rate of decrease of the associated second-largest eigenvalue. Together with the one-shot bound on the information leakage, the existence of these sequences implies an asymptotic coding result for modular BRI schemes applied to discrete and Gaussian wiretap channels. It shows that the separation of error correction and security as done in a modular BRI scheme is secrecy capacity-achieving for every discrete and Gaussian wiretap channel. The same holds for a derived construction where the seed is generated locally by the sender and reused several times. It is shown that the optimal sequences of biregular irreducible functions used in the above constructions must be nearly Ramanujan.
Introduction
In the classic wiretap channel model, a sender transmits a message to a legitimate receiver while keeping it hidden from an eavesdropper. Traditionally, researchers have used Universal Hash Functions (UHF) to "blind" the eavesdropper. However, achieving semantic security—the gold standard where an eavesdropper learns nothing regardless of the message distribution—often requires specific channel symmetries or complex, intertwined coding/security designs.
This paper addresses the challenge of modularity. The authors, Moritz Wiese and Holger Boche, ask: Can we build a system where the error-correcting code (which handles noise) and the security component (which handles the eavesdropper) are designed independently, without sacrificing the overall transmission rate or security strength?
The Modular BRI Framework
The core of the proposed solution is the Modular BRI Scheme. This architecture decouples the tasks of reliability and secrecy by using a two-step encoding process.
As illustrated in Figure 1, the scheme processes a message $m \in \mathcal{M}$ using a randomized inverse function $f_s^{-1}$ (dependent on a seed $s$) to produce $x$. This is followed by a function $\phi$ and transmission through the channel $T$. The legitimate receiver uses a decoder $\psi$ and the seed-dependent function $f(s, \cdot)$ to recover the estimate $\hat{m}$. Crucially, the eavesdropper observes $z$ through a channel $U$, but the security component ensures that the information leakage is minimized even if the eavesdropper has knowledge of the seed $s$.
Spectral Security and Ramanujan Graphs
The paper introduces Biregular Irreducible Functions (BRI) as a novel mathematical tool for these modular schemes. These functions are equivalent to decomposing a complete bipartite graph into edge-disjoint, biregular subgraphs.
The "strength" of the security is determined by the second-largest eigenvalue ($\lambda_2$) of a stochastic matrix associated with the function. A smaller $\lambda_2$ indicates a better "expander" graph, which spreads the messages so thinly across the possible codewords that the eavesdropper cannot distinguish between them. To find the best possible functions, the authors turn to Ramanujan graphs—graphs that are optimal expanders. They leverage recent breakthroughs in graph theory (the Marcus-Spielman-Srivastava existence proofs) to show that these optimal BRI functions exist.
Key Insights and Results
- The Separation Principle: The most significant finding is the proof that error correction and secrecy can be completely decoupled. One can pick a standard error-correcting code and "wrap" it in a BRI function to achieve capacity-achieving secrecy.
- Capacity Achievement: Modular BRI schemes are proven to achieve the secrecy capacity for all discrete and Gaussian wiretap channels, hitting the theoretical limit of secure information transmission.
- One-Shot Bound: The authors derived a "one-shot" upper bound on information leakage. This bound is particularly useful because it separates the influence of the security function from the influence of the physical channel.
- Seed Reuse: Seeded schemes usually require extra data to inform the receiver which seed was used, potentially lowering the effective transmission rate. The authors provide a construction for "seed reuse" that makes this rate loss negligible in the long run.
Conclusion and Future Work
While the paper proves that Ramanujan BRI functions exist, the current proof is non-constructive. We know they are there, but we do not yet have an efficient, polynomial-time algorithm to generate them for all parameters. A major future direction is finding explicit, efficiently computable Ramanujan BRI functions. Additionally, while the results are asymptotically optimal, further research is needed to evaluate performance in finite blocklength, low-latency applications.
Summary updated