## CryptoDB

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

Authors: Itai Dinur Daniel Kales Angela Promitzer Sebastian Ramacher Christian Rechberger DOI: 10.1007/978-3-030-17653-2_12 (login may be required) Search ePrint Search Google $\textsc {LowMC}$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. $\textsc {LowMC}$LOWMC is used in the $\textsc {Picnic}$PICNIC signature scheme, submitted to NIST’s post-quantum standardization project and is a substantial building block in other novel post-quantum cryptosystems. Many $\textsc {LowMC}$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 $\textsc {LowMC}$LOWMC instances with block size n, partial non-linear layers of size $s \le n$s≤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$s
##### BibTeX
@article{eurocrypt-2019-29340,
title={Linear Equivalence of Block Ciphers with Partial Non-Linear Layers: Application to LowMC},
booktitle={Advances in Cryptology – EUROCRYPT 2019},
series={Advances in Cryptology – EUROCRYPT 2019},
publisher={Springer},
volume={11476},
pages={343-372},
doi={10.1007/978-3-030-17653-2_12},
author={Itai Dinur and Daniel Kales and Angela Promitzer and Sebastian Ramacher and Christian Rechberger},
year=2019
}