ExpanderGraph-128: A Novel Graph-Theoretic Block Cipher with Formal Security Analysis and Hardware Implementation

• URL: http://arxiv.org/abs/2603.12637v1
• Date: Fri, 13 Mar 2026 04:15:20 GMT
• Title: ExpanderGraph-128: A Novel Graph-Theoretic Block Cipher with Formal Security Analysis and Hardware Implementation
• Abstract summary: We present bfExpanderGraph-128 (EGC128), a 128-bit block cipher constructed as a 20-round balanced Feistel network.<n>Security analysis combines MILP-based differential bounds, proven optimal through 10 rounds via SCIP, establishing 147.3-bit differential security and conservatively extrapolating to 413 bits for the full cipher.<n> FPGA synthesis on Xilinx Artix-7 achieves 261Mbps at 100MHz using only 380 LUTs, while ARM Cortex-M4F software requires 25.8KB Flash and 1.66ms per encryption.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lightweight block cipher design has largely focused on incremental optimization of established paradigms such as substitution--permutation networks, Feistel structures, and ARX constructions, where security derives from the algebraic complexity of individual components. We propose a different approach based on \emph{expander-graph interaction networks}, where diffusion and security arise from sparse structural connectivity rather than component sophistication. We present \textbf{ExpanderGraph-128 (EGC128)}, a 128-bit block cipher constructed as a 20-round balanced Feistel network. Each round applies a 64-bit nonlinear transformation governed by a 3-regular expander graph whose vertices execute identical 4-input Boolean functions on local neighborhoods. Security analysis combines MILP-based differential bounds, proven optimal through 10 rounds via SCIP, establishing 147.3-bit differential security and conservatively extrapolating to 413 bits for the full cipher. Linear analysis provides MILP bounds of $\geq 2^{145}$, while related-key evaluation shows no free rounds for any nonzero key difference. Additional tests confirm rapid algebraic degree growth and the absence of invariant affine subspaces. Implementation results demonstrate practical efficiency. FPGA synthesis on Xilinx Artix-7 achieves 261~Mbps at 100~MHz using only 380 LUTs, while ARM Cortex-M4F software requires 25.8~KB Flash and 1.66~ms per encryption. These results show that expander-graph-driven diffusion provides a promising design methodology for lightweight cryptography.

Related papers

• Bridging the Gap Between PHE and FHE: A Performance and Trade-off Analysis of The Somewhat Homomorphic BGN Cryptosystem [0.0]
  Homomorphic encryption (HE) enables privacy-preserving data analytics, but practitioners often face a trade-off between lightweight Partially Homomorphic Encryption (PHE) and computationally dominant Fully Homomorphic Encryption (FHE)<n>The Boneh-Goh-Nissim (BGN) cryptosystem bridges this gap as a Somewhat Homomorphic Encryption (SWHE) scheme supporting unlimited additions and one ciphertext multiplication.<n>This paper presents a comparative analysis of BGN against PHE and FHE paradigms through its integration into the lightphe Python framework.
  arXiv  Detail & Related papers  (2026-07-30T12:33:25Z)
• Scalable Optimal Transport Algorithm for Network Alignment [47.18609734795849]
  We present FastAlign, a scalable, sparsity-aware framework for optimal transport-based network alignment.<n>FastAlign preserves the original OT formulation and reinterprets its computation as a set of recurring mixed sparse-dense operations.<n>Our results show that FastAlign achieves alignment quality comparable to state-of-the-art OT-based methods while substantially reducing end-to-end runtime.
  arXiv  Detail & Related papers  (2026-07-11T21:30:10Z)
• BPDQ: Bit-Plane Decomposition Quantization on a Variable Grid for Large Language Models [56.504879072674015]
  We propose Bit-Plane Decomposition Quantization (BPDQ), which constructs a variable quantization grid via bit-planes and scalar coefficients.<n>BPDQ enables serving Qwen2.5-72B on a single GTX 3090 with 83.85% GSM8K accuracy (vs. 90.83% at 16-bit)
  arXiv  Detail & Related papers  (2026-02-04T02:54:37Z)
• Cryptanalysis of Gleeok-128 [19.615215937105898]
  This paper provides the first comprehensive third party cryptanalysis of Gleeok-128.<n>We introduce a two stage MILP based framework for constructing branch wise and full cipher differential linear (DL) distinguishers.<n>We derive 9, 9, and 7 round integral distinguishers for the three branches and a 7 round distinguisher for the full PRF.
  arXiv  Detail & Related papers  (2025-12-04T11:09:11Z)
• INT v.s. FP: A Comprehensive Study of Fine-Grained Low-bit Quantization Formats [51.72056104795248]
  Modern AI hardware, such as Nvidia's Blackwell architecture, is increasingly embracing low-precision floating-point (FP) formats.<n>This paper systematically investigates the trade-offs between FP and integer (INT) formats.<n>We reveal a critical performance crossover: while FP excels in coarse-grained quantization, the comparison at fine-grained (block-wise) levels is more nuanced.
  arXiv  Detail & Related papers  (2025-10-29T15:11:53Z)
• A Light Weight Cryptographic Solution for 6LoWPAN Protocol Stack [0.0]
  This paper presents an implementation of a lightweight 6LoWPAN Protocol stack by using a Light weight Cipher instead of regular heavy encryption cipher AES.<n>The cipher proposed in this paper is specifically suitable for 6LoWPAN architecture as it addresses all the constraints possessed by wireless sensor nodes.<n>The proposed cipher LiCi2 is motivated from LiCi cipher design but outclasses it in every design metric.
  arXiv  Detail & Related papers  (2025-10-09T23:47:04Z)
• A Compact 16-bit S-box over Tower Field $\F_{(((2^2)^2)^2)^2}$ with High Security [0.0]
  This paper introduces a compact and secure 16-bit substitution box (S-box) designed over the composite field $F_(((22)2)2)2$.<n>The proposed S-box decomposes operations into subfields, leveraging a tower field architecture.<n> Hardware results show the proposed 16-bit S-box has lower hardware resources consumption and lower critical path delay.
  arXiv  Detail & Related papers  (2025-07-02T07:22:22Z)
• Lightweight Hybrid Block-Stream Cryptographic Algorithm for the Internet of Things [1.6114012813668932]
  algorithm is designed specifically for application in Internet of Things (IoT) technology devices.<n>Design concept of this algorithm is based on the integration of a pseudo-random permutation function and a pseudo-random generator function.<n>Security analyses conducted on the algorithm, along with the results of NIST statistical tests, confirm its robustness against most common and advanced cryptographic attacks.
  arXiv  Detail & Related papers  (2025-05-13T11:29:20Z)
• How Learnable Grids Recover Fine Detail in Low Dimensions: A Neural Tangent Kernel Analysis of Multigrid Parametric Encodings [106.3726679697804]
  We compare the two most common techniques for mitigating this spectral bias: Fourier feature encodings (FFE) and multigrid parametric encodings (MPE)<n>MPEs are seen as the standard for low dimensional mappings, but MPEs often outperform them and learn representations with higher resolution and finer detail.<n>We prove that MPEs improve a network's performance through the structure of their grid and not their learnable embedding.
  arXiv  Detail & Related papers  (2025-04-18T02:18:08Z)
• Next Block Prediction: Video Generation via Semi-Autoregressive Modeling [92.60177942930946]
  Next-Block Prediction (NBP) is a semi-autoregressive (semi-AR) framework for video generation.<n>NBP employs bidirectional attention within each block, enabling tokens to capture more robust spatial dependencies.<n>Our model achieves FVD scores of 103.3 on UCF101 and 25.5 on K600, outperforming the vanilla NTP model by an average of 4.4.
  arXiv  Detail & Related papers  (2025-02-11T17:57:53Z)
• Variable-size Symmetry-based Graph Fourier Transforms for image compression [65.7352685872625]
  We propose a new family of Symmetry-based Graph Fourier Transforms of variable sizes into a coding framework. Our proposed algorithm generates symmetric graphs on the grid by adding specific symmetrical connections between nodes. Experiments show that SBGFTs outperform the primary transforms integrated in the explicit Multiple Transform Selection.
  arXiv  Detail & Related papers  (2024-11-24T13:00:44Z)
• Modeling Linear and Non-linear Layers: An MILP Approach Towards Finding Differential and Impossible Differential Propagations [1.5327660568487471]
  We introduce an automatic tool for exploring differential and impossible propagations within a cipher. The tool is successfully applied to five lightweight block ciphers: Lilliput, GIFT64, SKINNY64, Klein, and M.IBS.
  arXiv  Detail & Related papers  (2024-05-01T10:48:23Z)
• Factorizers for Distributed Sparse Block Codes [45.29870215671697]
  We propose a fast and highly accurate method for factorizing distributed block codes (SBCs) Our iterative factorizer introduces a threshold-based nonlinear activation, conditional random sampling, and an $ell_infty$-based similarity metric. We demonstrate the feasibility of our method on four deep CNN architectures over CIFAR-100, ImageNet-1K, and RAVEN datasets.
  arXiv  Detail & Related papers  (2023-03-24T12:31:48Z)
• VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
  We propose textitVersaGNN, an ultra-efficient, systolic-array-based versatile hardware accelerator. textitVersaGNN achieves on average 3712$times$ speedup with 1301.25$times$ energy reduction on CPU, and 35.4$times$ speedup with 17.66$times$ energy reduction on GPU.
  arXiv  Detail & Related papers  (2021-05-04T04:10:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.