{ "cells": [ { "cell_type": "markdown", "id": "5e875560", "metadata": {}, "source": [ "# TP2 - Sécurité de Regev et LWE Estimator\n", "\n", "Après avoir implémenté un schéma cryptographique, il est essentiel de connaitre la sécurité de vos sché-\n", "mas. Précédemment, les paramètres choisies en fonction du paramètre de sécurité en entrée vous étaient\n", "initialement définies. Dans un premier temps, nous allons redécouvrir la sécurité prouvée en reliant la\n", "difficulté de résolution des problèmes de réseaux à celle du schéma.\n", "\n", "Ensuite, vous utiliserez un outil appelé [lwe-estimator](https://github.com/malb/lattice-estimator), permettant d'estimation la difficulté d'un problème LWE en fonction des paramètres en entrée. Cet outil est (très) utilisé en pratique afin d'assurer un choix de paramètres judicieux et efficaces. \n", "\n", "### 0.1. Paquetages et notations\n", "\n", "On vous joint ici un ensemble de paquetages $\\textsf{Sage}$ pouvant vous être utile lors de vos implémentations.\n", "\n", "- [LWE](https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/lwe.html)\n", "- [Distributions Gaussiennes Discrètes sur les réseaux](https://doc.sagemath.org/html/en/reference/stats/sage/stats/distributions/discrete_gaussian_lattice.html),\n", "- [Echantilloneur uniforme](https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/lwe.html#sage.crypto.lwe.UniformSampler),\n", "- [Generateur de mauvaise base](https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/lattice.html).\n", "- [LWE Estimator](https://github.com/malb/lattice-estimator)\n", "\n", "### Exercice 1: sur papier\n", "\n", "### Exercice 2: LWE Estimator\n", "\n", "\n", " Martin R. Albrecht, Rachel Player and Sam Scott. On the concrete hardness of Learning with Errors.\n", " Journal of Mathematical Cryptology. Volume 9, Issue 3, Pages 169–203, ISSN (Online) 1862-2984,\n", " ISSN (Print) 1862-2976 DOI: 10.1515/jmc-2015-0016, October 2015\n", "\n", "\n", "Le [LWE-Estimator](https://github.com/malb/lattice-estimator) est un outil fréquemment utilisé afin de s'assurer d'avoir des paramètres permettant la sécurité des constructions cryptographiques basées sur les réseaux et plus spécifiquement $\\textsf{LWE}$. Importez l'estimateur dans ce notebook, et isoler le dossier *estimator* dans le même dossier que ce fichier." ] }, { "cell_type": "code", "execution_count": null, "id": "e79107fc", "metadata": {}, "outputs": [], "source": [ "from estimator import *" ] }, { "cell_type": "markdown", "id": "30113896", "metadata": {}, "source": [ "Dans $\\texttt{schemes}$, vous trouverez des jeux de paramètres déjà bien établis. Voici un exemple, celui de la semaine précédente, le KEM Kyber pour un paramètre de sécurité $\\lambda = 128$. Le problème LWE sur lequel on assure la sécurité devra donc prendre les valeurs suivantes. On identifie 5 paramètres différents:\n", " - $n$: la taille du secret,\n", " - $m$: le nombre de sample $\\textsf{LWE}$,\n", " - $q$: le modulo utilisé,\n", " - $Xs$: la distribution du secret ici $D(σ=1.22)$ signifie Distribution Gaussienne d'écart-type $σ=1.22$,\n", " - $Xe$: la distribution de l'erreur." ] }, { "cell_type": "code", "execution_count": null, "id": "f4321792", "metadata": {}, "outputs": [], "source": [ "schemes.Kyber512" ] }, { "cell_type": "markdown", "id": "f1b04066", "metadata": {}, "source": [ "Une fois les paramètres choisies dans un objet $\\texttt{LWEParameters()}$ qu'on nommera $\\texttt{paramsLWE}$, on peut exécuter la fonction $\\texttt{LWE.estimate(paramsLWE)}$.\n", "\n", "La fonction évoluera la difficulté de plusieurs attaques optimisées de $\\textsf{LWE}$ selon vos paramètres en entrée, afin de déterminer la facilité (ou non) de performer ces attaques sur des samples $\\textsf{LWE}$ et/ou des bkw, usvp, bdd, dual et dual_hybrid. \n", "L'entrée importante a regardé est l'entrée \"rop\" signifiant \"ring operations\" c'est-à-dire le nombre d'opérations nécessaire à chaque attaque afin de \"casser\" le schéma. Chaque attaque a des coûts différents et il faut vérifier que l'attaque la plus rapide a besoin de réaliser au moins $2^\\lambda$ operations (minimum) où $\\lambda$ est le paramètres de sécurité. " ] }, { "cell_type": "code", "execution_count": null, "id": "d9184bf5", "metadata": {}, "outputs": [], "source": [ "est = LWE.estimate(schemes.Kyber512)" ] }, { "cell_type": "code", "execution_count": null, "id": "e133aae2", "metadata": {}, "outputs": [], "source": [ "total_op = []\n", "for keys in est:\n", " value = est[keys][\"rop\"]\n", " if value in ZZ:\n", " total_op += [floor(log(value,2))]\n", "\n", "print(\"Ce jeu de paramètre valide une sécurité Lambda=\",min(total_op))" ] }, { "cell_type": "markdown", "id": "5271c569", "metadata": {}, "source": [ "Si vous souhaitez analyser la robustesse de votre jeu de paramètres, instanciez un nouvel objet LWE.parameters et lancer $\\texttt{𝙻𝚆𝙴.𝚎𝚜𝚝𝚒𝚖𝚊𝚝𝚎}$ sur cet objet." ] }, { "cell_type": "code", "execution_count": null, "id": "f9ab75e6", "metadata": {}, "outputs": [], "source": [ "ParamsLWE = LWE.Parameters(\n", " n = 128, #taille du secret s & largeur de la matrice A\n", " q = 128.next_prime(), #modulo q employé\n", " Xs = ND.Uniform(-1,1), #distribution du secret s (coefficient par coefficient)\n", " Xe = ND.Uniform(-1,1), #distribution du secret e (coefficient par coefficient)\n", " m = 128 #nombre de sample LWE & hauteur de la matrice A\n", ")" ] }, { "cell_type": "code", "execution_count": null, "id": "a42fd6a6", "metadata": {}, "outputs": [], "source": [ "security_parameter = 128\n", "total_op = []\n", "for keys in est:\n", " value = est[keys][\"rop\"]\n", " if value in ZZ:\n", " total_op += [floor(log(value,2))]\n", "assert min(total_op) >= security_parameter" ] }, { "cell_type": "markdown", "id": "26b3c5c9", "metadata": {}, "source": [ "4. Trouvez un jeu de paramètres satisfiant $\\lambda = 64$ mais pas $\\lambda = 65$. Modifiez les paramètres de **RegevGenerator** en conséquence et testez votre implémentation." ] }, { "cell_type": "code", "execution_count": null, "id": "3a9d456b", "metadata": {}, "outputs": [], "source": [ "ParamsLWE = LWE.Parameters(\n", " n = , #taille du secret s & largeur de la matrice A\n", " q = , #modulo q employé\n", " Xs = , #distribution du secret s (coefficient par coefficient)\n", " Xe = , #distribution du secret e (coefficient par coefficient)\n", " m = #nombre de sample LWE & hauteur de la matrice A\n", ")" ] }, { "cell_type": "markdown", "id": "7d7cb434", "metadata": {}, "source": [ "5. Trouvez le jeu de paramètres optimale satisfiant $\\lambda = 64$ tout en garantissant des tailles minimales (clés et/ou chiffrés). Modifiez les paramètres de **RegevGenerator** en conséquence et testez votre implémentation." ] }, { "cell_type": "code", "execution_count": null, "id": "156b0e1f", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "214ab330", "metadata": {}, "source": [ "### 2.2. Utilisation de LWE-Estimator\n", "\n", "Votre objectif est de manipuler le LWE-estimator afin d'avoir un jeu de paramètres assurant la sécurité pour un paramètres de sécurité en entrée $\\lambda = 64$. \n", "\n", "1. Pour cela, faites un script permettant d'évaluer la difficulté des attaques sur les jeux de paramètres en entrée, l'objectif est de faire évoluer vos jeux de paramètres jusqu'à atteindre un point fixe.\n", "\n", " - Vous devez construire un jeu de paramètre pour une implémentation, pour laquelle sa sécurité serait basée sur une instance d'un problème $\\textsf{LWE}$ pour laquelle:\n", " - $q$ est un nombre premier de la forme $q = 2^k + 1$ et $q = \\omega(n)$,\n", " - le vecteur $\\mathbf{s}$ et le vecteur $\\mathbf{e}$ suivent chacun une loi uniforme dans à coefficient $[-1,0,1]$, \n", " - la matrice $\\mathbf{A}$ sera une matrice carré à coefficients dans $\\mathbb{Z}_q^{m \\times n}$ où $m = n$.\n", " - Vous allez procéder de la manière suivante:\n", " - Faites évoluer $k$ pour avoir $q = 2^k + 1$ étant premier,\n", " - Considérer $n=m=q$ et rechercher le bon un $q$ valide tel que le jeu valide une bonne sécurité,\n", " - Une fois que vous avez un bon ensemble de paramètres, refaites un script recherchant $n=m$ le plus judicieux possible avec une dichotomie (c'est-à-dire le plus petit assurant tout de même la sécurité). \n", "\n", "2. (Facultatif) Même question:\n", " - Vous devez construire un jeu de paramètre pour une implémentation, pour laquelle sa sécurité serait basée sur une instance d'un problème $\\textsf{MLWE}$ pour laquelle:\n", " - $d$ sera le degré du polynôme engendrant l'idéal $$, $d$ est une puissance de 2 (plus il est grand mieux c'est),\n", " - $q$ vaudra un nombre premier $q = \\omega(nd)$,\n", " - le vecteur $\\mathbf{s}$ et le vecteur $\\mathbf{e}$ suivent chacun une loi uniforme dans à coefficient $[-1,0,1]$, \n", " - rappel: $\\mathcal{R}_q := \\mathbb{Z}_q[X]/$ \n", " - la matrice $\\mathbf{A}$ sera une matrice carré à coefficients dans $\\mathcal{R}_q^{m \\times n}$ où $m = n$.\n", " - INDICE: On analyse la sécurité d'un problème $\\textsf{MLWE}$ de la même manière qu'un problème $\\textsf{LWE}$ (mais pour des tailles $md \\times nd$) on ne considèrera pas la structure dans la recherche des paramètres optimaux." ] }, { "cell_type": "code", "execution_count": null, "id": "495c3bf5", "metadata": {}, "outputs": [], "source": [ "def searchParams(security_parameter):\n", " # à remplir" ] }, { "cell_type": "markdown", "id": "b78dd32a", "metadata": {}, "source": [ "3. Modifier les questions précédentes afin d’obtenir des jeux de paramètres optimisés pour $\\lambda \\in \\{128, 196, 256\\}$." ] }, { "cell_type": "code", "execution_count": null, "id": "f4a4fe81", "metadata": {}, "outputs": [], "source": [ "for lmbda in [128,196,256]:\n", " print(searchParams(lmbda))" ] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.5", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.12" } }, "nbformat": 4, "nbformat_minor": 5 }