Key-Dependent Graph Symmetry Breaking for Block-Based Image Encryption

Image encryption requires effective local transformation together with reliable propagation across image blocks. This study proposes a block-based encryption scheme that transforms a symmetric circulant graph into a key-dependent asymmetric directed acyclic graph (DAG) through vertex ordering, edge orientation, and directed shortcuts. The graph determines inter-block dependencies, while ciphertext feedback is incorporated into block-state generation. Each block is processed using a graph-conditioned dynamic S-box generated by unbiased Fisher–Yates shuffling, intra-block permutation, and bidirectional add-rotate-XOR (ARX) diffusion. The rank-forward construction guarantees acyclicity, and the embedded Hamiltonian path yields a unique topological order and a trivial automorphism group. Under 256 one-bit key perturbations, the mean edge-set Jaccard distance and node-order change rate are 0.8661 and 0.9836, respectively. For 100 one-bit plaintext perturbations, the mean Number of Pixels Change Rate (NPCR) and Unified Average Changing Intensity (UACI) are 99.6102% and 33.4595%, respectively. Ciphertext entropy approaches 8 bits, adjacent-pixel correlations remain near zero, and ablation results show that reverse traversal and ciphertext feedback contribute substantially to cross-block propagation. These results support key-dependent graph asymmetry as a viable mechanism for coupling global dependency structures with local cryptographic processing.