Source-linked AI summary
Graph Representation Learning of Lightweight IoT Ciphers
Jonathan Cook, Sabih ur Rehman, M. Arif Khan
TL;DR
Differential analysis of SIMON32 and SIMECK32 lacks efficient ML-guided graph methods for identifying and visualising high-probability clusters. The paper enriches pDDT data with four engineered features and compares KNN, DT, and RF directed graphs. All models achieve precision 1.0, while KNN provides the strongest cluster separation and fastest construction, and DT/RF provide near-perfect regression and optimal paths.
Problem
ML-guided Graph Representation Learning has been little applied to efficiently identify and visualise high-probability differential clusters in lightweight IoT ciphers.
Method
The framework extracts four differential attributes from pDDT data and constructs comparative directed graphs for SIMON32 and SIMECK32 using KNN, DT, and RF.
Results
All three models achieve precision 1.0 with zero false positives; KNN has the strongest cluster separation and highest F1 score, while DT and RF achieve near-perfect regression.
Takeaways & Limitations
The results consistently identify and structurally separate high-probability differentials across both LCAs, with KNN favouring cluster identification and efficiency and DT/RF favouring compact path-optimised graphs.
Abstract
from arXiv · showhide
SIMON and SIMECK belong to a family of Lightweight Cryptographic Algorithms (LCAs) based on the Feistel block cipher, designed for Internet of Things (IoT) devices. As with all Feistel ciphers, they are susceptible to differential cryptanalysis, necessitating rigorous resilience evaluations. While state-of-the-art techniques leverage heuristics and sampling to improve efficiency, little work has applied Machine Learning (ML) guided Graph Representation Learning (GRL) to efficiently identify and visualise high-probability differential clusters. We address this gap by introducing an efficient feature engineering strategy that extracts four differential attributes from a partial Difference Distribution Table (pDDT), revealing structural information concealed in raw differential data. Utilising the enriched features, we construct and compare three ML-guided directed graphs for SIMON$32$ and SIMECK$32$ using K-Nearest Neighbour (KNN), Decision Trees (DT), and Random Forests (RF). To the best of our knowledge, our framework produces the first graph-based visualisation of the differential clustering effect, in which high-probability single-bit differentials form geometrically close clusters in the learned embedding. All three models achieve a precision of $1.0$ in identifying high-probability differentials, confirming zero false positives. KNN achieves the strongest cluster separation, the highest F1 score and the lowest graph construction time of approximately $2.3$ seconds, while DT and RF produce optimal paths with near-perfect regression. The results are consistent across both LCAs, demonstrating the applicability of the framework to other AND-rotation LCA families.
1 Introduction
SIMON and SIMECK are lightweight IoT ciphers whose differential clustering has not previously been investigated through ML-guided graph representations. The paper introduces a GRL framework using engineered pDDT features and compares three graph-construction models.
- SIMON and SIMECK are lightweight cryptographic algorithms designed for resource-constrained IoT applications.
- Existing pDDT records contain limited differential information, and efficiency degrades as table size grows with word size.
- Graph representations had not yet been used to investigate differential clustering in SIMON and SIMECK with learnable features.
- The proposed framework converts pDDT differentials into directed graphs whose nodes represent differential pairs and whose edges encode structural and probabilistic proximity.
- The study compares KNN, DT, and RF as graph-construction engines while evaluating cluster quality and graph structure.
2 Methodology
The methodology enriches pDDT differentials with engineered features, uses those features to guide KNN, DT, and RF graph construction, and evaluates graph paths, structure, and execution time.
- Feature engineering: Feature engineering augments pDDT data with Hamming-weight, matching-position, logarithmic-probability, and extrema-related differential features.
- Model comparison: The study compares KNN, DT, and RF for guiding graphs toward high-probability non-trivial differentials, with graph size limited to 500 nodes.
- Graph evaluation: Graph analysis measures execution time, total edges, critical attack paths, hops to the stable-state node, and time per random hop.
- Graph construction: The graphs use Euclidean distance for neighbour or branch selection and an importance score that prioritises matching inputs, single-bit weights, and high differential probability.
- K-Nearest Neighbour: KNN assigns a stable-state root and creates directed edges toward nearer neighbours, weighting edges with target probability and similarity.
- Decision Tree: DT predicts blended structural scores and builds within-leaf and up-tree edges toward higher-scoring nodes, with proximity penalties for long-range connections.
- Random Forest: RF averages predictions from independently trained decision trees, tracks prediction variance as confidence, and applies the DT edge strategy.
3 Results
Across SIMON32 and SIMECK32, ML-guided graphs reveal distinct differential structures and trade-offs among KNN, DT, and RF. KNN provides stronger clustering and efficient construction, while DT and RF provide sparser, shorter-path graphs with near-perfect regression.
- KNN-guided graphs: 500-node KNN graphs place high-probability single-bit differentials in tight geometric clusters for both SIMON32 and SIMECK32.SIMECK’s cluster is centrally cohesive, while SIMON’s broader structure differs in lobe distribution and root placement.
- DT-guided graphs: DT graphs distribute nodes in dense, approximately circular interiors, placing high-probability differentials inward rather than in KNN-like peripheral clusters.Leaf-based within-leaf and up-tree edges guide connectivity and make black edges visible.
- RF-guided graphs: RF graphs create spatially separated orange single-bit differentials and fewer, more localized red critical paths concentrated on an orange spine and central cluster.RF also produces denser black scaffolding and a more structured concentric arrangement of lower-probability nodes.
- Path and construction analysis: KNN reliably finds paths from random nodes to the stable state, whereas DT and RF can fail with smaller pDDT samples despite reducing relationships by at least 90%.KNN explores more neighbours and paths, while DT and RF identify fewer, more rigid optimal paths.
- Evaluation metrics: 1.0000 precision across all models and both LCAs indicates zero false positives for identifying single-bit, matching-input differentials.KNN achieves the highest F1 score, while DT and RF produce near-perfect regression with R2 values of 0.9974 and 0.9964, respectively.
4 Discussion
The framework identifies and separates high-probability differential clusters while exposing a trade-off between cluster quality, classification coverage, graph density, and path optimisation. KNN offers the strongest cluster separation and fastest construction, whereas DT and RF produce sparser, path-optimised graphs.
- All three models achieve precision of 1.0 for optimal differentials, ensuring that high-priority classifications contain no false positives.The targeted differentials satisfy ˆ∆ = 1 and ∆Xw = 1.
- KNN constructs graphs approximately five times faster, while DT and RF produce sparser graphs with shorter Dijkstra distances.KNN retains more neighbourhood edges, whereas DT and RF favour compact, path-optimised structures.
- The clustering-quality comparison reports CQ = 1.9221 for KNN versus 1.545 for DT and RF.The CQ comparison quantifies KNN’s stronger separation of differential groups.
- Dijkstra distance to root by group is presented as a graph-analysis measure for comparing path structure.The supplied figure label identifies this comparison but does not state its numerical outcome.
5 Conclusion and Future Research
The paper introduces a GRL framework that enriches pDDT differentials with four engineered features and applies KNN, DT, and RF graphs to SIMON32 and SIMECK32. The framework identifies high-probability differentials without false positives, visualises their clustering, and shows model-specific trade-offs while motivating broader evaluation.
- The framework enhances pDDT differentials with four engineered features for supervised ML models.The features reveal structural information that is hidden in the raw pDDT.
- KNN, DT, and RF graphs identify stable-state, high-probability differentials for SIMON32 and SIMECK32 without false positives.
- Graph embeddings provide a novel visualisation of the differential clustering effect for both algorithms.
- Model comparisons reveal a trade-off between strong cluster separation and graph construction time, with KNN showing better separation.
- The framework appears generalisable across SIMON32 and SIMECK32, while future work may test additional LCAs and larger word sizes.Future work may also explore using identified differential clusters to reduce attack round counts.