Paper 2017/1148

Improvements to the Linear Layer of LowMC: A Faster Picnic

Léo Perrin and Angela Promitzer and Sebastian Ramacher and Christian Rechberger

Abstract

Picnic is a practical approach to digital signatures where the security is largely based on the existence of a one-way function, and the signature size strongly depends on the number of multiplications in the description of that one-way function. The highly parameterizable block cipher family LowMC has the most competitive properties with respect to this metric, and is hence a standard choice. In this paper we study various options for efficient implementations of LowMC in-depth. First, we investigate optimizations of the linear layer of LowMC independently of any implementation optimizations. By decomposing the round key computations based on the keys' effect on the S-box layer and general optimizations, we reduce runtime costs by up to 40 % and furthermore reduce the size of the LowMC matrices by around 55 % compared to the original Picnic implementation (CCS'17). Second, we propose a Feistel structure using smaller matrices completely replacing the remaining large matrix multiplication in LowMC's linear layer. With this approach we achieve an operation count logarithmic in the blocksize, but more importantly improve over Picnic's constant-time matrix multiplication by 60 % while retaining a constant-time algorithm. Furthermore, this technique also enables us to reduce the memory requirements for the LowMC matrices by 50 %.