title: Cryptosystème de Cramer-Shoup
text: # Cryptosystème de Cramer-Shoup
  
  En cryptologie, le cryptosystème de Cramer-Shoup est un chiffrement à clé publique introduit en 1998 par les cryptologues Ronald Cramer et Victor $Shoup^,^,.$ 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 $efficace^,.$ Ces propriétés et d'autres le rendent particulièrement attrayant pour construire des mécanismes d'encapsulation de $clés^,.$
  
  ## Histoire et motivation
  
  La résistance aux attaques adaptatives à chiffrés choisis (IND-CCA2), introduite par Rackoff et Simon en 1991, correspond au plus haut niveau de sécurité atteignable par un cryptosystème pour le chiffrement. La nécessité pratique d'une telle sécurité a été mise en avant par Bleichenbacher en 1998.
  
  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 standard. La première preuve que de tels cryptosystèmes existent pourtant est due à Dolev, Dwork et Naor.
  
  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 standard.
  
  ## Description du cryptosystème
  
  Le cryptosystème de Cramer-Shoup repose sur trois algorithmes $(G,E,D)$ décrits $ici^,^,.$
  
  ### 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 $\mathbb {G}$ d'ordre $q$ et une fonction $H:\mathbb {G} ^{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 $\mathbb {G}$ 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\gets g_{1}^{x_{1}}g_{2}^{x_{2}},\quad d\gets g_{1}^{y_{1}}g_{2}^{y_{2}},\quad {\text{et}}\quad h\gets g_{1}^{z_{1}}g_{2}^{z_{2}}$
  
  Finalement l'algorithme retourne une clé publique ${\mathsf {pk}}=\{c,d,h\}$, des paramètres publics ${\mathsf {pp}}=\{\lambda ,\mathbb {G} ,g_{1},g_{2},q,H\}$, et la clé privée ${\mathsf {sk}}=\{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 \mathbb {G}$. Un exposant $r\in \mathbb {Z} /(q)$ est choisi uniformément au hasard, puis l'algorithme calcule :
  
  $u_{1}\gets g_{1}^{r},\quad u_{2}\gets g_{2}^{r},\quad e\gets mh^{r},\quad \alpha \gets H(u_{1},u_{2},e)\quad {\text{et}}\quad v\gets (cd^{\alpha })^{r}$
  
  Le chiffré correspondant est ${\mathsf {ct}}=\{u_{1},u_{2},e,v\}\in \mathbb {G} ^{4}$.
  
  ### Déchiffrement
  
  L'algorithme de déchiffrement $D$ prend en entrée les paramètres publics, la clé privée, et un chiffré ${\mathsf {ct}}=\{u_{1},u_{2},e,v\}\in \mathbb {G} ^{4}$. Il calcule $\alpha \gets 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 ($\bot$). Sinon, il renvoie $m\gets eu_{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 $unique^,$ par réduction, dans le modèle standard, à la difficulté du problème décisionnel de Diffie-Hellman dans $\mathbb {G}$$^,.$
  
  