## CryptoDB

### Gregor Leander

#### Publications

Year
Venue
Title
2019
EUROCRYPT
We give the first practical instance – bison – of the Whitened Swap-Or-Not construction. After clarifying inherent limitations of the construction, we point out that this way of building block ciphers allows easy and very strong arguments against differential attacks.
2019
FSE
2019
TOSC
Traditionally, countermeasures against physical attacks are integrated into the implementation of cryptographic primitives after the algorithms have been designed for achieving a certain level of cryptanalytic security. This picture has been changed by the introduction of PICARO, ZORRO, and FIDES, where efficient protection against Side-Channel Analysis (SCA) attacks has been considered in their design. In this work we present the tweakable block cipher CRAFT: the efficient protection of its implementations against Differential Fault Analysis (DFA) attacks has been one of the main design criteria, while we provide strong bounds for its security in the related-tweak model. Considering the area footprint of round-based hardware implementations, CRAFT outperforms the other lightweight ciphers with the same state and key size. This holds not only for unprotected implementations but also when fault-detection facilities, side-channel protection, and their combination are integrated into the implementation. In addition to supporting a 64-bit tweak, CRAFT has the additional property that the circuit realizing the encryption can support the decryption functionality as well with very little area overhead.
2019
TOSC
The design and analysis of dedicated tweakable block ciphers is a quite recent and very active research field that provides an ongoing stream of new insights. For instance, results of Kranz, Leander, and Wiemer from FSE 2017 show that the addition of a tweak using a linear tweak schedule does not introduce new linear characteristics. In this paper, we consider – to the best of our knowledge – for the first time the effect of the tweak on zero-correlation linear cryptanalysis for ciphers that have a linear tweak schedule. It turns out that the tweak can often be used to get zero-correlation linear hulls covering more rounds compared to just searching zero-correlation linear hulls on the data-path of a cipher. Moreover, this also implies the existence of integral distinguishers on the same number of rounds. We have applied our technique on round reduced versions of Qarma, Mantis, and Skinny. As a result, we can present – to the best of our knowledge – the best attack (with respect to number of rounds) on a round-reduced variant of Qarma.
2018
TOSC
Grassi et al. [Gra+16] introduced subspace trail cryptanalysis as a generalization of invariant subspaces and used it to give the first five round distinguisher for Aes. While it is a generic method, up to now it was only applied to the Aes and Prince. One problem for a broad adoption of the attack is a missing generic analysis algorithm. In this work we provide efficient and generic algorithms that allow to compute the provably best subspace trails for any substitution permutation cipher.
2018
CRYPTO
Recent developments in multi party computation (MPC) and fully homomorphic encryption (FHE) promoted the design and analysis of symmetric cryptographic schemes that minimize multiplications in one way or another. In this paper, we propose with Rastaa design strategy for symmetric encryption that has ANDdepth d and at the same time only needs d ANDs per encrypted bit. Even for very low values of d between 2 and 6 we can give strong evidence that attacks may not exist. This contributes to a better understanding of the limits of what concrete symmetric-key constructions can theoretically achieve with respect to AND-related metrics, and is to the best of our knowledge the first attempt that minimizes both metrics simultaneously. Furthermore, we can give evidence that for choices of d between 4 and 6 the resulting implementation properties may well be competitive by testing our construction in the use-case of removing the large ciphertext-expansion when using the BGV scheme.
2018
TOSC
We study possible alternatives for ShiftRows to be used as cell permutations in AES-like ciphers. As observed during the design process of the block cipher Midori, when using a matrix with a non-optimal branch number for the MixColumns operation, the choice of the cell permutation, i.e., an alternative for ShiftRows, can actually improve the security of the primitive. In contrast, when using an MDS matrix it is known that one cannot increase the minimum number of active S-boxes by deviating from the ShiftRows-type permutation. However, finding the optimal choice for the cell permutation for a given, non-optimal, MixColumns operation is a highly non-trivial problem. In this work, we propose techniques to speed up the search for the optimal cell permutations significantly. As case studies, we apply those techniques to Midori and Skinny and provide possible alternatives for their cell permutations. We finally state an easy-to-verify sufficient condition on a cell permutation, to be used as an alternative in Midori, that attains a high number of active S-boxes and thus provides good resistance against differential and linear attacks.
2018
TOSC
This work studies deterministic and non-deterministic nonlinear approximations for cryptanalysis of block ciphers and cryptographic permutations and embeds it into the well-understood framework of linear cryptanalysis. For a deterministic (i.e., with correlation ±1) nonlinear approximation we show that in many cases, such a nonlinear approximation implies the existence of a highly-biased linear approximation. For non-deterministic nonlinear approximations, by transforming the cipher under consideration by conjugating each keyed instance with a fixed permutation, we are able to transfer many methods from linear cryptanalysis to the nonlinear case. Using this framework we in particular show that there exist ciphers for which some transformed versions are significantly weaker with regard to linear cryptanalysis than their original counterparts.
2017
TOSC
This paper serves as a systematization of knowledge of linear cryptanalysis and provides novel insights in the areas of key schedule design and tweakable block ciphers. We examine in a step by step manner the linear hull theorem in a general and consistent setting. Based on this, we study the influence of the choice of the key scheduling on linear cryptanalysis, a – notoriously difficult – but important subject. Moreover, we investigate how tweakable block ciphers can be analyzed with respect to linear cryptanalysis, a topic that surprisingly has not been scrutinized until now.
2017
CRYPTO
2017
ASIACRYPT
2017
JOFC
2017
TOSC
Recently a lot of attention is paid to the search for efficiently implementable MDS matrices for lightweight symmetric primitives. Most previous work concentrated on locally optimizing the multiplication with single matrix elements. Separate from this line of work, several heuristics were developed to find shortest linear straightline programs. Solving this problem actually corresponds to globally optimizing multiplications by matrices. In this work we combine those, so far largely independent lines of work. As a result, we achieve implementations of known, locally optimized, and new MDS matrices that significantly outperform all implementations from the literature. Interestingly, almost all previous locally optimized constructions behave very similar with respect to the globally optimized implementation. As a side effect, our work reveals the so far best implementation of the Aes Mix- Columns operation with respect to the number of XOR operations needed.
2016
CRYPTO
2016
CRYPTO
2016
CHES
2016
ASIACRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EUROCRYPT
2015
CRYPTO
2014
CRYPTO
2014
EPRINT
2014
FSE
2013
CRYPTO
2013
CRYPTO
2012
EUROCRYPT
2012
CRYPTO
2012
ASIACRYPT
2012
ASIACRYPT
2011
FSE
2011
FSE
2011
CRYPTO
2011
EUROCRYPT
2011
CHES
2010
EPRINT
In this note we de¯ne small scale variants of the block cipher present [1]. The main reason for this is that the running time of some recent attacks (e.g. [2, 3]) remain unclear as they are based on heuristics that are hard or even impossible to verify in practice. Those attacks usually require the full code bock of present to be available and they work only if some independence assumptions hold in practice. While those assumptions are clearly wrong from a theoretical point of view, the impact on the running times of the attacks in question is not clear. With versions of present with smaller block size it might be possible to verify how those attacks scale for those versions and hopefully learn something about present itself.
2010
CHES
2009
PKC
2009
CRYPTO
2008
ASIACRYPT
2008
CHES
2007
CHES
2007
FSE
2007
EPRINT
We present a method for constructing new quadratic APN functions from known ones. Applying this method to the Gold power functions we construct an APN function $x^3+\tr(x^9)$ over $\F_{2^n}$. It is proven that in general this function is CCZ-inequivalent to the Gold functions (and therefore EA-inequivalent to power functions), to the inverse and Dobbertin mappings, and in the case $n=7$ it is CCZ-inequivalent to all power mappings.
2007
EPRINT
The generic group model is a valuable methodology for analyzing the computational hardness of the number-theoretic problems used in cryptography. Although generic hardness proofs exhibit many similarities, still the computational intractability of every newly introduced problem needs to be proven from scratch, a task that can easily become complicated and cumbersome when done rigorously. In this paper we make the first steps towards overcoming this problem by identifying verifiable criteria which if met by a cryptographic problem guarantee its hardness with respect to generic algorithms. As useful means for formalization of definitions and proofs we relate the concepts of generic algorithms and straight-line programs that have only been used independently in cryptography so far. The class of problems we cover includes a significant number of the cryptographic problems currently known, and is general enough to also include many future problems. Moreover, we strengthen the conventional generic model by incorporating a broader class of possible oracles (operations) since the underlying algebraic groups may possibly be related through mappings such as isomorphisms, homomorphisms or multilinear maps. Our approach could serve as an appropriate basis for tool-aided hardness verification in the generic model.
2006
ASIACRYPT
2006
EPRINT
We exhibit an infinite class of almost perfect nonlinear quadratic binomials from $\mathbb{F}_{2^{n}}$ to $\mathbb{F}_{2^{n}}$ with $n=4k$ and $k$ odd. We prove that these functions are CCZ-inequivalent to known APN power functions when $k\ne 1$. In particular it means that for $n=12,20,28$, they are CCZ-inequivalent to any power function.
2006
EPRINT
We exhibit an infinite class of almost perfect nonlinear quadratic binomials from $\mathbb{F}_{2^n}$ to $\mathbb{F}_{2^n}$ ($n\geq 12$, $n$ divisible by 3 but not by 9). We prove that these functions are EA-inequivalent to any power function and that they are CCZ-inequivalent to any Gold function and to any Kasami function. It means that for $n$ even they are CCZ-inequivalent to any known APN function, and in particular for $n=12,24$, they are therefore CCZ-inequivalent to any power function. It is also proven that, except in particular cases, the Gold mappings are CCZ-inequivalent to the Kasami and Welch functions.
2005
CRYPTO
2005
TCC
2005
EPRINT
Boolean functions form basic building blocks in various cryptographic algorithms. They are used for instance as filters in stream ciphers. Maximally non-linear (necessarily non-balanced) Boolean functions with an even number of variables are called bent functions. Bent functions can be modified to get balanced highly non-linear Boolean functions. Recently the first author has demonstrated how bent functions can be studied in a recursive framework of certain integer-valued functions. Based on this new approach we describe the practical systematic construction of $8$-bit bent functions. We outline also how to compute the number of all $8$-bit bent functions.
2005
EPRINT
We exhibit an infinite class of almost perfect nonlinear quadratic polynomials from $\mathbb{F}_{2^n}$ to $\mathbb{F}_{2^n}$ ($n\geq 12$, $n$ divisible by 3 but not by 9). We prove that these functions are EA-inequivalent to any power function. In the forthcoming version of the present paper we will proof that these functions are CCZ-inequivalent to any Gold function and to any Kasami function, in particular for $n=12$, they are therefore CCZ-inequivalent to power functions.
2004
CHES
2004
EPRINT
Error correcting codes and matroids have been widely used in the study of ordinary secret sharing schemes. In this paper, we study the connections between codes, matroids, and a special class of secret sharing schemes: multiplicative linear secret sharing schemes. Such schemes are known to enable multi-party computation protocols secure against general (non-threshold) adversaries. Two open problems related to the complexity of multiplicative LSSSs are considered in this paper. The first one deals with strongly multiplicative LSSSs. As opposed to the case of multiplicative LSSSs, it is not known whether there is an efficient method to transform an LSSS into a strongly multiplicative LSSS for the same access structure with a polynomial increase of the complexity. We prove a property of strongly multiplicative LSSSs that could be useful in solving this problem. Namely, using a suitable generalization of the well-known Berlekamp-Welch decoder, we show that all strongly multiplicative LSSSs enable efficient reconstruction of a shared secret in the presence of malicious faults. The second one is to characterize the access structures of ideal multiplicative LSSSs. Specifically, we wonder whether all self-dual vector space access structures are in this situation. By the aforementioned connection, this in fact constitutes an open problem about matroid theory, since it can be re-stated in terms of representability of identically self-dual matroids by self-dual codes. We introduce a new concept, the flat-partition, that provides a useful classification of identically self-dual matroids. Uniform identically self-dual matroids, which are known to be representable by self-dual codes, form one of the classes. We prove that this property also holds for the family of matroids that, in a natural way, is the next class in the above classification: the identically self-dual bipartite matroids.
2004
EPRINT
In recent years there has been massive progress in the development of technologies for storing and processing of data. If statistical analysis could be applied to such data when it is distributed between several organisations, there could be huge benefits. Unfortunately, in many cases, for legal or commercial reasons, this is not possible. The idea of using the theory of multi-party computation to analyse efficient algorithms for privacy preserving data-mining was proposed by Pinkas and Lindell. The point is that algorithms developed in this way can be used to overcome the apparent impasse described above: the owners of data can, in effect, pool their data while ensuring that privacy is maintained. Motivated by this, we describe how to securely compute the mean of an attribute value in a database that is shared between two parties. We also demonstrate that existing solutions in the literature that could be used to do this leak information, therefore underlining the importance of applying rigorous theoretical analysis rather than settling for ad hoc techniques.

FSE 2020
Eurocrypt 2019
FSE 2019
FSE 2018
Eurocrypt 2018
Eurocrypt 2017
FSE 2017
Crypto 2016
Eurocrypt 2015
FSE 2015
Crypto 2015
CHES 2014
FSE 2014
Asiacrypt 2014
FSE 2013
CHES 2013
Eurocrypt 2013
FSE 2012

#### Coauthors

Mohamed Ahmed Abdelraheem (3)
Martin Ågren (1)
Martin R. Albrecht (2)
Gianira N. Alfarano (1)
Hoda AlKhzaimi (1)
Ralph Ankele (1)
Endre Bangerter (2)
Peter Beelen (1)
Christof Beierle (7)
Céline Blondeau (3)
Andrey Bogdanov (6)
Julia Borghoff (3)
Erik Boss (1)
Lilya Budaghyan (4)
Anne Canteaut (4)
Claude Carlet (4)
Ronald Cramer (2)
Vanesa Daza (2)
Alexander W. Dent (2)
Itai Dinur (1)
Hans Dobbertin (1)
Christoph Dobraunig (2)
Benedikt Driessen (3)
Orr Dunkelman (1)
Maria Eichlseder (1)
Patrick Felke (2)
Ignacio Gracia (2)
Lorenzo Grassi (1)
Vincent Grosso (1)
Tim Güneysu (2)
Jian Guo (1)
Mathias Herrmann (1)
Takanori Isobe (1)
Jérémy Jean (1)
Philipp Jovanovic (1)
Timo Kasper (1)
Elif Bilge Kavun (3)
Eike Kiltz (2)
Miroslav Knezevic (2)
Lars R. Knudsen (6)
Stefan Kölbl (4)
Thorsten Kranz (4)
Virginie Lallemand (2)
Eran Lambooij (1)
Martin M. Lauridsen (1)
Eik List (1)
John Malone-Lee (2)
Jaume Martí-Farré (2)
Krystian Matusiewicz (1)
Alexander May (1)
Florian Mendel (1)
Brice Minaud (2)
Patrick Neumann (1)
Ventzislav Nikov (1)
Kaisa Nyberg (3)
David Oswald (1)
Christof Paar (8)
Thomas Peyrin (1)
Axel Poschmann (4)
Christian Rechberger (3)
Matthew J. B. Robshaw (3)
Peter Rombouts (1)
Yann Rotella (1)
Andy Rupp (3)
Sondre Rønjom (2)
Yu Sasaki (2)
Pascal Sasdrich (1)
Falk Schellenberg (1)
Tobias Schneider (1)
Kai Schramm (2)
Yannick Seurin (2)
Siang Meng Sim (1)
François-Xavier Standaert (1)
John P. Steinberger (1)
Ko Stoffelen (1)
Daehyun Strobel (1)
Cihangir Tezcan (1)
Søren S. Thomsen (1)
Søren S. Thomsen (1)
Tyge Tiessen (2)
Elmar Tischhauser (1)
Yosuke Todo (2)
Deniz Toz (1)
Jorge Jiménez Urroz (2)
Kerem Varici (1)
Ingrid Verbauwhede (1)
C. Vikkelsoe (1)
Meiqin Wang (1)
Friedrich Wiemer (4)
Tolga Yalçin (3)
Erik Zenner (2)