## CryptoDB

### Gregor Leander

#### Affiliation: Ruhr University Bochum, Germany

#### Publications

**Year**

**Venue**

**Title**

2019

EUROCRYPT

bison Instantiating the Whitened Swap-Or-Not Construction
📺
Abstract

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

TOSC

CRAFT: Lightweight Tweakable Block Cipher with Efficient Protection Against DFA Attacks
Abstract

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

Zero-Correlation Attacks on Tweakable Block Ciphers with Linear Tweakey Expansion
Abstract

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

Searching for Subspace Trails and Truncated Differentials
Abstract

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

Rasta: A Cipher with Low ANDdepth and Few ANDs per Bit
📺
Abstract

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

ShiftRows Alternatives for AES-like Ciphers and Optimal Cell Permutations for Midori and Skinny
Abstract

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

Nonlinear Approximations in Cryptanalysis Revisited
Abstract

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

Linear Cryptanalysis: Key Schedules and Tweakable Block Ciphers
Abstract

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

TOSC

Shorter Linear Straight-Line Programs for MDS Matrices
Abstract

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

ASIACRYPT

2015

EPRINT

2015

EUROCRYPT

2013

CRYPTO

2012

EUROCRYPT

2012

ASIACRYPT

2011

EUROCRYPT

2010

EPRINT

Small Scale Variants Of The Block Cipher PRESENT
Abstract

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.

2008

ASIACRYPT

2007

EPRINT

Constructing new APN functions from known ones
Abstract

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

Sufficient Conditions for Computational Intractability Regarding Generic Algorithms
Abstract

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

EPRINT

Another class of quadratic APN binomials over $\F_{2^n}$: the case $n$ divisible by 4
Abstract

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

A class of quadratic APN binomials inequivalent to power functions
Abstract

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

EPRINT

Cryptographer's Toolkit for Construction of $8$-Bit Bent Functions
Abstract

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

An infinite class of quadratic APN functions which are not equivalent to power mappings
Abstract

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

EPRINT

On codes, matroids and secure multi-party computation from linear secret sharing schemes
Abstract

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

Secure Computation of the Mean and Related Statistics
Abstract

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.

#### Program Committees

- 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)
- Amir Moradi (3)
- Patrick Neumann (1)
- Ventzislav Nikov (1)
- Kaisa Nyberg (3)
- David Oswald (1)
- Christof Paar (8)
- Carles Padró (2)
- Thomas Peyrin (1)
- Axel Poschmann (4)
- Shahram Rasoolzadeh (1)
- Christian Rechberger (3)
- Matthew J. B. Robshaw (3)
- Peter Rombouts (1)
- Yann Rotella (1)
- Andy Rupp (3)
- Sondre Rønjom (2)
- Ahmad-Reza Sadeghi (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)