Cryptosystème de Cramer-Shoup

Pour les articles homonymes, voir Cramer.

En cryptologie, le cryptosystème de Cramer-Shoup est un chiffrement à clé publique introduit en 1998 par les cryptologues Ronald Cramer et Victor Shoup^[1],[2],[3]. 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^[1],[3]. Ces propriétés et d'autres le rendent particulièrement attrayant pour construire des mécanismes d'encapsulation de clés^[4],[5].

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

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^[3]. La première preuve que de tels cryptosystèmes existent pourtant est due à Dolev, Dwork et Naor^[9].

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^[10].

Le cryptosystème de Cramer-Shoup repose sur trois algorithmes ${\displaystyle (G,E,D)}$ décrits ici^{[1],[note 1],[11]}.

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

L'algorithme donne deux générateurs aléatoires ${\displaystyle g_{1},g_{2}}$ de ${\displaystyle \mathbb {G} }$ et tire six exposants aléatoires ${\displaystyle x_{1},x_{2},y_{1},y_{2},z_{1},z_{2}\in \mathbb {Z} /(q)}$. Il calcule alors :

$${\displaystyle 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 ${\displaystyle {\mathsf {pk}}=\{c,d,h\}}$, des paramètres publics ${\displaystyle {\mathsf {pp}}=\{\lambda ,\mathbb {G} ,g_{1},g_{2},q,H\}}$, et la clé privée ${\displaystyle {\mathsf {sk}}=\{x_{1},x_{2},y_{1},y_{2},z_{1},z_{2}\}}$.

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

$${\displaystyle 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 ${\displaystyle {\mathsf {ct}}=\{u_{1},u_{2},e,v\}\in \mathbb {G} ^{4}}$.

L'algorithme de déchiffrement ${\displaystyle D}$ prend en entrée les paramètres publics, la clé privée, et un chiffré ${\displaystyle {\mathsf {ct}}=\{u_{1},u_{2},e,v\}\in \mathbb {G} ^{4}}$. Il calcule ${\displaystyle \alpha \gets H(u_{1},u_{2},e)}$ et vérifie ${\displaystyle 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 (${\displaystyle \bot }$). Sinon, il renvoie ${\displaystyle m\gets eu_{1}^{-z_{1}}u_{2}^{-z_{2}}}$.

Le cryptosystème de Cramer-Shoup est résistant aux attaques adaptatives à chiffrés choisis (IND-CCA2) lorsque la fonction ${\displaystyle H}$ est choisie dans une famille de fonctions de hachage universelles à sens unique^{[12],[note 2]} par réduction, dans le modèle standard, à la difficulté du problème décisionnel de Diffie-Hellman dans ${\displaystyle \mathbb {G} }$^{[1],[note 3]}.

• [Bellare et al. 1998] (en) Mihir Bellare, Anand Desai, David Pointcheval et Phillip Rogaway, « Relations among notions of security for public-key encryption schemes », dans Advances in Cryptology — CRYPTO '98, Springer Berlin Heidelberg, 1998 (ISBN 9783540648925, DOI 10.1007/bfb0055718, lire en ligne), p. 26-45 ;
• [Bleichenbacher 1998] (en) Daniel Bleichenbacher, « Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 », dans Advances in Cryptology — CRYPTO '98, Springer Berlin Heidelberg, 1998 (ISBN 9783540648925, DOI 10.1007/bfb0055716, lire en ligne), p. 1-12 ;
• [Boneh 2011] (en) Dan Boneh, « Cramer–Shoup Public-Key System », dans Encyclopedia of Cryptography and Security, Springer US, 2011 (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_144, lire en ligne), p. 269–270 ;
• [Boneh et Shoup 2017] (en) Dan Boneh et Victor Shoup, « A Graduate Course in Applied Cryptography », sur crypto.stanford.edu, 2017 (consulté le 1^er septembre 2018) ;
• [Cramer et Shoup 1998] (en) Ronald Cramer et Victor Shoup, « A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack », dans Advances in Cryptology — CRYPTO '98, Springer Berlin Heidelberg, 1998 (ISBN 9783540648925, DOI 10.1007/bfb0055717, lire en ligne), p. 13-25 ;
• [Cramer et Shoup 2002] (en) Ronald Cramer et Victor Shoup, « Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption », dans Advances in Cryptology — EUROCRYPT 2002, Springer Berlin Heidelberg, 2002 (ISBN 9783540435532, DOI 10.1007/3-540-46035-7_4, lire en ligne), p. 45-64 ;
• [Dent 2006] (en) Alexander W. Dent, « The Cramer-Shoup Encryption Scheme Is Plaintext Aware in the Standard Model », dans Advances in Cryptology - EUROCRYPT 2006, Springer Berlin Heidelberg, 2006 (ISBN 9783540345466, DOI 10.1007/11761679_18, lire en ligne), p. 289-307 ;
• [Dolev, Dwork et Naor 2003] (en) Danny Dolev, Cynthia Dwork et Moni Naor, « Nonmalleable Cryptography », SIAM Review, vol. 45, n^o 4,‎ janvier 2003, p. 727-784 (ISSN 0036-1445 et 1095-7200, DOI 10.1137/s0036144503429856, lire en ligne, consulté le 1^er septembre 2018) ;
• [Naor et Yung 1989] (en) Mori Naor et Moti Yung, « Universal one-way hash functions and their cryptographic applications », STOC '89 Proceedings of the twenty-first annual ACM symposium on Theory of computing, ACM,‎ 1^er février 1989, p. 33-43 (ISBN 0897913078, DOI 10.1145/73007.73011, lire en ligne, consulté le 1^er septembre 2018) ;
• [Rackoff et Simon 1991] (en) Charles Rackoff et Daniel R. Simon, « Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack », dans Advances in Cryptology — CRYPTO ’91, Springer Berlin Heidelberg, 11 août 1991 (ISBN 9783540551881, DOI 10.1007/3-540-46766-1_35, lire en ligne), p. 433-444 ;
• [Shacham 2007] (en) Hovav Shacham, « A Cramer-Shoup Encryption Scheme from the Linear Assumption and from Progressively Weaker Linear Variants », sur eprint.iacr.org, 2007 (consulté le 1^er septembre 2018) ;
• [Teranishi et Ogata 2008] (en) Isamu Teranishi et Wakaha Ogata, « Cramer-Shoup Satisfies a Stronger Plaintext Awareness under a Weaker Assumption », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2008 (ISBN 9783540858546, DOI 10.1007/978-3-540-85855-3_8, lire en ligne), p. 109-125.

• Portail de la cryptologie