International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Jacques Patarin

Publications

Year
Venue
Title
2023
EUROCRYPT
Proof of Mirror Theory for a Wide Range of $\xi_{\max}$
In CRYPTO'03, Patarin conjectured a lower bound on the number of distinct solutions $(P_1, \ldots, P_{q}) \in (\{0, 1\}^{n})^{q}$ satisfying a system of equations of the form $X_i \oplus X_j = \lambda_{i,j}$ such that $P_1, P_2, \ldots$, $P_{q}$ are pairwise distinct. This result is known as \emph{``$P_i \oplus P_j$ Theorem for any $\xi_{\max}$"} or alternatively as \emph{Mirror Theory for general $\xi_{\max}$}, which was later proved by Patarin in ICISC'05. Mirror theory for general $\xi_{\max}$ stands as a powerful tool to provide a high-security guarantee for many blockcipher-(or even ideal permutation-) based designs. Unfortunately, the proof of the result contains gaps that are non-trivial to fix. In this work, we present the first complete proof of the $P_i \oplus P_j$ theorem for a wide range of $\xi_{\max}$, typically up to order $O(2^{n/4}/\sqrt{n})$. Furthermore, our proof approach is made simpler by using a new type of equation, dubbed link-deletion equation, that roughly corresponds to half of the so-called orange equations from earlier works. As an illustration of our result, we also revisit the security proofs of two optimally secure blockcipher-based pseudorandom functions, and $n$-bit security proof for six round Feistel cipher, and provide updated security bounds.
2016
JOFC
2014
FSE
2012
TCC
2012
ASIACRYPT
2010
ASIACRYPT
2008
CRYPTO
2007
ASIACRYPT
2006
ASIACRYPT
2006
EUROCRYPT
2004
CRYPTO
2003
CRYPTO
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