Paper 2017/1148

Improvements to the Linear Operations of LowMC: A Faster Picnic

Daniel Kales and 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 primarily based on the existence of a one-way function, and the signature size strongly depends on the number of multiplications in the circuit describing 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 round key computation 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 a factor of 2 and furthermore reduce the size of the LowMC matrices by around 45% compared to the original Picnic implementation (CCS'17). Second, we propose two modifications to the remaining matrix multiplication in LowMC's linear layer. The first modification decomposes the multiplication into parts depending on the their effect on the S-box layer. While this requires the linear layer matrices to have an invertible submatrix, it reduces the runtime and memory costs significantly, both by up to a factor of 4 for instances used by Picnic and up to a factor of 25 for LowMC instances with only one S-box. The second modification proposes 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 block size but more importantly, improve over Picnic's matrix multiplication by 60% while retaining a constant-time algorithm. Furthermore, this technique also enables us to reduce the memory requirements for storing LowMC matrices by 60%.

Note: Update with new improvements that were independently also described in Dinur18 (ePrint 2018/772), including benchmarking of optimized implementations of those improvements.