Sac à dos de Naccache-Stern

Fonction à trappe cryptographique basée sur la difficulté d'un sac à dos multiplicatif

En cryptologie, le sac à dos de Naccache-Stern est une fonction à trappe[Note 1] introduite en 1997 par les cryptologues David Naccache et Jacques Stern[1]. La sécurité de cette construction repose sur une variante multiplicative du problème du sac à dos, pour laquelle aucun algorithme efficace n'est aujourd'hui connu (en 2018). Cependant, cette construction n'est pas considérée compétitive par rapport à des schémas standard ; son intérêt est ainsi principalement théorique.

DescriptionModifier

On considère trois algorithmes   définis comme suit.

Génération des paramètresModifier

Soit   le  -ième nombre premier, commençant par  . L'algorithme   prend en entrée un paramètre de sécurité  , choisit un entier   et un premier   tel que

 
L'algorithme choisit alors un entier   premier avec  , puis retourne les paramètres publics   et les racines  -ièmes  [Note 2] et la trappe,   .

Évaluation en sens directModifier

L'algorithme   prend en entrée les paramètres publics et un message   représenté comme une chaîne binaire  . Il retourne

 

Inversion avec trappeModifier

L'algorithme   prend en entrée les paramètres publics, un élément  , et un entier  . Il retourne

 

SécuritéModifier

La sécurité de la fonction à trappe repose sur la difficulté du problème de sac à dos multiplicatif suivant : étant donné

 
retrouver les  . Contrairement aux cryptosystèmes à base de sacs à dos additifs, comme celui de Merkle-Hellman, les techniques de réduction de réseau euclidien ne s'appliquent pas à ce problème.

La meilleure attaque générique connue consiste à résoudre le problème du logarithme discret pour retrouver   à partir de  , ce qui est considéré difficile pour un calculateur classique. En revanche, l'algorithme quantique de Shor résout efficacement ce problème, et le sac à dos de Naccache-Stern n'est donc pas post-quantique. De plus, à l'heure actuelle (2018), il n'existe pas de preuve que le sac à dos de Naccache-Stern se réduit au logarithme discret.

La meilleure attaque spécifique connue (en 2018) utilise le théorème des anniversaires pour inverser partiellement la fonction sans connaître la trappe, sous l'hypothèse que le message est de poids de Hamming très faible[2]. Apprendre plus d'un nombre logarithmique de bits du message est un problème ouvert.

Variantes et améliorationsModifier

Bande passanteModifier

La bande passante (taille du message divisée par la taille de  ) tend asymptotiquement vers zéro, du fait de la raréfaction des nombres premiers. Ce phénomène peut toutefois être compensé en adoptant un meilleur encodage des messages[3],[4].

Cryptosystèmes à base du sac à dos de Naccache-SternModifier

Le sac à dos de Naccache-Stern est déterministe et ne peut donc pas garantir de sécurité sémantique, ce qui est un obstacle à la construction d'un cryptosystème à clé publique. Il est toutefois possible de modifier la fonction en introduisant un aléa, ce qui retire cet obstacle[5].

Notes et référencesModifier

NotesModifier

  1. Il s'agit d'un algorithme déterministe, qui ne peut donc garantir la sécurité sémantique attendue pour un cryptosystème. Voir plus bas.
  2. Le calcul de telles racines est aisé dans le corps fini  .

RéférencesModifier

  1. (en) David Naccache et Jacques Stern, « A New Public-Key Cryptosystem », dans Advances in Cryptology — EUROCRYPT ’97, Springer Berlin Heidelberg, (ISBN 9783540629757, DOI 10.1007/3-540-69053-0_3, lire en ligne), p. 27–36
  2. (en) M. Anastasiadis, N. Chatzis et K.A. Draziotis, « Birthday type attacks to the Naccache–Stern knapsack cryptosystem », Information Processing Letters, vol. 138,‎ , p. 39–43 (ISSN 0020-0190, DOI 10.1016/j.ipl.2018.06.002, lire en ligne, consulté le 11 septembre 2018)
  3. (en) Benoît Chevallier-Mames, David Naccache et Jacques Stern, « Linear Bandwidth Naccache-Stern Encryption », dans Lecture Notes in Computer Science, Springer Berlin Heidelberg, (ISBN 9783540858546, DOI 10.1007/978-3-540-85855-3_22, lire en ligne), p. 327–339
  4. (en) Rémi Géraud et David Naccache, « Mixed-radix Naccache–Stern encryption », Journal of Cryptographic Engineering,‎ (ISSN 2190-8508 et 2190-8516, DOI 10.1007/s13389-018-0188-7, lire en ligne, consulté le 11 septembre 2018)
  5. (en) Éric Brier, Rémi Géraud et David Naccache, « Exploring Naccache-Stern Knapsack Encryption », dans Innovative Security Solutions for Information Technology and Communications, Springer International Publishing, (ISBN 9783319692838, DOI 10.1007/978-3-319-69284-5_6, lire en ligne), p. 67–82