Nullspace Leakage Under Invertible Matrix Masking: Structural Cryptanalysis of a Subdivision-Star Graph Encryption Scheme
Symmetry · 12.11.2026 · 18 (11) · 1893
DOI: 10.3390/sym18111893 ↗Kurz gefasst
Fachartikel in der Zeitschrift Symmetry, online erschienen am 12.11.2026. Verfasst von Muhammad Saeed Ahmad und 4 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: University of Johannesburg.
Abstract (Originalsprache)
Graph-based encryption proposals often combine a message-dependent graph representation with matrix transformations and then assess security through key-space size, operation counts, entropy, or visual complexity. Those indicators can be useful implementation diagnostics, but they do not rule out algebraic leakage. This paper gives a structural cryptanalysis of a subdivision-star construction whose ciphertext has the form C=PTAPK over a finite field. We first prove a generic kernel-transport theorem: if a message matrix is masked on the left and right by invertible matrices, its rank and nullity are preserved and its left nullspace is merely transported by the left mask. For the subdivision-star family, A has rank 2m in dimension 2m+1, so every ciphertext exposes a one-dimensional, plaintext-dependent left nullspace. We derive that null vector explicitly and introduce a complete signature for its scale-and-permutation orbit. For the explicitly defined challenge over F101, this yields a chosen-message distinguisher that separates “AAAA” and “BBBB” with success probability one for every admissible permutation and invertible right key. Because the source construction lacks a complete key-generation specification, this is an IND-CPA-style experiment rather than an IND-CPA theorem for a fully specified conventional cipher. An explicitly reconstructed “RAIN” numerical instance is checked exactly over F101, and seeded regression tests recover the predicted signature in all 200 randomized trials. The available materials do not identify an independently verifiable earlier publication for that instance. We also correct the computational accounting, quantify the quadratic ciphertext expansion, explain why entropy and raw key counts are nondiagnostic, and give a practical audit checklist for graph- and matrix-based cipher proposals. The case study shows why an invertible right mask combined with a secret left permutation may leave a plaintext-dependent nullspace orbit visible in public ciphertexts.
Förderung
- University of Johannesburg
Zitieren
APA
Ahmad, M. S., Asghar, M. W., Yasmin, F., Nazeer, S., & Ashraf, R. (2026). Nullspace Leakage Under Invertible Matrix Masking: Structural Cryptanalysis of a Subdivision-Star Graph Encryption Scheme. Symmetry, 18(11), 1893. https://doi.org/10.3390/sym18111893
Vancouver
Ahmad MS, Asghar MW, Yasmin F, Nazeer S, Ashraf R. Nullspace Leakage Under Invertible Matrix Masking: Structural Cryptanalysis of a Subdivision-Star Graph Encryption Scheme. Symmetry. 2026;18(11):1893. doi:10.3390/sym18111893
BibTeX
@article{Ahmad2026,
author = {Ahmad, Muhammad Saeed and Asghar, Muhammad Waseem and Yasmin, Farkhanda and Nazeer, Saima and Ashraf, Rehana},
title = {Nullspace Leakage Under Invertible Matrix Masking: Structural Cryptanalysis of a Subdivision-Star Graph Encryption Scheme},
journal = {Symmetry},
year = {2026},
volume = {18},
number = {11},
pages = {1893},
doi = {10.3390/sym18111893}
}
EUVIMED