## CryptoDB

### Angela Promitzer

#### Publications

Year
Venue
Title
2019
EUROCRYPT
$\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<n, each $\textsc {LowMC}$LOWMC instance belongs to a large class of equivalent instances that differ in their linear layers. We then select a 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$r·n2 bits to about $r \cdot n^2 - (r-1)(n-s)^2$r·n2-(r-1)(n-s)2. Additionally, we reduce the size of LowMC’s round keys and constants and optimize its key schedule and instance generation algorithms. All of these optimizations give substantial improvements for small s and a reasonable choice of r. Finally, we formalize the notion of linear equivalence of block ciphers and prove the optimality of some of our results.Comprehensive benchmarking of our optimizations in various $\textsc {LowMC}$LOWMC applications (such as $\textsc {Picnic}$PICNIC) reveals improvements by factors that typically range between 2x and 40x in runtime and memory consumption.

#### Coauthors

Itai Dinur (1)
Daniel Kales (1)
Sebastian Ramacher (1)
Christian Rechberger (1)