Sac à dos de Naccache-Stern

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.

Description

On considère trois algorithmes ${\displaystyle G,E,D}$ définis comme suit.

Génération des paramètres

Soit ${\displaystyle p_{i}}$ le ${\displaystyle i}$-ième nombre premier, commençant par ${\displaystyle p_{0}=2}$. L'algorithme ${\displaystyle G}$ prend en entrée un paramètre de sécurité ${\displaystyle 1^{\lambda }}$, choisit un entier ${\displaystyle n}$ et un premier ${\displaystyle p}$ tel que $${\displaystyle p>\prod _{i=0}^{n}p_{i}.}$$ L'algorithme choisit alors un entier ${\displaystyle s}$ premier avec ${\displaystyle p-1}$, puis retourne les paramètres publics ${\displaystyle p,n}$ et les racines ${\displaystyle s}$-ièmes ${\displaystyle v_{i}=p_{i}^{1/s}{\bmod {p}}}$[Note 2] et la trappe, ${\displaystyle s}$ .

Évaluation en sens direct

L'algorithme ${\displaystyle E}$ prend en entrée les paramètres publics et un message ${\displaystyle m}$ représenté comme une chaîne binaire ${\displaystyle m_{0},m_{1},\dotsc ,m_{n}}$. Il retourne $${\displaystyle c=\prod _{i=0}^{n}v_{i}^{m_{i}}{\bmod {p}}.}$$

Inversion avec trappe

L'algorithme ${\displaystyle D}$ prend en entrée les paramètres publics, un élément ${\displaystyle c\in \mathbb {F} _{p}}$, et un entier ${\displaystyle s}$. Il retourne $${\displaystyle m=\sum _{i=0}^{n}{\frac {2^{i}}{p_{i}-1}}\cdot \left(\operatorname {pgcd} (p_{i},c^{s}{\bmod {p}})-1\right)}$$

Sécurité

La sécurité de la fonction à trappe repose sur la difficulté du problème de sac à dos multiplicatif suivant : étant donné $${\displaystyle c=\prod _{i=0}^{n}v_{i}^{m_{i}}{\bmod {p}}.}$$retrouver les ${\displaystyle m_{i}}$. 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 ${\displaystyle s}$ à partir de ${\displaystyle p,p_{i},v_{i}}$, 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éliorations

Bande passante

La bande passante (taille du message divisée par la taille de ${\displaystyle c}$) 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-Stern

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érences

Notes

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 ${\displaystyle \mathbb {F} _{p}}$.

Références

1. (en) David Naccache et Jacques Stern, « A New Public-Key Cryptosystem », dans Advances in Cryptology — EUROCRYPT ’97, Springer Berlin Heidelberg, 1997 (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,‎ octobre 2018, 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, 2008 (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,‎ 17 mars 2018 (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, 2017 (ISBN 9783319692838, DOI 10.1007/978-3-319-69284-5_6, lire en ligne), p. 67–82