## CryptoDB

### Jacques Patarin

#### Affiliation: University of Versailles

#### Publications

**Year**

**Venue**

**Title**

2012

TCC

2010

EPRINT

Transfinite Cryptography
Abstract

\begin{abstract}
Let assume that Alice, Bob, and Charlie, the three classical people of cryptography are not limited anymore to perform a finite number of computations on real
computers, but are limited to $\alpha$ computations and to $\alpha$ bits of memory, where $\alpha$ is a fixed infinite cardinal. For example $\alpha = \aleph _0$ (the countable cardinal, i.e. the cardinal of $\mathbb {N}$ the set of integers), or $\alpha = \mathfrak {C}$ (the cardinal of the set $\mathbb {R}$ of real numbers). Is it possible to do secret key cryptography? Public key cryptography? Encryption? Authentication? Signatures? Is it possible to generalize
the notion of one way function? The aim of this paper is to give some elements of answers to these questions. We will see for example that for secret key cryptography there are some simple solutions. However for public key cryptography the results are much less clear.
\end{abstract}

2010

EPRINT

Introduction to Mirror Theory: Analysis of Systems of Linear Equalities and Linear Non Equalities for Cryptography
Abstract

\begin{abstract}
In this paper we will first study two closely related problems:\\
1. The problem of distinguishing $f(x\Vert 0)\oplus f(x \Vert 1)$ where $f$ is a random permutation on $n$ bits. This problem was first studied by Bellare and Implagliazzo in~\cite{BI}.\\
2. The so-called ``Theorem $P_i \oplus P_j$'' of Patarin (cf~\cite{P05}).
Then, we will see many variants and generalizations of this ``Theorem $P_i \oplus P_j$'' useful in Cryptography. In fact all these results can be seen as part of the theory that analyzes the number of solutions of systems of linear equalities and linear non equalities in finite groups. We have nicknamed these analysis ``Mirror Theory'' due to the multiples induction properties that we have in it.
\end{abstract}

2010

EPRINT

Security of balanced and unbalanced Feistel Schemes with Linear Non Equalities
Abstract

\begin{abstract}
In this paper we will study 2 security results ``above the birthday bound'' related to secret key cryptographic problems.\\
1. The classical problem of the security of 4, 5, 6 rounds balanced Random Feistel Schemes.\\
2. The problem of the security of unbalanced Feistel Schemes with contracting functions from $2n$ bits to $n$ bits. This problem was studied by Naor and Reingold~\cite{NR99} and by~\cite{YPL} with a proof of security up to the birthday bound.\\
These two problems are included here in the same paper since their analysis is closely related, as we will see. In problem 1 we will obtain security result very near the information bound (in $O(\frac {2^n}{n})$) with improved proofs and stronger explicit security bounds than previously known. In problem 2 we will cross the birthday bound of Naor and Reingold. For some of our proofs we will use~\cite{A2} submitted to Crypto 2010.
\end{abstract}

2008

EPRINT

Generic Attacks for the Xor of k random permutations
Abstract

\begin{abstract}
Xoring the output of $k$ permutations, $k\geq 2$ is a very simple way to construct pseudo-random functions (PRF) from pseudo-random
permutations (PRP). Moreover such construction has many applications in cryptography (see \cite{BI,BKrR,HWKS,SL} for example).
Therefore it is interesting both from a theoretical and from a practical point of view, to get precise security results
for this construction.
In this paper, we will describe the best attacks that we have found on the Xor of $k$ random
$n$-bit to $n$-bit permutations. When $k=2$, we will get an attack of computational complexity $O(2^n)$. This result was
already stated in \cite{BI}. On the contrary, for $k \geq 3$, our analysis is new. We will see that the best known attacks require much more than $2^n$ computations when not all of the $2^n$ outputs are given, or when the function is changed on a few points. We obtain like this a new and very simple design that can be very usefull when a security larger than $2^n$ is wanted, for example when $n$ is very small.
\end{abstract}

2008

EPRINT

A Proof of Security in O(2^n) for the Xor of Two Random Permutations
Abstract

\begin{abstract}
Xoring two permutations is a very simple way to construct pseudorandom functions from pseudorandom permutations. The aim of this paper is to get precise security results for this construction. Since such construction has many applications in cryptography (see \cite{BI,BKrR,HWKS,SL} for example), this problem is interesting both from a theoretical and from a practical point of view. In \cite{SL}, it was proved that Xoring two random permutations gives a secure pseudorandom function if $m << 2^{\frac {2n}{3}}$. By ``secure'' we mean here that the scheme will resist all adaptive chosen plaintext attacks limited to $m$ queries (even with unlimited computing power). More generally in \cite{SL} it is also proved that with $k$ Xor, instead of 2, we have security when $m << 2^{\frac {kn}{k+1}}$. In this paper we will prove that for $k=2$, we have in fact already security when $m << O(2^n)$. Therefore we will obtain a proof of a similar result claimed in \cite{BI} (security when $m<<O(2^n /n^{2/3})$). Moreover our proof is very different from the proof strategy suggested in \cite{BI} (we do not use Azuma inequality and Chernoff bounds for example), and we will get precise and explicit $O$ functions. Another interesting point of our proof is that we will show that this (cryptographic) problem of security is directly related to a very simple to describe and purely combinatorial problem.
\end{abstract}

2008

EPRINT

Generic Attacks on Feistel Schemes
Abstract

\begin{abstract}
Let $A$ be a Feistel scheme with $5$ rounds from $2n$ bits to $2n$
bits. In the present paper we show that for most such schemes $A$:
\begin{enumerate}
\item It is possible to distinguish $A$ from a random
permutation from $2n$ bits to $2n$ bits
after doing at most ${\cal O}(2^{n})$ computations with ${\cal
O}(2^{n})$ non-adaptive {\bf chosen} plaintexts.
\item It is possible to distinguish $A$ from a random
permutation from $2n$ bits to $2n$ bits
after doing at most ${\cal O}(2^{\frac{3n}{2}})$ computations with
${\cal O}(2^{\frac{3n}{2}})$ {\bf random} plaintext/ciphertext
pairs.
\end{enumerate}
Since the complexities are smaller than the number $2^{2n}$ of
possible inputs, they show that some generic attacks always exist
on Feistel schemes with $5$ rounds. Therefore we recommend in
Cryptography to use Feistel schemes with at least $6$ rounds
in the design of pseudo-random permutations.
We will also show in this paper that it is possible to distinguish
most of $6$ round Feistel permutations generator from a truly
random permutation generator by using a few (i.e. ${\cal O}(1)$)
permutations of the generator and by using a total number of
${\cal O}(2^{2n})$ queries and a total of ${\cal O}(2^{2n})$
computations. This result is not really useful to attack a single
$6$ round Feistel permutation, but it shows that when we have to
generate several pseudo-random permutations on a small number of
bits we recommend to use more than $6$ rounds.
We also show that
it is also possible to extend these results to any number of
rounds, however with an even larger complexity.
\end{abstract}

2008

EPRINT

The Random Oracle Model and the Ideal Cipher Model are Equivalent
Abstract

The Random Oracle Model and the Ideal Cipher Model are two well known idealised models of computation for proving the security of cryptosystems. At Crypto 2005, Coron et al. showed that security in the random oracle model implies security in the ideal cipher model; namely they showed that a random oracle can be replaced by a block cipher-based construction, and the resulting scheme remains secure in the ideal cipher model. The other direction was left as an open problem, i.e. constructing an ideal cipher from a random oracle. In this paper we solve this open problem and show that the Feistel construction with 6 rounds is enough to obtain an ideal cipher; we also show that 5 rounds are insufficient by providing a simple attack. This contrasts with the classical Luby-Rackoff result that 4 rounds are necessary and sufficient to obtain a (strong) pseudo-random permutation from a pseudo-random function.

2007

EPRINT

Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions
Abstract

\begin{abstract}
Unbalanced Feistel schemes with expanding functions are used to construct pseudo-random permutations from $kn$ bits to $kn$ bits by using random functions from $n$ bits to $(k-1)n$ bits. At each round, all the bits except $n$ bits are changed by using a function that depends only on these $n$ bits. C.S.Jutla \cite{Jut} investigated such schemes, which he denotes by $F^d_k$, where $d$ is the number of rounds.
In this paper, we describe novel Known Plaintext Attacks (KPA) and Non Adaptive Chosen Plaintext Attacks (CPA-1) against these schemes. With these attacks we will often be able to improve the result of C.S.Jutla. We also give precise formulas for the complexity of our attacks in $d$, $k$ and $n$.
\end{abstract}

2005

EPRINT

Benes and Butterfly schemes revisited
Abstract

In~\cite{AV96}, W. Aiello and R. Venkatesan have shown how to
construct pseudo-random functions of $2n$ bits $\rightarrow 2n$
bits from pseudo-random functions of $n$ bits $\rightarrow n$
bits. They claimed that their construction, called ``Benes'',
reaches the optimal bound ($m\ll 2^n$) of security against
adversaries with unlimited computing power but limited by $m$
queries in an adaptive chosen plaintext attack (CPA-2). However a
complete proof of this result is not given in~\cite{AV96} since
one of the assertions of~\cite{AV96} is wrong. Due to this, the
proof given in~\cite{AV96} is valid for most attacks, but not for
all the possible chosen plaintext attacks. In this paper we will
in a way fix this problem since for all $\varepsilon>0$, we will
prove CPA-2 security when $m\ll 2^{n(1-\varepsilon)}$. However we
will also see that the probability to distinguish Benes functions
from random functions is sometime larger than the term in
$\frac{m^2}{2^{2n}}$ given in~\cite{AV96}. One of the key idea in
our proof will be to notice that, when $m\gg2^{2n/3}$ and
$m\ll2^n$, for large number of variables linked with some critical
equalities, the average number of solutions may be large (i.e.
$\gg1$) while, at the same time, the probability to have at least
one such critical equalities is negligible (i.e. $\ll1$).\\
\textbf{Key Words}: Pseudo-random functions, unconditional
security, information-theoretic primitive, design of keyed hash
functions.

2005

EPRINT

Design of near-optimal pseudorandom functions and pseudorandom permutations in the information-theoretic model
Abstract

In this paper we will extend the Benes and Luby-Rackoff
constructions to design various pseudo-random functions and
pseudo-random permutations with near optimal information-theoretic
properties. An example of application is when Alice wants to
transmit to Bob some messages against Charlie, an adversary with
unlimited computing power, when Charlie can receive only a
percentage $\tau$ of the transmitted bits. By using Benes,
Luby-Rackoff iterations, concatenations and fixing at 0 some
values, we will show in this paper how to design near optimal
pseudo-random functions for all values of $\tau$. Moreover we will
show how to design near optimal pseudo-random permutations when
$\tau$ can have any value such that the number of bits obtained by
Charlie is smaller than the square root of all the transmitted
bits.

2003

EPRINT

SFLASHv3, a fast asymmetric signature scheme
Abstract

SFLASH-v2 is one of the three asymmetric signature schemes recommended by the European consortium for low-cost smart cards. The latest implementation report published at PKC 2003 shows that SFLASH-v2 is the fastest signature scheme known.
This is a detailed specification of SFLASH-v3 produced in 2003 for fear of v2 being broken. HOWEVER after detailed analysis by Chen Courtois and Yang [ICICS04], Sflash-v2 is not broken and we still recommend the previous version Sflash-v2, already recommended by Nessie, instead of this version.

2000

EUROCRYPT

1998

ASIACRYPT

1996

EUROCRYPT

1992

EUROCRYPT

#### Program Committees

- Asiacrypt 2008
- PKC 2003
- Crypto 2001

#### Coauthors

- Côme Berbain (4)
- Paul Camion (2)
- Pascal Chauvaud (1)
- Benoît Cogliati (1)
- Don Coppersmith (1)
- Jean-Sébastien Coron (3)
- Nicolas Courtois (4)
- Matthew K. Franklin (1)
- Henri Gilbert (1)
- Louis Goubin (5)
- Thomas Holenstein (1)
- Aviad Kipnis (1)
- Alexander Klimov (1)
- Robin Künzler (1)
- Rodolphe Lampe (2)
- Avradip Mandal (1)
- Audrey Montreuil (1)
- Valérie Nachef (5)
- Michael K. Reiter (1)
- Yannick Seurin (5)
- Adi Shamir (1)
- Stefano Tessaro (1)
- Emmanuel Volte (2)