# Hashing to elliptic curves and cryptanalysis of RSA-based schemes

Mehdi Tibouchi

► To cite this version:

Mehdi Tibouchi. Hashing to elliptic curves and cryptanalysis of RSA-based schemes. Cryptography and Security [cs.CR]. Université Paris Diderot (Paris 7); Université du Luxembourg, 2011. English.

NNT: tel-04161093

HAL Id: tel-04161093

https://theses.hal.science/tel-04161093

Submitted on 13 Jul 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License
____________________ THÈSE DE DOCTORAT ______________________

# Hachage vers les courbes elliptiques et cryptanalyse de schémas RSA.

____________________ Spécialité : informatique ______________________

présentée et soutenue publiquement le 23 septembre 2011 par

Mehdi Tibouchi

pour obtenir le grade de

Docteur de l'Université Paris Diderot et de l'Université du Luxembourg

devant le jury composé de

Directeurs de thèse : Jean-Sébastien CORON (Université du Luxembourg, Luxembourg)
David NACCACHE (Université Paris II & ENS, France)

Rapporteurs : Pierrick GAUDRY (CNRS & LORIA, France)
Igor SHPARLINSKI (Macquarie University, Australie)

Examinateurs : Pierre-Alain FOUQUE (ENS, France)
Jean-François MESTRE (Université Paris 7, France)
Tatsuaki OKAMOTO (NTT, Japon)
Jacques STERN (ENS, France)
<figure><img src="image_2.png" /></figure>
# Remerciements

Merci tout d'abord à Pierrick et Igor qui ont accepté la lourde tâche de relire ce manuscrit, et à tous les membres du jury, qui ont bien voulu se libérer à cet horaire inhabituel, et qui pour certains viennent de fort loin !

Merci encore à mes directeurs de thèse, David et Jean-Sébastien, qui m'ont accueilli alors que j'étais un matheux naïf et non sans préjugés, et m'ont fait découvrir combien la cryptographie est un domaine vaste, où l'on trouve des questions passionnantes aussi bien théoriques que très proches des applications. Merci aussi pour nos réunions de recherches itinérantes et toujours intéressantes, et pour leur soutien dans toutes sortes de projets, scientifiques ou non.

Merci également à l'équipe de cryptologie de l'ENS, qui offre aussi bien un environnement scientifique idéal où l'on jouit d'une grande liberté que la possibilité d'aller découvrir le monde. Merci notamment à Damien, Pierre-Alain, Phong, Michel et Vadim, tant pour nos discussions autour d'un tableau noir que pour celles, pas moins importantes, autour d'une pizza à Taormina ou des fraises au chocolat de CRYPTO. Merci à tous les chercheurs de l'équipe, permanents, post-docs, doctorants ou plus jeunes, pour l'ambiance toujours agréable au labo, et aux administratifs pour faire en sorte que tout cela fonctionne (pensée particulière pour Joëlle, Valérie et Michelle, pour avoir supporté mon côté tête-en-l'air).

Merci aussi aux collègues qui m'ont accueilli à Ingenico au début de cette thèse, en particulier Éric, avec qui discuter de mathématiques est toujours un plaisir, et Thomas, avec qui j'espère avoir encore l'occasion de prendre un verre sur Orchard Road ou à Shibuya.

Merci aux collègues de NTT, auprès de qui j'ai passé six excellents mois de stage et que j'aurai plaisir à rejoindre par la suite. Merci à Okamoto-san pour son accueil si aimable, à Uchida-san pour sa prévenance et les discussions en français que nous avions sur le Japon (ou inversement), à Yamamoto-san, Abe-san, Fujioka-san et bien d'autres pour des discussions scientifiques toujours intéressantes, à Nishimaki-san et Sasaki-san pour leur aide à la résidence de Sayamagaoka, et à Berkant et Daegun avec qui j'ai pu partager l'expérience de la vie d'étranger au Japon.

Au cours de cette thèse, j'ai eu l'occasion de collaborer avec de nombreux co-auteurs. Merci à tous : ce travail est le vôtre autant que le mien.

Merci à tous ceux qui ont permis que j'aie de quoi vivre pendant cette thèse : David N., David P. et Damien, qui se sont démenés pour cela, Ingenico, NTT, l'ENS et le
projet ANR PACE, ainsi que le projet européen ECRYPT II et le ministère des Affaires étrangères qui ont pris en charge certains de mes déplacements. Merci aussi à ceux qui m'ont encouragé à entreprendre cette thèse ou m'ont soutenu au travers de débuts administrativement délicats : David et Damien, Philippe Clarisse et les collègues de Saint-Louis, Johan Yebbou, Louis Vogel et Chantal Ladoux, David Madore, Yazid Sabeg et d'autres sans doute qui sont intervenus sans que j'en aie eu connaissance.

Et parce qu'il y a une vie en dehors du labo, merci enfin à ceux qui m'ont supporté
au quotidien pendant ces trois ans : mes parents bien sûr (et ça n'a pas dû être facile !) ;
Chantal Ladoux ; Viêt-Linh, JB et Jean-Rémy ; yaforum ; et mes compagnons de virées
du côté de la rue de la Michodière ou de Higashi-Ikebukuro.
はるかまで旅してみたり昼寝覚

森 澄雄
<figure><img src="image_3.png" /></figure>
# Sommaire

<table><tr><td>1</td><td>Introduction</td><td>1</td></tr><tr><td>2</td><td>Présentation des travaux</td><td>11</td></tr><tr><td>I</td><td>Contributions à la cryptographie par courbes elliptiques</td><td>31</td></tr><tr><td>3</td><td>Hachage en temps constant vers les courbes (hyper)elliptiques</td><td>37</td></tr><tr><td>4</td><td>Estimation de la taille de l'image des encodages en temps constant</td><td>63</td></tr><tr><td>5</td><td>Hachage indifférentiable vers les courbes elliptiques</td><td>75</td></tr><tr><td>6</td><td>Encodages bien distribués</td><td>99</td></tr><tr><td>7</td><td>Hachage et encodage vers les courbes hyperelliptiques impaires</td><td>115</td></tr><tr><td>8</td><td>Le modèle de Huff</td><td>125</td></tr><tr><td>II</td><td>Cryptanalyse de schémas fondés sur RSA</td><td>141</td></tr><tr><td>9</td><td>Cryptanalyse pratique des signatures ISO/IEC 9796-2 et EMV</td><td>149</td></tr><tr><td>10</td><td>Attaques par fautes sur les signatures EMV</td><td>175</td></tr><tr><td>11</td><td>Attaques par fautes sur le module contre les signatures RSA</td><td>191</td></tr><tr><td>12</td><td>Sur la sécurité du chiffrement PKCS#1 v1.5</td><td>209</td></tr><tr><td>13</td><td>Cryptanalyse de l'hypothèse RSA dans un sous-groupe</td><td>229</td></tr><tr><td></td><td>Table des matières</td><td>243</td></tr><tr><td></td><td>Liste des figures</td><td>245</td></tr><tr><td></td><td>Liste des tables</td><td>246</td></tr><tr><td></td><td>Liste des algorithmes</td><td>247</td></tr><tr><td></td><td>Bibliographie</td><td>248</td></tr></table>
<figure><img src="image_4.png" /></figure>
# Introduction

## 1.1 Introduction à la cryptologie

L'usage de codes secrets, principalement dans les communications diplomatiques et militaires, remonte à l'Antiquité (on en trouve déjà des traces dans l'Égypte du moyen empire, puis en Grèce antique), où il était encore artisanal. Peu à peu, une compétition s'installe entre les utilisateurs de codes secrets et ceux qui tentent de les percer : à partir du Moyen Âge, plusieurs traités sont ainsi écrits sur des techniques permettant de casser les codes secrets (notamment l'analyse de fréquence à l'encontre des chiffrements par substitution simple). L'étude des messages secrets se constitue progressivement comme une science, la cryptologie, rassemblant ces deux aspects apparemment antagonistes : la cryptographie d'une part, visant à élaborer des méthodes pour sécuriser les communications, et la cryptanalyse d'autre part, visant à déceler des faiblesses dans ces méthodes.

Depuis quelques décennies, l'essor des télécommunications et le développement et la miniaturisation des moyens de calcul ont permis à la cryptographie de dépasser le champ militaire et d'investir notre vie quotidienne : des dispositifs aussi variés qu'un téléphone mobile, une carte bancaire, un passeport biométrique et un navigateur web effectuent des calculs cryptographiques, afin de garantir diverses propriétés de sécurité de leurs communications.

Parmi les propriétés de sécurité auxquelles s'intéresse la cryptologie, on peut citer l'intégrité des messages (lorsque l'on veut s'assurer qu'ils n'ont pas été altérés sur le canal de transmission : par exemple quand on télécharge un fichier), leur authenticité (lorsque l'on veut s'assurer que l'expéditeur est bien celui qu'il prétend : par exemple qu'une transaction bancaire est bien réalisée par une carte de paiement autorisée) ou encore leur confidentialité (lorsque l'on veut les garder secrets en dépit des personnes pouvant espionner la communication : par exemple lorsque l'on consulte son courrier électronique à distance). Le cryptographe propose des algorithmes à exécuter par les différentes parties pour satisfaire ces propriétés de sécurité, et le cryptanalyste y cherche des faiblesses.

Si par le passé il a pu être courant de chercher à dissimuler ou garder secret les
algorithmes cryptographiques afin de compliquer la tâche du cryptanalyste, on reconnaît désormais que ce genre de secret, qu'il faut nécessairement partager avec ses correspondants, est peu robuste, et que l'impression de « sécurité par l'obscurité» est largement illusoire. Selon le principe énoncé par Kerckhoffs en 1883, il convient qu'un système cryptographique utilise des algorithmes publics, qui n'utilisent eux-mêmes qu'une petite quantité d'information gardée secrète : la clef. Si la clef est compromise, elle peut être remplacée sans avoir à concevoir tout un nouveau système. De plus, cela permet à l'algorithme d'être évalué publiquement : si un algorithme cryptographique public a résisté longtemps aux tentatives d'attaques des cryptanalystes, on a davantage confiance en sa sécurité qu'en celle d'un algorithme secret qu'aucun analyste n'a eu l'occasion d'étudier.

## 1.2 Cryptographie moderne

### 1.2.1 Clef symétrique et clef publique

Jusque dans les années 1970, il était entendu que la clef cryptographique était un secret partagé entre l'expéditeur et le destinataire : les systèmes cryptographiques étaient alors toujours symétriques, au sens où la même clef servait au deux parties.

Pour assurer la confidentialité, par exemple, on utilisait des systèmes de chiffrement symétriques par blocs ; un tel système est la donnée deux algorithmes, $E_k$ et $D_k$, qui constituent des familles de permutations inverses l'une de l'autre des chaînes de bits d'une certaine longueur fixée (par exemple 64 ou 128 bits), indicées par la clef symétrique $k$. L'expéditeur, Alice, désirant faire parvenir à Bob, avec qui elle partage une clef secrète $k$, un certain message $m$ d'une façon qui préserve la confidentialité, envoie alors le chiffré (ou cryptogramme) $c = E_k(m)$, et Bob, à la réception, retrouve $m$ en déchiffrant $c$ : $m = D_k(c)$.

Pourvu que les algorithmes $E_k$ et $D_k$ aient de bonnes propriétés de sécurité, cette approche fonctionne très bien et est encore d'un usage courant aujourd'hui. Cependant, elle présente certains défauts, notamment du point de vue de la distribution de clef. Pour limiter l'impact de la compromission d'une clef, il est important que, dans une organisation où les individus s'échangent des messages chiffrés, chaque personne utilise une clef différente pour communiquer avec n'importe quelle autre. En cryptographie symétrique, cela impose d'utiliser une clef différente pour chaque paire d'individus : dans une organisation comptant plusieurs milliers de personnes, le nombre de clef à maintenir se compte en millions, et devient donc rapidement ingérable.

D'autre part, il y a des primitives de sécurité intéressantes qui ne sont pas réalisables en cryptographie symétrique. Par exemple, deux personnes partageant une clef commune $k$ peuvent s'assurer mutuellement de l'authenticité des messages qu'elle s'échangent (on peut pour cela utiliser la primitive cryptographique appelée *code d'authentification de message*, ou MAC). En revanche, elles ne peuvent pas convaincre un tiers de cette authenticité, puisque lui-même ne dispose pas du secret $k$. On ne peut donc pas espérer apposer une signature publiquement vérifiable sur un message en utilisant de la cryptographie symétrique.
Ces limites ont pu être dépassées avec l'avènement de la cryptographie à clef publique, proposée par Diffie et Hellman en 1976 [Hel76], et dont la première réalisation, peu de temps après, est due à Rivest, Shamir et Adleman [RSA78].

En cryptographie à clef publique, l'expéditeur et le destinataire n'ont pas besoin de partager de secret. Si Alice souhaite envoyer un message $m$ à Bob de manière confidentielle, elle lui demande sa clef publique $pk$, une information qui n'a pas besoin d'être gardée secrète, et applique un algorithme de chiffrement utilisant cette clef publique, pour obtenir un chiffré $c = Encrypt(pk, m)$. La clef publique, en revanche, ne permet pas de retrouver $m$ à partir de $c$. Il faut pour cela disposer de la clef privée $sk$ de Bob, que celui-ci garde secrète; il est donc le seul à pouvoir retrouver $m$ à partir de $c$, sous la forme $m = Decrypt(sk, m)$.

La cryptographie à clef publique simplifie ainsi grandement le problème de la distribution de clefs : dans une grande organisation, il suffit d'une paire de clef ($sk, pk$) par individu, et non plus d'une clef secrète par paire d'individus désirant communiquer : plus besoin de millions de clefs pour quelques milliers de personnes !

De plus, comme l'avaient observé Diffie et Hellman, la cryptographie à clef publique permet l'existence de signatures numériques. Dans ce contexte, Alice possède une clef de signature secrète $sk$ et une clef de vérification publique $pk$. La clef de signature permet de construire une signature $\sigma = \text{Sign}(sk, m)$ publiquement vérifiable à l'aide de $pk$ : $\text{Verify}(pk, \sigma, m) = \text{true}$ si et seulement si $\sigma$ est de la forme précédente. En revanche, la connaissance de $pk$ ne permet pas de retrouver $sk$, ni de produire des signatures. On a donc un système dans lequel une signature est « opposable aux tiers » ; depuis une dizaine d'années, elles ont d'ailleurs acquis la même valeur juridique en droit français que les signatures papier (Code civil, art. 1316-4).

Malgré ces nombreux avantages, la cryptographie à clef publique possède un inconvénient de taille : celui d'être, en pratique, sensiblement moins efficace que la cryptographie symétrique. C'est pourquoi de nos jours on utilise souvent l'une et l'autre en conjonction : pour chiffrer un long message, par exemple, on va souvent chiffrer une clef symétrique aléatoire (clef de session) avec une clef publique, et chiffrer le long message lui-même avec la clef de session, en utilisant un algorithme de chiffrement symétrique (c'est ce que l'on appelle le chiffrement hybride).

Les travaux présentés dans ce manuscrit relèvent tous de la cryptologie à clef publique.

### 1.2.2 Problèmes difficiles

Un algorithme de chiffrement à clef publique est une fonction à sens unique : la fonction qui à un message $m$ associe le chiffré $c = Encrypt(pk, m)$ doit être efficacement calculable pour que le chiffrement soit utilisable, mais elle doit également être difficile à inverser, puisqu'il ne doit pas être possible de retrouver publiquement $m$ à partir de $c$. Or on ignore s'il existe réellement des fonctions à sens unique : leur existence implique $P \neq NP$ (en tout cas si l'on interprète, comme on le fait habituellement, « efficace » comme signifiant « polynomial »), ce qui est peut-être le plus célèbre problème ouvert en informatique théorique.

Par conséquent, toute la cryptographie à clef publique est en fait heuristique ou
conjecturale. Pour construire des primitives cryptographiques à clef publique, on doit en général supposer que certains problèmes NP sont difficiles (non résolubles en temps polynomial), sans que l'on sache pour le moment établir un tel résultat. Citons quelques un des problèmes supposés difficiles les plus couramment utilisés dans la conception de systèmes cryptographiques à clef publique.

**Factorisation et RSA.** Le premier algorithme de chiffrement à clef publique, proposé par Rivest, Shamir et Adleman [RSA78], avait la forme suivante (que l'on appelle aujourd'hui « textbook RSA »).

La génération de clef tire au hasard deux grands nombres premiers $p$ et $q$, et les multiplie pour obtenir le module public $N = pq$. Il est par ailleurs choisi (généralement pas au hasard) un entier $e$ premier à $\varphi(N) = (p-1)(q-1)$ (et en particulier impair), appelé exposant public. La clef publique $pk$ est le couple $(N, e)$. La clef privée $sk$ est un entier $d$ inverse de $e$ modulo $\varphi(N)$.

Le chiffrement d'un message $m \in \mathbb{Z}_N^*$ s'obtient alors simplement en élevant à la puissance $e : c = m^e \bmod N$ ; et le déchiffrement est l'élévation à la puissance $d : m = c^d \bmod N$ en vertu du théorème d'Euler sur l'ordre multiplicatif des entiers modulo $N$.

Retrouver la clef privée $d$ en connaissant la clef publique $(N, e)$ est essentiellement équivalent à factoriser $N$. En effet, si l'on connait $p$ et $q$, on peut calculer $\varphi(N)$ et donc l'inverse de $e$ modulo $\varphi(N)$. Réciproquement, connaissant $d$ et $e$, on peut arriver à retrouver $\varphi(N)$, ce qui fournit ensuite la somme $p+q = N - \varphi(N) + 1$ et le produit $pq = N$ de $p$ et $q$, et donc révèle la factorisation.

Or jusqu'à présent, on ne connaît pas d'algorithme efficace (disons polynomial) pour factoriser le produit de deux grands nombres premiers : c'est l'un des problèmes supposés difficiles les plus importants en cryptographie. Le meilleur algorithme connu actuellement pour la factorisation de tels entiers date des années 1990 et est nettement sous-exponentiel : il s'agit du crible algébrique [LJMP90].

Notons que le caractère « à sens unique » du textbook RSA, c'est-à-dire l'impossibilité de retrouver $m$ à partir de $c$ (i.e. de calculer des racines $e$-ièmes modulo $N$) est a priori un problème plus facile que la factorisation, que l'on appelle problème RSA : si l'on sait factoriser $N$, on peut calculer des racines $e$-ièmes, mais on ne voit pas comment factoriser $N$ à l'aide d'un calcul de racines $e$-ièmes. Néanmoins, on ne connaît pas non plus d'algorithme meilleur que la factorisation pour calculer des racines $e$-ièmes : l'équivalence ou non du problème RSA avec la factorisation est un problème ouvert.

Le chiffrement textbook RSA n'est pas considéré comme sûr (le fait qu'il soit déterministe, par exemple, l'empêche de satisfaire la propriété de sécurité importante appelée indistinguabilité des chiffrés), mais l'on sait effectivement construire des systèmes de chiffrement, de signature, et beaucoup d'autres primitives cryptographiques qui sont sûrs si l'on suppose le problème RSA difficile, et ces primitives restent les plus utilisées aujourd'hui dans les applications.

On peut également effectuer la plupart de ces constructions en supposant seulement la factorisation difficile, en se fondant sur le système de Rabin (qui consiste essentiellement à choisir $e = 2$ dans ce qui précède), au prix d'une certaine perte de simplicité ou
d'efficacité.

Toute la seconde partie de cette thèse est consacrée à l'analyse de systèmes crypto-
graphiques (principalement des schémas de chiffrement ou de signature) dérivés de RSA
ou de certaines de ses variantes.

Logarithme discret et problèmes Diffie-Hellman. Dans leur article marquant le départ de la cryptographie à clef publique [Hel76], Diffie et Hellman n'ont pas construit de système de chiffrement, mais ils ont proposé une construction pour une primitive différente : l'échange de clef. Il s'agit pour Alice et Bob, communiquant sur un canal susceptible d'être écouté, de dériver un secret commun (par exemple une clef de session) d'une façon qui ne permette pas à un adversaire ayant espionné l'ensemble de la communication de découvrir ce secret.

La méthode proposé par Diffie et Hellman est la suivante. On suppose fixés une fois
pour toute un grand nombre premier $q$, et un générateur $g$ d'une grand sous-groupe $\mathbb{G}$
d'ordre premier $p$ de $\mathbb{Z}_q^*$. Alors Alice tire au hasard $x \in \mathbb{Z}_p$ et envoie à Bob l'élément $g^x$
de $\mathbb{G}$. De même Bob tire au hasard $y \in \mathbb{Z}_p$ et envoie à Alice $g^y$. Ils peuvent alors tous les
deux calculer la valeur commune $g^{xy} = (g^x)^y = (g^y)^x$.

L'adversaire espionnant la communication, Ève, peut alors casser le protocole si elle est capable de calculer $g^{xy}$ à partir de $g^x$ et $g^y$. Ce problème s'appelle CDH, ou *problème Diffie-Hellman calculatoire*. On ne connaît pas de meilleure attaque que celle consistant à retrouver $x$ à partir de $g^x$ et de même pour $y$, ce qui constitue le *problème du logarithme discret* (DL). L'algorithme le plus efficace connu pour le calcul du logarithme discret dans $\mathbb{Z}_q^*$ est d'une complexité équivalente à celle de la factorisation : c'est également un algorithme de crible algébrique.

De nombreuses primitives cryptographiques ont été construites sur la base du loga-
rithme discret, du problème CDH, de sa variante décisionnelle DDH (i.e. distinguer le
triplet ($g^x, g^y, g^{xy}$) de ($g^x, g^y, g^z$)) ou de variantes plus exotiques : outre l'échange de clef,
de nombreux schémas de chiffrement, de signature ou d'identification sont basés sur ces
problèmes difficiles.

Bien que le groupe $\mathbb{G}$ considéré originellement par Diffie et Hellman est dans $\mathbb{Z}_q^*$, le problème du logarithme discret et ses variantes ont un sens dans un groupe cyclique arbitraire, et la plupart des constructions se transposent immédiatement à un autre groupe sous réserve que ces problèmes y soient encore difficiles. Ce n’est pas toujours le cas (par exemple le logarithme discret est très facile dans un groupe tel que le groupe additif $\mathbb{Z}_p$ lui-même), ou parfois ce n’est pas plus intéressant que $\mathbb{Z}_q^*$ lui-même (par exemple travailler dans un sous-groupe cyclique d’un groupe algébrique linéaire n’apporte généralement rien en terme de sécurité). Mais le cas où $\mathbb{G}$ est un sous-groupe cyclique du groupe des points d’une courbe elliptique sur un corps fini, envisagé dès 1985 par Koblitz [Kob87] et Miller [Mil85], présente un intérêt tout particulier : on appelle *cryptographie par courbes elliptiques* la cryptographie construite sur les problèmes difficiles précédents dans un tel groupe.

La cryptographie par courbes elliptiques a d'abord été considérée avec une relative
méfiance, ou en tout cas prudence, par la communauté cryptologique. Des attaques
<table><caption>TABLE 1.1 : Comparaison des tailles de clefs pour RSA ou DL dans les corps finis d'une part, et DL dans les courbes elliptiques d'autre part, pour divers niveaux de sécurité [S+10a].</caption><thead><tr><td>Niveau de sécurité (bits)</td><td>RSA/Corps finis</td><td>Courbes elliptiques</td></tr></thead><tbody><tr><td>80</td><td>1248</td><td>160</td></tr><tr><td>96</td><td>1776</td><td>192</td></tr><tr><td>112</td><td>2432</td><td>224</td></tr><tr><td>128</td><td>3248</td><td>256</td></tr><tr><td>256</td><td>15424</td><td>512</td></tr></tbody></table>

comme celle de Menezes-Okamoto-Vanstone [MVO91, MOV93], réduisant le problème du logarithme discret sur certaines courbes elliptiques à celui dans le groupe multiplicatif d'un corps fini, ont suscité une certaine circonspection. Cependant, à mesure que les efforts pour casser le logarithme discret sur les courbes ordinaires se sont révélés infructueux, et que l'arithmétique sur ces courbes s'est faite plus efficace, les courbes elliptiques ont gagné la faveur des cryptographes. Mais c'est sans doute l'avènement de la cryptographie à base de couplages, utilisant la structure bilinéaire du groupe des points de certaines courbes, et permettant des constructions cryptographiques riches et totalement nouvelles (comme le chiffrement à base d'identité de Boneh-Franklin [BF01] ou l'échange de clef tripartite de Joux [Jou00]) qui a imposé les courbes elliptiques dans la communauté académique.

Depuis lors, comme le logarithme discret et les problèmes apparentés semblent toujours avoir une complexité exponentielle sur les courbes elliptiques là où elle est sous-exponentielle dans les corps finis (comme la factorisation et RSA), les courbes elliptiques ont suscité un vif intérêt industriel, en étant susceptible d'améliorer notablement les performances des applications tant logicielles que matérielles grâce à des clefs plus courtes (voir Tab. 1.1). L'usage des courbes elliptiques est désormais recommandé par des agences comme la NSA [NSA05].

La première partie de cette thèse est consacrée à diverses contributions à la cryptographie par courbes elliptiques.

*Autres problèmes.* De nombreux autres problèmes difficiles ont été envisagés pour la construction de systèmes cryptographiques à clef publique, depuis les problèmes de sac à dos (Merkle-Hellman [MH78]) ou des problèmes de décodage pour les codes linéaires (McEliece [McE78]) jusqu'à la résolutions de grands systèmes polynomiaux (cryptographie multivariée). Toutefois, la plupart de ces systèmes restent peu usités en pratique.

Une famille de problèmes qui s'est avérée particulièrement fructueuse pour la construction de primitives cryptographiques ces dernières années concerne les réseaux (les sous-groupes discrets de $\mathbb{R}^n$), où il peut s'agir par exemple de trouver un plus court vecteur non nul, ou bien un plus proche vecteur à un point donné de l'espace vectoriel ambiant, éventuellement à un certain facteur d'approximation près. Des constructions basées sur
ces problèmes ont été proposées pour la plupart des primitives dont on connaissait une
instanciation à base de couplages (chiffrement à base d'identité...), ainsi que pour de
toutes nouvelles primitives, notamment le chiffrement totalement homomorphe. Ces
constructions, même si elles sont parfois « asymptotiquement efficaces », utilisent en
général des paramètres trop grands pour envisager leur utilisation pratique, en particulier
dans les applications embarquées, mais elles revêtent une importance théorique certaine.
Par ailleurs, il existe un schéma de chiffrement à base de réseaux, NTRUEncrypt, ayant
reçu une normalisation ANSI pour des usages embarqués [ANSI X9.98].

Nous avons consacré quelques travaux à la cryptographie à base de réseaux, non
présentés dans ce manuscrit. On en mentionne certains au paragraphe §2.3.1.

1.2.3 Sécurité heuristique et sécurité prouvée

Quand peut-on dire qu'une certaine primitive cryptographique, par exemple un schéma de
chiffrement ou de signature, est sûre ? Aux débuts de la cryptographie à clef publique, la
réponse à cette question n'était pas claire. Par exemple, s'il est vrai que, sous l'hypothèse
que le problème RSA est difficile, il n'est pas possible en général de décrypter<fnref n="1" /> un chiffré
textbook RSA ; cependant, comme on l'a indiqué plus haut, ce schéma n'est pas considéré
comme sûr : il est ainsi possible de décrypter les chiffrés des messages courts, ou encore
de déterminer si deux chiffrés correspondent au même message clair.

En cherchant à porter une réponse assez générale à cette question, les cryptographes
des années 1980 ont été amenés à formaliser la cryptographie à clef publique en donnant
des définitions rigoureuses des propriétés de sécurité que l'on cherche à atteindre pour
différentes primitives, et en tentant de proposer des schémas satisfaisant ces propriétés.
Ainsi, pour le chiffrement, Goldwasser et Micali [GM82, GM84] ont dégagé la notion de
sécurité sémantique, ou d'indistinguabilité des chiffrés : un schéma de chiffrement satisfait
cette propriété lorsqu'un adversaire efficace ne peut obtenir aucun bit d'information sur
un message à partir d'un chiffré (ou de façon équivalente, étant donné un chiffré d'un
message parmi deux de son choix, il ne peut pas deviner duquel des deux messages c'est
le chiffré significativement mieux qu'en répondant au hasard : il est clair dit comme cela
qu'un chiffrement sémantiquement sûr ne peut pas être déterministe). Pour les signatures,
Goldwasser, Micali et Rivest [GMR84, GMR88] ont défini l'infalsifiabilité existentielle :
un adversaire ne possédant pas la clef de signature ne peut produire de signature sur
aucun nouveau message. Ces notions ont été largement reconnues par la suite comme
« les bonnes »,<fnref n="2" /> pourvu qu'il soit donné à l'adversaire des moyens suffisamment puissant
(l'accès adaptatif à un oracle de déchiffrement ou à un oracle de signature selon le

<footnote n="1">¹Rappelons que « déchiffrer » un cryptogramme consiste à retrouver le message clair quand on possède la clef privée, tandis que le « décrypter » consiste à faire de même sans la clef. Un algorithme de déchiffrement relève de la cryptographie, tandis qu’un algorithme de décryptement relève de la cryptanalyse.</footnote>

<footnote n="2">²À tel point que les cryptographes théoriciens considèrent parfois qu'une attaque qui ne met pas en défaut ces propriétés de sécurité « n'est pas une attaque », dans la mesure où elle ne fait pas partie du « cahier des charges » de la primitive correspondante, et ce même si l'attaque en question peut être un problème de sécurité dans un cas courant d'utilisation de la primitive. Une discussion un peu polémique de cette question a récemment été donnée par Koblitz et Menezes [KM11].</footnote>
cas). Et des études similaires ont été conduites pour toute sorte d'autres primitives cryptographiques.

Une fois définies rigoureusement les notions à atteindre, il a été possible de construire des schémas et de prouver qu'ils les atteignaient, sous réserve qu'un certain problème soit difficile. La forme que prennent ces démonstrations est celle d'une réduction de sécurité : on suppose qu'il existe un adversaire efficace (polynomial) cassant la propriété voulue du schéma avec probabilité non négligeable, et on montre que cet adversaire peut être utilisé comme « sous-programme » pour résoudre efficacement le problème supposé difficile. Mais comme le problème est supposé difficile, il ne peut être résolu efficacement, et l'adversaire ne peut donc pas exister ! De cette manière, les articles cités précédemment exhibent des schémas dont ils prouvent qu'ils satisfont les propriétés de sécurité voulues.

Cependant, la plupart des schémas « prouvés sûrs » proposés jusque dans les années 1990 (et un bon nombre de ceux proposés depuis lors également) étaient d'une efficacité limitée, ou en tout cas insuffisante pour les applications. L'industrie et le grand public se contentaient donc souvent de schémas ad hoc, c'est-à-dire conçus pour résister à un certain nombre d'attaques connues, mais dont il n'était pas pour autant établi qu'il satisfaisait les propriétés de sécurité souhaitables. Par exemple, pour construire des schémas de chiffrement ou de signature RSA palliant les attaques simples décrites plus haut et quelques autres de ce type, il a été proposé diverses constructions ad hoc appliquant la fonction RSA non pas au message lui-même, mais à son image par fonction de remplissage ou padding, pouvant par exemple consister à faire précéder le message d'un certain nombre de bits d'aléa. Ces techniques sont beaucoup plus efficaces que celles utilisés dans les schémas prouvés, mais il n'est pas démontré qu'elles sont sûres, et on y a souvent découvert des faiblesses (c'est d'ailleurs l'un des buts de cette thèse).

Cette division entre une cryptographie théorique prouvée sûre mais inefficace et une cryptographie pratique rapide mais à la sécurité incertaine s'est un peu réduite dans les années 1990, notamment grâce à l'introduction par Bellare et Rogaway du modèle de l'oracle aléatoire [BR93], dans lequel les fonctions de hachage cryptographiques sont modélisées par des fonctionnalités idéales répondant uniformément au hasard à chaque nouvelle requête. Des constructions bien plus efficaces qu'auparavant (et souvent aussi efficaces que les constructions ad hoc) ont pu être prouvées sûres dans ce modèle. Une telle preuve n'est pas aussi « solide » qu'une preuve dans le modèle standard, puisqu'il n'existe pas de véritable oracle aléatoire, et qu'instancier un oracle aléatoire par une fonction de hachage cryptographique réelle ne préserve la sécurité que de façon heuristique. Cependant, un schéma prouvé sur dans ce modèle est certainement bien préférable à un schéma ad hoc, et de fait, on n'a pas constaté d'attaque sérieuse sur ces nouvelles constructions contrairement à celles qui les ont précédées.

Jusque dans les années 1990, les systèmes cryptographiques à clef publique qui ont été consacrés par une agence de normalisation, ce qui est en général un préalable nécessaire à une large adoption industrielle, étaient pour ainsi dire tous des schémas ad hoc. S'agissant de RSA, on peut citer par exemple les paddings ad hoc [PKCS#1 v1.5], [ISO9796-1] et [ISO9796-2]. Depuis les années 2000, des schémas prouvés dans le modèle de l'oracle aléatoire ont également été normalisés (c'est le cas des paddings RSA comme
OAEP [BR94, ISO18033-2] pour le chiffrement et PSS [BR96, PKCS#1 v2.1] pour les signatures), et on peut espérer que cela ouvre la voie à leur déploiement dans les applications. Malgré tout, aujourd'hui encore, les schémas ad hoc demeurent les plus utilisés, du fait des cycles de renouvellement assez lents de beaucoup d'applications embarquées (comme les terminaux de paiement) et d'une certaine réticence des industriels à faire évoluer leur code cryptographique (ce qui est coûteux) en l'absence d'attaque directe sérieuse sur leur produit (et parfois même dans ce cas!).
<figure><img src="image_5.png" /></figure>
Présentation des travaux

Les travaux présentés dans ce manuscrit appliquent diverses techniques d’algèbre et d’arithmétiques aux deux versants de la cryptologie, construction et analyse, dans deux directions distinctes qui correspondent également aux deux familles de cryptosystèmes à clef publique sans doute les plus utilisés de nos jours : ceux fondés sur RSA d’un côté et sur le logarithme discret dans les courbes elliptiques (ou les jacobiennes de courbes algébriques) de l’autre.

Les travaux de construction, d'une part, concernent la cryptographie à base de courbes algébriques, et plus particulièrement, pour l'essentiel, le problème précis de l'encodage et du hachage à valeurs dans les courbes elliptiques ou les jacobiennes de courbes hyperelliptiques. Nous avons notamment étudié certaines propriétés quantitatives de diverses fonctions d'encodage vers les courbes, notamment la taille de leur image ou leur probabilité de collision, et obtenu une construction satisfaisante (c'est-à-dire indifférentiable d'un oracle aléatoire) de fonctions de hachage à partir de ces encodages. Ces résultats utilisent principalement des méthodes d'arithmétique des corps de fonctions, de géométrie des courbes et des surfaces, et de sommes de caractères. Toujours en cryptographie à base de courbes elliptiques, nous avons également travaillé sur une question d'implémentation : l'obtention de formules d'addition et de doublement sûres et efficaces.

Les travaux de cryptanalyse, d'autre part, ont porté sur divers cryptosystèmes fondés sur RSA, principalement des schémas de chiffrement et de signature. Nous avons en particulier obtenu et mis en œuvre une attaque pratique à messages choisis sur la norme ISO/IEC 9796-2:2002 de signatures RSA, utilisée notamment par les cartes et terminaux de paiement EMV. Sur cette même norme, nous avons également étudié et implémenté une attaque physique par fautes. Plus généralement, nous avons travaillé sur un nouveau type d'attaque par fautes sur les implémentations de schémas de signatures RSA utilisant les restes chinois. Par ailleurs, nous avons obtenu de nouveaux résultats sur la sécurité de la norme PKCS#1 v1.5 de chiffrement RSA, et une meilleure attaque sur les schémas RSA utilisant de petits sous-groupes. Les outils employés vont des techniques de calcul d'indice ou de réduction de réseaux à l'algorithmique efficace des polynômes de grand degré.
Le présent manuscrit rassemble ces différents travaux en deux parties selon cette double distinction : cryptographie par courbes elliptiques, puis cryptanalyse de schémas RSA. À ces deux familles de travaux s'ajoutent quelques résultats non présentés dans ce manuscrit mais mentionnés à la fin de ce chapitre, et portant sur des questions telles que le chiffrement totalement homomorphe.

## 2.1 Contributions à la cryptographie par courbes elliptiques

La première partie de ce manuscrit rassemble les travaux sur la cryptographie par courbes elliptiques et hyperelliptiques, notamment sur l'encodage et le hachage vers les courbes.

### 2.1.1 Hachage en temps constant vers les courbes (hyper)elliptiques

Le problème principal considéré dans cette partie, et présenté plus longuement au chapitre 3, est celui du hachage en temps constant vers les courbes elliptiques et hyperelliptiques. Comme mentionné plus haut, un certain nombre de protocoles cryptographiques utilisant des courbes elliptiques, notamment basés sur les couplages, nécessitent de pouvoir hacher dans le groupe $\mathbb{G}$ des points de la courbe : ils mettent en jeu une ou plusieurs fonctions de hachage $\mathfrak{H} : \{0, 1\}^* \to \mathbb{G}$ envoyant des chaînes de bits quelconques vers la courbe. Il en va ainsi du schéma de chiffrement basé sur l'identité de Boneh-Franklin [BF01], des signatures courtes de Boneh-Lynn-Schacham [BLS01] et beaucoup d'autres schémas de chiffrement, de signatures ou d'identification prouvés sûrs dans le modèle de l'oracle aléatoire pour ces fonctions $\mathfrak{H}$.

Cependant, s'il est souvent raisonnable d'instancier un oracle aléatoire à valeurs dans les chaînes de bits de longueur fixée par une fonction de hachage cryptographique, et que l'on peut aisément en déduire des oracles aléatoires à valeurs dans des groupes tels que $\mathbb{Z}_p^*$ ou $\mathbb{F}_q^*$, obtenir un oracle aléatoire à valeurs dans le groupe des points d'une courbe elliptique est en revanche plus délicat, et beaucoup de constructions naïves cassent totalement la sécurité des protocoles où elles sont utilisées.

Une construction dont on peut prouver qu'elle fonctionne effectivement est l'algorithme dit *try-and-increment* : partant d'une courbe elliptique $E$ sur $\mathbb{F}_q$ donnée par son équation de Weierstrass

$$E: y^2 = x^3 + ax + b$$

on se donne un oracle aléatoire $\mathfrak{h} : \mathbb{F}_q \times \{0, 1\}$ (ce que l'on peut instancier raisonnablement en pratique) et l'on procède comme suit pour calculer l'image $\mathfrak{H}(m)$ d'un message $m$. On commence par faire précéder $m$ d'un compteur $c$ de longueur fixe initialisé à zéro, et l'on évalue $(x, b) = \mathfrak{h}(c \| m)$. Alors si $x$ est l'abscisse d'un point dans $\mathbb{G} = E(\mathbb{F}_q)$, on retourne $(x, y)$ où $y$ est l'une des deux ordonnées correspondantes choisie en fonction du bit $b$; sinon, on incrémente le compteur $c$ et on recommence. Si la longueur du compteur est choisie suffisamment grande (supérieure à $\log_2 k$ où $k$ est le paramètre de sécurité), la fonction $\mathfrak{H}$ se comporte comme un oracle aléatoire, et peut donc être utilisée dans les protocoles nécessitant de hacher vers les courbes elliptiques.
Toutefois, la méthode try-and-increment a l'inconvénient que le temps de calcul de l'algorithme dépend du message à hacher. Cela peut permettre à un attaquant physique d'acquérir de l'information sur le message par chronométrage : c'est par exemple un problème particulièrement sérieux pour les protocoles d'authentification à base de mot de passe implémentés dans des dispositifs comme les passeports électroniques, où une telle attaque peut révéler complètement un mot de passe après tout juste quelques exécutions du protocole.

Pour cette raison, et parce que c'est sans doute plus efficace, on cherche à obtenir une construction de fonctions de hachages vers les courbes elliptiques qui s'exécute naturellement en temps constant. Une première étape dans cette direction consiste à construire des « encodages » en temps constant, c'est-à-dire des fonctions $F_q \to E(F_q)$ d'image grande et pouvant s'évaluer en temps constant (tous les cas connus de tels fonctions sont en fait des fonctions algébriques, ou au moins « algébriques par morceaux », de petit degré). Pour certaines courbes particulières, notamment supersingulières, il est assez facile d'exhiber de tels encodages, mais traiter le cas général est un problème qui, après avoir essentiellement été formulé par Schoof en 1985 [Sch85], est resté ouvert pendant une vingtaine d'années, jusqu'aux travaux de Skałba [Ska05] et surtout Shallue et van de Woestijne [SvdW06]. À la suite de ces articles, une succession assez rapide de résultats ([Ula07, Ica09, SH09, KLR10] et d'autres encore) a fourni une solution raisonnablement efficace au problème de l'encodage vers toutes les courbes elliptiques, et l'a étendu à un certain nombres de courbes de genre supérieur.

Partant d'un encodage $f: F_q \to E(F_q)$ et d'un oracle aléatoire $\mathfrak{h}: \{0,1\}^* \to F_q$, on obtient alors une fonction de hachage $\mathfrak{H}(m) = f(\mathfrak{h}(m))$ dont on peut montrer dans beaucoup de protocoles particuliers qu'elle peut remplacer un oracle aléatoire à valeurs dans $\mathbb{G} = E(F_q)$ en préservant la sécurité. Néanmoins, on peut trouver des protocoles pour lesquels ce n'est pas le cas, et il est de fait assez facile pour la plupart des encodages $f$ de distinguer efficacement la fonction $\mathfrak{H}$ d'un véritable oracle aléatoire, ce qui rend difficile l'obtention d'un résultat général de composition.

Plusieurs résultats de cette thèse, mentionnés dans les quatre sections qui suivent, ont pour objet d'éclairer ces questions et de combler certaines lacunes de ce programme.

### 2.1.2 Estimation de la taille de l'image des encodages en temps constant [FT10b]

Un premier résultat sur l'étude des encodages en temps constant, présenté au chapitre 4 de ce manuscrit, porte sur le calcul du nombre de points dans leur image. Ce nombre de point permet d'une part de constater qu'il existe des distingueurs simples entre la construction $\mathfrak{H}(m) = f(\mathfrak{h}(m))$ visée plus haut et un oracle aléatoire, et joue par ailleurs un rôle dans la qualité de la réduction de sécurité dans des constructions plus élaborées.

L'une des fonctions d'encodage en temps constant les mieux connues est par exemple celle d'Icart [Ica09]. Dans cet article, Icart montre que cette fonction $f$, lorsqu'elle est définie vers une courbe elliptique $E$ sur $F_q$, a une image de taille au moins $\#f(F_q) \ge q/4$. Cependant, cette borne inférieure est assez grossière, et il donne un argument heuristique
lui suggérant de conjecturer l'estimation bien plus précise :

$$ \left| \#f(\mathbb{F}_q) - \frac{5q}{8} \right| \le \lambda \sqrt{q} $$

pour une certaine constante $\lambda$ universelle. On donne dans cette thèse une preuve de ce résultat, qui repose sur l'interprétation de la fonction d'Icart comme une correspondance algébrique entre $E$ et la droite ainsi que sur le théorème de Chebotarev.

On montre également comment la méthode se généralise de manière naturelle aux autres encodages (y compris ceux dérivés des travaux de Shallue, van de Woestijne et Ulas, dont la structure géométrique est un peu plus compliquée puisqu'elle fait intervenir deux correspondances algébriques au lieu d'une), et ramène le calcul de la taille de l'image au calcul du groupe de Galois du corps de fonctions associé à l'encodage considéré (le corps de fonctions de la courbe donnant la correspondance) vu comme extension du corps de fonctions de la courbe elliptique. On effectue en particulier ce calcul pour la variante de la fonction d'Icart en caractéristique 2, et pour l'encodage « SWU simplifié » introduit en §3.5.4.

### 2.1.3 Hachage indifférentiable vers les courbes elliptiques [BCI$^{+}$10a]

Comme mentionné plus haut, la construction $\mathfrak{H}(m) = f(\mathfrak{h}(m))$, où $f$ est un encodage en temps constant vers le groupe $\mathbb{G}$ des points d'une courbe elliptique, ne peut pas génériquement remplacer un oracle aléatoire à valeurs dans $\mathbb{G}$ en préservant la sécurité dans le modèle de l'oracle aléatoire. Bien que cette construction soit suffisante dans un certain nombre de protocoles, on peut en trouver d'autres où la sécurité est perdue lorsque l'on utilise cette construction (nous donnons un tel exemple en §5.4.2).

Aussi avons-nous étudié en détails les conditions sur une fonction $F$ garantissant que la construction $\mathfrak{H}(m) = F(\mathfrak{h}(m))$ soit indifférentiable d'un oracle aléatoire au sens de Maurer [MRH04], ce qui fournit aussitôt un résultat générique de composition (dans les limites précisées par Ristenpart et al. [RSS11]). Nous avons dégagé la notion d'encodage admissible comme condition suffisante et pratique à établir pour obtenir l'indifférentiabilité : un encodage $F: S \to \mathbb{G}$ est admissible lorsqu'il est calculable en temps polynomial déterministe, efficacement échantillonnable (c'est-à-dire qu'il existe un algorithme efficace donnant pour tout $\mathbf{P} \in \mathbb{G}$ un antécédent par $F$ presque uniformément distribuée dans $F^{-1}(\mathbf{P})$) et régulier (c'est-à-dire que si $s$ est uniforme dans $S$, $F(s)$ est presque uniformément distribué dans $\mathbb{G}$).

Les encodages en temps constant $f: \mathbb{F}_q \to \mathbb{G}$ vers les courbes elliptiques ne sont pas eux-mêmes des encodages admissibles (sauf quelques exemples très particuliers, comme l'encodage de Boneh-Franklin vers une certaine courbe supersingulière), mais nous donnons deux méthodes permettant de construire un encodage admissible à partir d'un tel $f$.

Une première méthode consiste à considérer $F: \mathbb{F}_q \times \mathbb{Z}/NZ \to \mathbb{G}$ avec $N = \#\mathbb{G}$ donnée par $F(u, v) = \mathbf{P} + [v] \cdot \mathbf{G}$ où $\mathbf{G}$ est un générateur de $\mathbb{G}$ (supposé cyclique). L'admissibilité de $F$ est assez aisée à établir pour tous les encodages $f$ connus, mais la fonction de
hachage qui en résulte :

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + [\mathfrak{h}_2(m)] \cdot \mathbf{G} $$

(où $\mathfrak{h}_1, \mathfrak{h}_2$ sont des oracles aléatoires indépendants vers $\mathbb{F}_q$ et $\mathbb{Z}/N\mathbb{Z}$) est assez peu efficace, du fait de la multiplication de longueur pleine dans le groupe $\mathbb{G}$, qui est en général au moins un ordre de grandeur plus lente que l'évaluation de $f$.

Une seconde méthode plus efficace consiste à prendre $F: \mathbb{F}_q \times \mathbb{F}_q \to \mathbb{G}$ donnée par $F(u, v) = f(u) + f(v)$. La fonction de hachage qui en résulte est rapide, mais son indifférentiabilité (l'admissibilité de $F$) est plus délicate à établir. La difficulté principale consiste à montrer que la fonction $F$ est régulière. Dans un premier premier temps, nous n'avons pu obtenir cette régularité que pour la fonction d'Icart et sa variante en caractéristique 2. L'idée de base, assez simple, consiste à dire que l'ensemble des antécédents $(u, v)$ d'un point $\mathbf{P}$ forme une courbe dans le plan, en général irréductible et de genre borné, et donc de cardinal à peu près constant en dehors de quelques points exceptionnels d'après la borne de Hasse-Weil ; cependant, faire effectivement fonctionner cette idée de preuve nécessite de résoudre un certain nombre d'obstacles techniques assez délicat qui rendent l'extension à d'autres fonctions que celle d'Icart malaisée.

En tout état de cause, nous avons obtenu à ce stade une construction vraiment satisfaisante (sûre et efficace) de fonctions de hachage vers une large classe de courbes elliptiques :

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + f(\mathfrak{h}_2(m)) $$

avec $f$ l'encodage d'Icart et $\mathfrak{h}_1, \mathfrak{h}_2$ des oracles aléatoires indépendants à valeurs dans $\mathbb{F}_q$. Notre approche démontre que cette construction peut remplacer un oracle aléatoire à valeurs dans $\mathbb{G}$ dans essentiellement tout protocole le nécessitant.

### 2.1.4 Encodages bien distribués [FFS$^{+}$11]

Nous avons ensuite cherché à étendre cette construction satisfaisante à d'autres fonctions $f$ que celle d'Icart, et dans la mesure du possible à des courbes de genre supérieur.

Comme la méthode de preuve géométrique considérée précédemment s'avère impraticable, nous avons introduit une nouvelle approche de nature arithmétique, décrite au chapitre 6, permettant d'étudier les constructions de fonctions de hachage de la forme plus générale :

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + \cdots + f(\mathfrak{h}_s(m)) $$

où $f$ est l'un quelconque des encodages en temps constant proposés jusqu'ici, à valeurs dans les courbes elliptiques et même hyperelliptiques (dans ce dernier cas, on plonge la courbe dans sa jacobienne et l'addition est celle de la jacobienne). Nous sommes en mesure d'établir que cette construction se comporte convenablement (i.e. est indifférentiable d'un oracle aléatoire quand les $\mathfrak{h}_i$ sont des oracles aléatoires à valeurs dans $\mathbb{F}_q$) dès que $s$ est supérieur au genre de la courbe d'arrivée (autrement dit, $s \ge 2$ pour une courbe elliptique, $s \ge 3$ pour une courbe de genre 2, etc.). Nous retrouvons notamment les résultats précédents sur la fonction d'Icart comme cas particulier et avec de meilleures
constantes dans les inégalités, et ils s'étendent à tous les encodage en temps constant connus, y compris vers les courbes de genre supérieur.

Afin d'établir ces résultats, nous introduisons la notion d'encodage *bon distribué*, définie en termes d'un nouveau type de somme de caractères sur le groupe des points de la jacobienne de la courbe d'arrivée. Si $f$ est un encodage bien distribué, on obtient de manière formelle des bornes de régularité sur les fonctions de la forme $(u_1, \dots, u_s) \mapsto f(u_1) + \dots + f(u_s)$. Il suffit alors de montrer que les encodages en temps constant que l'on considère sont bien distribués, ce qui se ramène, à l'aide d'estimations classiques dues à Weil et Bombieri [Wei95, Bom66], à une propriété géométrique relativement simple (bien plus que celle considérée dans l'approche antérieure, car elle ne met en jeu que la courbe associée à l'encodage, et non des variétés de dimension plus grande).

Au final, nous obtenons des fonctions de hachages efficaces vers toutes les courbes elliptiques, et vers les jacobiennes de toutes les courbes hyperelliptiques pour lesquelles une fonction d'encodage est connue, avec en outre des bornes fines sur la qualité des réductions de sécurité.

### 2.1.5 Hachage et encodage vers les courbes hyperelliptiques impaires [FT10a]

Un autre champ d'investigation dans le domaine du hachage vers les courbes est celui de la construction des encodages en temps constant eux-mêmes. Nous y avons contribué en passant dans le travail décrit au chapitre 5, en proposant plusieurs encodages efficaces vers les courbes elliptiques sur les corps de caractéristique 3, et de façon plus substantielle dans celui présenté au chapitre 7.

Ce dernier travail porte sur la construction d'une nouvelle famille de fonctions d'encodages particulièrement simple et efficace vers une large classe de courbes hyperelliptiques de genres arbitrairement grand, à savoir les courbes de la forme :

$$H: y^2 = g(x)$$

où $g$ est un polynôme impair. Nous appelons ces courbes $H$ courbes hyperelliptiques impaires. On en trouve de fréquents exemples dans la littérature s'agissant du calcul efficace de leur fonction zêta ou de calculs efficaces de couplages, ce qui en fait de bons candidats à diverses applications cryptographiques.

Notre nouvel encodage est presque une bijection de $\mathbb{F}_q$ dans $H(\mathbb{F}_q)$, ce qui rend très simple l'obtention du hachage indifférentiable dans la jacobienne, en utilisant la propriété de bonne distribution évoquée précédemment. Cela permet en outre de construire une fonction d'encodage *injective* d'image grande dans la jacobienne, ce qui est utile pour des applications telles que le chiffrement El Gamal.

L'encodage a également l'avantage de se calculer très efficacement, sans division ni branchement, avec une seule exponentiation et quelques multiplications dans $\mathbb{F}_q$. Cela en fait sans doute l'encodage le plus rapide existant. De plus, il étend de manière significative la famille des courbes hyperelliptiques pour lesquelles un encodage est connu, qui se limitait jusqu'alors à un certain nombre de courbes de genre 2 et seulement quelques courbes isolées en genre plus grand.
2.1.6 Le modèle de Huff [JTV10]

Outre les questions de constructions de fonctions de hachage évoquées jusqu'ici, et
qui relèvent de la sécurité des protocoles, nous avons examiné au cours de cette thèse
un problème de cryptographie par courbes elliptiques relevant plus directement de
préoccupations d'implémentation : celui de l'obtention de formules d'addition et de
doublement rapides.

Les courbes elliptiques ont l'avantage sur les groupes multiplicatifs des corps finis
ou les groupes RSA d'avoir des tailles de paramètres plus petites à niveau de sécurité
égal. Cependant, l'arithmétique y est plus complexe : ainsi, pour une courbe en forme
de Weierstrass dont les points sont représentés en coordonnées de Jacobi, très utilisées
en pratique, une addition sur la courbe nécessite 16 multiplications dans le corps de
base, ce qui relativise le gain d'efficacité obtenu. De ce fait, de nombreuses « formes » de
courbes elliptiques ont été examinées dans le but de réduire ce nombre de multiplications
et d'obtenir une arithmétique plus efficace pour les applications cryptographiques. On
trouve ainsi dans la littérature des formules d'addition efficaces sur les courbes elliptiques
en forme d'intersection de Jacobi, de courbes de Hesse, de de Montgomery, de Doche-
Icart-Kohel, d'Edwards, etc.

Dans cette thèse, nous avons examiné un autre modèle introduit en 1948 par le
mathématicien Gerald Huff [Huf48], à l'origine pour l'étude d'un problème diophantien.
Nous avons pu déterminer l'ensemble des courbes elliptiques pouvant se mettre sous cette
forme (il s'agit des courbes ayant un sous-groupe isomorphe à $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ sur le corps
de base) et proposer des formules d'addition assez compétitives (en 11 multiplications
dans le corps de base, ce qui est proche du record détenu par les courbes d'Edwards),
possédant de plus des propriétés d'unification et d'indépendance en les paramètres de la
courbe utiles contre les attaques par canaux auxiliaires. En outre, nous avons obtenu des
formules relativement efficaces pour le calcul de couplages.

Ces résultats, ainsi que leurs extensions à des modèles analogues un peu plus généraux,
sont présentés au chapitre 8.

2.1.7 Problèmes ouverts et perspectives

On peut considérer la question de l'encodage et du hachage vers la plupart des courbes elliptiques comme réglée de façon assez satisfaisante. Elle a d'ailleurs déjà trouvé certaines applications industrielles, notamment dans le domaine des passeports électroniques [CT11, CGIP11, BCI10b]. Il subsiste néanmoins un champ assez vaste de questions à explorer, tant pratiques que théoriques.

Sur le plan pratique, on souhaiterait disposer de fonctions d'encodage aussi efficaces
que celle d'Icart ou que SWU simplifié pour toutes les courbes elliptiques, et notamment
des courbes de Barreto-Naehrig, très utiles dans les applications mettant en jeu des
couplages : le seul encodage connu vers ce type de courbes, celui plus général de Shallue
et van de Woestijne, est en effet sensiblement plus exigeant en calculs. De même, il serait
souhaitable de disposer d'algorithmes explicites efficaces et sans division, comme il en
existe pour la fonction d'Icart et pour notre encodage vers les courbes hyperelliptiques
impaires, pour le calcul de chacun des différents encodages en temps constant—afin de s'assurer qu'ils se calculent effectivement en temps constant ! Comme la résistance aux attaques physiques est l'un des buts de ces encodages, il est également souhaitable que les algorithmes ne contiennent pas de branchement conditionnel.

D'un point de vue beaucoup plus théorique, un problème intéressant serait de formuler et d'établir des résultats d'impossibilité dans un groupe générique : il ne devrait pas être possible de construire des fonctions de hachage comme on le fait dans cette thèse sans utiliser la représentation particulière du groupe d'arrivée. On peut par exemple raisonnablement conjecturer qu'il n'existe pas d'encodage admissible de $\{0, 1\}^{\text{poly}(N)}$ dans un groupe générique $G$ de cardinal $N$. Un tel résultat pourrait généraliser le résultat de Shoup sur la difficulté générique du logarithme discret [Sho97].

À mi-chemin entre le très pratique et le très théorique, on peut constater que les constructions de fonctions d'encodage dont on dispose semblent assez disparates et très ad hoc. On aimerait pouvoir dégager des principes généraux derrière la profusion de formules (ce qui permettrait peut-être en outre de construire des encodages vers de plus larges classes de courbes hyperelliptiques). Un premier pas dans cette direction a récemment été franchi par Couveignes et Kammerer [CK11], qui ont pu donner une description géométrique élégante et unifiée de trois fonctions d'encodage semblables à celle d'Icart, mais qui ne semblaient pas jusqu'alors naturellement liées. Cependant, cette approche ne semble pas se généraliser davantage, et en particulier elle n'admet pas d'analogue évident en genre supérieur. Une autre piste pourrait passer par le constat, dû à Ritzenthaler, que la correspondance algébrique associée à une fonction d'encodage (au moins de « type Icart ») est, d'après un résultat de Guralnick et al., un revêtement exceptionnel de la droite projective, et que ces revêtements admettent une classification combinatoire plus ou moins explicite.

Enfin, une autre voie à explorer sur le plan tant théorique que pratique est celui de la construction d'encodages injectifs. Nous en avons donné un exemple à valeurs dans les jacobiennes de courbes hyperelliptiques impaires, mais le problème de construire de tels encodages reste grand ouvert même pour la plupart des classes d'isomorphismes de courbes elliptiques. Le résultat le plus fort à ce jour dans cette direction est dû à Farashahi [Far11], qui obtient une fonction d'encodage injective vers toutes les courbes de Hesse (i.e. possédant un point d'ordre 3) sur les corps $\mathbb{F}_q$ avec $q \equiv 2 \pmod 3$), qui atteint environ la moitié des points. Il serait intéressant d'aller plus loin.

S'agissant par ailleurs des courbes de Huff, on peut noter que leur généralisation en caractéristique 2, présentée dans cette thèse, admet des formules d'addition et de doublement particulièrement efficaces, exhibées par Devigne et Joye [DJ11], qui en font le modèle binaire le plus rapide actuellement. On peut certainement espérer améliorer également les formules que nous donnons pour le calcul de couplages.

Sur une note plus mathématiquement curieuse, le modèle de Huff a ceci d'assez remarquable qu'il manifeste le fait que la courbe modulaire $X_1(4,2)$, qui paramétrise les courbes elliptiques contenant 8 points rationnels formant un sous-groupe isomorphe à $\mathbb{Z}/4\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$, est de genre 0. En effet, il existe un isomorphisme évident entre $\mathbb{P}^1$ et la famille des courbes de Huff, et comme ces courbes ont bien les 8 points rationnels requis,
on en déduit un morphisme non trivial $\mathbb{P}^1 \to X_1(4, 2)$. Il serait intéressant d'obtenir un modèle similaire (et si possible d'un niveau comparable de simplicité) associé à toutes les courbes modulaires $X_1(m, n)$ de genre 0. Le problème est, semble-t-il, partiellement ouvert, et pourrait avoir des applications pratiques à des questions comme l'optimisation pratique de l'algorithme de factorisation ECM.

## 2.2 Cryptanalyse de schémas fondés sur RSA

La seconde partie de ce manuscrit rassemble les travaux de cryptanalyse à l'encontre de divers schémas de signature et de chiffrement RSA, dont plusieurs paddings normalisés. Ces attaques sont pour certaines « en boîte noire » et pour d'autres des attaques physiques ou supposant un accès à un oracle spécifique.

### 2.2.1 Cryptanalyse pratique des signatures ISO/IEC 9796-2 et EMV [CNTW09]

Le premier de ces travaux, présenté au chapitre 9, concerne le padding ISO/IEC 9796-2 pour les signatures RSA avec récupération partielle de messages, utilisé notamment dans les cartes et terminaux de paiement EMV. Il se fonde sur une attaque antérieure en falsification existentielle par messages choisis, due à Coron, Naccache et Stern [CNS99], sur une version précédente de la norme [ISO9796-2], et qui avait conduit à sa révision.

Nous avons proposé un certain nombre d'améliorations algorithmiques importantes à la technique de Coron-Naccache-Stern, qui nous ont permis d'élaborer et de mener à bien une attaque pratique sur la version alors valide de la norme [ISO9796-2:2002].

Concrètement, notre attaque, comme celle de Coron-Naccache-Stern, est basée sur l'observation suivante de Desmedt et Odlyzko [DO85]. Considérons un padding RSA $\mu$ encodant des messages $m$ en des entiers $\mu(m)$ relativement courts et d'apparence aléatoire (par exemple $\mu = \text{SHA-1}$), et montrons comment on peut espérer falsifier les signatures RSA utilisant $\mu$ :

1. On se fixe une borne $B$ et on pose $\mathfrak{P} = \{p_1, \dots, p_\ell\}$ l'ensemble des nombres premiers inférieurs à $B$.

2. En essayant des messages $m_i$ au hasard, on fait en sorte d'en trouver $\tau \ge l + 1$ tels que $\mu(m_i)$ ait tous ses facteurs premiers dans $\mathfrak{P}$ (c'est-à-dire qu'il soit $B$-friable).

3. En résolvant le système linéaire dans $\mathbb{Z}/e\mathbb{Z}$ (e étant l'exposant public RSA) donné par les exposants $m_i$ dans la décomposition en facteur premier sur la base $\mathfrak{P}$, on peut alors exprimer l'un des $\mu(m_j)$ comme combinaison multiplicative des $\mu(m_i)$ pour $i \ne j$ : c'est analogue à l'étape d'algèbre linéaire des algorithmes de calcul d'indice ou de crible algébrique.

4. Cela fait, on peut obtenir par requête à un oracle les signatures des messages $m_i$ pour $i \ne j$, et en déduire la signature de $m_j$.
La complexité de cette attaque dépend principalement de la probabilité pour qu'un nombre de la taille de $\mu(m)$ soit B-friable, et de la complexité du test de friabilité : c'est pourquoi si $\mu(m)$ est trop grand, l'attaque peut être nettement plus lente que la factorisation du module RSA lui-même ! Par exemple, la probabilité qu'un nombre de 1024 bits soit $2^{25}$-friable est d'environ $2^{-247}$, donc l'attaque est inutile contre le Full Domain Hash avec un module de 1024 bits. En revanche, la probabilité qu'un nombre de 100 bits soit $2^{25}$-friable est d'environ 0.5%, de sorte que l'on peut aisément trouver $\ell \approx 2^{25}/\log(2^{25}) \approx 2^{21}$ tels nombres et mener l'attaque si $\mu$ se comporte comme un oracle aléatoire de longueur 100 bits !

Le padding $\mu$ défini par la norme ISO/IEC 9796-2 est de longueur pleine, donc l'attaque de Desmedt-Odlyzko ne peut pas s'appliquer directement. En revanche, Coron, Naccache et Stern ont observé que pour certains messages $m_i$ bien choisis, les entiers $t_i = (2^8 \cdot \mu(m_i)) \bmod N$ étaient assez courts (de taille $k_h + 16$ bits, où $k_h$ est la taille de sortie d'une fonction de hachage utilisé dans le padding), et il est facile d'adapter la technique précédente pour qu'elle s'applique aux $t_i$ plutôt qu'aux $\mu(m_i)$. Cela suffisait pour traiter le cas $k_h = 128$ prévue par la version d'origine de la norme. En revanche, la version révisée, imposant $k_h \ge 160$, était hors de portée d'une attaque pratique.

Notre travail a consisté à améliorer cette approche pour réussir à attaquer la version révisée. Les techniques employées sont les suivantes :

* l'utilisation d'un algorithme « par lots » dû à Bernstein [Ber04a] pour le test de friabilité, beaucoup plus efficace en pratique que l'algorithme naïf;

* l'utilisation d'une variante « avec grand premier » pour la friabilité, comme dans les implémentations modernes des algorithmes de factorisation ou de logarithme discret;

* un choix plus judicieux de constante à la place du $2^8$ dans la définition des $t_i$, qui permet de réduire leur taille de $k_h + 16$ à $k_h + 8$ environ;

* une recherche exhaustive sur les bits de poids faible et forts des valeurs de hachage mis en jeu, qui permet d'équilibrer les vitesses respectives du calcul de hachage et du test de friabilité.

On obtient avec ces différentes méthodes une accélération d'un facteur de plusieurs milliers, qui a permis d'attaquer [ISO9796-2:2002] en environ 1000 heures CPU (et deux jours réels) sur le « nuage » Amazon EC2, pour un coût total de 800 USD. Nous estimons qu'une attaque sur les signatures formatées selon les spécifications EMV, avec la même technique, aurait un coût de 45 000 USD sur les mêmes machines Amazon.

Cette nouvelle attaque a conduit à la publication d'une nouvelle révision de la norme ISO/IEC 9796-2 fin 2010 [ISO9796-2:2010].

### 2.2.2 Attaques par fautes sur les signatures EMV [CNT10]

Nous avons également étudié, dans un travail présenté au chapitre 10, la sécurité de la norme ISO/IEC 9796-2 et des spécifications EMV du point de vue des attaques physiques,
et plus précisément des attaques par fautes. Dans ce modèle, l'adversaire a accès au dispositif physique de signature (tel qu'une carte à puce), et est en mesure de le manipuler, à l'aide par exemple de pics électriques ou de flashes laser, pour provoquer des erreurs dans le calcul d'une signature.

Les attaques par fautes ont été introduites par Boneh, DeMillo et Lipton en 1997 [BDL01]. Ils ont montré notamment que les signatures RSA, en particulier lorsqu'elles sont calculées en utilisant le théorème des restes chinois (ce qui est presque toujours le cas en pratique, a fortiori dans les applications embarquées), sont très souvent vulnérables à ce type d'attaques. Une unique signature fautive produite par un dispositif non protégé peut suffire à révéler la clef secrète! Depuis lors, les attaques par fautes sur les signatures RSA et le contremesures à ces attaques ont constitué un sujet de recherche actif.

Cependant, l'attaque de Boneh et al. n'est pas directement applicable aux signatures ISO/IEC 9796-2 ou EMV, car une partie de l'information utilisée pour calculer ces signatures n'est pas accessible à l'adversaire (soit parce qu'elle est choisie aléatoirement au moment de la génération de signatures, soit parce qu'elle est retrouvée au moment de la vérification—sous réserve que la signature soit correcte!).

À CHES 2009, Coron, Joux, Kizhvatov, Naccache et Paillier [CJK+09] ont montré comment l'attaque de Boneh et al. pouvait malgré tout se généraliser aux signatures ISO/IEC 9796-2, pourvu que la partie du message encodé inconnue de l'adversaire soit suffisamment courte. L'idée est de retrouver les chaînes de bits inconnues comme des petites racines modulaires d'un polynôme multivarié, à l'aide de variantes multivariées de l'algorithme de Coppersmith [Cop97]. Toutefois, les restrictions de taille sur ces chaînes de bits inconnues sont très fortes, ce qui limite significativement la portée de cette attaque en pratique.

Notre contribution a consisté à proposer une approche très différente pour retrouver ces chaînes de bits inconnues, en utilisant plusieurs signatures fautives simultanément, et en en déduisant les parties inconnues avec techniques de réseaux orthogonaux introduites par Nguyen et Stern [NS97, NS98]. Nous montrons que cette approche permet de traiter aisément et très efficacement des chaînes inconnues d'une longueur pouvant aller jusqu'à la moitié de la taille du module.

Sur un exemple pratique de format de signature EMV dépassant de très loin ce qui pouvait être traité avec l'attaque précédente, nous montrons qu'avec notre nouvelle attaque, une dizaine de signatures fautives suffisent à retrouver la clef secrète en une fraction de seconde.

### 2.2.3 Attaques par fautes sur le module contre les signatures RSA [BNNT11a, BNNT11b]

Toujours en matière d'attaques par fautes contre les signatures RSA utilisant le théorème des restes chinois, nous avons proposé un nouveau type d'attaque, qui s'écarte de la tradition des attaques dérivées de celle de Boneh et al.. Ce travail est présenté au chapitre 11.

L'attaque par fautes traditionnelle de Boneh et al. consiste à perturber l'exponentiation
modulo l'un des deux facteurs du module RSA lors de la génération de signature, et en réponse à cette attaque, de nombreuses contremesures protègent l'exposant RSA privé. Nous montrons dans ce travail que l'on peut mettre en œuvre une attaque par fautes récupérant la clef privé en perturbant plutôt le module RSA public juste avant l'interpolation par les restes chinois. C'est une approche très différente, nécessite des contremesures a priori différentes.

Notre nouvelle attaque est, comme celle décrite précédemment, basée sur les techniques de réseaux orthogonaux de Nguyen et Stern, et nous montrons qu'elle est très efficace en pratique. Selon le modèle de fautes considéré, 5 à 45 signatures fautives suffisent à retrouver la clef privée en quelques secondes au plus. Dans sa version la plus simple, l'attaque nécessite que l'adversaire connaisse le module fautif, mais des versions plus sophistiquées fonctionnent même lorsque ce module fautif est inconnu, pourvu que les fautes respectent une forme raisonnable.

Tant l'attaque dans ses diverses variantes que les modèles de fautes considérés ont fait l'objet d'une validation expérimentale complète, à l'aide d'injections de fautes par laser sur un microcontrôleur 8 bits très commun.

### 2.2.4 Sur la sécurité du chiffrement PKCS#1 v1.5 [BCN+10]

Outre les signatures RSA, nous nous sommes également intéressés à la sécurité de certains paddings de *chiffrement* RSA. En particulier, dans le travail présenté au chapitre 12, nous avons proposé plusieurs nouvelles attaques sur le chiffrement PKCS#1 v1.5, un schéma dont l'utilisation est aujourd'hui déconseillée mais qui reste l'un des plus répandus en pratique. Nous obtenus deux résultats principaux.

Le premier peut être vu comme un prolongement théorique de l'attaque de Bleichenbacher [Ble98], qui permettait de décrypter n'importe quel chiffré PKCS#1 v1.5 à l'aide d'un nombre important (de l'ordre du million) de requêtes adaptatives à un oracle un peu particulier permettant de déterminer si un entier donné était un chiffré PKCS#1 v1.5 valide. De telles attaques « à oracle » sont parfois considérées comme peu problématiques en pratique, mais Bleichenbacher a montré que beaucoup d'implémentations du protocole SSL à l'époque se comportaient précisément comme un tel oracle, en délivrant un message d'erreur en cas de chiffré invalide, ce qui permettait de retrouver en pratique une clef de session SSL en quelques centaines de milliers ou quelques millions d'interaction avec le serveur. Notre nouvelle attaque utilise le même type d'oracle de validité, mais pour casser l'indistinguabilité des chiffrés plutôt que le caractère à sens unique de PKCS#1 v1.5. C'est en un sens plus faible, mais nous montrons qu'il suffit pour cela d'une unique requête à l'oracle plutôt que d'un million.

L'autre résultat cryptanalytique, assez différent, que nous obtenons, concerne la sécurité *broadcast* du chiffrement PKCS#1 v1.5, c'est-à-dire lorsqu'un même message est chiffré à destination de plusieurs utilisateurs. Ce type de modèle d'attaque avait été considéré par Håstad [Hås88] dans les années 1980 pour des paddings qui sont des fonctions polynômes déterministes du message à chiffrer. Nous étendons cette attaque au cas du padding probabiliste PKCS#1 v1.5. L'idée est de retrouver, connaissant plusieurs chiffrés d'un même message pour des destinataires différents, les aléas utilisés pour chacun
des chiffrés en même temps que le message. Nous utilisons pour cela une généralisation multivariée des techniques de Coppersmith, et particulièrement la méthode de Jochemsz et May [JM06] pour la construction du réseau à réduire. En particulier, nous pouvons au moins en principe retrouver un message clair de 936 bits en connaissant un chiffré PKCS#1 v1.5 pour chacun de 4 destinataires différents utilisant des clefs de 1024 bits.

### 2.2.5 Cryptanalyse de l'hypothèse RSA dans un sous-groupe [CJM+11]

Le dernier résultat exposé dans ce manuscrit, au chapitre 13, s'intéresse non pas à un schéma de signature ou de chiffrement RSA particulier, mais plutôt à la réfutation d'une hypothèse de sécurité liée à RSA et sur la base de laquelle Groth a proposé en 2005 la construction de diverses primitives cryptographiques [Gro05].

Groth considère des modules RSA particuliers de la forme :

$$N = p \cdot q = (2p'r + 1) \cdot (2q's + 1)$$

où $p, q, p'$ et $q'$ sont premiers, avec $p', q'$ relativement petits. Il existe alors un sous-groupe $\mathbb{Z}_N^*$ d'ordre $p'q'$ dont on publie un générateur $g$ avec le module $N$. Tout le reste, y compris l'ordre $p'q'$ de $g$, est gardé secret. L'hypothèse est alors que la fonction RSA est difficile à inverser dans $\mathbb{Z}_N^*$.

La meilleure attaque considérée par Groth (outre la factorisation de $N$) considérée sur cette hypothèse a pour complexité $O(p')$, ce qui lui permet de proposer un choix de paramètres dans lequel $p'$ et $q'$ sont de l'ordre de 100 bits.

Nous montrons qu'il existe en réalité une attaque permettant de factoriser $N$ connaisant le couple $(N, g)$ en temps $\tilde{O}(\sqrt{p'})$, ce qui casse le choix de paramètres précédents avec un nombre d'opération de l'ordre de $2^{50}$ : cela rend ce choix de paramètres potentiellement peu sûr, et a conduit Groth a réviser notablement à la hausse ses prescriptions.

Cette nouvelle attaque consiste essentiellement à appliquer l'algorithme « pas de bébé, pas de géant » dans le groupe $\mathbb{G}$, en utilisant un calcul de PGCD comme test d'égalité. Nous en fournissons une implémentation asymptotiquement efficace, utilisant notamment les techniques de Bostan et Schost pour l'évaluation et l'interpolation de polynômes de grand degré [BS05].

Il faut toutefois noter que, comme il se doit pour une variante du « pas de bébé, pas de géant », la complexité en espace de l'algorithme est aussi en $O(\sqrt{p'})$, ce qui limite la portée pratique de l'attaque. Imaginer une variante en espace constant, à la manière de l'algorithme lambda de Pollard, est un problème ouvert intéressant.

### 2.2.6 Factorisation de nombres RSA déséquilibrés partiellement connus [BNT09]

Un travail supplémentaire non présenté en détails dans ce manuscrit a concerné la factorisation des entiers RSA déséquilibrés (ayant un facteur beaucoup plus grand que l'autre), popularisés par un célèbre article de Shamir dans CryptoBytes [Sha95].

Plus précisément, il s'est agi de déterminer dans quelle mesure la connaissance d'une sous-chaîne de bits du grand facteur premier $p$ permet de factoriser un nombre RSA
déséquilibré $N = pq$ en temps polynomial. On peut interpréter cette question tant comme un problème théorique sur la complexité de la factorisation avec oracle que comme une préoccupation pratique sur la sécurité de RSA dans des implémentations physiques présentant des fuites ou pouvant faire l'objet d'attaques de type *cold boot*.

Nous établissons que la connaissance de $2[\log_2 q]$ bits consécutifs de $p$ suffisent à factoriser $N = pq$ en temps polynomial, quelle que soit la position de cette chaîne de bits. Par ailleurs, nous pouvons montrer que selon la position de la chaîne, un nombre plus faible de bits peut suffire.

Ces résultats sont à nouveau obtenus par une technique de type Coppersmith multiva-
rié. Plus précisément, nous montrons que la factorisation peut se ramener à la résolution
d'une équation quadratique de la même forme que celle de Boneh et Durfee [BD00], dont
on sait prouvablement retrouver les petites racines d'après les résultats de Bauer et Joux
[BJ07].

2.2.7 Falsification de signatures RSA à padding affine [CNT11a]

Un autre résultat un peu particulier, et non repris en détails dans ce manuscrit, a concerné
l'étude des paddings affines pour les signatures RSA. Ces paddings, sans doute les plus
simples qu'on puisse imaginer, encodent un message $m$ à signer par RSA sous la forme
$\mu(m) = \omega \cdot m + a$ pour certaines constantes $\omega, a$ données.

Parce qu'ils sont si simples, ils ont fait l'objet d'une étude assez approfondie depuis
les années 1980. Il s'avère que si la taille permise pour $m$ est une trop grande fraction de
la taille du module, on peut construire en temps polynomial des relations multiplicatives
entre les paddings de plusieurs messages, et donc construire des falsifications. Une série
de publications [dJC85, GM97, BCCN01] a progressivement réduit cette fraction de 2/3
à 1/2 puis 1/3, meilleure borne connue aujourd'hui. Cependant, on conjecture que cette
borne devrait pouvoir être encore améliorée, par exemple à 1/4 de la taille du module.
Ce problème reste ouvert depuis une décennie.

Sans fournir une solution à ce problème ouvert, nous donnons un certain nombre
de résultats nouveaux tentant d'avancer dans cette direction en tirant de nouvelles
 conséquences des méthodes de fractions continuées de Brier et al. [BCCN01].

Nous montrons tout d'abord qu'il est possible de falsifier en temps polynomial des signatures à padding affine sur des messages dont l'entropie est 1/4 de la taille du module, bien qu'ils soient de longueur plus grande que cette fraction. Nous montrons également comment on peut construire en pratique (en temps superpolynomial mais bien plus rapide que celui nécessaire à factoriser le module) une relation multiplicative entre quatre messages dont les longueurs sont respectivement 1/4, 1/4, 1/4 et 3/8 de la taille du module.

Nous montrons également que des falsifications à 1/4 peuvent être obtenues en temps
polynomial dans des scénarios particuliers, notamment lorsqu’il est possible de signer
avec deux paddings affines indépendants, ou encore lorsque les bits de poids fort du
module sont choisis de façon malveillante.
### 2.2.8 Problèmes ouverts et perspectives

Bien que la communauté cryptologique s'accorde à ne plus recommander que l'utilisation de paddings RSA prouvés, leur adoption industrielle reste modeste. Par conséquent, la cryptanalyse des paddings RSA ad hoc, bien qu'elle soit un sujet de recherche moins actif qu'il y a quelques années, demeure très pertinente, et nombre de schémas à la sécurité qu'on peut considérer « suspecte » n'ont pas encore fait l'objet d'attaques pratiques. On peut par exemple citer l'exemple des signatures PKCS#1 v1.5, qui à l'inverse du chiffrement PKCS#1 v1.5 ou des signatures ISO/IEC 9796-2 n'ont pas encore été cassées. Il est concevable que certaines des techniques utilisées dans cette thèse puissent s'y appliquer, même si l'angle d'attaque semblent pour le moment nous échapper.

S'agissant des attaques par fautes, les attaques sur le module que nous avons introduites ne peuvent avoir qu'un impact pratique limité sous leur forme actuelle car elles ne s'appliquent pas lorsque l'interpolation par les restes chinois s'effectue par la formule de Garner, ce qui est très souvent le cas dans les applications. Il serait très intéressant d'essayer de généraliser ce nouveau type d'attaques à une implémentation des signatures RSA protégée selon l'état de l'art. D'autre part, l'idée de perturber le module semble pouvoir s'appliquer de manière fructueuse à d'autres contextes, comme celui du logarithme discret aussi bien dans un corps fini que sur une courbe elliptique : il y a là aussi des pistes intéressantes à explorer.

## 2.3 Autres travaux

Nous avons par ailleurs mené quelques travaux qui ne s'inscrivent pas dans l'un des deux grands axes esquissés jusqu'ici, principalement parce qu'ils ne relèvent pas de l'un des deux problèmes difficiles que sont RSA et le logarithme discret dans les courbes elliptiques. Ces travaux ne sont pas présentés en détails dans ce manuscrit, mais nous en donnons les grandes lignes ci-après.

### 2.3.1 Chiffrement totalement homomorphe sur les entiers [CMNT11, CNT11b]

L'une des avancées théoriques les plus marquantes en cryptographie ces dernières années a certainement été la construction par Gentry en 2009 du premier schéma de chiffrement totalement homomorphe [Gen09].

Un schéma de chiffrement à clef publique est dit *homomorphe* lorsqu'il permet de calculer publiquement sur des données chiffrées. Par exemple le chiffrement « textbook RSA » est *multiplicativement homomorphe* car connaissant les chiffrés de deux entiers, on peut calculer un chiffré de leur produit (à savoir le produit des chiffrés) sans avoir à déchiffrer ni connaître la clef privée. De la même façon, le chiffrement de Paillier est *additivement homomorphe*, et ainsi de suite.

Dès 1978, alors que RSA avait à peine été inventé, Rivest, Adleman et Dertouzos [RAD78] ont imaginé qu'il puisse exister un schéma de chiffrement *totalement homomorphe*, c'est-à-dire pour lequel on puisse appliquer aux chiffrés non pas juste des additions
ou juste des multiplications, mais n'importe quelle fonction efficacement calculable. Un tel schéma aurait de nombreuses applications pratiques, permettant notamment de sous-traiter des calculs à des serveurs distants sans que ces serveurs n'acquèrent d'information sur les données traitées, qui peuvent rester confidentielles. Un tel scénario semblait attirant en 1978, et l'est encore davantage de nos jours à l'heure du *cloud computing*. Toutefois, Rivest et al. ne sont pas parvenus à exhiber de schéma sûr satisfaisant cette propriété, et le problème est resté ouvert pendant plus de 30 ans jusqu'aux travaux de Gentry.

Depuis, plusieurs schémas ont été proposés : celui original de Gentry, dont la sécurité est basée sur des problèmes de réseaux idéaux (ICP), celui de van Dijk, Gentry, Halevi et Vaikuntanathan [vDGHV10] reposant sur le problème du diviseur commun approché, et plus récemment quelques autres, notamment ceux dûs à Brakerski et Vaikuntanathan basés sur des problèmes de réseaux mieux compris comme LWE [BV11].

Cependant, aucun de ces schémas n'est utilisable en pratique. Les tailles de clefs nécessaires pour assurer un niveau de sécurité raisonnable, notamment s'agissant des deux premiers schémas, sont gigantesques (plus de $2^{60}$ bits au minimum pour le schéma de van Dijk et al., par exemple) et la complexité des opérations homomorphes sur les chiffrés sont du même ordre.

Compte tenu de l'importance à la fois théorique et pratique du chiffrement totalement homomorphe, beaucoup d'efforts ont été menés pour améliorer l'efficacité de ces schémas. S'agissant du schéma original de Gentry, on peut citer les travaux de Smart et Vercauteren [SV10] et de Stehlé et Steinfeld [SS10], qui ont abouti à la première implémentation véritable du schéma par Gentry et Halevi [GH11]. Cette implémentation est encore loin d'être « pratique », avec une clef publique de plusieurs giga-octets et environ une demi-heure pour multiplier les chiffrés de deux bits, mais elle représente une réelle avancée, en ce qu'elle concrétise pour la première fois le chiffrement totalement homomorphe.

Nos contributions à ce champ de recherche comprennent une amélioration importante du schéma de van Dijk et al. sur les entiers (réduisant en particulier considérable la taille des clefs) et sa première implémentation. Pour cela, il nous a fallu modifier l'algorithme de chiffrement pour en quelque sorte combiner multiplicativement des éléments de la clef publique et ainsi se contenter d'en avoir un nombre plus faible dans la clef. La preuve de sécurité de ce schéma modifié met en jeu des résultats sur le nombre de points des hypersurfaces algébriques de grande dimension sur les corps finis.

Certains de nos travaux en cours plus récents concernent également le chiffrement totalement homomorphe sur les entiers : nous obtenons une nouvelle réduction importante de la taille de clef, et nous sommes en mesure d'adapter à ce contexte les nouvelles techniques de Brakerski, Gentry et Vaikuntanathan sur le chiffrement homomorphe « sans bootstrapping » [BGV11].

### 2.3.2 Génération efficace et quasi-uniforme de nombres premiers [FT11]

Dans une direction très différente, nous nous sommes intéressés à la génération aléatoire efficace de nombres premiers. On peut imaginer diverses mesures d'un algorithme de génération de nombres premiers, telles que sa rapidité, sa précision (la probabilité qu'un
nombre produit soit en fait composé), ses propriétés statistiques (la régularité de sa distribution de sortie), la quantité d'aléa qu'il consomme pour produire un nombre premier (car de l'aléa de qualité n'est pas aisé à obtenir), etc.

On trouve dans la littérature un certain nombre de travaux consacrés à l'accélération de la génération de nombres premiers [BDL91, BD92, JPV00, JP06] ou à la construction d'algorithmes de génération fournissant en outre une preuve de primalité [Mau89, Mau95, Mih94].

Parmi ces articles, certains démontrent des bornes inférieures à l'entropie des distributions de sortie des algorithmes qu'ils considèrent, en utilisant généralement des conjectures très fortes sur la distribution des nombres premiers, comme la conjecture des *r*-uples de nombres premiers de Hardy-Littlewood. Toutefois, de telles bornes ne suffisent pas à assurer que la distribution obtenue soit statistiquement proche de la distribution uniforme sur les nombres premiers de la taille considérée; et l'on peut en fait généralement montrer avec l'aide des mêmes conjectures que la distance statistique entre ces distributions n'est pas négligeable (par exemple qu'elle est minorée par une constante : nous obtenons un résultat de ce type dans notre article).

Or certains protocoles cryptographiques particuliers, notamment basés sur l'hypothèse Strong RSA, requièrent explicitement des nombres premiers uniformes pour que les preuves de sécurité fonctionnent. D'autre part, pour une application plus commune comme la génération de module RSA, il semble intuitivement préférable d'avoir des facteurs premiers choisis sans biais, même si l'existence d'un biais statistique ou d'un distingueur explicite entre la distribution des nombres premiers et l'uniforme ne fournit pas immédiatement d'attaque sur la factorisation.

L'algorithme le plus simple imaginable pour générer des nombres premiers uniformes consiste simplement à tirer des entiers (disons impairs) de taille voulue uniformément au hasard, de tester leur primalité, et de recommencer si l'on a tiré un nombre composé. La distribution de sortie est exactement uniforme, mais cette méthode est relativement peu efficace et a surtout le défaut de consommer une quantité considérable d'aléa. À l'inverse, l'algorithme PRIMEINC étudié par Brandt et Damgård [BD92] (essentiellement, prendre un nombre au hasard et incrémenter jusqu'à tomber sur un premier) ou l'algorithme de Joye, Paillier et Vaudenay [JPV00, JP06] consomment peu d'aléa (seulement au début de l'algorithme) mais ont l'inconvénient d'avoir une distribution assez éloignée de l'uniforme.

Dans ce travail, nous introduisons un nouvel algorithme de génération de premiers
tentant de combiner les avantages de ces deux approches opposées : il consomme relative-
ment peu d'aléa, et la distance statistique à la distribution uniforme est prouvablement
contrôlée (en admettant l'hypothèse de Riemann étendue, ce qui est moins audacieux
que la conjecture de Hardy-Littlewood). Il a par ailleurs l'avantage d'être au moins aussi
rapide que l'algorithme de Joye-Paillier.

La majoration de la distance statistique utilise des majorations de sommes de carac-
tères de façon très analogue à nos travaux sur les encodages bien distribués (chapitre 6) :
il est intéressant de voir de telles techniques s'appliquer à des contextes aussi différents.
## 2.4 Liste des publications

### 2.4.1 Articles de revues

[BNNT11b] Modulus Fault Attacks Against RSA Signatures. É. Brier, D. Naccache, P. Q. Nguyen, M. Tibouchi. (JCEN)

[FFS$^{+11}$] Indifferentiable Deterministic Hashing to Elliptic and Hyperelliptic Curves. R. R. Farashahi, P.-A. Fouque, I. E. Shparlinski, M. Tibouchi, J. F. Vologloch. (Math. Comp.)

### 2.4.2 Articles de conférences

[CNTW09] Practical Cryptanalysis of ISO/IEC 9796-2 and EMV Signatures. J.-S. Coron, D. Naccache, M. Tibouchi, R.-P. Weinmann. (CRYPTO 2009)

[BNT09] Factoring Unbalanced Moduli with Known Bits. É. Brier, D. Naccache, M. Tibouchi. (ICISC 2009)

[CNT10] Fault Attacks Against EMV Signatures. J.-S. Coron, D. Naccache, M. Tibouchi. (CT-RSA 2010)

[BCN$^{+10}$] On the Broadcast and Validity-Checking Security of PKCS#1 v1.5. A. Bauer, J.-S. Coron, D. Naccache, M. Tibouchi, D. Vergnaud. (ACNS 2010, best student paper)

[JTV10] Huff's Model for Elliptic Curves. M. Joye, M. Tibouchi, D. Vergnaud. (ANTS-IX)

[FT10b] Estimating the Size of the Image of Deterministic Hash Functions to Elliptic Curves. P.-A. Fouque, M. Tibouchi. (LATINCRYPT 2010)

[BCI$^{+10a}$] Efficient Indifferentiable Hashing into Ordinary Elliptic Curves. É. Brier, J.-S. Coron, T. Icart, D. Madore, H. Randriam, M. Tibouchi. (CRYPTO 2010)

[FT10a] Deterministic Encoding and Hashing to Odd Hyperelliptic Curves. P.-A. Fouque, M. Tibouchi. (Pairing 2010)

[CJM$^{+11}$] Cryptanalysis of the RSA Subgroup Assumption from TCC 2005. J.-S. Coron, A. Joux, A. Mandal, D. Naccache, M. Tibouchi. (PKC 2011)

[CMNT11] Fully Homomorphic Encryption over the Integers with Shorter Public Keys. J.-S. Coron, A. Mandal, D. Naccache, M. Tibouchi. (CRYPTO 2011)

[BNNT11a] Modulus Fault Attacks Against RSA Signatures. É. Brier, D. Naccache, P. Q. Nguyen, M. Tibouchi. (CHES 2011)
### 2.4.3 Articles d'exposition et chapitres de livres

[CT11] Securing E-passports with Elliptic Curves. H. Chabanne, M. Tibouchi. (IEEE Security & Privacy)

[NT11] Lattice-Based Fault Attacks on Signatures. P. Q. Nguyen, M. Tibouchi. (Fault Analysis in Cryptography)

[Tib11] A Nagell Algorithm in Any Characteristic. M. Tibouchi. (Festschrift J.-J. Quisquater)

### 2.4.4 Prépublications

[CNT11a] Another Look at RSA Signatures With Affine Padding. J.-S. Coron, D. Naccache, M. Tibouchi.

[CNT11b] Optimization of Fully Homomorphic Encryption. J.-S. Coron, D. Naccache, M. Tibouchi.

[FT11] Close to Uniform Prime Number Generation With Fewer Random Bits. P.-A. Fouque, M. Tibouchi.
<figure><img src="image_6.png" /></figure>
# Contributions to Elliptic Curve Cryptography

## Overview

In 1985, Koblitz [Kob87] and Miller [Mil85] independently proposed the use of elliptic curves in public-key cryptography. The main advantage of elliptic curve systems stems from the absence of a subexponential-time algorithm to compute discrete logarithms on general elliptic curves over finite fields. Consequently, one can use an elliptic curve group that is smaller in size compared with systems based on either integer factorization or the discrete log problem in the multiplicative group of a finite field, while maintaining the same (heuristic) level of security.

Despite initial misgivings about the potential for unforeseen, mathematically sophisticated attacks, elliptic curve cryptography became widely accepted by the cryptographic community in the early 2000s [KKM11], particularly owing to the advent of pairing-based cryptography: protocols such as Joux's tripartite key agreement [Jou00] and especially the first efficient construction by Boneh and Franklin of an identity-based encryption scheme [BF01] quickly won cryptographers over. Since then, elliptic curves have also made important inroads in the industry, with the standardization of multiple elliptic curve-based cryptographic primitives [ISO18033-2, ANSI X9.62, ANSI X9.63] (ECDSA [FIPS186-3] in particular has been widely adopted), agencies weighing in favor of their use [NSA05], and new embedded applications such as secure e-passports mandating them [ICAO10].

This part of the thesis presents contributions to two areas of elliptic curve cryptography. On the one hand, we have used a range of tools from algebraic geometry and algebraic number theory to construct and analyze so-called encoding functions to elliptic curves, which are building blocks in a number of elliptic curve-based protocols (signatures, password-based authenticated key exchange, encryption and more). Chapters 3–7 are devoted to our work on this topic, some of which has found quick concrete applications. On the other hand, we have studied the more basic problem of finding representations
## 2. PRÉSENTATION DES TRAVAUX

of elliptic curves with efficient arithmetic operations, specifically looking into an elliptic curve model introduced by G.B. Huff in 1948. This work is covered in Chapter 8.
# Contents

## 3 Constant-Time Hashing to Elliptic and Hyperelliptic Curves

<table><tr><td>3.1 Introduction</td><td>37</td></tr><tr><td>3.1.1 Background</td><td>37</td></tr><tr><td>3.1.2 Outline</td><td>38</td></tr><tr><td>3.2 The Trivial Encoding: Totally Insecure</td><td>38</td></tr><tr><td>3.2.1 A naive construction</td><td>38</td></tr><tr><td>3.2.2 BLS signatures</td><td>39</td></tr><tr><td>3.3 Try-and-Increment: Why Constant Time Matters</td><td>40</td></tr><tr><td>3.3.1 The try-and-increment algorithm</td><td>40</td></tr><tr><td>3.3.2 Timing attacks on key agreement protocols</td><td>42</td></tr><tr><td>3.4 Encoding to Elliptic Curves</td><td>44</td></tr><tr><td>3.4.1 Main idea</td><td>44</td></tr><tr><td>3.4.2 A simple example</td><td>44</td></tr><tr><td>3.4.3 Beyond supersingular curves</td><td>45</td></tr><tr><td>3.5 Constructing Encodings to Elliptic Curves and Hyperelliptic Curves</td><td>46</td></tr><tr><td>3.5.1 The Shallue-van de Woestijne-Ulas approach</td><td>46</td></tr><tr><td>3.5.2 Icart's approach</td><td>50</td></tr><tr><td>3.5.3 Extensions to hyperelliptic curves</td><td>53</td></tr><tr><td>3.5.4 Our contributions</td><td>55</td></tr><tr><td>3.6 Further Work</td><td>59</td></tr><tr><td>3.6.1 Is the problem solved?</td><td>59</td></tr><tr><td>3.6.2 Applications</td><td>61</td></tr></table>
# 4 Estimating the Size of the Image of Constant-Time Encodings

<table><tr><td>4.1 Introduction</td><td>63</td></tr><tr><td>4.1.1 Icart's conjecture</td><td>63</td></tr><tr><td>4.1.2 Related work</td><td>64</td></tr><tr><td>4.1.3 Outline</td><td>64</td></tr><tr><td>4.2 Preliminaries</td><td>64</td></tr><tr><td>4.2.1 Icart's encoding</td><td>64</td></tr><tr><td>4.2.2 Icart's conjecture</td><td>65</td></tr><tr><td>4.3 Proof of Icart's Conjecture</td><td>65</td></tr><tr><td>4.3.1 Genericity of P</td><td>65</td></tr><tr><td>4.3.2 Applying Chebotarev</td><td>67</td></tr><tr><td>4.4 Analogue in Characteristic 2</td><td>68</td></tr><tr><td>4.5 Analogue for the Simplified Shallue-van de Woestijne-Ulas Encoding</td><td>70</td></tr><tr><td>4.6 Constructing Surjective Hash Functions</td><td>72</td></tr><tr><td>Appendices</td><td>72</td></tr><tr><td>4.A Galois Groups of Quartics</td><td>72</td></tr></table>

# 5 Indifferentiable Hashing to Elliptic Curves

<table><tr><td>5.1 Introduction</td><td>75</td></tr><tr><td>5.1.1 The random oracle model</td><td>75</td></tr><tr><td>5.1.2 Constructing good hash functions from elliptic curve encodings</td><td>76</td></tr><tr><td>5.1.3 Our goal</td><td>76</td></tr><tr><td>5.1.4 Our results</td><td>76</td></tr><tr><td>5.2 Admissible Encodings and Indifferentiability</td><td>78</td></tr><tr><td>5.2.1 Preliminaries</td><td>78</td></tr><tr><td>5.2.2 Admissible encodings</td><td>79</td></tr><tr><td>5.3 Our Main Construction</td><td>81</td></tr><tr><td>5.3.1 Admissibility of F(u, v) = f(u) + f(v)</td><td>82</td></tr><tr><td>5.3.2 Geometric interpretation of Icart's encoding</td><td>83</td></tr><tr><td>5.3.3 The square correspondence</td><td>86</td></tr><tr><td>5.3.4 Generalization to even characteristic</td><td>88</td></tr><tr><td>5.4 A More General Construction</td><td>89</td></tr><tr><td>5.4.1 Proof of Theorem 5.3</td><td>90</td></tr></table>
<table><tr><td>5.4.2 Discussion</td><td>92</td></tr><tr><td>5.5 Extensions</td><td>93</td></tr><tr><td>5.5.1 Extension to a prime order subgroup</td><td>93</td></tr><tr><td>5.5.2 Extension to bit string-valued random oracles</td><td>94</td></tr><tr><td>5.5.3 Extension to primes p = 2<sup>l</sup> - ω</td><td>94</td></tr><tr><td>Appendices</td><td>94</td></tr><tr><td>5.A Composition Lemmas</td><td>95</td></tr><tr><td>5.A.1 Generalized admissible encodings</td><td>95</td></tr><tr><td>5.A.2 Proof of Proposition 5.2</td><td>96</td></tr><tr><td>5.A.3 Proof of Proposition 5.3</td><td>96</td></tr><tr><td>5.A.4 Proof of Proposition 5.4</td><td>97</td></tr></table>

# 6 Well-Distributed Encodings

<table><tr><td>6.1 Introduction</td><td>99</td></tr><tr><td>6.1.1 Background</td><td>99</td></tr><tr><td>6.1.2 Our contributions</td><td>100</td></tr><tr><td>6.1.3 Outline</td><td>100</td></tr><tr><td>6.2 Well-Distributed Encodings</td><td>101</td></tr><tr><td>6.2.1 Character sums</td><td>101</td></tr><tr><td>6.2.2 Collision probability</td><td>101</td></tr><tr><td>6.2.3 Distribution of image sums</td><td>102</td></tr><tr><td>6.3 Character Sums on Curves</td><td>104</td></tr><tr><td>6.4 Examples of Well-Distributed Encodings</td><td>106</td></tr><tr><td>6.4.1 Icart's encoding</td><td>106</td></tr><tr><td>6.4.2 The Kammerer-Lercier-Renault encodings</td><td>109</td></tr><tr><td>6.4.3 The simplified SWU encoding</td><td>111</td></tr></table>

# 7 Hashing and Encoding to Odd Hyperelliptic Curves

<table><tr><td>7.1 Introduction</td><td>115</td></tr><tr><td>7.1.1 Hyperelliptic curve encodings.</td><td>115</td></tr><tr><td>7.1.2 Our contribution</td><td>116</td></tr><tr><td>7.2 Odd Hyperelliptic Curves</td><td>116</td></tr><tr><td>7.3 Our New Encoding</td><td>117</td></tr><tr><td>7.3.1 Definition</td><td>117</td></tr></table>
TABLE OF CONTENTS

<table><tr><td>7.3.2 Efficient computation</td><td>119</td></tr><tr><td>7.4 Mapping to the Jacobian</td><td>120</td></tr><tr><td>7.4.1 Injective encoding to the Jacobian</td><td>120</td></tr><tr><td>7.4.2 Indifferentiable hashing to the Jacobian</td><td>121</td></tr><tr><td>7.5 Conclusion</td><td>123</td></tr></table>

8 Huff's Model for Elliptic Curves

<table><tr><td>8.1 Introduction</td><td>125</td></tr><tr><td>8.1.1 Background</td><td>125</td></tr><tr><td>8.1.2 Our contributions</td><td>126</td></tr><tr><td>8.2 Huff's Model</td><td>127</td></tr><tr><td>8.2.1 Affine formulas</td><td>129</td></tr><tr><td>8.2.2 Projective formulas</td><td>130</td></tr><tr><td>8.2.3 Applicability</td><td>131</td></tr><tr><td>8.2.4 Universality of the model</td><td>132</td></tr><tr><td>8.3 Generalizations and Extensions</td><td>133</td></tr><tr><td>8.3.1 Faster computations</td><td>133</td></tr><tr><td>8.3.2 More formulas</td><td>134</td></tr><tr><td>8.3.3 Twisted curves</td><td>135</td></tr><tr><td>8.3.4 Binary fields</td><td>135</td></tr><tr><td>8.4 Pairings</td><td>136</td></tr><tr><td>8.4.1 Preliminaries</td><td>136</td></tr><tr><td>8.4.2 Pairing formulas for Huff curves</td><td>137</td></tr><tr><td>8.5 Conclusion and Perspectives</td><td>139</td></tr></table>
# Constant-Time Hashing to Elliptic and Hyperelliptic Curves

## 3.1 Introduction

This chapter introduces the general problem of constant-time hashing to elliptic and hyperelliptic curves, and discusses on several examples why this problem is of interest to elliptic curve-based cryptographic protocols. It also presents a round-up of the various constant-time encoding functions to elliptic and hyperelliptic curves that have been proposed to this day to obtain hash functions.

### 3.1.1 Background

Many elliptic curve-based cryptographic protocols require hashing to the elliptic curve group $G$: they involve one or more hash functions $H : \{0, 1\}^* \to G$ mapping arbitrary values to points on the elliptic curve.

For example, in the Boneh-Franklin identity-based encryption scheme [BF01], the public key for identity id $\in \{0, 1\}^*$ is a point $Q_{id} = H(id)$ on the curve. This is also the case in many other pairing-based cryptosystems including IBE and HIBE schemes [BZ04, GS02, HL02], signature and identity-based signature schemes [Bol03, BGLS03, BLS01, CC03, ZK02] and identity-based signcryption schemes [Boy03, LQ04].

Hashing into elliptic curves is also required for some passwords-based authentication protocols such as the SPEKE [Jab96] and PAK [BMP00] protocols, as well as various signature schemes based on the hardness of the discrete logarithm problem, like [CM05], when they are instantiated over elliptic curves.

In all of those cases, the hash functions are modeled as random oracles [BR93] in security proofs. However, it is not clear how such a hash function can be instantiated in practice. Indeed, random oracles to groups like $\mathbb{Z}_p^*$ can be easily constructed from random oracles to fixed-length bit strings, for which conventional cryptographic hash functions usually provide acceptable substitutes. On the other hand, constructing random oracles
to an elliptic curves even from random oracles to bit strings appears difficult in general, and some of the more obvious instantiations actually break security completely.

### 3.1.2 Outline

We first present in §3.2 a naive construction of an elliptic curve-valued hash function and show on a concrete example how this naive construction breaks security completely. We then introduce in §3.3 a better solution, the so-called “try-and-increment” hashing, that has satisfactory black-box security properties (it preserves random oracle proofs of security). However, it has the drawback of not running in constant time, which, as we shall see, can be a security concern for physical implementations. We then discuss in §3.4 another strategy for constructing elliptic curve-valued hash functions, based on simpler building blocks called encodings. In §3.5, we turn to the problem of constructing elliptic and hyperelliptic curve encodings. Finally, in §3.6, we discuss the extent to which those constructions actually solve our original hashing problem, as well as some practical applications that those constructions have found in the industry.

## 3.2 The Trivial Encoding: Totally Insecure

To gain a sense of why the construction of hash functions to elliptic curves requires some care, we first show how a naive construction can completely break the security of a protocol that uses it.

### 3.2.1 A naive construction

We would like to construct a hash function $\mathfrak{H} : \{0, 1\}^* \to \mathbb{G}$ to an elliptic curve group $\mathbb{G}$, which we can assume is cyclic of order $N$ and generated by a given point $\mathbf{G}$. The simplest, most naive way to do so is probably to start from an integer-valued hash function $\mathfrak{h} : \{0, 1\}^* \to \mathbb{Z}_N$ (for which reasonable instantiations are easy to come by) and to define $\mathfrak{H}$ as:

$$ \mathfrak{H}(m) = [\mathfrak{h}(m)] \cdot \mathbf{G}. \qquad (3.1) $$

This is, however, a bad idea on multiple levels.

On the one hand, it is easy to see why this will typically break security *proofs* in the random oracle model. Indeed, at some point in a random oracle model security reduction, the simulator will typically want to “program” the random oracle by setting some of its outputs to specific values. In this case, it will want to set the value $\mathfrak{H}(m)$ for some input $m$ to a certain elliptic curve point $\mathbf{P}$. However, if $\mathfrak{H}$ is defined as in (3.1), the simulator should actually program the integer-valued random oracle $\mathfrak{h}$ to satisfy $[\mathfrak{h}(m)] \cdot \mathbf{G} = \mathbf{P}$. In other words, it should set $\mathfrak{h}(m)$ to the discrete logarithm of $\mathbf{P}$ with respect to $\mathbf{G}$. But this discrete logarithm isn’t usually known to the simulator, and it cannot be computed efficiently: therefore, the security reduction breaks down.

On the other hand, it is often not clear how this problem translates into an actual security weakness for a protocol using the hash function $\mathfrak{H}$: one could think that it is
* KeyGen(): Pick $x \stackrel{\$}{\leftarrow} \mathbb{Z}_p$ as the private key, and $\mathbf{P} \leftarrow [x] \cdot \mathbf{G}$ as the public key.

* Sign($m, x$): Compute the signature as $\mathbf{S} \leftarrow [x] \cdot \mathcal{H}(m)$.

* Verify($m, \mathbf{S}, \mathbf{P}$): accept if and only if $e(\mathcal{H}(m), \mathbf{P}) = e(\mathbf{S}, \mathbf{G})$.

<caption>Figure 3.1: The BLS signature scheme.</caption>

mostly an artifact of the security proof. Nevertheless, a construction like (3.1) makes it
possible for an adversary to compute the discrete logarithm of $\mathcal{H}(m)$ whenever $m$ is known,
which certainly feels uncomfortable from a security standpoint. We demonstrate below
that this discomfort is entirely warranted, by showing that the Boneh-Lynn-Shacham
signature scheme [BLS01]—certainly the best-known signature scheme that involves
hashing to elliptic curves—becomes completely insecure if the hash function involved is
instantiated as in (3.1).

3.2.2 BLS signatures

Proposed by Boneh, Lynn and Shacham in 2001 [BLS01], the BLS signature scheme remains the efficient scheme which achieves the shortest signature length to this day: about 160 bits at the 80-bit security level<fnref n="1" />.

It is also quite simple to describe. The public parameters are a cyclic group $G$ of
prime order $p$ endowed with a symmetric<fnref n="2" /> non degenerate bilinear pairing $e : G \times G \to G_T$
and a hash function $\mathcal{H} : \{0, 1\}^* \to G$. A generator $\mathbf{G}$ of the group is also fixed.

In practical instances, $G$ is a prime order subgroup in the group of rational points
of a supersingular elliptic curve over a finite field and $e$ is the modified Weil pairing.
Therefore, we denote the group law of $G$ additively, and that of $G_T$ multiplicatively. The
signature scheme is then as described in Figure 3.1. Boneh, Lynn and Shacham prove
that if the Computational Diffie-Hellman problem is hard in $G$, then this scheme is secure
(in the usual sense of existential unforgeability under chosen message attacks) when $\mathcal{H}$ is
modeled as a random oracle.

Now consider the case when $\mathcal{H}$ is instantiated as in (3.1). Then, the signature on a
message $m$ can be written as:

$$
\mathbf{S} = [x] \cdot \mathcal{H}(m) = [x\mathfrak{h}(m)] \cdot \mathbf{G} = [\mathfrak{h}(m)] \cdot \mathbf{P}
$$

<footnote n="1">¹The security reduction for the original scheme is not tight (and cannot be made tight, much like that of the Full Domain Hash [Cor00]), so one may want to increase signature size accordingly for really conservative security. However, Katz and Wang [KW03] showed how a slight modification of the scheme makes it possible to obtain tight security without increasing the signature size.</footnote>

<footnote n="2">²As was noted in the journal version of the BLS paper [BLS04b], the construction extends in a
natural way to an asymmetric pairing, and hence to non supersingular pairing-friendly curves, such as
Barreto-Naehrig elliptic curves [BN05]. See also [SV07] for a discussion of how this affects the precise
statement of the security result.</footnote>
and hence, one can forge a signature on any message using only publicly available data!
There is no security left at all when using the trivial hash function construction.

A slightly less naive variant of the trivial construction consists in defining $\mathfrak{H}$ as:

$$ \mathfrak{H}(m) = [\mathfrak{h}(m)] \cdot \mathbf{Q} \qquad (3.2) $$

where $\mathbf{Q}$ is an auxiliary public point distinct from the generator $\mathbf{G}$ and whose discrete logarithm $\alpha$ with respect to $\mathbf{G}$ is not published. Using this alternate construction for $\mathfrak{H}$ thwarts the key-only attack described above against BLS signatures. However, the scheme remains far from secure. Indeed, the signature on a message $m$ can be written as:

$$ \mathbf{S} = [x\mathfrak{h}(m)] \cdot \mathbf{Q} = [\alpha x\mathfrak{h}(m)] \cdot \mathbf{G} = [\mathfrak{h}(m)] \cdot \alpha \mathbf{P}. $$

Now suppose an attacker knows a valid signature $\mathbf{S}_0$ on some message $m_0$. Then the signature $\mathbf{S}$ on an arbitrary $m$ is simply:

$$ \mathbf{S} = \left[ \frac{\mathfrak{h}(m)}{\mathfrak{h}(m_0)} \right] \cdot [\mathfrak{h}(m_0)] \cdot [\alpha] \mathbf{P} = \left[ \frac{\mathfrak{h}(m)}{\mathfrak{h}(m_0)} \right] \cdot \mathbf{S}_0 $$

where the division is computed in $\mathbb{Z}_p$. Thus, even with this slightly less naive construction, knowing a single valid signature is enough to produce forgeries on arbitrary messages: again, a complete security break down.

## 3.3 Try-and-Increment: Why Constant Time Matters

A classical construction of a hash function to elliptic curves which does work (and one variant of which is suggested by Boneh, Lynn and Shacham in the original short signatures paper [BLS01]) is the so-called “try-and-increment” algorithm. We present this algorithm here, as well as some of the limitations that explain why different constructions may be preferable.

### 3.3.1 The try-and-increment algorithm

Consider an elliptic curve $E$ over a finite field $\mathbb{F}_q$ of odd characteristic. It admits a Weierstrass equation of the form:

$$ E: y^2 = x^3 + ax^2 + bx + c \qquad (3.3) $$

for some $a, b, c \in \mathbb{F}_q$. A probabilistic way of constructing points on $E(\mathbb{F}_q)$ is then to pick a random $x \in \mathbb{F}_q$, check whether $t = x^3 + ax^2 + bx + c$ is a square in $\mathbb{F}_q$, and if so, let $y = \pm\sqrt{t}$ and return $(x, y)$. If $t$ is not a square, then $x$ is not the abscissa of a point on the curve: then, one can pick another $x$ and try again, and if so, let $y = \pm\sqrt{t}$ and return $(x, y)$. If $t$ is not a square, then $x$ is not the abscissa of a point on the curve: then, one can pick another $x$ and try again.

It is an easy consequence of the Hasse bound [Has36] on the number of points on $E(\mathbb{F}_q)$ (namely, $|\#E(\mathbb{F}_q) - q - 1| \le 2\sqrt{q}$) that the success probability of a single try is
very close to 1/2. Indeed, if we denote by $\chi_q$ the non trivial quadratic character of $\mathbb{F}_q^*$, extended by 0 to $\mathbb{F}_q$ as usual, we have:

$$ \#E(\mathbb{F}_q) = 1 + \sum_{x \in \mathbb{F}_q} (1 + \chi_q(x^3 + ax^2 + bx + c)) = q + 1 + \sum_{x \in \mathbb{F}_q} \chi_q(x^3 + ax^2 + bx + c) $$

On the other hand, the success probability $\varpi$ of a single iteration of this point construction algorithm is the proportion of $x \in \mathbb{F}_q$ such that $\chi_q(x^3 + ax^2 + bx + c) = 1$ or 0, namely:

$$ \varpi = \frac{\alpha}{2q} + \frac{1}{q} \sum_{x \in \mathbb{F}_q} \frac{1 + \chi_q(x^3 + ax^2 + bx + c)}{2} $$

where $\alpha \in \{0, 1, 2, 3\}$ is the number of roots of the polynomial $x^3 + ax^2 + bx + c$ in $\mathbb{F}_q$. This gives:

$$ \varpi = \frac{1}{2} + \frac{\#E(\mathbb{F}_q) - q - 1 + \alpha}{2q} = \frac{1}{2} + O\left(\frac{1}{\sqrt{q}}\right) $$

Now this point construction algorithm can be turned into a hash function based on an $\mathbb{F}_q$-valued random oracle $\mathfrak{h} : \{0, 1\}^* \to \mathbb{F}_q$. To hash a message $m$, the idea is to pick the $x$-coordinate as, essentially, $\mathfrak{h}(m)$ (which amounts to picking it at random once) and carry out the point construction above. However, since one should also be able to retry in case the first $x$-coordinate that is tried out is not the abscissa of an actual curve point, we rather let $x \leftarrow \mathfrak{h}(c \| m)$, where $c$ is a fixed length counter initially set to 0 and incremented in case of a failure. Since there is a choice of sign to make when taking the square root of $t = x^3 + ax^2 + bx + c$, we also modify $\mathfrak{h}$ to output an extra bit for that purpose: $\mathfrak{h} : \{0, 1\}^* \to \mathbb{F}_q \times \{0, 1\}$. This is the try-and-increment algorithm, described more precisely in Algorithm 3.1 (and called MAPTOGROUP in [BLS01]$^3$). The failure probability after up to $k$ iterations is about $2^{-k}$ by the previous computations, so choosing the length of the counter $c$ to be large enough for up to $k \approx 128$ iterations, say, is enough to ensure that the algorithm succeeds except with negligible probability.

Boneh, Lynn and Shacham prove that this construction can replace the random oracle $\mathfrak{H} : \{0, 1\}^* \to E(\mathbb{F}_q)$ in BLS signatures without compromising security. In fact, it is not hard to see that it is *indifferentiable* from such a random oracle, in the sense of Maurer, Renner and Holenstein [MRH04]: this ensures that this construction can be plugged in many protocols$^4$ requiring a random oracle $\mathfrak{H} : \{0, 1\}^* \to E(\mathbb{F}_q)$ while preserving random oracle security proofs—this will be discussed in more details in Chapter 5.

Nevertheless, there are various reasons why Algorithm 3.1 is not a completely satisfying construction for hash functions to elliptic curves. There is arguably a certain lack of

<footnote>$^3$Boneh et al. were in fact concerned with hashing to a supersingular curve of characteristic 3 of the form $y^2 = x^3 + 2x \pm 1$. In this case, it was later observed by Barreto and Kim [BK01] that picking $y$ at random and solving the resulting Artin-Schreier equation for $x$ was actually much more efficient, as that equation can be seen as a linear system over $\mathbb{F}_3$. But the basic principle of trying a value and incrementing a counter in case of failure remains the same.</footnote>

<footnote>$^4$Not necessarily all protocols, as conventional wisdom would have it until recently, but at least all protocols with single-stage security games, as clarified by Ristenpart, Shacham and Shrimpton [RSS11].</footnote>
<caption>**Algorithm 3.1** The try-and-increment algorithm.</caption>

1: **procedure** TRYANDINCREMENTHASH($m$) ▷ hash to $E: y^2 = x^3 + ax^2 + bx + c$
2:     $c \leftarrow 0$ ▷ $c$ is represented as a $\lceil \log_2 k \rceil$-bit bit string
3:     $(x, b) \leftarrow \mathfrak{h}(c \| m)$ ▷ $\mathfrak{h}$ is a random oracle to $\mathbb{F}_q \times \{0, 1\}$
4:     $t \leftarrow x^3 + ax^2 + bx + c$
5:     **if** $t$ is a square in $\mathbb{F}_q$ **then**
6:         $y \leftarrow (-1)^b \cdot \sqrt{t}$ ▷ define $\sqrt{t}$ as the smaller square root wrt some ordering
7:         **return** $(x, y)$
8:     **else**
9:         $c \leftarrow c + 1$
10:        **if** $c < k$ **then**
11:            **goto** step 3
12:        **end if**
13:        **end if**
14:        **return** $\perp$
15: **end procedure**

mathematical elegance in the underlying idea of picking $x$-coordinates at random until a correct one is found, especially as the length of the counter, and hence the maximum number of trials, has to be fixed (to prevent collisions). More importantly, this may have adverse consequences for the security of physical devices implementing a protocol using this construction: for example, since the number of iterations in the algorithm depends on the input $m$, an adversary can obtain information on $m$ by measuring the running time or the power consumption of a physical implementation.

### 3.3.2 Timing attacks on key agreement protocols

A concrete situation in which this varying running time can be a serious issue is the case of embedded devices (especially e-passports) implementing an elliptic curve-based Password-Authenticated Key Exchange (PAKE) protocol.

PAKE is a method for two parties sharing a common low-entropy secret (such as a four-digit PIN, or a self-picked alphabetic password) to derive a high-entropy session key for secure communication in an authenticated way. One of the main security requirements is, informally, that an attacker should not be able to gain any information about the password, except through a brute force online dictionary attack (i.e. impersonating one of the parties in the protocol and attempting to authenticate with each password, one password at a time), which can be prevented in practice by latency, smart card blocking and other operational measures. In particular, a PAKE protocol should be considered broken if a *passive* adversary can learn any information about the password.

Now consider the PAKE protocol described in Figure 3.2, which is essentially Jablon's Simple Password-base Exponential Key Exchange (SPEKE) [Jab96] implemented over an elliptic curve, except with a random salt as suggested in [Jab97]. The public parameters are an elliptic curve group $\mathbb{G}$ of prime order $p$ and a hash function $\mathfrak{H}: \{0, 1\}^* \to \mathbb{G}$.
<figure><img src="image_7.png" /><figcaption>Figure 3.2: A randomized variant of the SPEKE protocol.</figcaption></figure>

The two parties share a common password $\pi$, and derive a high-entropy $K \in G$ using Diffie-Hellman key agreement in $G$ but with a variable generator $G \in G$ computed by hashing the password.

But if the hash function $\mathcal{H}$ is instantiated by the try-and-increment construction and an eavesdropper is able to measure the running time of one of the parties, he will find different running times or different power traces depending on how many trials it takes to find a suitable $x$-coordinate in the computation of $\mathcal{H}(s\|\pi)$. Since it takes a single iteration with probability close to $1/2$, an execution of the protocol provides at least one bit of information about $\pi$ to the adversary (and about $-\sum_{k \ge 1} 2^{-k} \log_2(2^{-k}) = 2$ bits on average).

This leads to a so-called “partition attack”, conceptually similar to those described by Boyd et al. in [BMN01]: the adversary can count the number of iterations needed to compute $\mathcal{H}(s\|\pi_0)$ for each password $\pi_0$ in the password dictionary, keeping only the $\pi_0$'s for which this number of iterations matches the side-channel measurement. This reduces the search space by a factor of at least 2 (and more typically 4) for each execution of the protocol, as the running times for different values of $s$ are independent. As a result, the eavesdropper can typically reduce his search space to a single password after at most a few dozen executions of the protocol!

A rather inefficient countermeasure that can be considered is to run all $k$ iterations of the try-and-increment algorithm every time. However, even that is probably insufficient to thwart the attack: indeed, the usual algorithm (using quadratic reciprocity) for testing whether an element of $\mathbb{F}_q$ is a square, as is done in Step 5 of Algorithm 3.1, also has different running times depending on its input. This can be provide information to the adversary as well, unless this part is somehow tweaked to run in constant time, which seems difficult to do short of computing the quadratic character with an exponentiation and making the algorithm prohibitively slow with $k$ exponentiations every time. In principle, padding the quadratic reciprocity-based algorithm with dummy operations might provide a less computationally expensive solution, but implementing such a countermeasure securely seems quite daunting. A construction that naturally runs in constant time would certainly be preferable.
## 3.4 Encoding to Elliptic Curves

### 3.4.1 Main idea

A natural way to construct a constant-time hash function to an elliptic curve $E$ would be use, as a building block, a suitable function $f: \mathbb{F}_q \to E(\mathbb{F}_q)$ that can be efficiently computed in constant time<fnref n="5" />. Then, combining $f$ with a hash function $h: \{0, 1\}^* \to \mathbb{F}_q$, we can hope to obtain a well-behaved hash function to $E(\mathbb{F}_q)$.

Of course, not all such functions $f$ are appropriate: for example, when $q = p$ is prime, the trivial encoding described in §3.2 is essentially of that form, with $f: u \mapsto [\hat{u}] \cdot \mathbf{G}$ (and $u \mapsto \hat{u}$ any lifting of $\mathbb{F}_p$ to $\mathbb{Z}$).

On the other hand, if $f$ is a bijection between $\mathbb{F}_q$ and $E(\mathbb{F}_q)$ whose inverse is also efficiently computable, then the following construction:

$$ \mathfrak{H}(m) = f(h(m)) \qquad (3.4) $$

is well-behaved, in the sense that if $h$ is modeled as a random oracle to $\mathbb{F}_q$, then $\mathfrak{H}$ can replace a random oracle to $E(\mathbb{F}_q)$ in any protocol while preserving proofs of security in the random oracle model. Indeed, contrary to what happens in the case of the trivial encoding (where programming the random oracle would require computing discrete logarithm), a simulator can easily choose a value $\mathfrak{H}(m_0) = \mathbf{P}_0$ by setting $h(m_0) = f^{-1}(\mathbf{P}_0)$. More generally, such a construction is, again, indifferentiable from a random oracle to $E(\mathbb{F}_q)$ (and even reset indifferentiable in the sense of Ristenpart et al. [RSS11]).

The same holds if $f$ induces a bijection from $\mathbb{F}_q \setminus T$ to $E(\mathbb{F}_q) \setminus W$ for some finite or negligibly small sets of points $T, W$.

More generally, we will be considering cases where $f$ is not necessarily an efficiently invertible bijection but only a so-called *samplable* mapping, in the sense that for each $\mathbf{P} \in E(\mathbb{F}_q)$, one can compute a random element of $f^{-1}(\mathbf{P})$ in probabilistic polynomial time.

### 3.4.2 A simple example

It was actually one of the first papers requiring hashing to elliptic curves, namely Boneh and Franklin's construction [BF01] of identity-based encryption from the Weil pairing, that introduced the first practical example of a hash function of the form (3.4). Boneh and Franklin used elliptic curves of a very special form:

$$ E: y^2 = x^3 + b \qquad (3.5) $$

over a field $\mathbb{F}_q$ such that $q \equiv 2 \pmod 3$. In $\mathbb{F}_q$, $u \mapsto u^3$ is clearly a bijection, and thus each element has a unique cube root. This makes it possible, following Boneh and

<footnote n="5">⁵It is probably superfluous to point out that, by constant time, we mean “whose running time does not depend on the input” (once the choice of parameters like $E$ and $\mathbb{F}_q$ is fixed), and not $O(1)$ time in the sense of complexity theory.</footnote>
Franklin, to define a function $f$ as:

$$f: \mathbb{F}_q \to E(\mathbb{F}_q) \qquad (3.6)$$

$$u \mapsto ((u^2 - b)^{1/3}, u). \qquad (3.7)$$

In other words, instead of picking the $x$-coordinate and try to deduce the $y$-coordinate by taking a square root (which may not exist) as before, we first choose the $y$-coordinate and deduce the $x$-coordinate by taking a cube root (which always exists).

Obviously, the function $f$ is a bijection from $\mathbb{F}_q$ to all the finite points of $E(\mathbb{F}_q)$. In particular, this implies that $\#E(\mathbb{F}_q) = 1 + \#\mathbb{F}_q = q + 1$; thus, $E$ is supersingular (and hence comes with a computable symmetric pairing). This also means that $f$ satisfies the conditions mentioned in the previous section; therefore, construction (3.4) can replace the random oracle $\mathfrak{H}$ required by the Boneh-Franklin IBE scheme, or any other protocol proved secure in the random oracle model. And it can also easily be computed in constant time: it suffices to compute the cube root as an exponentiation to a fixed power $\alpha$ such that $3\alpha \equiv 1 \pmod{q-1}$.

Note that in fact, the group $\mathbb{G}$ considered by Boneh and Franklin isn't $E(\mathbb{F}_q)$ itself, but a subgroup $\mathbb{G} \subset E(\mathbb{F}_q)$ of prime order. More precisely, the cardinality $q$ of the base field is chosen of the form $6p - 1$ for some prime $p \neq 2,3$. Then $E(\mathbb{F}_q)$ has a unique subgroup $\mathbb{G}$ of order $p$ (and index 6), which is the group actually used in the scheme. Hashing to $\mathbb{G}$ rather than $E(\mathbb{F}_q)$ is then easy:

$$\mathfrak{H}(m) = f'(\mathfrak{h}(m)) \quad \text{where} \quad f'(u) = [6] \cdot f(u). \qquad (3.8)$$

The encoding $f'$ defined in that way isn't injective but it is samplable: indeed, to compute a random preimage of some point $\mathbf{P} \in \mathbb{G}$, we can simply compute the six points $\mathbf{Q}_i$ such that $[6] \cdot \mathbf{Q}_i = \mathbf{P}$, and return $f^{-1}(\mathbf{Q}_i)$ for a random index $i$. Using that observation, Boneh and Franklin prove that construction (3.8) can replace the random oracle to $\mathbb{G}$ in their IBE scheme. More generally, it is easy to see that it is indifferentiable from a random oracle in the sense of Chapter 5.

### 3.4.3 Beyond supersingular curves

The previous example suggests that a sensible first step towards constructing well-behaved constant-time hash functions to elliptic curves is to first obtain mappings $f: \mathbb{F}_q \to E(\mathbb{F}_q)$ that are computable in deterministic polynomial time and samplable, and admit constant-time implementations. We will refer to such mappings as *encoding functions* or simply *encodings*<fnref n="6" />. Note that despite what the name might suggest, there is no assumption of injectivity for those mappings.

It turns out that constructing encodings to elliptic curves beyond special cases such as 3.6 is far from an easy task. In fact, Schoof mentioned the presumably easier problem

<footnote n="6">⁶We do not attempt to formulate a very precise definition for those terms, as we will be using them rather informally. Precise statements will be made about more restricted (and properly defined) classes of encodings in later chapters.</footnote>
of constructing a single non-identity point on a general elliptic curve over a finite field (the Hasse bound ensures that there is always such a point over fields of cardinality at least 5) as open in his 1985 paper on point counting [Sch85], and little progress was made on this problem before the 2000s.

The first significant result in that direction was obtained by Schinzel and Skałba in 2004 [SS04]. They exhibited one non-identity point on the elliptic curve (3.5) without any assumption on the cardinality of the base field. A part of their result is as follows.

**Theorem 3.1** ([SS04, Th. 1]). Let $\mathbb{F}_q$ be a finite field of characteristic at least 5 and b an element of $\mathbb{F}_q$ such that $b^3 + 72^3 \neq 0$. Further set:

$$y_1 = -2^{-9}3^{-5}b^3 + 2^{-6}3^{-3}b^2 - 2^{-3}b - 3$$

$$y_2 = 2^{-8}3^{-6}b^3 - 2^{-5}3^{-3}b^2 + 2^{-2}3^{-1}b + 2$$

$$y_3 = \frac{b^6 - 2^5 3^2 b^5 + 2^6 3^6 b^4 - 2^{10} 3^6 5 b^3 + 2^{12} 3^8 5 b^2 - 2^{16} 3^{11} b + 2^{18} 3^{12}}{2^8 3^5 (b + 72)^3}$$

$$y_4 = \frac{b^9 - 2^3 3^2 7 b^8 + 2^9 3^5 b^7 - 2^{13} 3^7 b^6 + 2^{13} 3^8 29 b^5}{2^{10} 3^5 (b^2 - 72b + 72^2)^3}$$

$$+ \frac{-2^{17} 3^{12} b^4 + 2^{19} 3^{13} 7 b^3 + 2^{22} 3^{14} b^2 + 2^{24} 3^{17} b + 2^{27} 3^{18}}{2^{10} 3^5 (b^2 - 72b + 72^2)^3}.$$

Then for at least one $j = 1, 2, 3, 4$, $y_j^2 - b$ is a cube $x^3$ in $\mathbb{F}_q$, and hence $(x, y)$ is a non-identity rational point on the elliptic curve $y^2 = x^3 + b$.

This rather contrived result only shows how to construct a single non trivial $\mathbb{F}_q$-point on the special curve $E: y^2 = x^3 + b$ in deterministic polynomial time. However, further research in recent years by Skałba and others led to the construction of more or less practical encoding functions to all elliptic curves in recent years. Several approaches have been proposed. We introduce the main ones in the next section.

## 3.5 Constructing Encodings to Elliptic Curves and Hyperelliptic Curves

### 3.5.1 The Shallue-van de Woestijne-Ulas approach

*Skałba's theorem.* The first construction of a constant-time encoding function to a large class of elliptic curves is due to Skałba in 2005 [Ska05], who was trying to generalize the results of his earlier paper with Schinzel [SS04]. He was able to prove a result of the following form.

**Theorem 3.2** ([Ska05, Th. 1]). Let $\mathbb{F}_q$ be a finite field of characteristic at least 5, and $g(x) = x^3 + ax + b \in \mathbb{F}_q[x]$ a polynomial over $\mathbb{F}_q$ with $a \neq 0$. Then there exists non constant rational functions $X_1, X_2, X_3, U \in \mathbb{F}_q(x)$ such that the following identity holds in $\mathbb{F}_q(t)$:

$$g(X_1(t^2))g(X_2(t^2))g(X_3(t^2)) = U(t)^2. \qquad (3.9)$$
The rational functions $X_i$ and $U$ are given explicitly, but since they are quite large (the product $X_1X_2X_3$ is a rational function of degree 26 with coefficients that are several hundred bits long), we omit them here. However, let us recall how, from identity (3.9), one can readily deduce an encoding function to the elliptic curve:

$$E: y^2 = x^3 + ax + b. \qquad (3.10)$$

For any value $u \in \mathbb{F}_q$ such that $u^2$ is not a pole of the $X_i$'s, we see that the product $g(X_1(u^2))g(X_2(u^2))g(X_3(u^2))$ is a square in $\mathbb{F}_q$, which implies that at least one of the three values $g(X_i(u^2))$ is a quadratic residue. If $i$ is the smallest index for which that is the case, we can then set:

$$(x, y) = (X_i(u^2), \sqrt{g(X_i(u^2))})$$

and $(x, y)$ is then a non trivial point in $E(\mathbb{F}_q)$.

This defines an encoding to any elliptic curve over finite fields of characteristic $\neq 2, 3$, except those of $j$-invariant 0, so this is already “almost” a complete solution.

A caveat is that no unconditional polynomial deterministic algorithm is known for computing square roots in general finite fields. However, this is never really a problem in cryptographic applications, where it is usually possible to either make mild congruential assumptions on the cardinality of the field (such that $q \neq 1 \pmod 8$), in which case computing square roots is easy) or assume that a fixed quadratic nonresidue is known (and then use an algorithm such as Tonelli-Shanks [Sha73]). And a later result by van de Woestijne ensures that, in this particular setting, the square root can actually be computed in deterministic polynomial time without any restriction on $q$ (see below).

Still, depending on the particular case under consideration, it may be somewhat difficult to write down a constant-time implementation. And the rational functions $X_i$ are complex enough to make them unattractive for practical applications.

*Shallue and van de Woestijne's construction.* In a paper presented at ANTS in 2006, Shallue and van de Woestijne [SvdW06] proposed a more general construction along the same lines, that applies to all elliptic curves.

Consider the general Weierstrass equation for an elliptic curve in odd characteristic (possibly including 3):

$$E: y^2 = x^3 + ax^2 + bx + c.$$

Let further $g(x) = x^3 + ax^2 + bx + c \in \mathbb{F}_q[x]$. It is possible to construct an encoding function to $E(\mathbb{F}_q)$ like before from a rational curve on the three-dimensional variety:

$$V: y^2 = g(x_1)g(x_2)g(x_3)$$

(which, geometrically, is the quotient of $E \times E \times E$ by $(\mathbb{Z}/2\mathbb{Z})^2$, where each non trivial element acts by $[-1]$ on two components and by the identity on the third one). Indeed, if $\phi: \mathbb{A}^1 \to V$, $t \mapsto (x_1(t), x_2(t), x_3(t), y(t))$ is such a rational curve, then for any $u \in \mathbb{F}_q$ that is not a pole of $\phi$, at least one of $g(x_i(u))$ for $i = 1, 2, 3$ is a quadratic residue, and we obtain a corresponding point on $E(\mathbb{F}_q)$ like before.
Then, Shallue and van de Woestijne show how to construct such a rational curve $\phi$ (and in fact a large number of them). They first obtain an explicit rational map $\psi: S \to V$, where S is the surface of equation:

$$S: y^2 \cdot (u^2 + uv + v^2 + a(u + v) + b) = -g(u)$$

which can also be written, by completing the square with respect to $v$, as:

$$[y(v + \frac{1}{2}u + \frac{1}{2}a)]^2 + [\frac{3}{4}u^2 + \frac{1}{2}au + b - \frac{1}{4}a^2]y^2 = -g(u).$$

Now observe that for any fixed $u \in \mathbb{F}_q$, the previous equation defines a curve of genus 0 in the $(v, y)$-plane. More precisely, it can be written as:

$$z^2 + \alpha y^2 = -g(u) \qquad (3.11)$$

with $z = y(v + \frac{1}{2}u + \frac{1}{2}a)$ and $\alpha = \frac{3}{4}u^2 + \frac{1}{2}au + b - \frac{1}{4}a^2$. This is a non degenerate conic as soon as $\alpha$ and $g(u)$ are both non zero (which happens for all $u \in \mathbb{F}_q$ except at most 5), and then admits a rational parametrization, yielding a rational curve $A^1 \to S$. Composing with $\psi$, we get the required rational curve on $V$, and hence an encoding, provided that $q > 5$.

Two steps in this algorithm are potentially non deterministic: taking the square root required to map a point of $V(\mathbb{F}_q)$ to $E(\mathbb{F}_q)$ (like in Skałba's case), and finding one point on the non degenerate conic defined by (3.11) (which is necessary to obtain a parametrization). Van de Woestijne actually proves in his thesis that both of these computations can be carried out in deterministic polynomial time: on the one hand, he gives a deterministic variant of the Tonelli-Shanks algorithm which, given $a_1, a_2, a_3, b \in \mathbb{F}_q$ such that $a_1a_2a_3 = b^2$, returns an index $i \in \{1, 2, 3\}$ and a square root of $a_i$; on the other hand, he proves that a solution of $ax^2 + by^2 = c$ can be found in deterministic polynomial time for any $a, b, c \in \mathbb{F}_q^*$.

Combining all of those results, we obtain an encoding function to any elliptic curve over a field of odd characteristic with $q > 5$ elements. Moreover, Shallue and van de Woestijne show that the image of this encoding contains at least $(q - 4)/8$ points in $E(\mathbb{F}_q)$.

They also give a variant of this approach for elliptic curves over binary fields. For example, to obtain an encoding to the binary curves with Weierstrass equation:

$$E: y^2 + a_3y = x^3 + a_4x + a_6$$

they construct rational curves on the following threefold:

$$V: y^2 + a_3y = g(x_1) + g(x_2) + g(x_3)$$

where $g(x) = x^3 + a_4x + a_6$. Indeed, since the map $y \mapsto y^2 + a_3y$ is $\mathbb{F}_2$-linear, elements of $\mathbb{F}_q = \mathbb{F}_{2^m}$ of the form $y^2 + a_3y$ make up a subgroup of index 2 of the additive group of $\mathbb{F}_q$. Hence, if $(x_1, x_2, x_3, y)$ is a point in $V(\mathbb{F}_q)$, at least one of $g(x_i)$, $i = 1, 2, 3$, belongs
to this subgroup, and hence the corresponding $x_i$ is the abscissa of a point in $E(\mathbb{F}_q)$ as before. A similar reasoning, together with the construction of the corresponding rational curves, can deal with both reduced Weierstrass forms in characteristic two.

In the end, Shallue and van de Woestijne obtain an encoding functions to every elliptic curve over any finite field $\mathbb{F}_q$ with $q > 5$. The main drawback of their approach is that the computations are relatively cumbersome, and implementing them in constant time is not straightforward. It also requires finding a point on a conic: this is a one-time pre-computation for any given elliptic curve, so not a serious issue from a cryptographic viewpoint, but it does preclude nice formulas with small coefficients for the encoding function, for example.

**The contributions of Ulas.** In a paper published the following year [Ula07], Ulas considered again the problem of constructing rational curves on the threefold:

$$V: y^2 = g(x_1)g(x_2)g(x_3)$$

where, however, $g$ is of the following somewhat special form (slightly more restricted than the one considered by Skałba):

$$g(x) = x^3 + ax + b \quad \text{with } ab \neq 0.$$

He was actually able to construct an explicit rational parametrization for a surface embedded in $V$, which has the advantage of being much simpler than the rational curves of Skałba and Shallue-van de Woestijne. A special case of his result can be written as follows.

**Theorem 3.3 ([Ula07, Th. 2.3(2)])**. Let $\mathbb{F}$ be any field, and $g(x) = x^3 + ax + b \in \mathbb{F}[x]$ a polynomial over $\mathbb{F}$ with $ab \neq 0$. Define the following bivariate rational functions over $\mathbb{F}$:

$$\begin{align*}
X_1(t, u) &= u \\
X_2(t, u) &= -\frac{b}{a} \cdot \frac{t^6 g(u)^3 - 1}{t^6 g(u)^2 - t^2 g(u)} \\
X_3(t, u) &= t^2 g(u) \cdot X_2(t, u) \\
U(t, u) &= t^3 g(u)^2 \cdot g(X_2(t, u)).
\end{align*}$$

Then the following identity holds in $\mathbb{F}(t, u)$:

$$g(X_1(t, u))g(X_2(t, u))g(X_3(t, u)) = U(t, u)^2.$$

Composing this rational parametrization of a surface embedded in $V$ with almost any rational map $\mathbb{A}^1 \to \mathbb{A}^2$ gives rise to a rational curve on $V$ and hence an encoding function to the elliptic curve:

$$E: y^2 = x^3 + ax + b, \quad ab \neq 0$$
as before, which is simple enough to write down in full. Any elliptic curve over a finite field of characteristic $\neq 2,3$ and of $j$-invariant $\neq 0,1728$ admits such a Weierstrass equation, making these encoding functions suitable for many cryptographic applications. We call them the SWU encodings (for “Shallue-van de Woestijne-Ulas”). They have actually been considered in certain practical cryptographic settings (particularly for a secure e-passport standard), although the arguably simpler encoding proposed by Icart (§3.5.2) was ultimately preferred.

In [BCI+10a], we proposed a further simplification of these formulas, together with an elementary derivation of them. We also extended them to the case of elliptic curves in characteristic 3. See §3.5.4 for details.

It may be interesting to note that the original paper by Ulas has a somewhat more general scope than suggested by our description. He was able to find rational curves on all varieties of the form:

$$V_k: y^2 = g(x_1)g(x_2)\cdots g(x_k)$$

for $k \ge 2$. This doesn't have further impact on the construction of elliptic curve encodings, however (but see §3.5.3).

*The work of Sato and Hakuta.* A different but related approach to construct encodings to elliptic curves was later proposed by Sato and Hakuta [SH09]. They consider again elliptic curves over fields of characteristic $\neq 2,3$, given in short Weierstrass form:

$$E: y^2 = x^3 + ax + b.$$

If we put their basic idea in geometric terms, it is again to parametrize a curve on a higher dimensional variety and map it to the elliptic curve, but instead of considering the threefold $E^3/(\mathbb{Z}/2\mathbb{Z})^2$, they use the abelian surface $A = \text{Res}_{\mathbb{F}_{q^2}/\mathbb{F}_q}(E)$ given by the Weil restriction of $E$ from $\mathbb{F}_{q^2}$ to $\mathbb{F}_q$. The norm $N_{\mathbb{F}_{q^2}/\mathbb{F}_q}: \mathbf{P} \mapsto \mathbf{P} + \mathbf{P}^\sigma$ then gives a rational map $A \to E$ which can turn a parametrized curve on $A$ into an encoding to $E$.

Of course, we cannot hope to find a rational curve directly on $A$, but Sato and Hakuta show in essence that there is a conic on the Kummer variety $K = A/\{\pm 1\}$ that is non-degenerate provided that $a \neq 0$, and whose $\mathbb{F}_q$-points are entirely contained in the image of $A(\mathbb{F}_q) \to K(\mathbb{F}_q)$. Thus, when $a \neq 0$, they obtain a curve on $A(\mathbb{F}_q)$ with an algebraic parametrization, and composing with the norm map, a non-constant algebraic encoding to $E(\mathbb{F}_q)$.

This approach has the same drawbacks as the original Shallue-van de Woestijne technique (cumbersome formulas and the need to find a point on a conic) without the generality and unconditional deterministicness, but it looks as if it might lend itself to interesting generalizations (e.g. to higher-dimensional abelian varieties).

### 3.5.2 Icart's approach

*Icart's encoding.* In [Ica09], Icart introduced an encoding function based on a very different idea—namely, trying to adapt the Boneh-Franklin encoding discussed in §3.4.2
$$f: \mathbb{F}_q \to E(\mathbb{F}_q) \\ u \mapsto \left( \left( v^2 - b - \frac{u^6}{27} \right)^{1/3} + \frac{u^2}{3} ; ux + v \right)$$

where $v = (a - 3u^4)/(6u)$. By convention, $f(0) = \mathbf{O}$, the identity element.

Figure 3.3: Icart’s encoding to $E: y^2 = x^3 + ax + b$ over $\mathbb{F}_q$ with $q \equiv 2 \pmod 3$.

to the case of an ordinary elliptic curve. More precisely, consider again an elliptic curve $E$ given by a short Weierstrass equation:

$$E: y^2 = x^3 + ax + b$$

over a field $\mathbb{F}_q$ of odd characteristic with $q \equiv 2 \pmod 3$. The idea is again to reduce the equation to a binomial cubic which can be solved directly in $\mathbb{F}_q$ (where $u \mapsto u^3$ is a bijection).

Unlike the simple case considered by Boneh and Franklin, this cannot be done by picking $y$ as a constant: doing so results in a trinomial cubic which does not always have a root in $\mathbb{F}_q$. Icart’s idea is to set $y = ux + v$ for two parameters $u, v$ to be chosen later. This gives:

$$x^3 - u^2 x^2 + (a - 2uv)x + b - v^2 = 0$$

and after completing the cube:

$$\left(x - \frac{u^2}{3}\right)^3 + \left(a - 2uv - \frac{u^4}{3}\right) x = v^2 - b - \frac{u^6}{27}.$$

Thus, by setting $v = (a - 3u^4)/(6u)$, it is possible to cancel the term of degree 1 and obtain a binomial cubic equation:

$$\left(x - \frac{u^2}{3}\right)^3 = v^2 - b - \frac{u^6}{27}$$

which is easy to solve for $x$ in $\mathbb{F}_q$. This gives Icart’s encoding, described in Figure 3.3.

This encoding applies to a slightly more restricted setting than the SWU encodings, due to the requirement that $q \equiv 2 \pmod 3$, but it has the advantage of being very easy to describe and implement in constant time.

As Icart observed, the exact same technique applies in even characteristic. Consider an elliptic curve $E$ of non zero $j$-invariant over a binary field $\mathbb{F}_q = \mathbb{F}_{2^n}$ with $n$ odd (in which case $u \mapsto u^3$ is again a bijection). $E$ has a reduced Weierstrass equation of the form:

$$E: y^2 + xy = x^3 + ax^2 + b$$
$$f: \mathbb{F}_{2^n} \to E(\mathbb{F}_{2^n}) \\ u \mapsto ((v^4 + v^3 + b)^{1/3} + v; ux + v^2)$$

where $v = a + u + u^2$.

<caption>Figure 3.4: Icart’s binary encoding to $E: y^2 + xy = x^3 + ax^2 + b$ over $\mathbb{F}_{2^n}$ with $n$ odd.</caption>

with $b \neq 0$. We can set $y = ux + v$ and solve as before. However, we get slightly simpler formulas with $y = ux + v^2$ instead. This gives:

$$x^3 + (a + u + u^2)x^2 + v^2x + b + v^4 = 0$$

and completing the cube:

$$(x + (a + u + u^2))^3 + (v^2 - (a + u + u^2)^2)x = b + v^4 + (a + u + u^2)^3.$$

Thus, the degree 1 term disappears if we let $v = a + u + u^2$, and we can solve the resulting binomial cubic equation. This gives Icart’s binary encoding, described in Figure 3.4, which is even easier to write down than the odd characteristic variant.

*Generalizations.* Several variants and extensions of Icart’s encoding have been proposed, and various algebraic and geometric interpretations of it have been given afterwards. We now give a quick review of these works.

Farashahi [Far11] showed that Icart’s technique applies directly to Hessian curves (these are all elliptic curves with a rational point of order 3):

$$E: x^3 + y^3 + 1 = dxy$$

over fields $\mathbb{F}_q$ such that $q \equiv 2 \pmod 3$. Indeed, setting $y = ux + v$ again and completing the cube, the equation becomes:

$$(1 + u^3) \left( x + \frac{u^2 v - du}{1 + u^3} \right)^3 + 3(u^2 v - du) \cdot \left( 1 + \frac{u^2 v - du}{1 + u^3} \right) x = -1 - v^3 - \frac{(u^2 v - du)^3}{(1 + u^3)^2}$$

and we can cancel the term of degree 1 by setting $v = d/u$, and then solve for $x$. The encoding function obtained in this way is a bit less general than Icart’s since it only applies to Hessian curves, but it has certain interesting properties of its own, such as an inverse that is easier to describe.

Kammerer, Lercier and Renault [KLR10] interpreted (perhaps incorrectly) Icart’s approach as an application of Cardano’s formulas for the resolution of the cubic equation, and attempted to extend it in that direction. More precisely, consider a curve of the form:

$$E: x^3 + A(y)x + B(y) = 0 \qquad (3.12)$$
where A and B are rational functions of sufficiently low degree to ensure that E is of genus 1 (the reduced Weierstrass form corresponds to the case when A is constant and B is a polynomial of degree 2 with no linear term). Over a field $\mathbb{F}_q$ with $q \equiv 2 \pmod 3$, we can hope to parametrize $E(\mathbb{F}_q)$ by solving (3.12) using Cardano's formula:

$$x = r - \frac{A(y)}{3r} \quad \text{where} \quad r^3 = -\frac{B(y)}{2} + \sqrt{\frac{B(y)^2}{4} + \frac{A(y)^3}{27}}$$

This works when the square root exists, i.e. when the discriminant $A^3/27 + B^2/4$ is always a square. This can be ensured if the curve of equation:

$$4A(y)^3 + 27B(y)^2 = 4 \cdot 27z^2 \qquad (3.13)$$

is unicursal, in which case a rational parametrization $u \mapsto (y(u), z(u))$ provides an encoding function to $E(\mathbb{F}_q)$ as:

$$u \mapsto \left( r(u) - \frac{A(y(u))}{3r(u)} ; y(u) \right) \quad \text{where} \quad r(u) = \left( -\frac{B(y(u))}{2} + z(u) \right)^{1/3} . \qquad (3.14)$$

Unfortunately, in the usual Weierstrass case when A is constant and B is a polynomial of degree 2, the curve given by (3.13) is clearly of genus 1, and the method does not apply. However, Kammerer et al. noticed that if A is a polynomial of degree 1 and B is chosen as the product of A by another polynomial of degree 1, then $A^2$ can be factored out in (3.13) and the curve is birational to a non degenerate conic. Therefore, in that case, they obtain a new encoding function to the curve E, which turns out to be (isomorphic to) a Hessian curve again! Remarkably, this encoding is different from the one found by Farashahi, although they share many properties.

Couveignes and Kammerer [CK11] were later able to give a common geometric interpretation of all of these encodings (Icart's, Farashahi's and Kammerer et al.'s) in terms of unicursal curves passing through the nine cusps of the dual curve of an elliptic curve.

### 3.5.3 Extensions to hyperelliptic curves

The problem of constructing encoding functions extends naturally to any curve (or indeed any variety) over $\mathbb{F}_q$, and the case of hyperelliptic curves, in particular, has received some attention with the hope that it may be relevant to hyperelliptic curve cryptography.

Indeed, most elliptic curve-base cryptographic protocols, including those that require elliptic curve-valued hash functions (e.g. BLS signatures, Boneh-Franklin IBE, certain PAKE protocols, etc.) admit natural generalizations to a hyperelliptic curve-based setting, possibly with some efficiency gains and lower memory footprint (see e.g. [PWGP03]). A caveat is that in the hyperelliptic setting, the group where computations occur is not the set of point of the hyperelliptic curve itself (which does not have a natural group structure) but the Jacobian variety of the curve, which is a higher-dimensional abelian variety. Thus, hashing should be done to the Jacobian rather than to the curve itself.
However, as we have seen, constructing encoding functions to curves can already be quite tricky, so to the best of our knowledge, no attempt has been made to construct encodings to the Jacobian directly: rather, research has focused on encoding to hyperelliptic curves themselves, and then plugging those encodings into more general constructions to obtain Jacobian-valued hash functions. We give a quick review here of the encodings that have been proposed to date.

**Hyperelliptic SWU encoding.** The technique used by Ulas in [Ula07] to establish Theorem 3.3 generalizes directly to hyperelliptic curves of the form $y^2 = x^n + ax + b$ or $y^2 = x^n + ax^2 + bx$, for $ab \neq 0$ and any odd $n \ge 3$ coprime to the characteristic, and Ulas himself actually stated his results in terms of these curves of arbitrary large genus. In particular, the SWU encoding extends to these particular curves. These form two somewhat restricted families of hyperelliptic curves—families of dimension 1 in the $(2g-1)$-dimensional moduli space of genus $g$ hyperelliptic curves for any $g \ge 1$—but like the elliptic curve SWU encoding, this encoding has the advantage of being quite easy to describe. Furthermore, the simplified derivation we proposed in [BCI+10a] applies to this hyperelliptic setting as well.

**Kammerer et al.'s hyperelliptic encodings.** In addition to the Hessian curve encoding described above, Kammerer, Lercier and Renault [KLR10] presented several encodings to higher-genus hyperelliptic curve.

They first try to extend the technique of applying Cardano's formula to some genus 2 curves. They find that, for example, when $A$ is constant and $B$ is a rational function of degree 2, then the curve of equation (3.12) is hyperelliptic of genus 2, isomorphic to:

$$H: y^2 = \lambda(x^3 + 3\mu x + 2a)^2 + 4v^2 - 4\lambda u^2 \quad (3.15)$$

for some $\lambda, \mu, a, u, v \in \mathbb{F}_q$, and the curve (3.13) associated to the cubic discriminant is of genus 1. It is thus possible to construct an encoding to $H(\mathbb{F}_q)$ when $q \equiv 2 \pmod 3$ by first mapping to the associated genus 1 curve with Icart's encoding, and then deducing a function to $H(\mathbb{F}_q)$ by solving the cubic as in (3.14). The explicit formulas, given in [KLR10, Fig. 3], are rather daunting. However, a nice feature of this encoding is that the target family of genus 2 curves defined by (3.15) is rather large: it is a family of dimension 2 in the 3-dimensional moduli space of genus 2 hyperelliptic curves. This is the largest family of hyperelliptic curves of genus 2 for which an encoding is known (all over families are of dimension at most 1).

Kammerer et al. also give two examples of simpler encodings to restricted families of hyperelliptic curves of arbitrarily large genus. On the one hand, they describe an encoding to hyperelliptic curves of the form:

$$H: y^2 = x^{2d} + ax^d + b$$

where $d \ge 3$ is an integer coprime to $q(q-1)$ (and $a, b$ are such that the discriminant of the right-hand side is not zero). The idea is simply to write an explicit rational
parametrization of the non degenerate conic $y^2 = w^2 + aw + b$ and deduce an encoding
by setting $x = w^{1/d}$.

On the other hand, they use the solvability of De Moivre polynomials to construct an
encoding to hyperelliptic curves of the form:

$$
H: y^2 = x^d + dax^{d-2} + 2da^2x^{d-4} + 3da^3x^{d-6} + \dots + 2da^{(d-1)/2-1}x^3 + da^{(d-1)/2}x + b
$$

with $a, b \in \mathbb{F}_q$ and $d \ge 3$ odd and coprime to the characteristic. Both of these families of
hyperelliptic curves are of dimension 1 in the moduli space.

Odd hyperelliptic curves. In [FT10a], we proposed a very simple encoding to all hyperel-
liptic curves of the form:

$$
H: y^2 = x^{2g+1} + a_1 x^{2g-1} + a_2 x^{2g-3} + \dots + a_g x
$$

over finite fields $\mathbb{F}_q$ with $q \equiv 3 \pmod 4$. We called such curves *odd hyperelliptic curves* for obvious reasons. In genus $g$, they form a family of dimension $g-1$ in the $(2g-1)$-dimensional moduli space of hyperelliptic curves of genus $g$: for any genus $g \ge 3$ it is thus the largest family for which an encoding is known. Another nice feature of this family is that many hyperelliptic curves of cryptographic interest are “odd” in this sense, including those considered in [FKT03, HKT05, Sat09] and more. We give a short description our encoding in the next section, and a more thorough treatment in Chapter 7.

**3.5.4 Our contributions**

Our works include some contributions to the construction of elliptic and hyperelliptic
curve encodings. We present them here.

*The simplified SWU encoding.* In [BCI$^+$10a], we introduced a simpler, more efficient variant of the SWU encoding, and described an elementary derivation of its formula. It also extends in a straightforward way to the case of Ulas hyperelliptic curves.

To see where it comes from, consider what happens when we try to deduce an encoding
function from Theorem 3.3 by fixing the value of $u$. We know that a product of the
form $g(u)g(\tilde{X}_1(t, g(u)))g(\tilde{X}_2(t, g(u)))$ is a square for all $t$. If $g(u)$ itself is a square, we
don't get any interesting information on the values that depend on $t$, so we cannot
construct a non constant encoding. On the other hand, if $u$ is chosen such that $g(u)$ is a
quadratic nonresidue, then for all $t$, either $g(\tilde{X}_1(t, g(u)))$ or $g(\tilde{X}_2(t, g(u)))$ is a square,
and thus we get a well-behaved, non constant encoding to $E(\mathbb{F}_q)$. And we can check,
moreover, that the same formulas give rise to an encoding even if we replace $g(u)$ by
a quadratic nonresidue that isn't in the image of the polynomial $g$: any choice of a
quadratic nonresidue $\xi \in \mathbb{F}_q$ lets us construct an encoding.

Let us see, more formally, how we can derive the formulas for these encodings based
on that simple remark. We will consider the hyperelliptic case right away, and try to
encode to the set of $\mathbb{F}_q$-points of the curve:

$$
H: y^2 = g(x) \quad \text{where} \quad g(x) = x^n + ax + b
$$
with $n \ge 3$ odd and coprime to the characteristic, and $ab \ne 0$.

First observe that, for any $t \in \mathbb{F}_q$ such that $t^n - t \ne 0$, there is a unique $x \in \mathbb{F}_q$ such that $g(tx) = t^n \cdot g(x)$. Indeed, solving this equation for $x$, we get:

$$ 
\begin{aligned}
t^n x^n + atx + b &= t^n x^n + at^n x + bt^n \\
a(t - t^n)x &= b(t^n - 1) \\
x &= -\frac{b}{a} \cdot \frac{t^n - 1}{t^n - t}.
\end{aligned}
 $$

Now write $t = \xi u^2$, where $\xi \in \mathbb{F}_q$ is a fixed quadratic nonresidue, and $u$ is a variable parameter in $\mathbb{F}_q$. Then $t^n$ is a quadratic nonresidue for all $u$, and hence if $x$ is defined as before (which is possible for all values of $u$ except at most $2n$), either $g(x)$ or $g(tx) = t^n \cdot g(x)$ is a square. This means that either $x$ or $tx$ is the abscissa of a point in $H(\mathbb{F}_q)$, with the ordinate begin $\pm\sqrt{g(x)}$ or $\pm\sqrt{g(tx)}$ accordingly. We thus get the following encoding function:

$$ 
\begin{array}{l}
f: \mathbb{F}_q \setminus S \to H(\mathbb{F}_q) \\
u \mapsto \begin{cases} (x; \sqrt{g(x)}) & \text{if } g(x) \text{ is a square} \\ (\xi u^2 x; -\sqrt{g(\xi u^2 x)}) & \text{otherwise} \end{cases} \\
\text{where } x = -\frac{b}{a} \cdot \frac{\xi^n u^{2n} - 1}{\xi^n u^{2n} - \xi u^2}.
\end{array}
 $$

Here, $S$ is the set of cardinality at most $2n$ consisting of all $u \in \mathbb{F}_q$ such that $\xi^n u^{2n} - \xi u^2 = 0$. The minus sign before the second square root ensures that the two “branches” of this encoding function are almost disjoint, making the image somewhat larger.

Note again that this formula is really the same as the one we obtain when deducing an encoding function from Theorem 3.3 by fixing the parameter $u$, except that the choice of the quadratic nonresidue doesn't have to be in the image of $g$.

A particularly simple case is when $q \equiv 3 \pmod 4$. Then, we have a very simple nonresidue $\xi = -1$ (and taking square roots is just a matter of raising to the $(q+1)/4$-th power). The resulting simple formula, given in Figure 3.5, is what we call the simplified SWU encoding.

Note also that the same reasoning yields an encoding to hyperelliptic curves of the form:

$$ H: y^2 = x^n + ax^2 + bx. $$

*Simple encodings in characteristic 3.* Among the encodings we have described until now, the only one that applies to elliptic curves over fields of characteristic 3 is the original Shallue-van de Woestijne algorithm [SvdW06], which has rather limited efficiency. In [BCI+10a] we have proposed several more efficient constructions.

We only consider elliptic curves of non zero $j$-invariant over a field $\mathbb{F}_q$ of characteristic 3. They have a reduced Weierstrass equation of the form:

$$ E: y^2 = x^3 + ax^2 + b \qquad (3.16) $$
$$
\begin{array}{l}
f: \mathbb{F}_q \setminus S \to H(\mathbb{F}_q) \\
\\
u \mapsto \begin{cases} (x; \sqrt{g(x)}) & \text{if } g(x) \text{ is a square} \\ (-u^2x; -\sqrt{g(-u^2x)}) & \text{otherwise} \end{cases} \\
\\
\text{where } x = -\frac{b}{a} \cdot \frac{u^{2n} + 1}{u^{2n} - u^2}
\end{array}
$$

Here, $S = \{u \in \mathbb{F}_q | u^{2n} - u^2 = 0\}$. We can extend $f$ to all of $\mathbb{F}_q$ by setting $f(S) = \{\mathbf{O}\}$, the point at infinity.

Figure 3.5: Simplified SWU encoding to $H: y^2 = x^n + ax + b$ over $\mathbb{F}_q$ with $q \equiv 3 \pmod 4$.

and their discriminant is $\Delta = -a^3b$ (hence $ab \neq 0$).

A simple approach is to try and mimic the simplified SWU technique described above.
Suppose first that $\Delta$ is a square, and write $g(x) = x^3 + ax^2 + b$. For $t \in \mathbb{F}_q \setminus \{0, 1\}$, we
can again find $x \in \mathbb{F}_q$ such that $g(tx) = t^3 \cdot g(x)$. Indeed, trying to solve for $x$ we get:

$$
\begin{align*}
t^3 x^3 + at^2 x^2 + b &= t^3 x^3 + at^3 x^2 + bt^3 \\
a(t^2 - t^3)x^2 &= b(t^3 - 1) \\
at^2 x^2 &= b(t - 1)^2 \\
x^2 &= -\frac{b}{a} \cdot \left(1 - \frac{1}{t}\right)^2
\end{align*}
$$

but $-b/a = \Delta/a^2$ is a square $c^2$, so we get a solution $x = c(1 - 1/t)^2$. Then, picking $t$ of
the form $\xi u^2$ for some fixed quadratic nonresidue $\xi \in \mathbb{F}_q$ again, we get that one of $g(x)$
and $g(tx)$ must be square. Hence the encoding:

$$
f: \mathbb{F}_q^* \to E(\mathbb{F}_q) \\
u \mapsto \begin{cases} (x; \sqrt{g(x)}) & \text{if } g(x) \text{ is a square} \\ (\xi u^2 x; -\sqrt{g(\xi u^2 x)}) & \text{otherwise} \end{cases} \\
\text{where } x = c \cdot \left(1 - \frac{1}{\xi u^2}\right).
$$

On the other hand, when $\Delta$ is not a square, then the polynomial $g(x)$ has a root
$x_0 \in \mathbb{F}_q$ (indeed, if it were irreducible, it would have the non abelian group $S_3$ as its
Galois group, which is not possible over a finite field). Therefore, $g(x - x_0)$ is of the form
$x^3 + ax^2 + b'x$, which is amenable to the usual SWU approach. Hence another encoding
in this case.

However, as noted by Barreto and Kim in [BK01], we can obtain much more efficient
encoding (or in their case, try-and-increment hashing) in characteristic 3 if we can reduce
the problem to solving an Artin-Schreier cubic equation (which is linear over the prime field $\mathbb{F}_3$) instead of taking a square root (which is at least as costly as an exponentiation in $\mathbb{F}_q$). Let us describe how this can be done in our setting.

To put equation (3.16) in Artin-Schreier form (i.e. into a cubic with no term of degree 2), let $w = 1/x$. The equation becomes:

$$ \frac{1}{w^3} + \frac{a}{w^2} + (b - y^2) = 0 $$

and multiplying by $w^3/(b - y^2)$ to obtain the reciprocal of (3.16), we get:

$$ w^3 + \frac{a}{b - y^2} \cdot w = - \frac{1}{b - y^2}. \qquad (3.17) $$

This is an Artin-Schreier equation in $w$; clearly, the map $w \mapsto w^3 + a/(b - y^2) \cdot w$ is linear over $\mathbb{F}_3$, and bijective (hence invertible) if and only if it has a trivial kernel, i.e. if and only if $-a/(b - y^2)$ is not a square. We can ensure that this is the case by fixing a quadratic nonresidue $\xi \in \mathbb{F}_q$, and choosing $y$ such that $b - y^2 = -a\xi z^2$ for some $z \in \mathbb{F}_q$. But $a\xi z^2 + y^2 = b$ is a non degenerate conic over $\mathbb{F}_q$, and hence admits a rational parametrization. For all the values of $y$ given by this parametrization, we can solve equation (3.17) for $w$ and deduce $x = 1/w$. Hence yet another encoding function, which we describe in Algorithm 3.2.

Note that this encoding has some of the drawbacks of the Shallue-van de Woestijne one (e.g. the need to find a point on a conic), but the corresponding performance penalty is easily offset by the efficiency improvement provided by the linear nature of the Artin-Schreier equation.

<caption>**Algorithm 3.2 Efficient encoding in characteristic 3.**</caption>

1: **procedure** ARTINSCHREIERENCODING($u$) $\triangleright$ encode to $E: y^2 = x^3 + ax^2 + b$
2: $z \leftarrow \frac{-z_0u^2 + 2y_0u - a\xi z_0}{a\xi - u^2}$ $\triangleright$ ($z_0, y_0$) precomputed solution of $a\xi z^2 + y^2 = b$
3: $y \leftarrow y_0 + u \cdot (z - z_0)$
4: $s \leftarrow 1/(b - y^2)$
5: Find the unique solution $w$ of the Artin-Schreier equation $w^3 + as \cdot w = -s$
6: **return** (1/$w$; $y$)
7: **end procedure**

*Encoding to odd hyperelliptic curves.* Another contribution, alluded to in the previous section, is the construction of an encoding to so-called odd hyperelliptic curves, of the form:

$$ H: y^2 = g(x) \quad \text{where } g \text{ is an odd polynomial} $$

over fields $\mathbb{F}_q$ such that $q \equiv 3 \pmod 4$. The idea is really quite simple: since $-1$ is a quadratic nonresidue, we have that for any $u \in \mathbb{F}_q$, at least one of $g(u)$ and $g(-u) = -g(u)$
$$f: \mathbb{F}_q \to H(\mathbb{F}_q) \\ u \mapsto (\varepsilon(u) \cdot u; \varepsilon(u)\sqrt{\varepsilon(u) \cdot g(u)})$$

where $\varepsilon(u) = \chi_q(g(u))$.

Figure 3.6: Encoding to odd hyperelliptic curves $H: y^2 = g(x)$ over $\mathbb{F}_q$ with $q \equiv 3 \pmod 4$.

is a square (and indeed, exactly one of them if $g(u) \neq 0$). If we let $\varepsilon(u) = \chi_q(g(u))$, $\varepsilon(u) \cdot u$ is thus always the abscissa of a point in $H(\mathbb{F}_q)$. Hence the encoding function described in Figure 3.6.

This encoding has a number of nice properties: for example, it is “almost” a bijection (more precisely, it induces a bijection between $\mathbb{F}_q$ minus the set of roots of $g$ on the one had, and the non-Weierstrass points in $H(\mathbb{F}_q)$ on the other hand) and has the very simple inverse $(x; y) \mapsto \chi_q(y) \cdot x$. It is also easy to write a constant-time, branch-free and division-free implementation of this encoding, making it possibly the simplest of all encodings with the exception of the Boneh-Franklin supersingular encoding.

As we mentioned earlier, it is also an encoding of some cryptographic interest, since many remarkable hyperelliptic curves are “odd”. This includes the genus 2 curves considered by Furukawa et al. [FKT03] and their extension to genus $g$ by Haneda et al. [HKT05], the Type II pairing-friendly curves of genus 2 constructed by Kawazoe and Takahashi [KT08], the genus 2 hyperelliptic curves for which Satoh [Sat09] gave an efficient class group counting algorithm, and more. And even in genus 1, the construction is interesting, since “odd” elliptic curves are the supersingular elliptic curves of Joux [Jou02]: $y^2 = x^3 + ax$.

We present a more thorough discussion of this encoding as well as some constructions based on it in Chapter 7.

# 3.6 Further Work

## 3.6.1 Is the problem solved?

We have described a number of constructions of encodings to elliptic and hyperelliptic curves. It is not clear, however, that they solve our initial problem of hashing to elliptic curve groups.

The basic construction of a hash function $\mathfrak{H}: \{0, 1\}^* \to E(\mathbb{F}_q)$ from an $\mathbb{F}_q$-valued random oracle $\mathfrak{h}: \{0, 1\}^* \to \mathbb{F}_q$ and an encoding $f: \mathbb{F}_q \to E(\mathbb{F}_q)$, as suggested in §3.4, is simply:

$$\mathfrak{H}(m) = f(\mathfrak{h}(m)). \qquad (3.18)$$
However, unlike what happens for the Boneh-Franklin encoding, the resulting hash function $\mathfrak{H}$ does not necessarily have strong security properties.

Consider the case when $f$ is Icart's encoding, for example (most other encodings are similar). One can then prove some limited security properties on $\mathfrak{H}$, such as that $\mathfrak{H}$ is one-way if $\mathfrak{h}$ is [Ica09, Lemma 5]. However, unlike the Boneh-Franklin encoding, $f$ is not a surjective or “almost” surjective function to the target group $E(\mathbb{F}_q)$. Indeed, in his original paper [Ica09], Icart could only show that the image $f(\mathbb{F}_q)$ satisfies $\#f(\mathbb{F}_q) \gtrsim (1/4) \cdot \#E(\mathbb{F}_q)$, and conjectured that, in fact, $\#f(\mathbb{F}_q) \approx (5/8) \cdot \#E(\mathbb{F}_q)$ (a conjecture which we will prove in Chapter 4, and extend to other encodings). As a result, the hash function $\mathfrak{H}$ constructed from $f$ using formula (3.18) is easily distinguished from a random oracle!

To see this, note that since $f$ is an algebraic function, we can efficiently compute $f^{-1}(\mathbf{P})$ for any $\mathbf{P} \in E(\mathbb{F}_q)$ by solving a polynomial equation over $\mathbb{F}_q$. In particular, it is possible to decide efficiently whether $\mathbf{P}$ is in the image of $f$ or not. Therefore, we can construct a distinguisher $\mathcal{D}$ between $\mathfrak{H}_0 = \mathfrak{H}$ and a random oracle $\mathfrak{H}_1$ to $E(\mathbb{F}_q)$ as follows. $\mathcal{D}$ is given as input $\mathbf{P} = \mathfrak{H}_b(m) \in E(\mathbb{F}_q)$ for some message $m$ and a random bit $b \in \{0, 1\}$. It answers with a guess of the bit $b$, as $b = 0$ if $\mathbf{P}$ is in $f(\mathbb{F}_q)$ and $b = 1$ otherwise. Then $\mathcal{D}$ has a constant positive advantage. Indeed, it answers correctly with probability 1 if $\mathbf{P} \notin f(\mathbb{F}_q)$, and with probability $1/2$ otherwise. Hence:

$$ \mathrm{Adv} \mathcal{D} \approx (5/8) \cdot (1/2) + (1 - 5/8) \cdot 1 - 1/2 = 3/16. $$

Thus, clearly, construction (3.18) does not behave like a random oracle when $f$ is Icart's encoding (or most other encodings), and cannot replace a random oracle in a generic way.

In many protocols requiring a hash function to an elliptic curve group, this is actually not much of a problem, and an encoding with an image size that is a constant fraction of $\#E(\mathbb{F}_q)$ is often good enough. The reason is that, in a random oracle proof of security, the simulator does want to program the random oracle by setting the hash of some message $m$ to a value $\mathbf{P}$, but that point $\mathbf{P}$ itself can usually be anything depending on some randomness. So the simulator might typically want to set $\mathfrak{H}(m)$ to $\mathbf{P} = [r] \cdot \mathbf{G}$ for some random $r$, say. Now if $\mathfrak{H}$ is defined in the protocol using a construction like (3.18), the simulator would pick a random $r$ and set $\mathfrak{h}(m)$ to one of the preimages $u \in f^{-1}(\mathbf{P})$ if $\mathbf{P} \in f(\mathbb{F}_q)$. If however $\mathbf{P}$ is not in the image of $f$, the simulator would pick another random $r$ and try again.

Nevertheless, it seems difficult to give formal sufficient conditions on a protocol for it to remain secure when the elliptic curve-valued random oracle is replaced by a construction like (3.18). One can actually find protocols that are secure in the random oracle model, but in which using that construction instead breaks security completely (we give an example of such a situation in §5.4.2).

Therefore, it would be desirable to obtain from the encodings discussed thus far a construction that does satisfy the *indifferentiability* property mentioned in §3.4, and can thus be used as a plug-in replacement for elliptic curve-valued random oracles in a very large class of protocols. We will see in Chapters 5–6 how we can prove that for the various encodings $f$ described above, the following construction achieves *indifferentiability* from
a random oracle:

$$ \mathfrak{H}(m) = f(\mathfrak{h}_1(m)) + f(\mathfrak{h}_2(m)) \qquad (3.19) $$

where $\mathfrak{h}_1$ and $\mathfrak{h}_2$ are modeled as random oracles $\{0, 1\}^* \to \mathbb{F}_q$ (and the addition is the usual group operation in $E(\mathbb{F}_q)$). As we will show in Chapter 6, a variant of this construction also provides indifferentiable hashing to the Jacobian of a hyperelliptic curve even when $f$ is an encoding to the curve itself: this is an important construction in the higher genus case, as a formula like (3.18) alone can never provide secure hashing in that setting$^7$.

### 3.6.2 Applications

Constant-time hashing to elliptic curves has already found its way into practical applications and the industry. We discuss some of these applications in a column to *IEEE Security & Privacy* [CT11].

The best-known of them is probably PACE v2 IM [CGIP11], a password-based authenticated key establishment protocol developed by Gemalto and Morpho for e-passports, and standardized as part of the ICAO specifications on Supplemental Access Control for Machine Readable Travel Documents [ICAO10]. This protocol uses a hash function to elliptic curves constructed from Icart's encoding, or alternatively the simplified SWU encoding, using the basic method 3.18.

Bringer, Chabanne and Icart [BCI10b] have also shown how using the indifferentiable hash construction (3.19) instead in a similar password-based key exchange protocol can provide interesting additional anonymity properties for e-passports.

<footnote>$^7$Formula (3.18) does define a hash function to the Jacobian if we fix an embedding of the curve into its Jacobian. However, its image only comprises a negligible proportion of all points on the Jacobian, and thus the re-randomizing trick described in the elliptic case does not apply. More concretely, suppose we were to instantiate BLS signatures over the 160-bit Jacobian of a pairing-friendly hyperelliptic curve of genus 2 using (3.18) as a hash function construction. Then the message hashes would only be 80-bit long, making it possible to find a collision and hence break the scheme in time $2^{40}$.</footnote>
<figure><img src="image_8.png" /></figure>
# Estimating the Size of the Image of Constant-Time Encodings

## 4.1 Introduction

This chapter is devoted to the problem of estimating the size of the image of constant-time encodings. Both Shallue and van de Woestijne [SvdW06] on the one hand, and Icart [Ica09] on the other, gave coarse lower bounds for the image size of their encodings. Obtaining more precise estimates is an interesting mathematical problem, and provides a better understanding of the tightness loss in random oracle security reductions when these encoding functions are used in hash function constructions. A previous version of this work was presented at LATINCRYPT 2010 [FT10b].

### 4.1.1 Icart's conjecture

To construct a hash function to an elliptic curve group $E(\mathbb{F}_q)$ based on an encoding $f: \mathbb{F}_q \to E(\mathbb{F}_q)$ as discussed in §3.4, one would ideally want $f$ to be surjective (possibly up to a negligible fraction of points), or better yet, to satisfy that for a uniformly random $u \in \mathbb{F}_q$, $f(u)$ is “almost” uniformly random (i.e. to be regular in the terminology of Chapter 5). The Boneh-Franklin encoding from §3.4.2 satisfies this property, as does the odd hyperelliptic curve encoding we describe in Chapter 7. However, most of the encodings we have described thus far actually factor through a rational map<fnref n="1" /> $C(\mathbb{F}_q) \to E(\mathbb{F}_q)$ of degree > 1 for some covering curve $C$, and such a map is usually not surjective. It is interesting to understand how far they fall short of being surjective.

Icart, for example, could only prove that his own encoding $f$ satisfies $\#f(\mathbb{F}_q) \ge q/4$. However, he conjectured the following much more precise result, which he left as an open

<footnote n="1">¹This is the case for Icart-like encodings. The precise geometric picture is slightly more complicated for SWU-like encodings, where there are typically two covering curves $C_1, C_2 \to E$, and a value $f(u)$ of the encoding $f$ is in the image of one cover or the other depending on the value of the quadratic character $\chi_q(u)$. But the end result is the same: $f$ is usually not surjective.</footnote>
problem:

$$ \left| \#f(\mathbb{F}_q) - \frac{5q}{8} \right| \le \lambda \sqrt{q} $$

for some universal constant $\lambda$. It turns out that this result is true: we prove it in this chapter using the Chebotarev density theorem, and show how the methodology naturally adapts to any other encoding by stating and proving the same result for the simplified SWU encoding introduced in §3.5.4, and for the variant of Icart's function over binary fields.

### 4.1.2 Related work

Independently of our work, Farashahi, Shparlinski and Voloch have obtained a very similar proof of Icart's conjecture [FSV10]. They did not investigate the case of other encoding functions, however.

### 4.1.3 Outline

In §4.2, we first recall some basic facts about Icart's encoding function, and then give a precise statement of Icart's conjecture. We prove this conjecture in §4.3. Then, we formulate and prove analogues of this conjecture for the binary variant of Icart's encoding (§4.4) and for the simplified SWU encoding (§4.5). Finally, in §4.6, we mention an interesting consequence, already noted by Icart, of the result established herein: namely, the construction of surjective hash functions from Icart's encoding.

## 4.2 Preliminaries

### 4.2.1 Icart's encoding

Let $\mathbb{F}_q$ be a finite field of characteristic $> 3$ and $E$ an elliptic curve over $\mathbb{F}_q$. $E$ can be represented as the union of its neutral element **O** and the set of points $(x, y)$ in the affine plane over $\mathbb{F}_q$ such that:

$$ y^2 = x^3 + ax + b $$

for some suitable constants $a, b \in \mathbb{F}_q$ satisfying $4a^3 + 27b^2 \neq 0$ (non-singularity).

When $q-1$ is not divisible by 3, these curves are supersingular for $a=0$. In all other cases, as discussed in §3.5.2, Icart [Ica09] defines the following function $f: \mathbb{F}_q \to E(\mathbb{F}_q)$. He sets $f(0) = \mathbf{O}$ and for all $u \neq 0$, $f(u) = (x, y)$ with:

$$ x = \left( v^2 - b - \frac{u^6}{27} \right)^{1/3} + \frac{u^2}{3} \\ y = ux + v $$

where $v = (3a - u^4)/(6u)$. This function is shown to be well-defined and easily computed in deterministic polynomial time.
More importantly for our purposes, Icart proves [Ica09, Lemma 3], and it is easy to verify, that there is an algebraic relation between elements $x, y, u \in \mathbb{F}_q$ such that $f(u) = (x, y)$. More precisely, the following holds for all $x, y, u \in \mathbb{F}_q$:

$$f(u) = (x, y) \iff u^4 - 6xu^2 + 6yu - 3a = 0. \qquad (4.1)$$

In geometric terms, this equation defines a curve $C \subset \mathbb{P}^1 \times E$ with projections to $\mathbb{P}^1$ and $E$, and Icart's function is really obtained by composing $C(\mathbb{F}_q) \to E(\mathbb{F}_q)$ with the inverse of $C(\mathbb{F}_q) \to \mathbb{P}^1(\mathbb{F}_q)$ (which is a bijection on $\mathbb{F}_q$-points). See §5.3.2 more a longer discussion of this geometric interpretation.

### 4.2.2 Icart's conjecture

In [Ica09], Icart conjectures that the image of $f$ contains $(5/8) \cdot \#E(\mathbb{F}_q) + O(q^{1/2})$ points of the curve. In view of relation (4.1), and since the curve itself has $\#E(\mathbb{F}_q) = q + O(q^{1/2})$ points in $\mathbb{F}_q$, this conjecture can be stated as follows.

**Conjecture 4.1** (Icart). Let $K = \mathbb{F}_q(x, y) = \mathbb{F}_q(x)[y]/(y^2 - x^3 - ax - b)$ be the function field of $E$, and $P$ the polynomial in $K[u]$ defined by $P(u) = u^4 - 6xu^2 + 6yu - 3a$. Let further $N$ be the number of points in $E(\mathbb{F}_q)$ at which the reduction of $P$ has a root in $\mathbb{F}_q$. Then

$$N = \frac{5}{8}q + O(q^{1/2})$$

where the implied constant in the big-$O$ is absolute.

The next section is devoted to the proof of this conjecture.

## 4.3 Proof of Icart's Conjecture

### 4.3.1 Genericity of $P$

**Proposition 4.1.** Let again $K = \mathbb{F}_q(x, y)$ be the function field of $E$. The polynomial $P(u) = u^4 - 6xu^2 + 6yu - 3a \in K[u]$ is irreducible over $K$, and its Galois group is $S_4$.

*Proof.* Introduce the resolvent cubic of $P$, whose roots in an algebraic closure are $(r_i + r_j)(r_k + r_l)$ for all permutations $(i, j, k, l)$ of $(1, 2, 3, 4)$, with $r_1, \dots, r_4$ the roots of $P$.<fnref n="2" />

$$ \begin{aligned} R(u) &= u^3 + 12xu^2 + (36x^2 + 12a)u + 36y^2 \\ &= u^3 + 12xu^2 + (36x^2 + 12a)u + 36(x^3 + ax + b) \in \mathbb{F}_q(x). \end{aligned} $$

According to classical facts about the quartic equation (see Appendix 4.A), it suffices to prove that $P$ and $R$ are irreducible over $K$, and that their common discriminant

$$\Delta = -432(9x^6 + 18ax^4 + 90bx^3 - 39a^2x^2 - 54abx + 16a^3 + 81b^2)$$

<footnote n="2">²Some texts use the resolvent whose roots are the $r_i r_j + r_k r_l$. This is of course equivalent, as both sets of roots have the same Galois action.</footnote>
is not a square in $\mathbb{K}$. Moreover, we can prove these assertions after extending the field of scalars to the algebraic closure $\mathbb{F} = \overline{\mathbb{F}}_q$. Indeed, if they hold over $\mathbb{F}$, they clearly hold a fortiori over $\mathbb{F}_q$. The following three lemmas conclude the proof. $\square$

**Lemma 4.1.** *The resolvent cubic $R(u)$ is irreducible over $\mathbb{F}(x, y)$.*

*Proof.* This amounts to showing that $R(u)$ has no root in $\mathbb{F}(x, y)$. Note first that it is actually sufficient to prove it has no root in $\mathbb{F}(x)$. Indeed, if it is irreducible in $\mathbb{F}(x)$ but has a root in $\mathbb{F}(x, y)$, the degree of the algebraic extension $\mathbb{F}(x, y)/\mathbb{F}(x)$ must be divisible by $\text{deg } R(u) = 3$. But this extension is quadratic: hence a contradiction.

Let then $g/h$ be a root of $R$ in $\mathbb{F}(x)$, with $g$ and $h$ coprime polynomials. Multiplying the equation $R(g/h) = 0$ by $h^3$, we get

$$g^3 = h \cdot (-12xg^2 - (36x^2 + 12a)gh - 36(x^3 + ax + b)h^2)$$

Thus $h$ divides $g^3$, and since it is coprime to $g$, it must be constant. Without loss of generality, we thus have $h = 1$ and

$$g^3 + 12xg^2 + (36x^2 + 12a)g + 36(x^3 + ax + b) = 0$$

Let $m = \text{deg } g$. Then the terms in the previous sum are of respective degrees $3m, 2m+1, m+2, 3$. If $m \ge 2$, the sum is thus of degree $3m$, and if $m \le 0$, it is of degree 3: in neither case can it be 0. The only possibility is thus $m = 1$ and $g = \alpha x + \beta$. We get

$$(\alpha^3 + 12\alpha^2 + 36\alpha + 36)x^3 + 3\beta(\alpha^2 + 8\alpha + 12)x^2 + (3\alpha\beta^2 + 12a\alpha + 12\beta^2 + 36a)x + (\beta^3 + 12a\beta + 36b) = 0$$

in $\mathbb{F}(x)$. Suppose $\beta \ne 0$. Since the coefficients of $x^3$ and $x^2$ must be zero, this gives $\alpha^3 + 12\alpha^2 + 36\alpha + 36 = \alpha^2 + 8\alpha + 12 = 0$, which is impossible, since the polynomials $X^3 + 12X^2 + 36X + 36$ and $X^2 + 8X + 12$ are coprime. Hence $\beta = 0$, and thus $\alpha^3 + 12\alpha^2 + 36\alpha + 36 = 12a(\alpha + 3) = 0$, which is similarly seen to be impossible (as $a \ne 0$). This completes the proof. $\square$

**Lemma 4.2.** *The discriminant $\Delta$ is not a square in $\mathbb{F}(x, y)$.*

*Proof.* Again, we will show that it is sufficient to prove that $\Delta$ is not a square in $\mathbb{F}(x)$. Indeed, suppose that $\Delta$ is not a square in $\mathbb{F}(x)$ but becomes a square in $\mathbb{F}(x, y)$. Since the extension is quadratic, this gives $\mathbb{F}(x, y) = \mathbb{F}(x, \sqrt{\Delta})$. In particular, if $\lambda$ is a root of $X^3 + aX + b$ in $\mathbb{F}$, the extension $\mathbb{F}(x, \sqrt{\Delta})/\mathbb{F}(x)$ must be ramified at $(x - \lambda)$. In other words, if we specialize $\Delta(x)$ at $x = \lambda$, we must get 0. But

$$\begin{align*}
(\lambda - 3b/a)\Delta(\lambda) &= 16 \cdot 432(\lambda - 3b/a)(3a^2\lambda^2 + 9ab\lambda - a^3) \\
&= 16 \cdot 432[3a^2(\lambda^3 + a\lambda + b) - (4a^3 + 27b^2)\lambda] \\
&= -16 \cdot 432(4a^3 + 27b^2)\lambda \ne 0
\end{align*}$$

since the characteristic does not divide 6 and $a \ne 0$. Hence a contradiction.
It remains to prove that $\Delta$ is not a square in $\mathbb{F}(x)$, or equivalently in $\mathbb{F}[x]$ (since $\mathbb{F}[x]$ is integrally closed). A square root of $\Delta$ in $\mathbb{F}[x]$ must have the form $S = \sqrt{-432} \cdot (3x^3 + rx^2 + sx + t)$. The coefficient of $x^5$ in $S^2$ must be 0, hence $r = 0$. The coefficient of $x^4$ must be $18a$, hence $s = 3a$. But then the coefficient of $x^2$ is equal to both $9a^2$ and $-39a^2$, which is a contradiction since $48a^2 \neq 0$. This completes the proof. $\square$

**Lemma 4.3.** *The polynomial $P$ is irreducible over $\mathbb{F}(x, y)$.*

*Proof.* Let $\sigma$ be the non trivial Galois automorphism of the extension $\mathbb{F}(x, y)/\mathbb{F}(x)$ ($\sigma(y) = -y$). If $P(u)$ decomposes as a product of non constant factors in $\mathbb{F}(x, y)[u]$, then its norm $P_0(u) = P(u)P(u)^\sigma$ is reducible over $\mathbb{F}(x)$. We will show that this is not the case. Note first that $P_0(u)$ can be written as $Q_0(u^2)$, where

$$Q_0(v) = v^4 - 12xv^3 + (36x^2 - 6a)v^2 - 36(x^3 + b)v + 9a^2$$

Now $Q_0(v)$ is easily seen to be an irreducible polynomial of $\mathbb{F}(x)[v]$. Indeed, if it had a root $g/h \in \mathbb{F}(x)$, the rational function $g/h$ would be constant, which is clearly impossible. And if it decomposes as a product of degree 2 factors $Q_0 = (v^2 + rv + s)(v^2 + r'v + s')$, these factors are in $\mathbb{F}[x]$ (integrally closed domain). Since $ss' = 9a^2$, both $s$ and $s'$ are constant. Then, since the coefficient of $v^2$, $rr' + s + s'$, is of degree 2, $r$ and $r'$ are both of degree at most 2. But then so is $rs' + r's$, which is the coefficient of $v$ in $Q_0$, namely $-36(x^3 + b)$, hence a contradiction.

Now let $w$ be a root of $P_0$ in the separable closure of $\mathbb{F}(x)$, and let $\mathcal{L} = \mathbb{F}(x, w)$, $\mathcal{L}' = \mathbb{F}(x, w^2)$. $\mathcal{L}'$ is a subfield of $\mathcal{L}$, and a rupture field of $Q_0$. In particular $[\mathcal{L} : \mathbb{F}(x)] = [\mathcal{L} : \mathcal{L}'] \cdot [\mathcal{L}' : \mathbb{F}(x)] = 4[\mathcal{L} : \mathcal{L}']$. Since the polynomial $P_0$ is even, $-w$ is another root of $P_0$. As $w \notin \mathbb{F}(x)$, $w \mapsto -w$ defines a non trivial $\mathbb{F}(x)$-automorphism of $\mathcal{L}$. This automorphism fixes $\mathcal{L}',$ so $[\mathcal{L} : \mathcal{L}'] \geq 2$. This gives $[\mathcal{L} : \mathbb{F}(x)] \geq 8$, and thus $P_0$ must have an irreducible factor of degree $\geq 8$. In other words, $P_0$ is irreducible over $\mathbb{F}(x)$ as required. $\square$

### 4.3.2 Applying Chebotarev

Now that Proposition 4.1 is established, Conjecture 4.1 readily follows from effective versions of the Chebotarev Density Theorem for function fields. One such version is [FJ05, Proposition 6.4.8], from which one can easily deduce:

**Theorem 4.1 (Chebotarev).** Let $\mathbb{K}$ be an extension of $\mathbb{F}_q(x)$ of degree $d < \infty$ and $\mathcal{L}$ a Galois extension of $\mathbb{K}$ of degree $m < \infty$. Assume $\mathbb{F}_q$ is algebraically closed in $\mathcal{L}$, and fix some subset $\mathcal{S}$ of $\text{Gal}(\mathcal{L}/\mathbb{K})$ stable under conjugation. Let $s = \#\mathcal{S}$ and $N(\mathcal{S})$ the number of places $v$ of $\mathbb{K}$ of degree 1, unramified in $\mathcal{L}$, such that the Artin symbol $(\mathcal{L}/\mathbb{K})/v$ (defined up to conjugation) is in $\mathcal{S}$. Then

$$\left|N(\mathcal{S}) - \frac{s}{m}q\right| \leq \frac{2s}{m}((m + g_{\mathcal{L}}) \cdot q^{1/2} + m(2g_{\mathbb{K}} + 1) \cdot q^{1/4} + g_{\mathcal{L}} + dm)$$

where $g_{\mathbb{K}}$ and $g_{\mathcal{L}}$ are the genera of the function fields $\mathbb{K}$ and $\mathcal{L}$.
Proof of Conjecture 4.1. In our case, $\mathbb{K}$ is the function field of $E$ and $\mathbb{L}$ the splitting field of $P(u)$. In particular, $d = 2$, $m = \#S_4 = 24$ and $g_{\mathbb{K}} = 1$. We consider the subset $\mathcal{S} \subset \text{Gal}(\mathbb{L}/\mathbb{K}) = S_4$ consisting of permutations with at least one fixed point—these are the conjugates of (1), (12) and (123), and there are $s = 1 + 6 + 8 = 15$ of them. Hence $s/m = 15/24 = 5/8$.

The places $v$ of $\mathbb{K}$ of degree 1 correspond to points of $E(\mathbb{F}_q)$ (in the projective plane), and for a point $(x_0, y_0) \in E(\mathbb{F}_q)$ not at infinity, saying that $v = (x - x_0)$ has its Artin symbol in $\mathcal{S}$ means that the reduction of $P(u)$ at $(x_0, y_0)$ is a polynomial over $\mathbb{F}_q$ which decomposes into a products of factors at least one of which is of degree 1 (it splits completely if the symbol is (1), decomposes as two linear factors and a quadratic if it is (12) and a product of a linear factor and a cubic if it is (123) up to conjugation).

In other words, $N(\mathcal{S})$ is the same as $N$ in the statement of Conjecture 4.1 up to a constant number accounting for ramified places (at most 12 since $\Delta$ is a polynomial of degree 6 in $x$) and the point at infinity. We then get

$$ \left|N - \frac{5}{8}q\right| \le \frac{5}{4}\left(\left(24 + g_{\mathbb{L}}\right)q^{1/2} + 72q^{1/4} + g_{\mathbb{L}} + 48\right) + 12 + 1 $$

To bound $g_{\mathbb{L}}$, note again that there are at most 12 ramified points, and the ramification index is at most $\text{deg } P_0 = 4$ at each of them. The Riemann-Hurwitz formula thus gives

$$ 2 - 2g_{\mathbb{L}} \ge 24(2 - 2g_{\mathbb{K}}) - 12 \cdot (4 - 1) \quad \text{i.e.} \quad g_{\mathbb{L}} \le 17 $$

and thus

$$ \left|N - \frac{5}{8}q\right| \le \frac{5}{4}(41q^{1/2} + 72q^{1/4} + 76) $$

In particular, $N = (5/8)q + O(q^{1/2})$. Concretely, for all $q \ge 2^{19}$, we have

$$ \left|N - \frac{5}{8}q\right| \le 55q^{1/2} \qquad (4.2) $$

□

## 4.4 Analogue in Characteristic 2

As discussed in 3.5.2, Icart also introduced a variant of his function for elliptic curves of non zero $j$-invariant over finite fields $\mathbb{F}_q$ of even characteristic, i.e. $q = 2^n$. Such an elliptic curve has the form

$$ y^2 + xy = x^3 + ax^2 + b $$

with $a, b \in \mathbb{F}_q, b \ne 0$. Recall from Figure 3.4 that Icart’s function for such a curve $E$ is defined when $n$ is odd as

$$ f: \mathbb{F}_q \to E(\mathbb{F}_q) \\ u \mapsto (x, ux + v^2) $$
where $v = a + u + u^2$ and $x = (v^4 + v^3 + b)^{1/3} + v$. It is shown that $u \in \mathbb{F}_q$ maps to $(x, y) \in E(\mathbb{F}_q)$ if and only if $P(u) = 0$, where $P \in \mathbb{K}[u]$ is defined as

$$P(u) = u^4 + u^2 + xu + (a^2 + y)$$

Using this result, we can prove the following analogue of Icart's conjecture.

**Proposition 4.2.** *The number of points $N$ in the image of $f$ satisfies:*

$$N = \frac{5}{8}q + O(q^{1/2})$$

where the implied constant in the big-O is universal.

The proof is identical to the one in §4.3.2. The only difference is that the computation of the Galois group is slightly different in even characteristic. However, the group is still $S_4$. Let us prove this fact now.

**Proposition 4.3.** *The polynomial $P(u) = u^4 + u^2 + xu + (a^2 + y) \in \mathbb{K}[u]$ is separable and irreducible over $\mathbb{K}$, and its Galois group is $S_4$.*

*Proof.* Since $P' = x$ is a unit in $\mathbb{K}[u]$, $P$ is certainly separable. Thus, if we prove that it is irreducible, its Galois group can be determined according to [Con07, Theorem 3.4]: to see that it is $S_4$, it suffices to show that both its resolvent cubic $R$ and its resolvent quadratic $Q$ are irreducible (see Appendix 4.A).

First, we have $R(u) = u^3 + u^2 + x^2$. If this polynomial had a root in $\mathbb{F}_q(x)$, it would be a polynomial of $\mathbb{F}_q[x]$ dividing $x^2$ by integral closure, which is clearly impossible. Therefore, $R(u)$ is irreducible over $\mathbb{F}_q(x)$, and also over $\mathbb{K}$ by the same degree argument as in the proof of Lemma 4.1: namely, if $R(u)$ had a root in $\mathbb{K}$, $[\mathbb{K} : \mathbb{F}_q(x)] = 2$ would be divisible by $\deg R(u) = 3$, a contradiction.

Additionally, we have $Q(u) = u^2 + x^2u + x^2 + x^4$. If $Q$ is reducible over $\mathbb{F}_q(x)$, we see again that it is split over $\mathbb{F}_q[x]$, and its roots $s, t$ satisfy $\deg s + \deg t = 4$ and $\deg(st) = 2$, hence $s$ and $t$ are quadratics dividing $x^2(1+x)^2$, i.e. constant multiples of $x^2$, $x^2+x$ or $x^2+1$, but no such quadratic is a root of $Q$. Thus, $Q$ is irreducible over $\mathbb{F}_q(x)$. To see that it remains irreducible over $\mathbb{K}$, it suffices to see that $\mathbb{K}$ and the splitting field $\mathbb{F}$ of $Q$ over $\mathbb{F}_q(x)$ are linearly disjoint, and this is certainly the case since $\mathbb{F}$ is a function field of genus 0 whereas $\mathbb{K}$ is of genus 1.

Finally, let us prove that $P$ is irreducible. Let first $\sigma$ be the non-trivial Galois automorphism of $\mathbb{K}/\mathbb{F}_q(x)$, namely $y \mapsto y + x$, and set $P_0 = PP^\sigma \in \mathbb{F}_q(x)$. It suffices to prove that $P_0$ is irreducible over $\mathbb{F}_q(x)$. We have

$$P_0 = (u^8 + u^4) + x(u^4 + u^2) + x^2(u^2 + u) + (x^3 + a^2x^2 + a^2x + a^4 + b) = Q_0(u^2 + u)$$

where $Q_0(v) = v^4 + xv^2 + x^2v + (x^3 + a^2x^2 + a^2x + a^4 + b)$.

If $Q_0$ has a root over $\mathbb{F}_q(x)$, it is in fact in $\mathbb{F}_q[x]$, which is not possible by inspection of the degrees of the four terms in the sum. Similarly, if $Q_0$ can be written as a product of factors of degree 2, we have $Q_0 = (v^2 + r + s)(v^2 + r + s')$ with $r, s$ and $s'$ are all
in $\mathbb{F}_q[x]$ (with $r$ appearing in both factors by inspection of the degree 3 coefficient of $Q_0$). We get $\deg(ss') = 3$, so the polynomial $s + s'$ must be of degree at least 2. Since $r(s + s') = x^2$, this implies that $r$ is constant. But then the relation $s + s' + r^2 = x$ gives a contradiction. Therefore $Q_0$ is irreducible over $\mathbb{F}_q(x)$.

Then, let $w$ be a root of $P_0$ in the separable closure of $\mathbb{F}_q(x)$, and set $\mathcal{L} = \mathbb{F}_q(x, w)$, $\mathcal{L}' = \mathbb{F}_q(x, w + w^2)$. Like in the proof of Lemma 4.3, we have a tower of extensions $\mathbb{F}_q(x) \subset \mathcal{L}' \subset \mathcal{L}$, and $\mathcal{L}'$ is a rupture field of $Q_0$, so $[\mathcal{L} : \mathbb{F}_q(x)] = 4[\mathcal{L} : \mathcal{L}']$. Furthermore, since $P_0(u + 1) = P(u)$, $w \mapsto w + 1$ is a non-trivial $\mathcal{L}'$-automorphism of $\mathcal{L}$, which gives $[\mathcal{L} : \mathbb{F}_q(x)] \ge 8$ and hence, $P_0$ is irreducible over $\mathbb{F}_q(x)$, which concludes the proof. $\square$

We can again give concrete bounds. With the notations of §4.3.2, we have $d = 2$, $m = 12$, $s = 8$, $g_{\mathbb{K}} = 1$ and there is exactly one ramified point corresponding to $x = 0$. The Riemann-Hurwitz formula then gives $g_{\mathcal{L}} \le 2$, and thus:

$$ \left|N - \frac{3}{4}q\right| \le 21q^{1/2} + 54q^{1/4} + 42 $$

In particular, for $q > 2^{16}$ we get

$$ \left|N - \frac{3}{4}q\right| \le 25q^{1/2} \qquad (4.3) $$

## 4.5 Analogue for the Simplified Shallue-van de Woestijne-Ulas Encoding

Recall from §3.5.4 the description of the simplified version of the SWU encoding [Ula07] that we gave in [BCI+10a]. We focus here on the case of elliptic curves:

$$ E: y^2 = x^3 + ax + b $$

with $ab \ne 0$ over fields $\mathbb{F}_q$ with $q \equiv 3 \pmod 4$. Then, $-1$ is a readily available quadratic nonresidue and we can then use the formula given in Figure 3.5, which simplifies a bit further still as $n = 3$. We finally get the following encoding function:

$$ \begin{array}{rcl} f: \mathbb{F}_q \setminus \{0, 1, -1\} & \to & E(\mathbb{F}_q) \\ u & \mapsto & \begin{cases} \left( x ; \sqrt{g(x)} \right) & \text{if } g(x) \text{ is a square} \\ \left( -u^2x ; -\sqrt{g(-u^2x)} \right) & \text{otherwise} \end{cases} \\ \text{where} & x = & -\frac{b}{a} \cdot \left( 1 + \frac{1}{u^4 - u^2} \right). \end{array} $$

Here, $g(x)$ is again the polynomial $x^3 + ax + b$, and $\sqrt{}$ denotes the standard square root in $\mathbb{F}_q$, obtained by exponentiation by $(q + 1)/4$.
Using the same notations as in Ulas's Theorem 3.3, define the following rational functions in $\mathbb{F}_q(u)$:

$$X_2(u) = -\frac{b}{a} \cdot \left(1 + \frac{1}{u^4 - u^2}\right) \quad \text{and} \quad X_3(u) = -u^2 \cdot X_2(u).$$

The image of $f$ is then made up of the points in $E(\mathbb{F}_q)$ with an $x$-coordinate of the form $X_2(u)$ for some $u$ and a positive$^3$ $y$-coordinate, and of those with an $x$-coordinate of the form $X_3(u)$ and a negative$^4$ $y$-coordinate. More formally, $f(\mathbb{F}_q \setminus \{0, 1, -1\})$ is the (almost disjoint) union of the sets $I_2$ and $I_3$ defined by

$$I_j = \{(x, y) \in E(\mathbb{F}_q) \mid \exists u \in \mathbb{F}_q, x = X_j(u) \text{ and } y = (-1)^j \sqrt{g(x)}\}.$$

Now, disregarding at most three points with zero $x$-coordinate, $I_j$ consists of half the points on the curve with an $x$-coordinate of the form $X_j(u)$ for some $u$. Therefore, if $N$ is the number of points in the image of the algorithm and $N_j$ denotes the number of points with an $x$-coordinate of the form $X_j(u)$, we get

$$N = \frac{N_2 + N_3}{2} + O(1)$$

and the implied constant is at most 6. We deduce the following result.

**Proposition 4.4.** *The number of points $N$ in the image of the simplified SWU encoding satisfies:*

$$N = \frac{3}{8}q + O(q^{1/2})$$

where the implied constant in the big-O is universal.

*Proof.* The proof is again similar to the previous ones. What we actually show is that $N_j = (3/8)q + O(q^{1/2})$ for $j = 2, 3$, using the Chebotarev density theorem again. Note that for all $u \in \mathbb{F}_q \setminus \{-1, 0, 1\}$, we have

$$\begin{align*} x &= X_2(u) \iff u^4 - u^2 + \frac{1}{\omega} = 0 \\ x &= X_3(u) \iff u^4 - \omega u^2 + \omega = 0 \end{align*}$$

where $\omega = \frac{a}{b}x + 1$. Hence, denoting by $\mathbb{K} = \mathbb{F}_q(x, y)$ the function field of $E$, it suffices to prove that the polynomials $P_2(u) = u^4 - u^2 + 1/\omega$ and $P_3(u) = u^4 - \omega u^2 + \omega$ are irreducible and have Galois group $D_8$ (the 8-element dihedral group, viewed as a transitive subgroup of $S_4$) over $\mathbb{K}$. Indeed, $D_8$ has 8 elements, 3 of which have a fixed point: the same technique as in §4.3.2 then gives the desired estimates for $N_2$ and $N_3$.

In view of [KW89, Theorems 2 and 3], a polynomial $P(u) = u^4 - ru^2 + s \in \mathbb{K}[u]$ is irreducible with Galois group $D_8$ if and only if none of $s, \delta = r^2 - 4s$ or $s\delta$ are

<footnote>$^3$That is, in the image of the square root function $\sqrt{\cdot}$, or equivalently, square.</footnote>

<footnote>$^4$That is, the opposite of a positive element, i.e. a quadratic nonresidue or zero. Using these definitions, all elements are either positive or negative, except $0 \in \mathbb{F}_q$ which is both.</footnote>
squares in $\mathbb{K}$. For $P_2$, we have $(s, \delta, s\delta) = \frac{1}{\omega^2}(\omega, \omega(\omega - 4), \omega - 4)$, and for $P_3$, $(s, \delta, s\delta) = (\omega, \omega(\omega - 4), \omega^2(\omega - 4))$. Thus, all we have to prove is that $\omega, \omega - 4$ and $\omega(\omega - 4)$ are not squares in $\mathbb{K}$. This is obvious in $\mathbb{F}_q(x)$ (since these are polynomials of $\mathbb{F}_q[x]$ which are not square), and extends to $\mathbb{K}$ by a ramification argument as in the proof of Lemma 4.2. $\square$

## 4.6 Constructing Surjective Hash Functions

In view of the previous results, encodings $\mathbb{F}_q \to E(\mathbb{F}_q)$ are not usually surjective. However, it is possible to use e.g. Icart's encoding to construct simple, efficient surjective hash functions to $E(\mathbb{F}_q)$ as explained in [Ica09, Corollary 2].

Indeed, let $f$ be Icart's function over $\mathbb{F}_q$ (which can be a field of characteristic 2 or > 3) and consider

$$F : (\mathbb{F}_q)^2 \to E(\mathbb{F}_q) \\ (u_1, u_2) \mapsto f(u_1) + f(u_2)$$

The following pigeonhole argument shows that $F$ is surjective for large $q$. Fix a point $P_0 \in E(\mathbb{F}_q)$. Then the sets $S_1 = \{f(u_1) / u_1 \in \mathbb{F}_q\}$ and $S_2 = \{P_0 - f(u_2) / u_2 \in \mathbb{F}_q\}$ both consist of $(5/8)q + O(q^{1/2})$ points of $E$. In particular $\#S_1 + \#S_2 = (5/4)q + O(q^{1/2})$, which is greater than $q + 2\sqrt{q} + 1 \ge \#E(\mathbb{F}_q) \ge \#S_1 \cup S_2$ for large enough $q$. Therefore, $S_1 \cap S_2$ is non empty provided that $q$ is large enough, and in that case $P_0$ is in the image of $F$.

More precisely, using the explicit bounds (4.2) and (4.3) that we have given for the image size, we obtain that $F$ is surjective as soon as $q > 2^{29}$ in characteristic $> 3$ (resp. $q > 2^{16}$ in characteristic 2), which is always true in cryptographic applications.

Thus, if we define a hash function $\mathfrak{h}$ as follows:

$$\mathfrak{h}(m) = f(\mathfrak{h}_1(m)) + f(\mathfrak{h}_2(m))$$

where $\mathfrak{h}_1$ and $\mathfrak{h}_2$ are $\mathbb{F}_q$-valued hash functions, then $\mathfrak{h}$ is a surjective hash function to $E(\mathbb{F}_q)$. This is not a very strong statement from a security viewpoint, but we will see in Chapter 5 that, in fact, a much stronger property holds—namely, that $\mathfrak{h}$ is indifferentiable from a random oracle when $\mathfrak{h}_1$ and $\mathfrak{h}_2$ are modeled as random oracles. Hence, $\mathfrak{h}$ can be used as a plug-in replacement for an $E(\mathbb{F}_q)$-valued random oracle in most protocols while preserving random oracle model proofs of security. It is thus a very interesting construction, considering its reasonable level of efficiency.

## 4.A Galois Groups of Quartics

In this appendix, we recall some classical results regarding the computation of Galois groups of quartic polynomials. The reader is referred to texts like [Cox04, Theorem 13.1.1] and [KW89] for details.
Let $\mathbb{K}$ be any field of odd characteristic, and $P(x) = x^4 + a_1x^3 + a_2x^2 + a_3x + a_4 \in \mathbb{K}[x]$ an irreducible polynomial of degree 4. Let further $\Delta \in \mathbb{K}$ be its discriminant, and

$$R(x) = x^3 - 2a_2x^2 + (a_2^2 + a_1a_3 - 4a_4)x + (a_3^2 + a_1^2a_4 - a_1a_2a_3)$$

its resolvent cubic. Then the Galois group $G$ of $P$ is conjugate to:

* $S_4$ if $R$ is irreducible and $\Delta$ is not a square in $\mathbb{K}$;

* $A_4$ if $R$ is irreducible and $\Delta$ is a square in $\mathbb{K}$;

* $V_4 = \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/2\mathbb{Z}$ if $R$ is reducible and $\Delta$ is a square in $\mathbb{K}$;

* $D_8$ or $\mathbb{Z}/4\mathbb{Z}$ otherwise.

If $P$ is a separable polynomial over a field $\mathbb{K}$ of characteristic 2, a similar result holds [Con07, Theorem 3.4], except that the condition that $\Delta$ is a square must be replaced by the reducibility over $\mathbb{K}$ of the resolvent quadratic $Q$ of $P$, defined by

$$Q(x) = x^2 + (a_1^2a_4 + a_1a_2a_3 + a_3^2)x + (a_1^4a_4 + a_1^3a_3 + a_1^2a_2a_4 + a_2^3a_3 + a_3^4)$$

Finally, when $P$ is an irreducible biquadratic polynomial (i.e. $a_1 = a_3 = 0$) in odd characteristic, its Galois group can be determined by inspection of its coefficients. It is conjugate to:

* $V_4$ if $a_4$ is a square in $\mathbb{K}$;

* $\mathbb{Z}/4\mathbb{Z}$ if $a_4(a_2^2 - 4a_4)$ is a square in $\mathbb{K}$;

* $D_8$ if neither $a_4$ nor $a_4(a_2^2 - 4a_4)$ are squares in $\mathbb{K}$.
<figure><img src="image_9.png" /></figure>