## CryptoDB

### Jooyoung Lee

#### Affiliation: KAIST, Korea

#### Publications

**Year**

**Venue**

**Title**

2019

ASIACRYPT

Indifferentiability of Truncated Random Permutations
Abstract

One of natural ways of constructing a pseudorandom function from a pseudorandom permutation is to simply truncate the output of the permutation. When n is the permutation size and m is the number of truncated bits, the resulting construction is known to be indistinguishable from a random function up to $$2^{{n+m}\over 2}$$ queries, which is tight.In this paper, we study the indifferentiability of a truncated random permutation where a fixed prefix is prepended to the inputs. We prove that this construction is (regularly) indifferentiable from a public random function up to $$\min \{2^{{n+m}\over 3}, 2^{m}, 2^\ell \}$$ queries, while it is publicly indifferentiable up to $$\min \{ \max \{2^{{n+m}\over 3}, 2^{n \over 2}\}, 2^\ell \}$$ queries, where $$\ell $$ is the size of the fixed prefix. Furthermore, the regular indifferentiability bound is proved to be tight when $$m+\ell \ll n$$.Our results significantly improve upon the previous bound of $$\min \{ 2^{m \over 2}, 2^\ell \}$$ given by Dodis et al. (FSE 2009), allowing us to construct, for instance, an $$\frac{n}{2}$$-to-$$\frac{n}{2}$$ bit random function that makes a single call to an n-bit permutation, achieving $$\frac{n}{2}$$-bit security.

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.

2018

ASIACRYPT

Tweakable Block Ciphers Secure Beyond the Birthday Bound in the Ideal Cipher Model
Abstract

We propose a new construction of tweakable block ciphers from standard block ciphers. Our construction, dubbed $$\mathsf {XHX2}$$, is the cascade of two independent $$\mathsf {XHX}$$ block ciphers, so it makes two calls to the underlying block cipher using tweak-dependent keys. We prove the security of $$\mathsf {XHX2}$$ up to $$\min \{2^{2(n+m)/3},2^{n+m/2}\}$$ queries (ignoring logarithmic factors) in the ideal cipher model, when the block cipher operates on n-bit blocks using m-bit keys. The $$\mathsf {XHX2}$$ tweakable block cipher is the first construction that achieves beyond-birthday-bound security with respect to the input size of the underlying block cipher in the ideal cipher model.

2017

TOSC

New Constructions of MACs from (Tweakable) Block Ciphers
Abstract

We propose new constructions of Message Authentication Codes (MACs) from tweakable or conventional block ciphers. Our new schemes are either stateless and deterministic, nonce-based, or randomized, and provably secure either in the standard model for tweakable block cipher-based ones, or in the ideal cipher model for block cipher-based ones. All our constructions are very efficient, requiring only one call to the underlying (tweakable) block cipher in addition to universally hashing the message. Moreover, the security bounds we obtain are quite strong: they are beyond the birthday bound, and nonce-based/randomized variants provide graceful security degradation in case of misuse, i.e., the security bound degrades linearly with the maximal number of repetitions of nonces/random values.

2015

EPRINT

2013

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.

2009

EPRINT

Adaptive Preimage Resistance and Permutation-based Hash Functions
Abstract

In this paper, we introduce a new notion of security, called adaptive preimage resistance. We prove that a compression function that is collision resistant and adaptive preimage resistant can be combined with a public random function to yield a hash function that is indifferentiable from a random oracle. Specifically, we analyze adaptive preimage resistance of 2n-bit to n-bit compression functions that use three calls to n-bit public random permutations. By using such compression functions as building blocks, we obtain a method for construction of permutation-based pseudorandom oracles that is comparable to the Sponge construction [4] both in terms of security and efficiency.

2008

EPRINT

Efficient RFID authentication protocols based on pseudorandom sequence generators
Abstract

In this paper, we introduce a new class of PRSGs, called
\emph{partitioned pseudorandom sequence generators}(PPRSGs), and
propose an RFID authentication protocol using a PPRSG, called {\em
$S$-protocol}. Since most existing stream ciphers can be regarded as
secure PPRSGs, and stream ciphers outperform other types of
symmetric key primitives such as block ciphers and hash functions in
terms of power, performance and gate size, $S$-protocol is expected
to be suitable for use in highly constrained environments such as
RFID systems. We present a formal proof that guarantees resistance
of $S$-protocol to desynchronization and tag-impersonation attacks.
Specifically, we reduce availability of $S$-protocol to
pseudorandomness of the underlying PPRSG, and the security of the
protocol to the availability. Finally, we give a modification of
$S$-protocol, called $S^*$-protocol, that provide mutual
authentication of tag and reader.

2008

EPRINT

Authenticated Key Exchange Secure under the Computational Diffie-Hellman Assumption
Abstract

In this paper, we present a new authenticated key exchange(AKE)
protocol and prove its security under the random oracle assumption
and the computational Diffie-Hellman(CDH) assumption. In the
extended Canetti-Krawczyk model, there has been no known AKE
protocol based on the CDH assumption. Our protocol, called NAXOS+,
is obtained by slightly modifying the NAXOS protocol proposed by
LaMacchia, Lauter and Mityagin. We establish a formal security proof
of NAXOS+ in the extended Canetti-Krawczyk model using as a main
tool the trapdoor test presented by Cash, Kiltz and Shoup.

2008

EPRINT

An Efficient Authenticated Key Exchange Protocol with a Tight Security Reduction
Abstract

In this paper, we present a new authenticated key exchange(AKE)
protocol, called NETS, and prove its security in the extended
Canetti-Krawczyk model under the random oracle assumption and the
gap Diffie-Hellman(GDH) assumption. Our protocol enjoys a simple and
tight security reduction compared to those of HMQV and CMQV without
using the Forking Lemma. Each session of the NETS protocol requires
only three exponentiations per party, which is comparable to the
efficiency of MQV, HMQV and CMQV.

2007

EPRINT

Lai-Massey Scheme and Quasi-Feistel Networks
Abstract

We introduce the notion of quasi-Feistel network, which is generalization of the Feistel network, and contains the Lai-Massey scheme as an instance. We show that some of the works on the Feistel network, including the works of Luby-Rackoff, Patarin, Naor-Reingold and Piret, can be naturally extended to our setting. This gives a new proof for theorems of Vaudenay on the security of the Lai-Massey scheme, and also introduces for Lai-Massey a new construction of pseudorandom permutation, analoguous to the construction of Naor-Reingold using pairwise independent permutations.
Also, we prove the birthday security of $(2b-1)$- and $(3b-2)$-round unbalanced quasi-Feistel networks with b branches against CPA and CPCA attacks, respectively. This answers an unsolved problem pointed out by Patarin et al.

#### Program Committees

- FSE 2020
- FSE 2019
- Asiacrypt 2019
- Asiacrypt 2017
- Asiacrypt 2015
- Asiacrypt 2014

#### Coauthors

- Frederik Armknecht (1)
- Shan Chen (2)
- Wonseok Choi (1)
- Benoît Cogliati (2)
- Yuanxi Dai (1)
- Yevgeniy Dodis (1)
- Ewan Fleischmann (1)
- Peter Gaži (2)
- Jonathan Katz (1)
- Matthias Krause (1)
- Rodolphe Lampe (2)
- ByeongHak Lee (2)
- Bart Mennink (1)
- Je Hong Park (3)
- Choon Sik Park (1)
- Yannick Seurin (5)
- Martijn Stam (5)
- John P. Steinberger (12)
- Stefano Tessaro (2)
- Aishwarya Thiruvengadam (1)
- Yongjin Yeom (1)
- Aaram Yun (1)
- Zhe Zhang (1)