International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Jacques Patarin

Affiliation: University of Versailles

Publications

Year
Venue
Title
2016
JOFC
2014
EPRINT
2014
FSE
2012
TCC
2012
ASIACRYPT
2010
ASIACRYPT
2010
EPRINT
Transfinite Cryptography
Jacques Patarin
\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
Jacques Patarin
\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
Jacques Patarin
\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
CRYPTO
2008
EPRINT
Generic Attacks for the Xor of k random permutations
Jacques Patarin
\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
Jacques Patarin
\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
Jacques Patarin
\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
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
ASIACRYPT
2007
EPRINT
Generic Attacks on Unbalanced Feistel Schemes with Expanding Functions
Valérie Nachef Jacques Patarin C?me Berbain
\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}
2006
ASIACRYPT
2006
EUROCRYPT
2005
EPRINT
Benes and Butterfly schemes revisited
Jacques Patarin Audrey Montreuil
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
Jacques Patarin Paul Camion
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.
2004
CRYPTO
2003
CRYPTO
2003
EPRINT
SFLASHv3, a fast asymmetric signature scheme
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.
2001
ASIACRYPT
2000
EUROCRYPT
1999
CHES
1999
EUROCRYPT
1998
ASIACRYPT
1998
EUROCRYPT
1998
FSE
1996
CRYPTO
1996
EUROCRYPT
1996
EUROCRYPT
1995
CRYPTO
1994
ASIACRYPT
1993
CRYPTO
1993
EUROCRYPT
1992
EUROCRYPT
1991
CRYPTO
1991
EUROCRYPT

Program Committees

Asiacrypt 2008
PKC 2003
Crypto 2001