Cryptographie à base de couplages

La cryptographie à base de couplages désigne une branche de la cryptographie qui s'intéresse aux constructions utilisant les accouplements ou couplages. Un couplage est une application bilinéaire non dégénérée, c'est-à-dire qui n'est pas identiquement nulle. L'utilisation de ces objets permet de débloquer des constructions que l'on ne sait pas faire en utilisant uniquement un groupe vérifiant des propriétés cryptographiques, comme l'hypothèse décisionnelle de Diffie-Hellman. Par exemple, le chiffrement par attributs.

L'utilisation des couplages en cryptographie a été popularisé par Antoine Joux en 2002.

Définition

Un couplage est une application $e:G_{1}\times G_{2}\to G_{T}$, qui est bilinéaire, c'est-à-dire qui vérifie pour tout entiers $(a,b)\in \mathbb {Z} ^{2}$ et tous éléments de groupes $(g,h)\in G_{1},G_{2}$ l'égalité $e(g^{a},h^{b})=e(g,h)^{ab}$. De plus le couplage ne doit pas être dégénéré, c'est-à-dire que $e(g,h)=1\iff g=1$ ou $h=1$. Finalement, comme on souhaite utiliser cette primitive en cryptographie, on souhaite finalement que le calcul de la fonction $e$ puisse être évalué par un algorithme fonctionnant en temps polynomial.

Catégorisation

On distingue principalement deux grandes familles de couplages: les couplage symétriques, lorsque les deux groupes sources sont les mêmes : $G_{1}=G_{2}$, et les couplages asymétriques lorsqu'ils sont différents.

Usuellement, les cryptographes distinguent de plus les couplages asymétriques forts, où il est difficile d’établir un homomorphisme entre $G_{1}$ et $G_{2}$, et faibles dans le cas contraire. Cette taxonomie est résumée en trois types :

• Type 1 : les couplages symétriques, $G_{1}=G_{2}$ ;
• Type 2 : les couplages asymétriques faibles, lorsqu'il existe un homomorphisme calculable en temps polynomial $\varphi :G_{2}\to G_{1}$ ;
• Type 3 : les couplages asymétriques forts, lorsqu'on ne connaît pas un tel homomorphisme entre $G_{1}$ et $G_{2}$.

Utilisation en cryptographie

Les couplages sont associés à des hypothèses de sécurité, comme une généralisation de l'hypothèse décisionnelle de Diffie-Hellman dans les groupes d'origine $G_{1}$ et $G_{2}$, appelé « Hypothèse de Diffie-Hellman symétrique externe » (SXDH en anglais).

À l'heure actuelle, ces hypothèses servent de base pour construire des cryptosystèmes, comme le chiffrement fondé sur l'identité de Boneh et Franklin.

Exemple : échange de clefs tripartite

Le protocole d’échange de clefs Diffie-Hellman permet à deux utilisateurs de s’entendre sur une clef privée qui reste secrète aux yeux d’un observateur extérieur et qui pourra ensuite être utilisée pour commencer un échange secret. La sécurité de cette primitive repose sur la sécurité de l'hypothèse calculatoire de Diffie-Hellman. Le principe est le suivant : Alice souhaite échanger une clef secrète avec Bob. Pour cela ils commencent tous les deux par générer un entier $a$ pour Alice et $b$ pour Bob. Alice calcule ensuite $A=g^{a}$ et Bob de son côté calcule $B=g^{b}$. Ces deux valeurs sont ensuite échangées entre les deux partis. Ainsi Alice peut calculer $g^{ab}=B^{a}$ et Bob peut calculer $g^{ab}=A^{b}$ ; mais un observateur qui ne dispose ni de $a$ ni de $b$ ne peut déterminer $g^{ab}$, auquel cas il résout l'hypothèse calculatoire de Diffie-Hellman. Ainsi $g^{ab}$ consistue la clef secrète partagée par Alice et Bob.

Ce protocole peut être étendu à trois utilisateurs en un seul tour à l'aide d'un couplage symétrique. En effet, si Alice partage $A=g^{a}\in \mathbb {G}$, Bob partage $B=g^{b}$ et Charles partage $C=g^{c}$ pour un entier aléatoire et secret $c$, alors Alice peut calculer ${\mathsf {sk}}=e(g,g)^{abc}=e(g^{b},g^{c})^{a}=e(B,C)^{a}$, Bob peut calculer $e(g,g)^{abc}=e(A,C)^{b}$ et Charles peut finalement calculer la même valeur $e(g,g)^{abc}=e(A,B)^{c}$.

Notes et références

Notes

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

Annexes

Articles connexes

• Schéma fondé sur l'identité

Bibliographie

• [Boneh et Franklin 2001] (en) Dan Boneh et Matthew Franklin, « Identity-Based Encryption from the Weil Pairing », Crypto, Springer,‎ 2001 (lire en ligne)
• [Ballard et al. 2005] Lucas Ballard, Matthew Green, Breno de Medeiros et Fabian Monrose, « Correlation-Resistant Storage via Keyword-Searchable Encryption », ePrint Report,‎ 2005 (lire en ligne)
• [Galbraith, Patterson et Smart 2006] Steven Galbraith, Kenneth Patterson et Nigel Smart, « Pairings for Cryptographers », ePrint Reports,‎ 2006 (lire en ligne)
• [Joux 2002] Antoine Joux, « The Weil and Tate pairings as building blocks for public key cryptosystems », ANTS, Springer,‎ 2002, p. 20−32