Avantage (cryptologie)

En cryptologie, la notion d'avantage mesure la capacité d'un adversaire à distinguer entre un objet cryptographique réel et un modèle idéalisé (ou plus généralement, entre deux situations). Essentiellement, l'avantage mesure à quel point l'adversaire fait « mieux que le hasard » dans cet exercice. La notion a été introduite en 1982 par les cryptologues Shafi Goldwasser et Silvio Micali pour définir formellement la sécurité sémantique du chiffrement à clé publique.

L'avantage dépend du jeu de sécurité considéré, des pouvoirs de l'adversaire (généralement formalisés au moyen d'oracles), de la classe d'adversaires étudiée et éventuellement d'autres paramètres. En règle générale, on cherche à prouver que l'avantage est une fonction négligeable du paramètre de sécurité, ce qui garantit que l'objet cryptographique réel et son modèle idéalisé ne peuvent pas être distingués par un attaquant.

Plusieurs techniques classiques permettent d'obtenir une borne sur l'avantage dans un jeu donné, comme les arguments hybrides ou les coefficients H.

Définition

Soit ${\mathcal {A}}$ une classe d'adversaires. Pour tout $A\in {\mathcal {A}}$, on note $A^{O_{1},O_{2},\dotsc }$ l'adversaire doté d'un accès aux oracles $O_{1},O_{2},\dotsc$.

On donne en plus à l'adversaire accès soit à (un oracle de) la véritable fonction cryptographique d'intérêt, soit à (un oracle de) la version idéalisée de celle-ci. L'objectif de l'adversaire est de distinguer entre ces deux situations, et de retourner 1 dans le premier cas et 0 dans le second. On définit alors l'avantage :

$${\mathsf {Adv}}({\mathcal {A}})=\max _{A\in {\mathcal {A}}}\left|\Pr \left[A^{O_{1},\dotsc }(F)=1\right]-\Pr \left[A^{O_{1},\dotsc }(F_{\mathrm {id} })=1\right]\right|$$

où $F$ (resp. $F_{\mathrm {id} }$) est la fonction réelle (resp. idéale) considérée. Alternativement, on peut définir l'avantage en termes de distributions (ou de jeux) :

$${\mathsf {Adv}}({\mathcal {A}})=\max _{A\in {\mathcal {A}}}\left|\Pr _{x\sim D}\left[A^{O_{1},\dotsc }(x)=1\right]-\Pr _{x\sim D'}\left[A^{O_{1},\dotsc }(x)=1\right]\right|$$

où cette fois on mesure la capacité de l'adversaire à distinguer entre une variable distribuée selon une loi D et une variable distribuée selon une loi D'.

La définition peut être ajustée en précisant les oracles ou les conditions de succès, afin de se spécialiser aux différents objets pseudo-aléatoires (PRNG, PRF, PRP...), donnant les notions de sécurité correspondante (sécurité sémantique etc.). Dans le cas général l'avantage dépend du nombre de requêtes effectuées auprès des oracles, $q_{1},q_{2},\dotsc$.

Exemples

Tirage biaisé

Considérons une pièce de monnaie, assimilée à une variable aléatoire suivant une loi de Bernoulli de probabilité p. Le modèle idéal correspondant est une variable aléatoire de probabilité 1/2, et l'avantage adversarial dans ce contexte est alors ${\mathsf {Adv}}({\mathcal {A}})=|p-1/2|$. Autrement dit, dès lors que $p-1/2$ n'est pas négligeable, un adversaire pourra amplifier l'écart en répétant l'expérience et distinguer s'il a affaire à une pièce réelle ou idéale.

Argument hybride

Dans un argument hybride, on définit une séquence de jeux dans lesquels ont remplace progressivement un objet réel par un modèle idéalisé. Lorsque l'avantage entre deux tels jeux est négligeable, on peut ainsi petit à petit ramener la sécurité d'un système complexe réel à celle d'un système idéal.

Fonction pseudo-aléatoire

On considère une famille de fonctions F prenant en entrée une clé k et une valeur x, et retournant une chaîne y de taille fixée. Le modèle idéal considéré est celui d'une fonction aléatoire g, et l'adversaire doit distinguer entre la fonction aléatoire et une fonction $f\in F$ dont la clé a été tirée uniformément au hasard parmi toutes les clés possibles. Cela correspond à l'avantage :

$${\mathsf {Adv}}_{\mathrm {PRF} }({\mathcal {A}})=\left|\Pr _{k\sim K,x\sim X}[{\mathcal {A}}(f(k,x))=1]-\Pr _{x\in X}[{\mathcal {A}}(g(x))=1]\right|$$

lorsque cet avantage est négligeable, on dit que les fonctions F sont pseudo-aléatoires.

Notes et références