Résumé technique : Bornes inférieures temps-espace cryptanalytiques non adaptatives via une inégalité de type Shearer pour les permutations

1. Énoncé du problème et motivation

Cet article examine la puissance de l'adaptativité dans les compromis temps-espace cryptanalytiques au sein du modèle de prétraitement (non uniforme). Dans ce modèle, un adversaire se compose d'une phase de prétraitement générant une chaîne de conseils de $S$ bits basée sur l'instance du problème, suivie d'une phase en ligne résolvant des défis spécifiques en utilisant $T$ requêtes oracle et la chaîne de conseils.

Bien que de nombreux algorithmes cryptanalytiques de pointe (par exemple, l'algorithme de Pollard Rho pour le logarithme discret, les attaques adaptatives sur Even-Mansour) reposent fortement sur l'adaptativité — où les requêtes dépendent des réponses précédentes de l'oracle —, il restait incertain si les algorithmes non adaptatifs (où les requêtes sont fixées à l'avance, dépendant potentiellement uniquement des conseils) pouvaient atteindre une efficacité similaire. Les techniques de bornes inférieures précédentes pour ces problèmes étaient généralement incapables de distinguer entre les algorithmes adaptatifs et non adaptatifs, produisant souvent des bornes trop faibles pour prouver que l'adaptativité offre un avantage significatif.

Les auteurs abordent la question soulevée par Corrigan-Gibbs et Kogan [CK19] : Quelle est la puissance de l'adaptativité dans les algorithmes cryptanalytiques non uniformes ? Plus précisément, ils visent à prouver des bornes inférieures précises montrant que les algorithmes non adaptatifs ne peuvent pas égaler l'efficacité des algorithmes adaptatifs dans le cadre du prétraitement pour des problèmes cryptographiques fondamentaux.

2. Méthodologie et cadre technique

2.1 Le modèle du Défi de Permutation (PC)

Pour unifier l'analyse de problèmes divers (Logarithme Discret, DDH, sqDDH et récupération de clé Even-Mansour), les auteurs introduisent le modèle du Défi de Permutation (PC).

• Structure : Le modèle implique une « permutation interne » $\sigma: [N] \to [N]$ et un secret $d$.
• Requêtes : L'adversaire effectue deux types de requêtes :
  1. Requêtes internes : Accès direct à $\sigma$ (ou $\sigma^{-1}$).
  2. Requêtes externes : Accès à une « fonction externe » définie par une fonction de traduction $tr(d, m)$ et une fonction de post-traitement $post(d, \cdot)$. La requête $m$ est traduite en une entrée pour $\sigma$ via $tr$, et la sortie est post-traitée.
• Définition de la non-adaptativité : Un algorithme est non adaptatif si ses requêtes pré-traduites (les valeurs $m$ et les indices de requêtes internes) sont fixées à l'avance sur la base de la chaîne de conseils $z$, mais pas sur le défi spécifique $d$ ou les sorties de $\sigma$. Crucialement, les réelles requêtes oracle à $\sigma$ peuvent dépendre de $d$ en raison de la fonction de traduction, permettant au modèle de capturer des algorithmes non adaptatifs classiques comme Baby-Step Giant-Step.

2.2 Outils informationnels

Le cœur de la preuve repose sur des outils informationnels appliqués à des distributions sur l'espace des permutations $S_N$, plutôt que sur des espaces produits.

• Lemme de Shearer pour les permutations : Les auteurs utilisent une variante du lemme de Shearer pour les bijections aléatoires (dérivée de Barthe et al. [BCELM11] et Caputo et Salez [CS24]). Cette inégalité relie la divergence de Kullback-Leibler (KL) d'une distribution sur les permutations aux divergences KL de ses marginales sur des sous-ensembles d'indices.
• Inégalités de concentration pour les familles Read-$k$ : Ils déduisent une borne de concentration pour des familles de fonctions sur les permutations où chaque fonction dépend d'un ensemble de variables « read-$k$ » (chaque coordonnée est accédée par au plus $k$ fonctions). Cela étend le résultat de Gavinsky et al. [GLSS15] des espaces produits à l'espace des bijections.
• Uniformité de la traduction : Une condition technique clé est que la fonction de traduction $tr$ doit être $u$-uniforme. Cela signifie que pour toute requête externe fixe, l'entrée résultante pour la permutation est distribuée de manière presque uniforme sur $[N]$ lorsque le secret $d$ est choisi uniformément.

2.3 Stratégie de preuve

Le théorème principal (Théorème 4.1) borne la probabilité de succès d'un adversaire de prétraitement non adaptatif en la reliant à la probabilité de succès d'un adversaire sans prétraitement.

1. Argument hybride : La preuve introduit un « jeu intermédiaire » où l'adversaire peut fixer un nombre limité de valeurs de permutation (simulant des requêtes internes) mais le reste est échantillonné uniformément.
2. Analyse de la divergence KL : En conditionnant sur la chaîne de conseils, les auteurs analysent la divergence KL entre la distribution de la permutation dans le cadre du prétraitement et la distribution uniforme.
3. Application de bornes de type Shearer : En utilisant l'uniformité $u$ de la fonction de traduction, ils montrent que l'ensemble des requêtes externes traduites forme une famille read-$k$. L'inégalité de concentration (Théorème 1.9) borne alors l'avantage obtenu grâce à la chaîne de conseils, montrant que sauf si la chaîne de conseils est suffisamment grande ($S \gg \sqrt{N}$), la probabilité de succès ne peut pas dépasser significativement celle d'un algorithme sans prétraitement.

3. Contributions et résultats clés

L'article établit des bornes inférieures précises démontrant que l'adaptativité offre un avantage significatif dans le modèle de prétraitement pour plusieurs problèmes cryptographiques.

3.1 Logarithme Discret (DLOG)

• Résultat : Pour un groupe générique d'ordre premier $N$, tout algorithme $(S, T)$ non adaptatif avec prétraitement a une probabilité de succès bornée par :
  $$\text{Succès} \le 2 \cdot \text{Max}_{S}^{\text{DLOG}}(T) + \frac{4 \log(2) ST}{N} + \frac{T^2}{N}$$
  où $\text{Max}_{S}^{\text{DLOG}}(T) \le T^2/N$ est la borne pour les algorithmes sans prétraitement (Shoup [Sho97]).
• Implication : La complexité temporelle en ligne $T = O(\sqrt{N})$ de l'algorithme non adaptatif Baby-Step Giant-Step ne peut pas être améliorée par le prétraitement, à moins que la taille de la chaîne de conseils $S$ ne dépasse $\Omega(\sqrt{N})$. Cela contraste nettement avec les algorithmes adaptatifs (par exemple, Mihalcik [Mih10], Bernstein et Lange [BL13], Corrigan-Gibbs et Kogan [CK18]) qui atteignent le compromis $ST^2 = \tilde{O}(N)$, permettant $T = O(N^{1/3})$ avec $S = \tilde{O}(N^{1/3})$.

3.2 Diffie-Hellman Décisionnel (DDH) et sqDDH

• Résultat : Des bornes similaires sont dérivées pour DDH et sqDDH. Pour sqDDH, la borne est précise et correspond à une variante non adaptative simple de l'algorithme adaptatif. Pour DDH, les auteurs conjecturent que la borne n'est pas serrée et proposent que la borne optimale soit $1/2 + \tilde{O}(T^2/N + ST/N)$.
• Implication : Le prétraitement non adaptatif n'offre pas les mêmes améliorations de compromis que le prétraitement adaptatif pour ces problèmes décisionnels.

3.3 Système de chiffrement Even-Mansour (EM)

• Résultat : Pour les attaques de récupération de clé sur le chiffrement Even-Mansour, un prétraitement illimité n'accélère pas les attaques non adaptatives (sauf si $S \ge \tilde{\Omega}(\sqrt{N})$).
• Implication : Cela contraste radicalement avec les attaques adaptatives (par exemple, Fouque, Joux et Mavromati [FJM14]) qui peuvent atteindre une complexité en ligne $T = \tilde{O}(2^{n/3})$ avec $S = \tilde{O}(2^{n/3})$. La borne inférieure non adaptative confirme que la réduction de mémoire dans les attaques adaptatives repose fondamentalement sur l'adaptativité.

4. Importance et limites

Importance

• Justification formelle de l'adaptativité : L'article fournit la première preuve formelle que l'adaptativité est essentielle pour atteindre une complexité temporelle inférieure à $\sqrt{N}$ pour DLOG et inférieure à $2^{n/3}$ pour la récupération de clé Even-Mansour dans le modèle de prétraitement.
• Nouvel outil technique : L'application d'une inégalité de type Shearer pour les permutations (Théorème 1.8) dans un contexte algorithmique est une contribution novatrice. Les auteurs notent qu'il s'agit de la première fois qu'une telle variante est utilisée pour des arguments de bornes inférieures dans ce domaine.
• Modèle unifié : Le modèle du Défi de Permutation abstrait avec succès un large éventail de problèmes de recherche et de décision, permettant une analyse collective de leurs compromis temps-espace non adaptatifs.

Limites et problèmes ouverts

• Requêtes dépendantes du défi : La stratégie de preuve repose sur l'indépendance des requêtes pré-traduites par rapport au défi. Étendre ces résultats pour permettre des requêtes pré-traduites dépendant du défi (par exemple, $f(d + f(d))$) nécessiterait de nouvelles inégalités de concentration, car les bornes de type Shearer actuelles ne traitent pas efficacement de telles entrées composées.
• Rounds adaptatifs : L'article laisse ouvert le problème de la caractérisation des compromis temps-espace pour les algorithmes adaptatifs avec un nombre spécifique de rounds d'adaptativité $r$. Les auteurs conjecturent une borne de $\tilde{O}(T^2/N + rST/N)$.
• Précision de DDH : La borne inférieure pour DDH non adaptatif est conjecturée comme étant lâche, les auteurs suggérant que la vraie borne pourrait être plus serrée que celle prouvée.

L'article conclut que les techniques génériques précédentes (arguments de compression, pré-échantillonnage, inégalités de concentration standard) sont intrinsèquement limitées dans leur capacité à distinguer entre les algorithmes adaptatifs et non adaptatifs, améliorant les bornes adaptatives d'au plus des facteurs polylogarithmiques. La nouvelle approche informationnelle présentée ici surmonte cette barrière pour la classe spécifique d'algorithmes non adaptatifs analysée.