Paper 2018/772

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

Itai Dinur

Abstract

LowMC is a block cipher family that is optimized for practical instantiations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. It was designed in 2015 by Albrecht et al., and has recently become a substantial building block in several novel post-quantum cryptosystems. A large portion of 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 show that when $s < n$, each LowMC instance belongs to a large class of equivalent instances. We then select a \emph{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$, which is a substantial improvement for small $s$ and a reasonable choice of $r$. For standard LowMC parameters, our new encryption algorithm achieves a reduction by a factor between 2 and 4, while for more extreme parameter choices (suggested by the designers) the reduction is by a factor of more than 140. Furthermore, our new encryption algorithm is applicable to all SP-networks with partial non-linear layers. An additional unique feature of LowMC is that the linear layers of its instances are sampled at random. In the second part of the paper, we show how to reduce the sampling time and randomness complexities (i.e., the number of random bits used) by directly sampling representative instances. Finally, we formalize the notion of linear equivalence of block ciphers with partial non-linear layers and prove that the memory complexity of our encryption algorithm and the randomness complexity of our sampling algorithm are optimal.