### Linear Equivalence of Block Ciphers with Partial Non-Linear Layers: Application to LowMC

Itai Dinur, Daniel Kales, Angela Promitzer, Sebastian Ramacher, and Christian Rechberger

##### Abstract

LowMC is a block cipher family designed in 2015 by Albrecht et al. It is optimized for practical instantiations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. LowMC is used in the Picnic signature scheme, submitted to NIST's post-quantum standardization project and is a substantial building block in other novel post-quantum cryptosystems. Many LowMC instances use a relatively recent design strategy (initiated by Gérard et al. at CHES 2013) of applying the non-linear layer to only a part of the state in each round, where the shortage of non-linear operations is partially compensated by heavy linear algebra. Since the high linear algebra complexity has been a bottleneck in several applications, one of the open questions raised by the designers was to reduce it, without introducing additional non-linear operations (or compromising security). In this paper, we consider LowMC instances with block size $n$, partial non-linear layers of size $s \leq n$ and $r$ encryption rounds. We redesign LowMC's linear components in a way that preserves its specification, yet improves LowMC's performance in essentially every aspect. Most of our optimizations are applicable to all SP-networks with partial non-linear layers and shed new light on this relatively new design methodology. Our main result shows that when $s < n$, each LowMC instance belongs to a large class of equivalent instances that differ in their linear layers. We then select a representative instance from this class for which encryption (and decryption) can be implemented much more efficiently than for an arbitrary instance. This yields a new encryption algorithm that is equivalent to the standard one, but reduces the evaluation time and storage of the linear layers from $r \cdot n^2$ bits to about $r \cdot n^2 - (r-1)(n-s)^2$. Additionally, we reduce the size of LowMC's round keys and constants and optimize its key schedule and instance generation algorithms. All of these optimizations give substantial improvements for small $s$ and a reasonable choice of $r$. Finally, we formalize the notion of linear equivalence of block ciphers and prove the optimality of some of our results. Comprehensive benchmarking of our optimizations in various LowMC applications (such as Picnic) reveals improvements by factors that typically range between $2$x and $40$x in runtime and memory consumption.

Note: Partial merge of the previous version of this report and the report at https://eprint.iacr.org/2017/1148.

Available format(s)
Category
Secret-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2019
Keywords
Block cipherLowMCPicnic signature algorithmlinear equivalence
Contact author(s)
dinuri @ cs bgu ac il
daniel kales @ iaik tugraz at
angela promitzer @ gmail com
sebastian ramacher @ iaik tugraz at
christian rechberger @ tugraz at
History
2019-02-26: revised
See all versions
Short URL
https://ia.cr/2018/772

CC BY

BibTeX

@misc{cryptoeprint:2018/772,
author = {Itai Dinur and Daniel Kales and Angela Promitzer and Sebastian Ramacher and Christian Rechberger},
title = {Linear Equivalence of Block Ciphers with Partial Non-Linear Layers: Application to LowMC},
howpublished = {Cryptology ePrint Archive, Paper 2018/772},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/772}},
url = {https://eprint.iacr.org/2018/772}
}

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