Nullspace Leakage Under Invertible Matrix Masking: Structural Cryptanalysis of a Subdivision-Star Graph Encryption Scheme

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.