Abstract. Digital signatures have become a key component of many embedded system solutions and are facing strong security and efficiency requirements. At the same time side-channel resistance is essential for a signature scheme to be accepted in real-world applications. Based on the Merkle signature scheme and Winternitz one-time signatures we propose a signature scheme with bounded side-channel leakage that is secure in a post-quantum setting. Novel algorithmic improvements for the authentication path computation bound side-channel leakage and improve the average signature computation time by close to 50 % when compared to state-of-the-art algorithms. The proposed scheme is implemented on an Intel Core i7 CPU and an AVR ATxmega microcontroller with carefully optimized versions for the respective target platform. The theoretical algorithmic improvements are verified in the implementations and cryptographic hardware accelerators are used to achieve competitive performance. Keywords. hash-based cryptography, signatures, side-channel leakage, software, microcontroller, post-quantum cryptography With the increasing popularity of contactless smart cards and near field communication, digital signature engines have become a key component of many embedded system solutions. The applications of digital signatures are numerous, ranging from identification over electronic payments to firmware updates and protection against product counterfeiting. Due to the high computational requirements for public-key cryptography, providing efficient signatures on embedded microprocessors without dedicated co-processors is a challenge. At the same time, side channel attacks are considered a serious threat for such embedded implementations. On the downside, adding effective protection against attacks like power or EM analysis is costly in terms of space and computation time. Hence, side-channel resistant public key engines are often just too bulky for widespread adoption. Exploring public key schemes that are both efficient on embedded platforms and offer inherent side-channel resistance can be a superior alternative to the prevailing choices of (EC-)DSA and RSA.
Extensive side-channel analysis of a fast Merkle signature scheme implementation on an AVR ATxmega is presented in REF .
Faster Hash-based Signatures with Bounded Leakage
Selected Areas in Cryptography
Computer Science