## CryptoDB

### John P. Steinberger

#### Publications

**Year**

**Venue**

**Title**

2018

CRYPTO

Provable Security of (Tweakable) Block Ciphers Based on Substitution-Permutation Networks
📺
Abstract

Substitution-Permutation Networks (SPNs) refer to a family of constructions which build a wn-bit block cipher from n-bit public permutations (often called S-boxes), which alternate keyless and “local” substitution steps utilizing such S-boxes, with keyed and “global” permutation steps which are non-cryptographic. Many widely deployed block ciphers are constructed based on the SPNs, but there are essentially no provable-security results about SPNs.In this work, we initiate a comprehensive study of the provable security of SPNs as (possibly tweakable) wn-bit block ciphers, when the underlying n-bit permutation is modeled as a public random permutation. When the permutation step is linear (which is the case for most existing designs), we show that 3 SPN rounds are necessary and sufficient for security. On the other hand, even 1-round SPNs can be secure when non-linearity is allowed. Moreover, 2-round non-linear SPNs can achieve “beyond-birthday” (up to
$$2^{2n/3}$$
22n/3 adversarial queries) security, and, as the number of non-linear rounds increases, our bounds are meaningful for the number of queries approaching
$$2^n$$
2n. Finally, our non-linear SPNs can be made tweakable by incorporating the tweak into the permutation layer, and provide good multi-user security.As an application, our construction can turn two public n-bit permutations (or fixed-key block ciphers) into a tweakable block cipher working on wn-bit inputs, 6n-bit key and an n-bit tweak (for any
$$w\ge 2$$
w≥2); the tweakable block cipher provides security up to
$$2^{2n/3}$$
22n/3 adversarial queries in the random permutation model, while only requiring w calls to each permutation, and 3w field multiplications for each wn-bit input.

2012

EUROCRYPT

2010

EPRINT

Multi-property-preserving Domain Extension Using Polynomial-based Modes of Operation
Abstract

In this paper, we propose a new double-piped mode of operation for multi-property-preserving domain extension of MACs~(message authentication codes), PRFs~(pseudorandom functions) and PROs~(pseudorandom oracles). Our mode of operation performs twice as fast as the original double-piped mode of operation of Lucks while providing comparable security. Our construction, which uses a class of polynomial-based compression functions proposed by Stam, makes a single call to a $3n$-bit to $n$-bit primitive at each iteration and uses a finalization function $f_2$ at the last iteration, producing an $n$-bit hash function $H[f_1,f_2]$ satisfying the following properties.
\begin{enumerate}
\item $H[f_1,f_2]$ is unforgeable up to $O(2^n/n)$ query complexity as long as $f_1$ and $f_2$ are unforgeable.
\item $H[f_1,f_2]$ is pseudorandom up to $O(2^n/n)$ query complexity as long as $f_1$ is unforgeable and $f_2$ is pseudorandom.
\item $H[f_1,f_2]$ is indifferentiable from a random oracle up to $O(2^{2n/3})$ query complexity as long as $f_1$ and $f_2$ are public random functions.
\end{enumerate}
To our knowledge, our result constitutes the first time $O(2^n/n)$ unforgeability has been achieved using only an unforgeable primitive of $n$-bit output length. (Yasuda showed unforgeability of $O(2^{5n/6})$ for Lucks' construction assuming an unforgeable primitive, but the analysis is sub-optimal; in this paper, we show how Yasuda's bound can be improved to $O(2^n)$.)
In related work, we strengthen Stam's collision resistance analysis of polynomial-based compression functions (showing that unforgeability of the primitive suffices) and discuss how to implement our mode by replacing $f_1$ with a $2n$-bit key blockcipher in Davies-Meyer mode or by replacing $f_1$ with the cascade of two $2n$-bit to $n$-bit compression functions.

2010

EPRINT

The collision security of Tandem-DM in the ideal cipher model
Abstract

We prove that Tandem-DM, one of the two ``classical'' schemes for turning a blockcipher of $2n$-bit key into a double block length hash function, has birthday-type collision resistance in the ideal cipher model. A collision resistance analysis for Tandem-DM achieving a similar birthday-type bound was already proposed by Fleischmann, Gorski and Lucks at FSE 2009. As we detail, however, the latter analysis is wrong, thus leaving the collision resistance of Tandem-DM as an open problem until now.

2006

EPRINT

The Collision Intractability of MDC-2 in the Ideal Cipher Model
Abstract

We provide the first proof of security for MDC-2, the most well-known construction for turning an n-bit blockcipher into a 2n-bit cryptographic hash function.

#### Program Committees

- FSE 2018
- Eurocrypt 2017
- Eurocrypt 2016
- Crypto 2013
- Eurocrypt 2013

#### Coauthors

- Elena Andreeva (1)
- Frederik Armknecht (1)
- Andrey Bogdanov (2)
- Shan Chen (3)
- Benoît Cogliati (1)
- Sandro Coretti (1)
- Yuanxi Dai (6)
- Yevgeniy Dodis (8)
- Ewan Fleischmann (1)
- Peter Gaži (2)
- Siyao Guo (1)
- Jonathan Katz (1)
- Lars R. Knudsen (1)
- Matthias Krause (1)
- Rodolphe Lampe (2)
- Gregor Leander (1)
- Jooyoung Lee (12)
- Tianren Liu (2)
- Bart Mennink (2)
- Thomas Ristenpart (1)
- Phillip Rogaway (2)
- Yannick Seurin (5)
- Martijn Stam (6)
- François-Xavier Standaert (1)
- Xiaoming Sun (1)
- Stefano Tessaro (3)
- Aishwarya Thiruvengadam (2)
- Elmar Tischhauser (1)
- Zhe Yang (1)
- Yu Yu (1)
- Zhe Zhang (1)