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 }