CryptoDB
Linear Equivalence of Block Ciphers with Partial Non-Linear Layers: Application to LowMC
| Authors: | |
|---|---|
| Download: |
|
| Abstract: | $$\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
}