Cryptosystème homomorphe de Naccache-Stern

Chiffrement à clé publique additivement homomorphe

En cryptologie, le cryptosystème homomorphe de Naccache-Stern est un chiffrement à clé publique introduit en 1998 par les cryptologues David Naccache et Jacques Stern[1]. La sécurité sémantique de ce cryptosystème repose sur le problème de la résiduosité supérieure[2], et il s'agit d'un système de chiffrement additivement homomorphe.

D'un point de vue historique, le cryptosystème de Naccache-Stern est une amélioration du cryptosystème de Benaloh-Fischer[3], lui-même une extension de celui de Goldwasser-Micali[4], dans une succession d'améliorations de bande passante de chiffrements homomorphes.

DescriptionModifier

Le cryptosystème s'appuie sur trois algorithmes   correspondant respectivement à la génération de clés, au chiffrement, et au déchiffrement.

Génération de clésModifier

L'algorithme de génération de clé prend en entrée un paramètre de sécurité   et retourne un couple de clés obtenues de la manière suivante[Note 1],[5] :

  • Deux ensembles de nombres premiers[Note 2]   et   sont choisis, tous distincts. Le nombre   est déterminé par l'algorithme en fonction de  , et les premiers sont choisis « petits », en un sens précisé plus tard.
  • Le produit des   (resp. des  ) est calculé et noté   (resp.  )
  • Deux grands premiers   sont alors choisis de sorte que   et   soient simultanément premiers.
  • Le produit   et calculé, et un élément   d'ordre   est choisi, où   est la fonction d'Euler[Note 3].

La clé publique est alors définie comme   et la clé privée correspondante est donnée par   (ou  , ce qui est équivalent).

Les nombreux tests de primalité intervenant lors de la génération de clés sont relativement coûteux, mais peuvent être en partie absorbés par une implémentation appropriée[1].

ChiffrementModifier

L'algorithme de chiffrement prend en entrée un message   et la clé publique  . Un élément aléatoire   est choisi[Note 4], puis le chiffré est obtenu en calculant  .

DéchiffrementModifier

L'algorithme de déchiffrement prend en entrée un chiffré   et la clé privée  . On calcule alors pour chaque  

 
On peut écrire ces équations en prenant pour base le générateur  , à savoir
 
Pour un message chiffré, on a   (resp.  ) où   (resp.  ). En résolvant un logarithme discret modulo  on obtient alors   ce qui permet via le théorème chinois des restes de retrouver  . Résoudre le logarithme discret est en général considéré difficile : c'est pourquoi les premiers   ont été choisis petits, au sens qu'une recherche exhaustive de   est possible.

Homomorphisme additifModifier

Le cryptosystème de Naccache-Stern jouit d'une propriété supplémentaire : il s'agit d'un chiffrement additivement homomorphe. En effet, on a pour tous messages  ,

 
de sorte que
 
qui se déchiffre en  . Contrairement au cryptosystème de Paillier, également additivement homomorphe, l'intérêt de la construction de Naccache-Stern est sa bande passante : on travaille modulo   et non pas modulo   comme Paillier.

SécuritéModifier

Le cryptosystème de Naccache-Stern est sémantiquement sûr (IND-CPA) sous l'hypothèse de la difficulté du problème de la résiduosité supérieure[2]. En réalité on peut montrer qu'il repose sur une hypothèse légèrement moins forte de résiduosité des premiers choisis[4]. Dans un cas comme dans l'autre, la meilleure approche connue (en 2018) pour résoudre ces problèmes est d'obtenir une factorisation de  . Les meilleurs algorithmes classiques connus (i.e., GNFS et ses variantes) permettent alors de fixer les paramètres pour viser un niveau de sécurité donné.

En revanche, s'agissant d'un chiffrement homomorphe, ce cryptosystème est malléable et ne peut donc pas prétendre aux notions plus fortes de sécurité (IND-CCA notamment).

De plus, on connait pour le problème de la factorisation un algorithme quantique efficace : l'algorithme de Shor. Le cryptosystème de Naccache-Stern n'est donc pas un candidat post-quantique.

Notes et référencesModifier

NotesModifier

  1. Nous suivons ici pour l'essentiel la description de la « version probabiliste » décrite dans (Naccache et Stern 1998), qui est le cas général et qui est la seule capable de sécurité sémantique.
  2. (Naccache et Stern 1998) observent qu'il n'est pas nécessaire que les nombres soient premiers : il suffit qu'ils soient premiers entre eux. Le choix de nombre premiers a le mérite de faciliter l'analyse.
  3. Lorsque les   sont les   plus petits nombres premiers, le théorème des nombres premiers permet d'estimer la probabilité qu'un élément   pris au hasard convienne à environ  .
  4. Si le nombre   est fixé, ce qui correspond à la « version déterministe » de (Naccache et Stern 1998), on n'a plus de sécurité sémantique : le cryptosystème est mieux décrit comme une fonction à trappe.

RéférencesModifier

  1. a et b (en) David Naccache et Jacques Stern, « A new public key cryptosystem based on higher residues », CCS '98 Proceedings of the 5th ACM conference on Computer and communications security, ACM,‎ , p. 59–66 (ISBN 1581130074, DOI 10.1145/288090.288106, lire en ligne, consulté le 18 septembre 2018)
  2. a et b (en) David Naccache, Mike Just, Bart Preneel et Angelos D. Keromytis, « Naccache–Stern Higher Residues Cryptosystem », dans Encyclopedia of Cryptography and Security, Springer US, (ISBN 9781441959058, DOI 10.1007/978-1-4419-5906-5_893, lire en ligne), p. 829–829
  3. (en) Josh D. (Benaloh) Cohen et Michael J. Fischer, « A robust and verifiable cryptographically secure election scheme », 26th Annual Symposium on Foundations of Computer Science (sfcs 1985),‎ , p. 372–382 (DOI 10.1109/SFCS.1985.2, lire en ligne, consulté le 18 septembre 2018)
  4. a et b (en) Fabrice Benhamouda, Javier Herranz, Marc Joye et Benoît Libert, « Efficient Cryptosystems From  -th Power Residue Symbols », Journal of Cryptology, vol. 30, no 2,‎ , p. 519–549 (ISSN 0933-2790 et 1432-1378, DOI 10.1007/s00145-016-9229-5, lire en ligne, consulté le 18 septembre 2018)
  5. (en) Thomas Baignères, A classical introduction to cryptography : Exercise book, New York, Springer, , 254 p. (ISBN 978-0-387-27934-3, 0387279342 et 9780387288352, OCLC 209962575, lire en ligne), p. 186