Paper 2022/138

Resisting Key-Extraction and Code-Compression: a Secure Implementation of the HFE Signature Scheme in the White-Box Model

Pierre Galissant and Louis Goubin

Abstract

Cryptography is increasingly deployed in applications running on open devices in which the software is extremely vulnerable to attacks, since the attacker has complete control over the execution platform and the software implementation itself. This creates a challenge for cryptography: design implementations of cryptographic algorithms that are secure, not only in the black-box model, but also in this attack context that is referred to as the white-box adversary model. Moreover, emerging applications such as mobile payment, mobile contract signing or blockchain-based technologies have created a need for white-box implementations of public-key cryptography, and especially of signature algorithms. However, while many attempts were made to construct white-box implementations of block-ciphers, almost no white-box implementations have been published for what concerns asymmetric schemes. We present here a concrete white-box implementation of the well-known HFE signature algorithm for a specific set of internal polynomials. For a security level $2^{80}$, the public key size is approximately 62.5 MB and the white-box implementation of the signature algorithm has a size approximately 256 GB.