### Improvements to the Linear Operations of LowMC: A Faster Picnic

Daniel Kales, Léo Perrin, Angela Promitzer, 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: Parts of the content of this report have been merged into the report at https://eprint.iacr.org/2018/772.

Available format(s)
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
LowMCefficient implementationPicnicpost-quantum digital signatures
Contact author(s)
sebastian ramacher @ iaik tugraz at
History
2019-02-26: last of 3 revisions
See all versions
Short URL
https://ia.cr/2017/1148

CC BY

BibTeX

@misc{cryptoeprint:2017/1148,
author = {Daniel Kales and Léo Perrin and Angela Promitzer and Sebastian Ramacher and Christian Rechberger},
title = {Improvements to the Linear Operations of LowMC: A Faster Picnic},
howpublished = {Cryptology ePrint Archive, Paper 2017/1148},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/1148}},
url = {https://eprint.iacr.org/2017/1148}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.