International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Itai Dinur
Daniel Kales
Angela Promitzer
Sebastian Ramacher
Christian Rechberger
Download:
DOI: 10.1007/978-3-030-17653-2_12 (login may be required)
Search ePrint
Search Google
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
}