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[modifier | modifier le code]

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

Génération des paramètres[modifier | modifier le code]

Soit $p_{i}$ le $i$ -ième nombre premier, commençant par $p_{0}=2$ . L'algorithme $G$ prend en entrée un paramètre de sécurité $1^{\lambda }$ , choisit un entier $n$ et un premier $p$ tel que

p>\prod _{i=0}^{n}p_{i}.

L'algorithme choisit alors un entier

s

premier avec

p-1

, puis retourne les paramètres publics

p,n

et les racines

s

-ièmes

v_{i}=p_{i}^{1/s}{\bmod {p}}

^{[Note 2]} et la trappe,

s

.

Évaluation en sens direct[modifier | modifier le code]

L'algorithme $E$ prend en entrée les paramètres publics et un message $m$ représenté comme une chaîne binaire $m_{0},m_{1},\dotsc ,m_{n}$ . Il retourne

c=\prod _{i=0}^{n}v_{i}^{m_{i}}{\bmod {p}}.

Inversion avec trappe[modifier | modifier le code]

L'algorithme $D$ prend en entrée les paramètres publics, un élément $c\in \mathbb {F} _{p}$ , et un entier $s$ . Il retourne

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é[modifier | modifier le code]

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

c=\prod _{i=0}^{n}v_{i}^{m_{i}}{\bmod {p}}.

retrouver les

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 $s$ à partir de $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[modifier | modifier le code]

Bande passante[modifier | modifier le code]

La bande passante (taille du message divisée par la taille de $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[modifier | modifier le code]

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[modifier | modifier le code]

Notes[modifier | modifier le code]

↑ 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.
↑ Le calcul de telles racines est aisé dans le corps fini $\mathbb {F} _{p}$ .

Références[modifier | modifier le code]

↑ (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
↑ (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)
↑ (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
↑ (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)
↑ (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

Portail de la cryptologie

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

[3] Le calcul de telles racines est aisé dans le corps fini $\mathbb {F} _{p}$ .

[2] (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

[4] (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)

[5] (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

[6] (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)

[7] (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

[Note 1]

[1]

[Note 2]

[2]

[3]

[4]

[5]