Cryptosystème de Cramer-Shoup

Modèle:Voir homonymes En cryptologie, le cryptosystème de Cramer-Shoup est un chiffrement à clé publique introduit en 1998 par les cryptologues Ronald Cramer et Victor ShoupModèle:SfnModèle:,Modèle:SfnModèle:,Modèle:Sfn. Historiquement, il s'agit du premier cryptosystème combinant les trois propriétés suivantes : il est résistant aux attaques adaptatives à chiffrés choisis (IND-CCA2), il est prouvé sûr dans le modèle standard, et il est efficaceModèle:SfnModèle:,Modèle:Sfn. Ces propriétés et d'autres le rendent particulièrement attrayant pour construire des mécanismes d'encapsulation de clésModèle:SfnModèle:,Modèle:Sfn.

Histoire et motivation

La résistance aux attaques adaptatives à chiffrés choisis (IND-CCA2), introduite par Rackoff et Simon en 1991Modèle:Sfn, correspond au plus haut niveau de sécurité atteignable par un cryptosystème pour le chiffrementModèle:Sfn. La nécessité pratique d'une telle sécurité a été mise en avant par Bleichenbacher en 1998Modèle:Sfn.

Plusieurs constructions IND-CCA2 ont été proposées dans le modèle de l'oracle aléatoire, notamment OAEP. Par ailleurs, des transformations génériques permettent d'atteindre ce niveau de sécurité, mais ils reposent sur des preuves à divulgation nulle de connaissance et s'avèrent très inefficaces. Jusqu'à l'introduction du cryptosystème de Cramer-Shoup, aucun chiffrement IND-CCA2 efficace n'était connu, dont la sécurité pouvait être prouvée dans le modèle standardModèle:Sfn. La première preuve que de tels cryptosystèmes existent pourtant est due à Dolev, Dwork et NaorModèle:Sfn.

Le cryptosystème de Cramer-Shoup est une extension de celui d'ElGamal qui bloque la malléabilité du chiffré. Le prix à payer est que les clés et les chiffrés sont beaucoup plus larges que pour ElGamal (4 éléments de groupe pour le chiffré). De nombreuses variantes de Cramer-Shoup proposées depuis cherchent à réduire ce phénomène, quitte à réintroduire des hypothèses hors du modèle standardModèle:Sfn.

Description du cryptosystème

Le cryptosystème de Cramer-Shoup repose sur trois algorithmes $(G,E,D)$ décrits iciModèle:SfnModèle:,Modèle:NoteModèle:,Modèle:Sfn.

Génération de clé

L'algorithme de « génération de clé » $G$ prend en entrée un paramètre de sécurité $\lambda$. Il détermine un groupe cyclique $𝔾$ d'ordre $q$ et une fonction $H:{𝔾}^3\to \mathbb{Z}/(q)$. Le choix de $q$ et de la fonction $H$ dépend de $\lambda$ et se fait à partir de l'analyse de sécurité, voir plus bas.

L'algorithme donne deux générateurs aléatoires $g_1,g_2$ de $𝔾$ et tire six exposants aléatoires $x_1,x_2,y_1,y_2,z_1,z_2\in \mathbb{Z}/(q)$. Il calcule alors :

$$c\leftarrow g_1^{x_1}{g}_2^{x_2},d\leftarrow g_1^{y_1}{g}_2^{y_2},\text{et}h\leftarrow g_1^{z_1}{g}_2^{z_2}$$

Finalement l'algorithme retourne une clé publique $𝗉𝗄=\{c,d,h\}$, des paramètres publics $𝗉𝗉=\{\lambda ,𝔾,g_1,g_2,q,H\}$, et la clé privée $𝗌𝗄=\{x_1,x_2,y_1,y_2,z_1,z_2\}$.

Chiffrement

L'algorithme de chiffrement $E$ prend en entrée les paramètres publics, la clé publique, et un message $m\in 𝔾$. Un exposant $r\in \mathbb{Z}/(q)$ est choisi uniformément au hasard, puis l'algorithme calcule :

$$u_1\leftarrow g_1^r,u_2\leftarrow g_2^r,e\leftarrow m{h}^r,\alpha \leftarrow H(u_1,u_2,e)\text{et}v\leftarrow (c{d}^{\alpha }{)}^r$$

Le chiffré correspondant est $𝖼𝗍=\{u_1,u_2,e,v\}\in {𝔾}^4$.

Déchiffrement

L'algorithme de déchiffrement $D$ prend en entrée les paramètres publics, la clé privée, et un chiffré $𝖼𝗍=\{u_1,u_2,e,v\}\in {𝔾}^4$. Il calcule $\alpha \leftarrow H(u_1,u_2,e)$ et vérifie $u_1^{x_1+\alpha y_1}\cdot u_2^{x_2+\alpha y_2}\stackrel{?}{=}v$. Si l'égalité est fausse, l'algorithme de déchiffrement échoue et renvoie un symbole d'erreur ($\mathrm{\perp }$). Sinon, il renvoie $m\leftarrow e{u}_1^{-z_1}{u}_2^{-z_2}$.

Sécurité

Le cryptosystème de Cramer-Shoup est résistant aux attaques adaptatives à chiffrés choisis (IND-CCA2) lorsque la fonction $H$ est choisie dans une famille de fonctions de hachage universelles à sens uniqueModèle:SfnModèle:,Modèle:Note par réduction, dans le modèle standard, à la difficulté du problème décisionnel de Diffie-Hellman dans $𝔾$Modèle:SfnModèle:,Modèle:Note.

Annexes

Bibliographie

• Modèle:Chapitre ;
• Modèle:Chapitre ;
• Modèle:Chapitre ;
• Modèle:Lien web ;
• Modèle:Chapitre ;
• Modèle:Chapitre ;
• Modèle:Chapitre ;
• Modèle:Article ;
• Modèle:Article ;
• Modèle:Chapitre ;
• Modèle:Lien web ;
• Modèle:Chapitre.