{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# Cryptage homomorphic de Craig Gentry\n", "\n", "Un cryptage homomorphe pr\u00e9serve l'addition et la multiplication : une addition sur des nombres crypt\u00e9s est \u00e9gale au r\u00e9sultat crypt\u00e9 de l'addition sur les nombres non crypt\u00e9es. Craig Gentry a propos\u00e9 un tel cryptage dans son article [Fully Homomorphic Encryption over the Integers](https://eprint.iacr.org/2009/616.pdf). Le syst\u00e8me de cryptage encrypte et d\u00e9crypte des bits (0 ou 1)."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## D\u00e9finition du cryptage\n", "\n", "$KeyGen(\\lambda)$\n", "\n", "* La cl\u00e9 secr\u00e8te $sk$ est un entier impair $p$ cod\u00e9 sur $\\eta$ bits : $p\\in (2\\mathbb{Z}+1) \\cap [2^{\\eta}, 2^{\\eta+1}[$.\n", "* La cl\u00e9 publique $pk$ est une s\u00e9quence de $\\tau+1$ entiers al\u00e9atoires tir\u00e9s selon un loi $\\mathcal{D}_{\\gamma,\\rho}(p)$. La s\u00e9quence $(x_0, ..., x_{\\tau})$ (doit v\u00e9rifier $x_0$ est impair et $r_p(x_0)$ est pair. Il faut recommencer si ce n'est pas le cas. Chaque entier est cod\u00e9 sur au plus $\\gamma$ bits.\n", "\n", "$Encrypt(pk, m\\in \\{0,1\\})$\n", "\n", "Choisir un ensemble al\u00e9atoire $S \\subset \\{1, ..., \\tau\\}$ et un entier al\u00e9atoire $r$ dans l'intervalle $]-2^{\\rho'}, 2^{\\rho'}[$. Calculer $c = (m + 2r + 2\\sum_{i \\in S} x_i) \\mod x_0$.\n", "\n", "$Evaluate(pk, C, c_1, ..., c_t)$\n", "\n", "La fonction $C$ effectue des op\u00e9rations sur $t$ bits. Le r\u00e9sultat est $c$.\n", "\n", "$Decrypt(sk, c)$\n", "\n", "Le r\u00e9sultat cherch\u00e9 est $(c \\mod p) \\mod 2$.\n", "\n", "**Avec :** (valeurs sugg\u00e9r\u00e9es par l'article mais d'autres sont possibles\n", "\n", "* $\\rho = \\lambda$\n", "* $\\rho' = 2\\lambda$\n", "* $\\eta \\sim O(\\lambda^2)$\n", "* $\\gamma \\sim O(\\lambda^5)$\n", "* $\\tau = \\gamma + \\lambda$\n", "* Pour simuler une loi $\\mathcal{D}_{\\gamma,\\rho}(p)$, choisir $q$ tel que $q \\in \\mathbb{Z} \\cap \\left[0, \\frac{2^{\\gamma}}{p}\\right[$, $r$ tel que $r \\in \\mathbb{Z} \\cap \\left]-2^{\\rho}, 2^{\\rho}\\right[$ et calculer $x = pq+r$.\n", "* $r_p(x)$ est le reste de la division enti\u00e8re de $x$ par $p$, reste choisi dans l'intervalle $\\left]-\\frac{p}{2}, \\frac{p}{2}\\right]$."]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 1 : impl\u00e9menter le cryptage"]}, {"cell_type": "code", "execution_count": 2, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 2 : v\u00e9rifier que le cryptage est stable par addition et multiplication"]}, {"cell_type": "code", "execution_count": 3, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 3 : impl\u00e9mententer l'addition enti\u00e8re "]}, {"cell_type": "code", "execution_count": 4, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice 4 : impl\u00e9menter la multiplication enti\u00e8re"]}, {"cell_type": "code", "execution_count": 5, "metadata": {"collapsed": true}, "outputs": [], "source": []}, {"cell_type": "code", "execution_count": 6, "metadata": {"collapsed": true}, "outputs": [], "source": []}], "metadata": {"kernelspec": {"display_name": "Python 3", "language": "python", "name": "python3"}, "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.6.1"}}, "nbformat": 4, "nbformat_minor": 2}