{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "c40991ae",
   "metadata": {},
   "source": [
    "# TP3 - Schémas sur les réseaux structurés\n",
    "\n",
    "## 1 - Réseaux Structurés et Module-LWE\n",
    "\n",
    "### Exercice 1 - sur papier\n",
    "\n",
    "### Exercice 2 - sur papier\n",
    "\n",
    "##  2 - Implémentation de variantes structurées\n",
    "\n",
    "Ici, l'objectif est de modifier le chiffrement Regev implémenté avant en remplaçant la structure d'entier $\\mathbb{Z}_q$ par la structure d'anneaux cyclotomiques de polynômes $\\mathbb{Z}_q[X]/\\langle X^d + 1\\rangle$ (où $d$ est une puissance de $2$).\n",
    "\n",
    "### Exercice 3: \n",
    "\n",
    "1. Modifier vos différentes fonctions afin de définir un schéma de chiffrement de Regev exploitant des réseaux structurés. Prenez en compte la chiffrement/déchiffrement de messages binaires $m \\in \\{0,1\\}^\\ell$ où $\\ell \\leq d$.\n",
    "\n",
    "    **Aide**: Vous pouvez vous inspirer de vos fonctions du TP1/2, mais il faudra adapter les fonctions pour prendre en compte la structure des réseaux., la taille des matrices et des polynômes, ainsi que les opérations sur les coefficients des polynômes dans $\\mathbb{Z}_q$. \n",
    "\n",
    "- $\\texttt{MLRegevGenerator}$ prenant en entrée un paramètre de sécurité $\\lambda$ ressortant **params**,\n",
    "- $\\texttt{MLRegevKeyGen}$ ressortant une clé publique et une clé privée associée,\n",
    "- $\\texttt{MLRegevEncrypt}$ prenant en entrée une clé publique, un polynôme à coefficients binaires de $\\mathbb{Z}_q[X]/(X^d + 1)$ ainsi qu'une seed (étant un tableau d'octets) (Vous en aurez besoin dans la suite de l'exercice),\n",
    "- $\\texttt{MLRegevDecrypt}$ prenant en entrée la clé privée ainsi que le chiffré $c$ et ressortant un message $m \\in \\mathbb{Z}_q[X]/(X^d + 1)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "62c0c2a2",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "422c2b6d",
   "metadata": {},
   "source": [
    "2. Réutiliser le LWE Estimator pour évaluer la robustesse de votre nouveau schéma. (Vous pouvez réutiliser vos fonctions du TP1/2) \n",
    "\n",
    "    **Aide**: Il existe peu d'attaques exploitant la structure sous-jacentes des réseaux et elle ne sont pas encore bien comprises. Ainsi, pour évaluer la robustesse de votre schéma, considérer simplement les attaques classiques comme s'il n'y avait pas de structure (mais attention aux tailles des matrices et des degrés des polynômes)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "091df066",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "1138132a",
   "metadata": {},
   "source": [
    "3. Comparer l'efficacité de votre nouveau schéma avec vos précédentes constructions non structurées. (Temps + Taille)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "343b29f7",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "4741f355",
   "metadata": {},
   "source": [
    "##  3 - Implémentation du standard ML-KEM\n",
    "\n",
    "Récemment, le standard ML-KEM (pour Méchanisme d'encapsulation de clé) a été adopté par le NIST en Août 2024. Dans un contexte professionnel, vous serez potentiellement amené à l'implémenter,l'utiliser ou identifier les potentiels points de pression cybersensibles. Pour s'assurer de l'efficacité et de l'optimalité du schéma, les paramètres ont donc été définis par le NIST lui-même. \n",
    "\n",
    "\n",
    "\n",
    "### Exercice 4\n",
    "Aller chercher dans la \\lien{https://csrc.nist.gov/pubs/fips/203/final}{documentation officielle} et modifier vos fonctions afin de prendre en compte les paramètres clairement définis.\n",
    "\n",
    "- (Attention les variables ne sont pas toujours les mêmes (les joies de la doc) + la documentation est un peu fouillie et pas toujours très claires (les joies de la doc v2)),\n",
    "- Si vous ne l'aviez pas fait, on considèrera maintenant le chiffrement d'un ensemble de $\\ell \\leq d$ bits que l'on manipulera comme un polynôme à coefficients $0$ ou $1$ dans $\\mathbb{Z}_q[X]/(X^d + 1)$,\n",
    "- Quittes à combler avec des $0$, on considère $\\ell = d$,\n",
    "- Vous n'avez que $\\texttt{MLRegevGenerator}$ à modifier."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1b6166d6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Voir section 8 de la documentation \n",
    "def MLRegevGenerator(security_parameter):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1774ccb4",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bdcf14af",
   "metadata": {},
   "outputs": [],
   "source": [
    "# test\n",
    "bit = UniformSampler(0,1)\n",
    "for security_parameter in [128,192,256]:\n",
    "    validity = 0\n",
    "    MLRegevGenerator(security_parameter)\n",
    "    for _ in range(100):\n",
    "        sk,pk = MLRegevKeyGen()\n",
    "        b = Rq([bit() for _ in range(d)])\n",
    "        if b == MLRegevDecrypt(sk,MLRegevEncrypt(pk,b)):\n",
    "            validity += 1\n",
    "\n",
    "    print(\"validity for lambda=\",security_parameter,\": \",validity,\"/100\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "75c0f68f",
   "metadata": {},
   "source": [
    "Enfin, le standard ML-KEM exploite la structure du chiffrement de Regev mais vous avez montré lors du TP1 que le schéma n'est pas IND-CCA (seulement IND-CPA). Or, il existe un paradigme de transformation cryptographique transformant n'importe quel schéma IND-CPA en schéma IND-CCA, appelé Transformation de Fujisaki-Okamoto. Renseignez-vous puis expliquez la transformation FO, en utilisant la [sous-section 4.8](https://eprint.iacr.org/2024/1287.pdf#subsection.4.8).\n",
    "   \n",
    "   3. Si vous avez été attentif, vous remarquez que le NIST n'a pas standardisé un schéma de chiffrement mais une méthode d'encapsulation de clé: pourquoi selon vous ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "27d02642",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "b1065abd",
   "metadata": {},
   "source": [
    "4. Construire le schéma d'encapsulation de clé $\\textsf{ML-KEM}$, auparavant appelé Kyber. Vous definirez les fonctions :\n",
    "- $\\texttt{MLKEMGenerator}$ prenant en entrée un paramètre de sécurité $\\lambda$,\n",
    "- $\\texttt{MLKEMKeyGen}$ ressortant une clé publique et une clé privée associée,\n",
    "- $\\texttt{MLKEMEncaps}$ prenant en entrée une clé publique, et ressortant 2 éléments, une clé partagée ainsi qu'un chiffré $c$,\n",
    "- $\\texttt{MLKEMDecaps}$ prenant en entrée les clés publiques et privée ainsi que le chiffré $c$ et ressortant une clé partagée.\n",
    "\n",
    "**Aide**: \n",
    "- Les différentes fonctions feront appels à fonctions $\\texttt{MLRegevXXX}$ précédentes.\n",
    "\n",
    "- Essayer dans un premier temps par vous même en essayant de comprendre à la fois la transformation FO et la définition du schéma de KEM.\n",
    "\n",
    "- Ensuite seulement corrigez-vous avec la représentation des fonctions définies dans la [Figure 4](https://eprint.iacr.org/2024/1287.pdf#figure.4)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7edc9d3e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def MLKEMGenerator(security_parameter):\n",
    "    return params\n",
    "\n",
    "def MLKEMKeyGen():\n",
    "    return MLRegevKeyGen()\n",
    "\n",
    "def MLKEMEncaps(pk):\n",
    "    return shared_key_sent, c\n",
    "\n",
    "def MLKEMDecaps(sk,pk,c):\n",
    "        \n",
    "    return shared_key_received"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1a687b9c",
   "metadata": {},
   "outputs": [],
   "source": [
    "#test\n",
    "bit = UniformSampler(0,1)\n",
    "for security_parameter in [128,192,256]:\n",
    "    validity = 0\n",
    "    MLKEMGenerator(security_parameter)\n",
    "    for _ in range(100):\n",
    "        sk,pk = MLKEMKeyGen()\n",
    "        (shared_key_sent, cipher) = MLKEMEncaps(pk)\n",
    "        shared_key_received = MLKEMDecaps(sk,pk,cipher)\n",
    "        if shared_key_received == shared_key_sent:\n",
    "            validity += 1\n",
    "    print(\"validity for lambda=\",security_parameter,\": \",validity,\"/100\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eae16139",
   "metadata": {},
   "source": [
    "**Bravo !** Vous venez d'implémenter votre premier schéma post-quantique (vous n'êtes pas beaucoup à l'avoir déjà fait dans le monde)\n",
    "\n",
    "5. Comparer l'efficacité de votre nouveau schéma avec vos précédentes constructions non structurées du TP1. (Temps + Taille)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9e52d7b3",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}