Argument hybride

Un argument hybride est une méthode de preuve en cryptographie permettant de montrer l'indistinguabilité calculatoire de deux distributions de probabilité.

Motivation

Pour montrer que deux distributions $D_{0}$ et $D_{1}$ sont calculatoirement indistinguables, la stratégie habituelle est d'exhiber une réduction d'un problème difficile à la sécurité du cryptosystème. Néanmoins, cette méthode n'est pas toujours facilement utilisable, et il existe des cas où il est plus facile d'exhiber une succession de distributions $H_{0},\ldots ,H_{n}$ telle que $D_{0}=H_{0}$ et $H_{n}=D_{1}$ . Ainsi, en montrant que, pour tout $0\leq i<n$ , $H_{i}$ est calculatoirement indistinguable de $H_{i+1}$ (une preuve qui a pu être faite par le biais d'une réduction par exemple), on obtient que $D_{0}$ et $D_{1}$ sont calculatoirement indistinguables: c'est une conséquence de l'inégalité triangulaire.

En effet, pour tout adversaire efficace (qui fonctionne en temps polynomial probabiliste) ${\mathcal {A}}$ , l'avantage de ${\mathcal {A}}$ pour distinguer deux distributions $D$ et $D'$ peut être défini par :

\displaystyle \mathrm {Advt} ^{D,D'}({\mathcal {A}})=\left|\Pr _{x\hookleftarrow D}[{\mathcal {A}}(x)=1]-\Pr _{x\hookleftarrow D'}[{\mathcal {A}}(x)=1]\right|.

Ainsi, dans notre cas, l'application de l'inégalité triangulaire nous donne :

\displaystyle \mathrm {Advt} ^{D_{0},D_{1}}({\mathcal {A}})\leq \sum _{i=0}^{n-1}\mathrm {Advt} ^{H_{i},H_{i+1}}({\mathcal {A}}).

Comme $H_{i}$ et $H_{i+1}$ sont calculatoirement indistinguables pour tout $i$ , $\mathrm {Advt} ^{H_{i},H_{i+1}}({\mathcal {A}})$ est négligeable pour tout $i$ et donc $\mathrm {Advt} ^{D_{0},D_{1}}({\mathcal {A}})$ est négligeable. Cependant, cet argument n'est valable que lorsque $n$ est fixé et borné : si un nombre polynomial de distributions intermédiaires est nécessaire, l'inégalité triangulaire ne permet plus de conclure. En effet, une somme polynomiale de fonctions négligeables n'est pas nécessairement négligeable. Par exemple, si on prend $\mu _{i}(\lambda )=2^{i-\lambda }$ pour tout $i$ , alors chaque $\mu _{i}$ est négligeable en $\lambda$ et pourtant $\sum _{i=1}^{\lambda }\mu _{i}$ n'est pas négligeable. Pour cette raison, on utilise à la place un argument hybride.

Énoncé

Soient deux distributions $X$ et $Y$ qui sont calculatoirement indistinguables, et soient deux distributions $D_{0}$ et $D_{1}$ . Pour fixer les idées, $D_{0}$ peut être une distribution sur des suites arbitrairement longues de la forme $(X,X,X,\ldots )$ tandis que $D_{1}$ serait une distribution sur des suites de la forme $(Y,Y,Y,\ldots )$ . Pour montrer que les deux distributions sont calculatoirement indistinguables, l'idée est d'introduire une suite de distributions hybrides $(H_{i})_{i\in \mathbb {N} }$ telle que $H_{0}=D_{1}$ (dans notre exemple, $H_{i}$ serait une distribution sur des suites obtenue en faisant $i$ copies de $X$ puis des copies de $Y$ ), qui permet de transformer petit à petit la distribution $D_{1}$ en la distribution $D_{0}$ . Ainsi, pour tout adversaire polynomial ${\mathcal {A}}$ , on demande à ce qu'il existe un entier $n_{\mathcal {A}}$ au plus polynomial tel que $\mathrm {Advt} ^{H_{n_{\mathcal {A}}},D_{0}}({\mathcal {A}})=0$ . Dans notre exemple, cela vient du fait que ${\mathcal {A}}$ ne peut lire que les $n_{\mathcal {A}}$ premiers éléments de la suite. Dans ce contexte, l'argument hybride permet de conclure. Il s'énonce comme suit ^[1]:

Argument hybride — Soient deux distributions calculatoirement indistinguables $X$ et $Y$ et soit $(H_{i})_{i\in \mathbb {N} }$ une suite de distributions. Supposons qu'il existe un algorithme probabilistique polynomial ${\mathcal {T}}$ tel que, pour tout $i$ , les distributions ${\mathcal {T}}(i,X)$ et $H_{i}$ (respectivement, ${\mathcal {T}}(i,Y)$ et $H_{i+1}$ ) sont identiquement distribuées. Alors, pour tout adversaire efficace ${\mathcal {A}}$ , pour tout polynôme $p$ , il existe un adversaire probabilistique polynomial ${\mathcal {B}}$ tel que $\displaystyle \mathrm {Advt} ^{H_{0},H_{p(\lambda )}}({\mathcal {A}})\leq p(\lambda )\mathrm {Advt} ^{X,Y}({\mathcal {B}}).$

Utilisations

Il existe des exemples de l'utilisation de l'argument hybride en cryptographie ^[2], généralement présenté sous forme de preuves par jeux. On peut citer parmi celles-ci les preuves simples suivantes :

Si un générateur de bits est imprédictible, alors il s'agit d'un générateur pseudo-aléatoire ^[3].
On peut étendre un générateur pseudo-aléatoire $G:\{0,1\}^{s}\to \{0,1\}^{s+1}$ pour construire un générateur pseudo-aléatoire dont la sortie est polynomialement plus grande que l'entrée ^[4].

Prédicteur à partir d'un distingueur pour un générateur pseudo-aléatoire

La sécurité d'un générateur pseudo-aléatoire est donnée par l'indistinguabilité de la distribution « $G\triangleq G(x)\in \{0,1\}^{n}:x\hookleftarrow {\mathcal {U}}(\{0,1\}^{s})$ » de la distribution uniforme sur les chaînes de longueur $n$ ^[5]. Une définition alternative est donnée par l'imprédictabilité du bit suivant, c'est-à-dire qu'il n'existe pas d'algorithme efficace permettant de prédire $G(x)_{i}$ sachant $G(x)_{<i}$ ^{[note 1]} avec une probabilité significativement différente de 1/2.

Andrew Yao a montré en 1982 que ces deux définitions sont équivalentes ^[3], on donne dans la suite une preuve de l'implication qui fait intervenir l'argument hybride.

Démonstration

Ainsi si les bits de $G(x)$ sont indistinguables de l'uniforme, alors il ne peut exister de prédicteur. Cela se fait par la construction de distributions hybrides, en posant les distributions hybrides $H_{i}=G(x)_{<n-i}\|{\mathcal {U}}(\{0,1\}^{i})$ , qui est telle que $H_{0}=G$ et $H_{n}={\mathcal {U}}(\{0,1\}^{n})$ .

L'argument hybride donne donc l'existence d'un indice $k^{\star }$ tel que

\displaystyle \mathrm {Advt} ^{H_{k^{\star }},H_{k^{\star }+1}}({\mathcal {A}})\geq {\frac {\mathrm {Advt} ^{G,{\mathcal {U}}(\{0,1\}^{n})}({\mathcal {A}})}{n}}

Par conséquent, un distingueur entre la distribution $G$ et la distribution uniforme sur les chaînes de bits de longueur n est aussi un distingueur entre les distributions $H_{k}$ et $H_{k+1}$ .

On construit ensuite le prédicteur suivant qui utilise de manière boîte noire un distingueur entre les distributions $G$ et la distribution uniforme sur n bits:

${\begin{array}{c c c c c}{\mbox{Distingueur }}(G,U)=D&&{\mbox{Predicteur de bit}}=P&&{\mbox{Challenger}}\\\hline &&{\text{Tire }}k\hookleftarrow {\mathcal {U}}(\{0,1,\ldots ,n-1\})&&{\text{Tire }}x\hookleftarrow {\mathcal {U}}(\{0,1\}^{s})\\&&&{\xrightarrow {k}}&\\&&&{\xleftarrow {G(x)_{<k+1}}}&\\&&{\text{Construit }}y=G(x)_{<k+1}\|{\mathcal {U}}(\{0,1\}^{n-k})&&\\&{\xleftarrow {y}}&&&\\&{\xrightarrow {b}}&&&\\&&{\text{Si }}b=1{\text{, alors on a probablement envoye }}H_{k+1}.&&\\&&{\text{On assigne }}p=y_{k+1}&&\\&&{\text{Si }}b=0{\text{, ça signifie qu'on a probablement envoye }}H_{k}.&&\\&&{\text{On assigne }}p=1-y_{k+1}&&\\&&&{\xrightarrow {p}}&\end{array}}$

Il ne reste plus qu'à calculer la probabilité pour notre prédicteur d'avoir donné le bon bit.

\displaystyle {\begin{aligned}\Pr _{x\in {\mathcal {U}}(\{0,1\}^{s})}[P(G(x)_{<k+1})=G(x)_{k+1}]&=\Pr[P(y)=y_{k+1}\land G(x)_{k+1}=y_{k+1}]+\Pr[P(y)=1-y_{k+1}\land G(x)_{k+1}=1-y_{k+1}]\\&=\Pr[G(x)_{k+1}=y_{k+1}]\cdot \Pr[P(y)=y_{k+1}\mid G(x)_{k+1}=y_{k+1}]+\Pr[G(x)_{k+1}=1-y_{k+1}]\cdot \Pr[P(y)=1-y_{k+1}\mid G(x)_{k+1}=1-y_{k+1}]\\&=\Pr[G(x)_{k+1}=y_{k+1}]\cdot \Pr[D(y)=1\mid G(x)_{k+1}=y_{k+1}]+\Pr[G(x)_{k+1}=1-y_{k+1}]\cdot \Pr[D(y)=0\mid G(x)_{k+1}=1-y_{k+1}]\\&={\frac {1}{2}}\cdot \left(\Pr[D(y)=1\mid G(x)_{k+1}=y_{k+1}]+\Pr[D(y)=0\mid G(x)_{k+1}=1-y_{k+1}]\right)\\&={\frac {1}{2}}\cdot \left(1+\Pr[D(y)=1\mid G(x)_{k+1}=y_{k+1}]-\Pr[D(y)=1\mid G(x)_{k+1}=1-y_{k+1}]\right)\\&\geq {\frac {1}{2}}\pm \mathrm {Advt} ^{H_{k^{\star }},H_{k^{\star }+1}}(A)\cdot \Pr[k=k^{\star }]\end{aligned}}

Ce qui donne une borne inférieure sur la distance de cette probabilité comme ${\frac {1}{2}}$ par ${\frac {\mathrm {Advt} ^{G,U(\{0,1\}^{n})}}{n^{2}}}$ , qui est non négligeable si le distingueur a un avantage significatif.

Notes et références

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Hybrid argument » (voir la liste des auteurs).

↑ Les i premiers bits de la chaîne G(x).

Annexes

Bibliographie

[Goldreich, Goldwasser et Micali 1984] (en) Oded Goldreich, Shafi Goldwasser et Silvio Micali, « How to Construct Random Functions », FOCS,‎ 1984 (DOI 10.1109/SFCS.1984.715949).
[Katz et Lindell 2014] (en) Jonathan Katz et Yehuda Lindell, Introduction to Modern Cryptography, 2nd Edition, Boca Raton, Chapman and Hall, 2014, 583 p. (ISBN 978-1-4665-7026-9, BNF 44284474), « Constructions of Pseudorandom Generators ».
[Shoup 2004] (en) Victor Shoup, « Sequences of games: a tool for taming complexity in security proofs », ePrint Reports,‎ 2004 (lire en ligne).
[Yao 1982] (en) Andrew Yao, « Theory and application of trapdoor functions », FOCS,‎ 1982 (DOI 10.1109/SFCS.1982.45, lire en ligne [PDF], consulté le 24 février 2017).
[MF21] (en) Arno Mittelbach et Marc Fischlin, The Theory of Hash Functions and Random Oracles, An Approach to Modern Cryptography, Springer, 2021, 798 p. (ISBN 978-3-0306-3287-8), « Pseudorandomness and Computational Indistinguishability ».