HILL: Efficient Low-Latency Implementations of Linear Layers via Heuristic Search

Lightweight cryptography aims to achieve security with minimal resource footprints and low computational overhead. In particular, efficient implementations of linear layers are recognized as a crucial component. Boyar et al. showed that finding an optimal implementation of linear layers reduces to the Shortest Linear Program (SLP) problem, which is NP-hard. Consequently, various heuristic methods have been developed to search for near-optimal solutions. In this work, low-latency implementations are prioritized, and a heuristic search algorithm named HILL (Heuristic Implementation for Low-Latency Linear layers) is proposed. To further balance cost and delay, the h-XOR metric is integrated into HILL, where 2/3-input XOR gates are dynamically weighted to achieve an optimized trade-off between the circuit area and depth. Compared with the heuristic search proposed by Li et al. (FSE 2019), which yields an AES MixColumns implementation requiring 315 gate equivalents (GEs) at depth 3, our approach achieves 270.4 GEs at the same depth, corresponding to a 14.2% area reduction. To the best of our knowledge, this is one of the most efficient hardware implementations of AES linear layers in terms of both area and depth. Furthermore, implementation costs are minimized for all 4254 Maximum Distance Separable (MDS) matrices proposed by Li et al.