Le but de la cryptographie homomorphe est de pouvoir exécuter des algorithme sur les messages chiffrés (calculs, recherche). Il faut pour cela disposer d'opérations booléennes compatibles avec la fonction de chiffrement, qui ne diminuent pas sa sécurité. On étudiera la proposition de Gentry (2009) pour résoudre ce problème.
thèmes cryptosystème, réseaux, progrès récent
Etudier un mécanisme d'échange de clef entre trois entités reposant sur l'accouplement de Weil sur les courbes elliptiques.
thèmes courbes elliptiques, protocole
étudier un cryptosystème récent et plusieurs attaques
thèmes cryptosystème, réseaux, attaques
On s'intéressera au calcul du cardinal d'une courbe elliptique sur un corps fini, à l'aide de méthodes génériques de type pas de bébé pas de géant, puis on étudiera l'algorithme de Schoof.
thèmes courbes elliptiques, algorithme
ECM, ou elliptic curves method, est une méthode de factorisation très efficace, obtenue en transposant le principe de la méthode p-1 aux groupes de points de courbes elliptiques. On programmera la méthode (phases 1 et 2) et on l'utilisera pour déterminer des facteurs d'entiers de Fermat ou de Mersenne.
thèmes courbes elliptiques, factorisation, algorithme
On présentera l'algorithme LLL de réduction de réseaux, et ses applications à diverses attaques cryptographiques (sac-à-dos, RSA).
thèmes réseaux, attaques
Ce test démontre que le problème de primalité est de complexité polynomiale. On démontrera la validité du test et on le programmera.
thèmes algorithme, primalité, arithmétique
Il s'agit de la méthode la plus efficace pour résoudre le logarithme discret. Il en existe de multiples variantes, on programmera l'algorithme dans sa forme simple, assez similaire au crible quadratique.
thèmes algorithme, logarithme discret
On recensera un certain nombre d'attaques arithmétiques (Wiener, Coppersmith,...) et on en fera des démonstrations.
thèmes attaques, réseaux, arithmétique
L'algorithmique de la factorisation sur Z[x] met en jeu la factorisation modulo p, et des problèmes de relèvement à Z. Le but est d'écrire un algorithme complet et d'évaluer sa complexité.
On cherche à résoudre des systèmes linéaires Ax=b en (très) grande dimension sur un corps fini, quand la matrice est creuse. La technique de Wiedemann passe par le calcul du polynôme minimal de A, obtenu via une utilisation ingénieuse de la théorie des suites récurrentes. On étudiera et programmera l'algorithme.
On s'intéressera aux algorithmes de multiplication rapides d'entiers de grande taille.
thèmes algorithme, arithmétique
comprendre les principes sous-jacents et les instructions disponibles, l'application à la factorisation et au logarithme discret, programmer des algorithmes simples sur des simulateurs.
Etudier, et démontrer les propriétés de cette nouvelle construction de codes correcteurs qui atteignent la borne de Shannon.
thèmes entropie, codage, progrès récent