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

Histoire et motivation

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].

Description du cryptosystème

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

Génération de clé

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}\}}$.

Chiffrement

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}}$.

Déchiffrement

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}}}$.

Sécurité

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]}.

Notes et références

Notes

1. Il existe plusieurs présentations équivalentes, et plusieurs variantes non équivalentes, du cryptosystème. Pour des alternatives (simplifiées ou étendues) voir Boneh et Shoup 2017, chap 12.5.
2. Une fonction de hachage résistante aux collisions est a fortiori universelle à sens unique et peut donc être utilisée pour instancier ce cryptosystème.
3. La preuve originelle de Cramer et Shoup opère par réduction directe d'un adversaire CCA2 au problème DDH. Une preuve alternative consiste à montrer la sécurité sémantique et la simulabilité^[4], qui ensemble impliquent IND-CCA2^[7].

Références

1. Cramer et Shoup 1998.
2. Cramer et Shoup 2002.
3. Boneh 2011.
4. Dent 2006.
5. Teranishi et Ogata 2008.
6. Rackoff et Simon 1991.
7. Bellare et al. 1998.
8. Bleichenbacher 1998.
9. Dolev, Dwork et Naor 2003.
10. Shacham 2007.
11. Boneh et Shoup 2017.
12. Naor et Yung 1989.

Annexes

Bibliographie

• [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