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 $(G,E,D)$ décrits ici^[1]^,^{[note 1]}^,^[11].

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^[12]^,^{[note 2]} par réduction, dans le modèle standard, à la difficulté du problème décisionnel de Diffie-Hellman dans $\mathbb {G}$ ^[1]^,^{[note 3]}.

Notes et références

Notes

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

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

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

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

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

[CramerShoup1998-1] 1 2 3 4 Cramer et Shoup 1998.

[CramerShoup2002-2] Cramer et Shoup 2002.

[Boneh2011-3] 1 2 3 Boneh 2011.

[Dent2006-4] 1 2 Dent 2006.

[TeranishiOgata2008-5] Teranishi et Ogata 2008.

[RackoffSimon1991-6] Rackoff et Simon 1991.

[BellareDesaiPointchevalRogaway1998-7] 1 2 Bellare et al. 1998.

[Bleichenbacher1998-8] Bleichenbacher 1998.

[DolevDworkNaor2003-9] Dolev, Dwork et Naor 2003.

[Shacham2007-10] Shacham 2007.

[BonehShoup2017-12] Boneh et Shoup 2017.

[NaorYung1989-13] Naor et Yung 1989.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[note 1]

[11]

[12]

[note 2]

[note 3]