Structural Cryptanalysis of a Middle-Graph Matrix Cipher and a Canonical Public Middle-Graph Encoding

Structural complexity in a graph-derived representation does not by itself establish cryptographic security. This paper performs a self-cryptanalysis of the authors’ own middle-graph matrix cipher from an earlier version of this manuscript; the attacked construction is not attributed to a previously published cipher. For a fixed key, the cipher right-multiplies a normalized weighted adjacency matrix of M(Sn+1) by an invertible secret matrix. We prove a ciphertext-visible row relation that, from one exact ciphertext, recovers every leaf parameter yi and the n secret key rows indexed by the edge vertices. A single ciphertext does not by itself reveal the message coordinates xi or zi; complete key recovery requires additional information such as known plaintexts and a full-column-rank stacked system. We give a concrete recovery algorithm and numerical example, an O(n3) arithmetic cost analysis, a perturbation bound for rounded ciphertexts, and experiments showing when integer parameter recovery survives decimal rounding. As a representation-only alternative, we define a canonical public byte-to-residue encoding and an optional expanded middle-graph matrix over F65521. The compact residue vector is the primary serialized object; the dense graph matrix is reconstructed only when a downstream graph or matrix algorithm actually consumes it. The map is public, deterministic, and reversible and is not claimed to provide confidentiality. Its clique identities can detect non-adversarial random corruption under an explicitly stated model, but they are not a form of authentication. If protected transport is required, then a standard AEAD scheme is applied as an independent security layer. This composition is included only to delimit the security boundary and not as a new cryptographic primitive. Benchmarks report the medians and interquartile ranges, compare the graph encoder with a simpler 16-bit baseline, and compare direct AES-GCM with encoding-plus-AES-GCM. The results show that the graph representation is justified only when its explicit graph structure is needed downstream; otherwise, direct authenticated encryption is simpler and faster.