Yongchao Li, Yongzhuang Wei, Lang Li, Jian Guo

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

Introduction

Hill: efficient low-latency implementations of linear layers via heuristic search. HILL proposes a heuristic search algorithm for efficient, low-latency linear layer implementations in lightweight cryptography, achieving significant area reduction for AES MixColumns.

Abstract

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.

Full Text

Comments

You need to be logged in to post a comment.