Cryptosystème de Cramer-Shoup

Cryptosystème prouvé IND-CCA2 dans le modèle standard sous l'hypothèse DDH

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 motivationModifier

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èmeModifier

Le cryptosystème de Cramer-Shoup repose sur trois algorithmes  décrits ici[1],[Note 1],[11].

Génération de cléModifier

L'algorithme de « génération de clé »   prend en entrée un paramètre de sécurité  . Il détermine un groupe cyclique   d'ordre   et une fonction  . Le choix de   et de la fonction   dépend de   et se fait à partir de l'analyse de sécurité, voir plus bas.

L'algorithme donne deux générateurs aléatoires   de   et tire six exposants aléatoires  . Il calcule alors :

 

Finalement l'algorithme retourne une clé publique  , des paramètres publics  , et la clé privée  .

ChiffrementModifier

L'algorithme de chiffrement   prend en entrée les paramètres publics, la clé publique, et un message  . Un exposant   est choisi uniformément au hasard, puis l'algorithme calcule :

 

Le chiffré correspondant est  .

DéchiffrementModifier

L'algorithme de déchiffrement   prend en entrée les paramètres publics, la clé privée, et un chiffré  . Il calcule   et vérifie  . Si l'égalité est fausse, l'algorithme de déchiffrement échoue et renvoie un symbole d'erreur ( ). Sinon, il renvoie  .

SécuritéModifier

Le cryptosystème de Cramer-Shoup est résistant aux attaques adaptatives à chiffrés choisis (IND-CCA2) lorsque la fonction   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  [1],[Note 3].

Notes et référencesModifier

NotesModifier

  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é, voir (Dent 2006), qui ensemble impliquent IND-CCA2, voir (Bellare et coll. 2001).

RéférencesModifier

  1. a b c et d (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, (ISBN 9783540648925, DOI 10.1007/bfb0055717, lire en ligne), p. 13–25
  2. (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, (ISBN 9783540435532, DOI 10.1007/3-540-46035-7_4, lire en ligne), p. 45–64
  3. a b et c (en) Dan Boneh, « Cramer–Shoup Public-Key System », dans Encyclopedia of Cryptography and Security, Springer US, (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_144, lire en ligne), p. 269–270
  4. (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, (ISBN 9783540345466, DOI 10.1007/11761679_18, lire en ligne), p. 289–307
  5. (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, (ISBN 9783540858546, DOI 10.1007/978-3-540-85855-3_8, lire en ligne), p. 109–125
  6. (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, (ISBN 9783540551881, DOI 10.1007/3-540-46766-1_35, lire en ligne), p. 433–444
  7. (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, (ISBN 9783540648925, DOI 10.1007/bfb0055718, lire en ligne), p. 26–45
  8. (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, (ISBN 9783540648925, DOI 10.1007/bfb0055716, lire en ligne), p. 1–12
  9. (en) Danny Dolev, Cynthia Dwork et Moni Naor, « Nonmalleable Cryptography », SIAM Review, vol. 45, no 4,‎ , p. 727–784 (ISSN 0036-1445 et 1095-7200, DOI 10.1137/s0036144503429856, lire en ligne, consulté le 1er septembre 2018)
  10. (en) Hovav Shacham, « A Cramer-Shoup Encryption Scheme from the Linear Assumption and from Progressively Weaker Linear Variants », sur eprint.iacr.org, (consulté le 1er septembre 2018)
  11. (en) Dan Boneh et Victor Shoup, « A Graduate Course in Applied Cryptography », sur crypto.stanford.edu, (consulté le 1er septembre 2018)
  12. (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,‎ , p. 33–43 (ISBN 0897913078, DOI 10.1145/73007.73011, lire en ligne, consulté le 1er septembre 2018)