lercier-fr.bib
lercier-fr.bib
@inproceedings{BLRS12,
author = {Basson, R. and Lercier, R. and Ritzenthaler, C. and
Sijsling, J.},
title = {An explicit expression of the Luroth invariant},
year = 2012,
month = nov,
note = {Soumis pour publication},
abstract = {Nous décrivons un algorithme qui permet de retrouver une
expression explicite de l'invariant de Luröth en fonction
des invariants de Dixmier-Ohno. On en déduit explicitement
sa factorisation lorsqu'on le spécialise sur le lieu des
quartiques de Ciani. Nous répondons aussi à deux questions
ouvertes sur le sous-lieu des quartiques de Lüroth
singulières.},
urlin = {../file/BLRS12.pdf},
urlout = {http://arxiv.org/abs/1211.1327}
}
@unpublished{CEL09,
author = {Couveignes, J.-M. and Ezome, T. and Lercier, R.},
title = {Elliptic periods and primality proving (extented version)},
journal = {Eprint arXiv:0810.2853v4},
year = 2009,
month = jun,
abstract = {Nous construisons des extensions d'anneaux avec arithmétique
rapide à l'aide d'isogénies entre courbes elliptiques. En
application, nous donnons une version elliptique du critère
de primalité AKS.},
urlin = {../file/CEL09.pdf},
urlout = {http://arxiv.org/abs/0810.2853}
}
@article{CEL12,
author = {Couveignes, J.-M. and Ezome, T. and Lercier, R.},
title = {A faster pseudo-primality test},
journal = {Rendiconti del Circolo Matematico di Palermo Journal},
note = {Springer},
month = aug,
year = 2012,
pages = {261-278},
volume = 61,
issue = 2,
abstract = { Nous proposons un test de pseudo-primalité utilisant des
extensions cycliques de $\mathbb Z/n \mathbb Z$. Pour tout
entier $k \leq \log n$, ce test apporte la sécurité de $k^2$
tests de Miller-Rabin, au coût de $k^{1/2+o(1)}$ tests de
Miller-Rabin. },
urlin = {../file/CEL12.pdf},
urlout = {http://dx.doi.org/10.1007/s12215-012-0088-0}
}
@article{CL08b,
author = {Couveignes, J.-M. and Lercier, R.},
title = {Galois invariant smoothness basis},
journal = {Series on Number Theory and Its Applications},
year = 2008,
month = may,
volume = 5,
pages = {142--167},
note = {World Scientific.},
abstract = { Ce texte r\'epond \`a une question de Joux et du second
auteur \`a propos du calcul de logarithmes discrets dans le
groupe multiplicatif d'un corps fini. \'Etant donn\'e un
corps fini r\'esiduel $K$, on recherche une base de
lissit\'e pour $K^*$ qui est invariante \`a gauche par les
automorphismes de $K$. Pour un grand nombre de corps finis,
nous parvenons \`a construire des mod\`eles qui disposent de
telles bases de lissit\'e. Ce travail vise \`a acc\'el\'erer
les calculs de logarithmes discrets dans de tels corps. On
traite les cas de codimension 1 (le crible lin\'eaire) et de
codimension 2 (le crible dans les corps de fonctions). },
urlin = {../file/CL08b.pdf},
urlout = {http://www.worldscibooks.com/mathematics/6761.html}
}
@article{CL09a,
author = {Couveignes, J.-M. and Lercier, R.},
title = {Elliptic periods for finite fields},
journal = {Finite Fields and their Applications},
year = 2009,
month = jan,
volume = 15,
number = 1,
pages = {1--22},
abstract = {Nous construisons deux nouvelles familles de bases pour les
extensions de corps finis. Les bases de la première famille,
que nous appelons \textit{bases elliptiques}, ne sont pas
tout à fait normales, mais elles permettent de calculer
rapidement le Frobenius tout en conservant des formules de
multiplication creuses. Les bases de la seconde famille,
appelées \textit{bases normales elliptiques}, sont des bases
normales et admettent des opérations arithmétiques rapides
(complexité asymptotique quasi-linéaire). Nous montrons que
toute extension admet de telles bases.},
urlin = {../file/CL08a.pdf},
urlout = {http://dx.doi.org/10.1016/j.ffa.2008.07.004}
}
@article{CL12,
author = {Couveignes, J.-M. and Lercier, R.},
title = {Fast construction of irreducible polynomials over finite
fields},
journal = {Israel Journal of Mathematics},
year = 2012,
month = may,
pages = {1-29},
publisher = {The Hebrew University Magnes Press},
abstract = { Nous proposons un algorithme randomisé qui sur entrée d'un
corps fini $K$ avec $q$ éléments et un entier strictement
positif $d$ retourne un polynôme irréductible de degré $d$
dans $K[x]$. Le temps d'exécution est $d^{1+\varepsilon(d)}
\times (\log q)^{5+\varepsilon(q)}$ opérations
élémentaires. La fonction $\varepsilon$ dans cette
expression est une fonction réelle positive appartenant à la
classe $o(1)$, en particulier, la complexité est
quasi-linéaire en $d$. Étant donné un polynôme irréductible
de degré $d$, on peut calculer un polynôme irréductible
aléatoire de degré $d$ au prix de $d^{1+\varepsilon(d)}
\times (\log q)^{1+\varepsilon(q)}$ opérations élémentaires.
},
urlin = {../file/CL11.pdf},
urlout = {http://dx.doi.org/10.1007/s11856-012-0070-8}
}
@manual{CL96,
title = {{ZEN, a new toolbox for computing in finite extension of
finite rings. User's manual}},
author = {Chabaud, F. and Lercier, R.},
year = 1996,
note = {Projet sourceforge},
abstract = { La r\'esolution de nombreux probl\`emes arithm\'etiques
n\'ecessite la manipulation d'extensions de degr\'e fini de
$Z/nZ$ pour des entiers positifs $n$. La factorisation des
nombres entiers, les tests de primalit\'e sont des exemples
de telles applications. Pour cela, les scientifiques
utilisent des logiciels de calculs formels ou \'ecrivent des
programmes sp\'ecifiques (la plupart du temps en langage
C).\\\\ Les logiciels de calculs symboliques manipulent avec
difficult\'e les \'el\'ements de corps finis. Dans les pires
cas, ces programmes ex\'ecutent les calculs dans les
rationnels avant de finalement r\'eduire les objets modulo
$n$. Dans tout les cas, les applications \'ecrites pour ces
logiciels sont dix \`a cent fois plus lentes qu'une
programmation en C. Les biblioth\`eques optimis\'ees en C,
par contre, ne sont souvent pr\'evues que pour quelques
anneaux finis, principalement $Z/nZ$.\\\\ Nous pensons que
nous pouvons garder l'efficacit\'e des biblioth\`eques
\'ecrites en C tout en travaillant dans n'importe quelle
extension polynomiale de $Z/nZ$. Nous avons con\c cu la
biblioth\`eque ZEN dans cet esprit. },
urlout = { http://sourceforge.net/projects/zenfact/ }
}
@inproceedings{DL10,
author = {Dunand, C. and Lercier, R.},
title = {{Normal Elliptic Bases and Torus-Based Cryptography}},
booktitle = {Finite Fields: Theory and Applications},
pages = {137--153},
year = 2010,
editor = {Gary McGuire, Gary L. Mullen, Daniel Panario and Igor
E. Shparlinski},
series = {Contemporary Mathematics},
publisher = {American Mathematical Society},
note = {Ninth International Conference Finite Fields and
Applications},
abstract = { Nous considérons des représentations de tores algébriques
$T_n(F_{q})$ au dessus de corps finis. Nous utilisons des
bases normales elliptiques pour montrer que, pour une
infinité d'entiers $n$ sans facteur carré et une infinité de
valeurs $q$, on peut encoder $m$ éléments d'un tore avec $m$
$\varphi(n)$-uplets d'éléments de $F_q$ et un complément de
taille fixe, en temps quasi-linéaire en $\log q$. Cela
améliore les algorithmes précédents qui ont tous une
complexité quasi-quadratique. Il en résulte que le coût de
la phase d'encodage dans un schéma cryptographique de type
Diffie-Hellman est maintenant négligeable.},
urlin = {../file/DL09.pdf},
urlout = {http://dx.doi.org/10.1090/conm/518}
}
@article{EL13,
author = {Ezome, T. and Lercier, R.},
title = {Elliptic periods and primality proving},
journal = {Journal of Number Theory},
volume = 133,
number = 1,
pages = {343--368},
year = 2013,
abstract = {Nous construisons des extensions d'anneaux avec arithmétique
rapide à l'aide d'isogénies entre courbes elliptiques. En
application, nous donnons une version elliptique du critère
de primalité AKS.},
urlin = {../file/EL13.pdf},
urlout = {http://dx.doi.org/10.1016/j.jnt.2012.07.007}
}
@inproceedings{FLRV08,
author = {Fouque, P.-A. and Lercier, R. and R{\'e}al, D. and Valette,
F.},
title = {{Fault Attack on Elliptic Curve with Montgomery Ladder
Implementation}},
booktitle = {FDTC '08. 5th Workshop on Fault Diagnosis and Tolerance in
Cryptography},
pages = {92--98},
month = aug,
year = 2008,
publisher = {IEEE-CS Press},
abstract = { Dans cet article, nous présentons une nouvelle attaque par
faute sur les algorithmes de multiplication scalaire pour
courbes elliptiques. Cette attaque est adaptée à la méthode
classique de l'échelle de Montgomery quand la coordonnée $y$
n'est pas utilisée. Aucune faiblesse n'a été précisément
raportée jusqu'à présent sur de telles implémentations,
connues pour être très efficaces et promues par de nombreux
auteurs. Mais prenant en compte la tordue des courbes
elliptiques, nous montrons comment, avec peu de fautes
(environ une ou deux), on peut retrouver complètement
l'exposant secret même si des contremesures sont utilisées
pour éviter les attaques par faute. Cette attaque n'ayant
pas été anticipée, la sécurité des courbes prévues dans les
standards peut être fortement réduite. En particulier,
l'attaque est pertinente sur certaines courbes promues par
le NIST ou le SECG.},
urlin = {../file/FLRV08.pdf},
urlout = {http://dx.doi.org/10.1109/FDTC.2008.15}
}
@article{JL01,
author = {Joux, A. and Lercier, R.},
title = {{``Chinese \& Match'', an alternative to Atkin's ``Match and
Sort'' method used in the SEA algorithm}},
journal = {Mathematics of Computation},
year = 2001,
volume = 70,
number = 234,
pages = {827--836},
month = apr,
abstract = { La m\'ethode classique pour d\'eterminer le nombre de
points de courbes elliptiques d\'efinies sur des corps finis
\`a partir de donn\'ees partielles obtenues avec
l'algorithme SEA (Schoof, Elkies, Atkin) est la m\'ethode
``Match and Sort'' due \`a Atkin. Cette m\'ethode est une
fa\c con de trouver via un algorithme de type ``pas de
b\'eb\'es, pas de g\'eants'' le nombre de points parmi $C$
candidats \`a l'aide de $O(\sqrt{C})$ additions sur courbes
elliptiques. La m\'ethode d\'ecrite dans cet article se
d\'ebarrasse des additions sur courbes elliptiques en se
servant du fait que l'on a souvent bien plus d'information
au sujet du nombre de points que ce qui est r\'eellement
utilis\'e par la m\'ethode d'Atkin. Cela conduit \`a un
algorithme de complexit\'e similaire mais l'espace
n\'ecessaire est moindre que celui n\'ecessaire par la
m\'ethode d'Atkin. En pratique, cette m\'ethode est bien
plus efficace que celle d'Atkin puisqu'elle nous a permis de
mener \`a bien le calcul du nombre de points d'une courbe
elliptique d\'efinie sur GF$({2^{1663}})$, ce qui, autant
que nous le sachions, est le plus important calcul de ce
type jamais r\'ealis\'e. Un avantage suppl\'ementaire est
qu'il est imm\'ediat de parall\'eliser ce calcul sur un
r\'eseau d'ordinateurs. },
urlin = {../file/JL01.pdf},
urlout = {http://dx.doi.org/10.1090/S0025-5718-00-01200-X}
}
@inproceedings{JL02,
author = {Joux, A. and Lercier, R.},
title = {{The Function Field Sieve is quite special}},
booktitle = {Algorithmic Number Theory: 5th International Symposium,
ANTS-V, Sydney, Australia, July 7-12, 2002. Proceedings},
pages = {431--445},
year = 2002,
editor = {Fieker, C. and Kohel, D.R.},
volume = 2369,
series = {Lecture Notes in Computer Science},
month = jul,
publisher = {Springer Berlin / Heidelberg},
abstract = { Dans cet article, nous d\'ecrivons des am\'eliorations \`a
l'algorithme ``Function Field Sieve'' (FFS) utilis\'e pour
le calcul de logarithmes discrets dans GF$({p^n})$ quand p
est petit. Notre contribution principale est une nouvelle
fa{\c{c}}on de construire les corps de fonctions
n\'ecessaires \`a l'algorithme. Avec cette nouvelle
construction, la complexit\'e heuristique est aussi bonne
que la complexit\'e de celle propos\'ee par Adleman et Huang
en 1999, i.e $L_{p^n}[1/3,c] = exp((c+o(1))log(p^n)^(1/3)log
(log (p^n))^(2/3))$ o\`u $c = (32/9)^(1/3)$. Avec ces deux
constructions, FFS devient un \'equivalent du crible
alg\'ebrique sp\'ecial utilis\'e pour factoriser des entiers
de la forme $A^N +/- B$. D'un point de vue asymptotique,
c'est plus rapide que des algorithmes plus anciens commme
celui de Coppersmith ou la version initiale de FFS
d'Adleman. D'un point de vue pratique, nous mettons en avant
que cette construction a de meilleures propri\'et\'es que la
construction d'Adleman et Huang. Nous d\'emontrons
l'efficacit\'e de l'algorithme en calculant avec succ\`es
des logarithmes discrets dans un grand corps fini de
caract\'eristique 2, i.e GF$({2^{521}})$. },
urlin = {<../file/JL02.pdf},
urlout = {http://dx.doi.org/10.1007/3-540-45455-1_34}
}
@article{JL03,
author = {Joux, A. and Lercier, R.},
title = {{Improvements to the general number field sieve for discrete
logarithms in prime fields. A comparison with the Gaussian
integer method}},
journal = {Mathematics of Computation},
year = 2003,
volume = 72,
number = 242,
pages = {953--967},
month = apr,
abstract = {Dans cet article, nous pr\'esentons de nombreuses
am\'eliorations au sujet du crible alg\'ebrique. Notre
principale contribution consiste en une nouvelle fa\c con de
calculer des logarithmes individuels avec le crible
alg\'ebrique sans avoir pour autant \`a r\'esoudre un grand
syst\`eme lin\'eaire pour chaque logarithme. Nous montrons
que, avec ces am\'eliorations, le crible alg\'ebrique est
plus efficace que la m\'ethode des entiers gaussiens \`a
partir de modulo d'une centaine de chiffres. Nous illustrons
aussi nos r\'esultats par le calcul effectif de logarithmes
discrets dans un grand corps premier. },
urlin = {../file/JL03.pdf},
urlout = {http://dx.doi.org/10.1090/S0025-5718-02-01482-5}
}
@unpublished{JL04,
author = {Jaulmes, E. and Lercier, R.},
title = {{FRMAC, a Fast Randomized Message Authentication Code}},
note = {Cryptology ePrint Archive, Report 2004/166},
month = jul,
year = 2004,
abstract = { Nous revisitons l'approche randomis\'ee introduite dans la
conception du code d'authentification de message RMAC afin
de construire un MAC avec des propri\'et\'es similaires,
except\'e qu'il repose sur une famille de fonctions de
hachage $\varepsilon$-universelle de type Wegman-Carter
plut\^ot que sur une cha\^\i{}ne CBC. Cela conduit \`a un
nouveau code d'authentification de message que nous appelons
FRMAC dont les bornes de s\'ecurit\'e sont, comme pour RMAC,
au del\`a de la limite classique du paradoxe des
anniversaires. Avec des fonctions de hachage efficaces en
logiciel, les performances de RMAC sont pour de grands
messages similaire \`a celles des sch\'emas les plus rapides
connus aujourd'hui. FRMAC peut aussi \^etre
significativement plus efficace pour de petits messages. De
plus, d\^u \`a des contraintes relax\'ees sur les vecteurs
d'initialisations dans la preuve de s\'ecurit\'e, la mise en
{\oe}uvre de FRMAC dans les applications r\'eelles est
facilit\'ee.},
urlin = {../file/JL04.pdf},
urlout = { http://eprint.iacr.org/2004/166 }
}
@inproceedings{JL06,
author = {Joux, A. and Lercier, R.},
title = {{The Function Field Sieve in the Medium Prime Case}},
booktitle = {Advances in Cryptology - EUROCRYPT 2006: 24th Annual
International Conference on the Theory and Applications of
Cryptographic Techniques, St. Petersburg, Russia, May 28 -
June 1, 2006. Proceedings},
pages = {254--270},
year = 2006,
editor = {Vaudenay, S.},
volume = 4004,
series = {Lecture Notes in Computer Science},
month = may,
publisher = {Springer Berlin / Heidelberg},
abstract = { Dans cet article, nous \'etudions l'application de
l'algorithme de crible dans les corps de fonctions
alg\'ebriques pour calculer des logarithmes discrets dans
des corps finis de la forme GF$({q^n})$ quand $q$ est une
puissance de nombre premier de taille moyenne. Cette
approche est une alternative \`a des r\'esultats r\'ecents
de Granger et Vercauteren pour calculer des logarithmes
discrets dans des tores, utilisant une repr\'esentation
efficace. Nous montrons que quand $q$ n'est pas trop large,
une variante tr\`es efficace du crible dans les corps de
fonctions peut \^etre mise en {\oe}uvre. De fa\c con
surprenante, avec cet algorithme, les calculs sont m\^eme
plus faciles que pour des corps premiers ou de
caract\'eristique deux. Nous montrons aussi que ce nouvel
algorithme a des cons\'equences sur la s\'ecurit\'e de
cryptosyst\`emes existants, tels que la cryptographie \`a
base de tore dans $T_{30}$, des sch\'emas de signature
courtes en caract\'eristique trois et des cryptosyst\`emes
bas\'es sur des vari\'et\'es ab\'eliennes
supersinguli\`eres. Mais par ailleurs, des cryptosyst\`emes
mettant en {\oe}uvre des corps de plus grande
caract\'eristique et des degr\'es d'extension plus petits,
typiquement de degr\'e au plus 6, tels que LUC, XTR ou tore
de type $T_6$, ne sont pas touch\'es.},
urlin = {../file/JL06.pdf},
urlout = {http://dx.doi.org/10.1007/11761679_16}
}
@unpublished{JL06a,
author = {Joux, A. and Lercier, R.},
title = {{Counting points on elliptic curves in medium
characteristic}},
note = {Cryptology ePrint Archive, Report 2006/176},
month = may,
year = 2006,
abstract = {Dans cet article, nos revisitons le probl\`eme du calcul du
noyau d'une isog\'enie s\'eparable de degr\'e $l$ entre deux
courbes elliptiques d\'efinies sur un corps finis GF$({q})$
de caract\'eristique $p$. Nous d\'ecrivons un algorithme de
complexit\'e asymptotique proche de $O(l^2(1+l / p)\log q)$
op\'erations \'el\'ementaires. Cet algorithme est
particuli\`erement utile quand $l > p$ et comme
sous-produit, nous obtenons une am\'elioration de
l'algorithme de comptage de point SEA pour de petites
valeurs de $p$. Plus pr\'ecis\'ement, nous obtenons une
complexit\'e heuristique proche de $O(\log^{4} q)$ et une
complexit\'e en espace \'egale \`a $O(\log^{2} q)$, dans le
cas jusqu'\`a pr\'esent d\'efavorable o{\`u} $p$ est proche
de $\log q$. Compar\'ee aux meilleurs algorithmes
aujourd'hui connus pour compter des points, les
n\'ecessit\'es m\'emoire de notre variante de SEA sont plus
petites d'un facteur $\log^2 q$.},
urlin = {../file/JL06a.pdf},
urlout = { http://eprint.iacr.org/2006/176 }
}
@inproceedings{JL07,
author = {Joux, A. and Lercier, R.},
title = {Algorithmes pour r{\'e}soudre le probl{\`e}me du logarithme
discret dans les corps finis},
booktitle = {Nouvelles M{\'e}thodes Math{\'e}matiques en Cryptographie},
year = 2007,
organization = {Soci{\'e}t{\'e} Math{\'e}matique de France},
series = {Fascicules Journ{\'e}es Annuelles},
month = jun,
pages = {23--53},
abstract = { Avec la publication d'un grand nombre de sch\'emas
cryptographiques \`a base d'accouplements de Weil sur
courbes elliptiques ou \`a base de tores alg\'ebriques, la
r\'esolution du probl\`eme du logarithme discret dans le
groupe multiplicatif d'un corps fini fait l'objet d'un
int\'er\^et renouvel\'e. Dans ce texte, nous nous
int\'eressons \`a trois algorithmes r\'ecents qui permettent
de r\'esoudre ce probl\`eme en toute g\'en\'eralit\'e, sans
limitation sur le degr\'e ou la caract\'eristique du corps,
et qui sont de complexit\'es similaires \`a celles des
algorithmes connus pour les corps premiers et les corps de
caract\'eristique deux.},
urlin = {../file/JL07.pdf},
urlout = {http://smf.emath.fr/VieSociete/JourneeAnnuelle/2007}
}
@inproceedings{JLNT09,
author = {Joux, A. and Lercier, R. and Naccache, D. and Thom{\'e}, E.},
title = {{Oracle-Assisted Static Diffie-Hellman Is Easier Than
Discrete Logarithms}},
month = dec,
year = 2009,
booktitle = {Cryptography and Coding},
volume = 5921,
series = {Lecture Notes in Computer Science},
editor = {Parker, MatthewG.},
pages = {351-367},
publisher = {Springer Berlin Heidelberg},
note = {Twelfth IMA International Conference on Cryptography and
Coding conference, Royal Agricultural College, Cirencester,
UK.},
abstract = { Cet article généralise l'algorithme de
Joux-Naccache-Thom\'e's de calcul de racine $e$-ième assisté
par oracle au cas du problème statique Diffie-Hellman
({SDHP}). Le nouvel algorithme s'applique à différents corps
finis sur une base {NFS} ou { FFS}. Dans les deux cas,
après interactions avec un oracle {SDHP}, l'attaquant est en
mesure de résoudre de nouvelles instances {SDHP}, {\sl
inconnues avant la phase de requètes}. Bien que de
complexité sous-exponentielle, l'algorithme est
significativement plus rapide que toutes les méthodes de
type {DLP} ou { SDHP} connues. Nous étudions l'applicabilité
de cette technique à de nombreux cryptosystèmes. Les
attaques ont été implantées pour GF$({2^{1025}})$ et
GF$({p})$, avec $p$ sur $516$ bits. },
urlin = {../file/JLNT09.pdf},
urlout = {http://dx.doi.org/10.1007/978-3-642-10868-6_21}
}
@inproceedings{JLSV06,
author = {Joux, A. and Lercier, R. and Smart, N. and Vercauteren, F.},
title = {{The Number Field Sieve in the Medium Prime Case}},
booktitle = {Advances in Cryptology - CRYPTO 2006. 26th Annual
International Cryptology Conference, Santa Barbara,
California, USA, August 20-24, 2006, Proceedings},
pages = {326--344},
year = 2006,
editor = {Dwork, C.},
volume = 4117,
series = {Lecture Notes in Computer Science},
month = aug,
publisher = {Springer Berlin / Heidelberg},
abstract = {Dans cet article, nous \'etudions plusieurs variantes du
crible alg\'ebrique pour calculer des logarithmes discrets
dans des corps finis de la forme GF$({p^n})$, avec $p$ un
nombre premier de taille moyenne \`a grande. Nous exhibons
pour $n$ pas trop grand un algorithme de complexit\'e
$L_{p^n}(1/3)$, d'efficacit\'e similaire \`a celle du crible
alg\'ebrique classique pour les corps finis premiers. Cette
approche compl\'emente les r\'esultats r\'ecents de Joux et
Lercier sur le crible dans les corps de fonctions. Si l'on
combine les deux r\'esultats, on en d\'eduit que calculer
des logarithmes discrets atteint une complexit\'e
heuristique \'egale \`a $L_{p^n}(1/3)$ dans tous les corps
finis. Pour illustrer l'efficacit\'e de notre algorithme,
nous calculons des logarithmes discrets dans un corps
GF$({p^3})$ avec un nombre d'\'el\'ements de 120 chiffres. },
urlin = {../file/JLSV06.pdf},
urlout = {http://dx.doi.org/10.1007/11818175_19}
}
@inproceedings{KLR10,
author = {Kammerer, J.-G. and Lercier, R. and Renault, G.},
title = {{Encoding Points on Hyperelliptic Curves over Finite Fields
in Deterministic Polynomial Time}},
booktitle = {{Pairing-Based Cryptography - Pairing 2010}},
pages = {278--297},
year = 2010,
editor = {Joye, M. and Miyaji, A. and Otsuka, A.},
volume = 6487,
series = {Lecture Notes in Computer Science},
month = dec,
publisher = {Springer},
note = {Eprint arxiv 1005.1454 (version préliminaire)},
abstract = { Nous introduisons de nouvelles fonctions de hachage vers
des courbes hyperelliptiques définies sur un corps fini. Ces
fonctions visent à instancier des protocoles
cryptographiques où l'on a besoin de faire correspondre des
chaînes de caractères à des points définis sur des courbes
algébriques, typiquement lorsque l'on doit déduire une clef
publique de l'identité d'un abonné. À l'inverse de
l'encodage proposé par Icart, nous partons de polynômes
résolubles par radicaux et nous obtenons des modèles de
courbes qui admettent un encodage déterministe. En suivant
cette stratégie, nous obtenons un encodage de bas degré pour
les courbes elliptiques hessiennes, et pour la première
fois, des fonctions de hachages pour des courbes de genre
2. Plus généralement, nous proposons en tout genre des
familles (plus restreintes) de courbes hyperelliptiques avec
cette propriété. L'image de ces encodages est assez étendue
pour être des encodages ``faibles'', au sens de Brier et
al. Comme tels, ils peuvent aisément devenir des fonctions
de hachage cryptographiques. },
urlin = {../file/KLR10.pdf},
urlout = {http://dx.doi.org/10.1007/978-3-642-17455-1_18}
}
@inproceedings{LL03,
author = {Lercier, R. and Lubicz, D},
title = {{Counting Points on Elliptic Curves over Finite Fields of
Small Characteristic in Quasi Quadratic Time}},
booktitle = {Advances in Cryptology - EUROCRPYT 2003: International
Conference on the Theory and Applications of Cryptographic
Techniques, Warsaw, Poland, May 4-8, 2003. Proceedings},
pages = {360--373},
year = 2003,
editor = {Biham, E.},
volume = 2656,
series = {Lecture Notes in Computer Science},
month = may,
publisher = {Springer Berlin / Heidelberg},
abstract = { Soit $p$, un petit nombre premier et $q=p^n$. Soit $E$ une
courbe elliptique d\'efinie sur GF$(q))$. Nous proposons un
algorithme qui calcule sans pr\'ecalculs le $j$-invariant du
relev\'e canonique de $E$ pour un co\^ut de $O(\log n)$ fois
le co\^ut n\'ecessaire au calcul du relev\'e d'une puissance
du Frobenius. Soit $M$ d\'efini comme \'etant une constante
telle que le produit de deux entiers de $n$ bits peut \^etre
r\'ealis\'e en $O(n^\mu)$ op\'erations \'el\'ementaires,
cela conduit \`a un algorithme pour calculer le nombre de
points d'une courbe elliptique qui atteint, au prix d'une
complexit\'e en espace de $O(n^{5/2})$, une borne
th\'eorique de complexit\'e en temps \'egale \`a
$O(n^{\max(1.19, \mu)+\mu+1/2}\log n)$. Quand le corps \`a
une Base Normale Gaussienne de petit type, on obtient de
plus un algorithme de complexit\'e en temps \'egale \`a
$O(\log(n)n^{2\mu})$ et en espace \'egale \`a $O(n^2)$. D'un
point de vue pratique, l'algorithme correspondant est
particuli\`erement bien adapt\'e \`a une implantation. Nous
soulignons cela par un calcul d'une taille de 100002 bits. },
urlin = {../file/LL03.pdf},
urlout = {http://dx.doi.org/10.1007/3-540-39200-9_22}
}
@article{LL06,
author = {Lercier, R. and Lubicz, D.},
title = {{A Quasi Quadratic Time Algorithm for Hyperelliptic Curve
Point Counting}},
journal = {The Ramanujan Journal},
year = 2006,
month = dec,
volume = 12,
number = 3,
pages = {399--423},
publisher = {Kluwer Academic Publishers},
abstract = {Nous d\'ecrivons un algorithme pour calculer la
cardinalit\'e de jacobiennes de courbes hyperelliptiques
ordinaires de petit genre d\'efinies sur des corps finis
GF$({2^n})$ avec complexit\'e $O(n^{2+o(1)})$. Cet
algorithme d\'erive d'id\'ees dues \`a Mestre. Plus
pr\'ecis\'ement, nous donnons les \'el\'ements
math\'ematiques derri\`ere l'algorithme de Mestre et
d\'eveloppons \`a partir de celui-ci une variante avec
complexit\'e quasi-quadratique. Entre autres choses, nous
pr\'esentons un algorithme pour trouver les racines d'un
syst\`eme d'\'equations d'Artin-Schreier g\'en\'eralis\'ees
et donnons les r\'esultats que nous obtenons avec une
implantation efficace. En particulier, nous avons pu
calculer la cardinalit\'e de courbes de genre un, deux ou
trois d\'efinies sur des corps finis de taille gigantesque.},
urlin = {../file/LL06.pdf},
urlout = {http://dx.doi.org/10.1007/s11139-006-0151-6}
}
@inbook{LLV06,
editor = {Cohen, H. and Frey, G.},
title = {{Handbook of Elliptic and Hyperelliptic Curve Cryptography}},
chapter = {17, Point Counting on Elliptic and Hyperelliptic Curves,
R. Lercier, D. Lubicz and F. Vercauteren},
publisher = {Chapman \& Hall/CRC},
year = 2006,
series = {Discrete Mathematics and its Applications},
pages = {407--449},
note = {K.H. Rosen, \'editeur de la collection},
abstract = { Le probl\`eme du logarithme discret pour des courbes
elliptiques et hyperelliptiques a gagn\'e beaucoup en
popularit\'e pour son utilisation comme primitive
cryptographique. La raison principale est qu'aucun
algorithme de complexit\'e sous-exponentielle pour calculer
des logarithmes discrets sur des courbes de petits genres
est aujourd'hui connu, except\'e dans de tr\`es rares
cas. Par cons\'equent, les cryptosyst\`emes \`a base de
courbe n\'ecessitent pour une s\'ecurit\'e similaire des
clefs de tailles bien plus petites que des clefs RSA. Cela
les rend particuli\`erement attractives pour les
implantation sur des supports contraints comme par exemple
des cartes \`a puce ou dans les applications \`a haut niveau
de s\'ecurit\'e.\\\\ Ce `` Handbook of Elliptic and
Hyperelliptic Curve Cryptography'' introduit la th\'eorie et
les algorithmes n\'ecessaire \`a une cryptographie de ce
type. Apr\`es une introduction math\'ematique tr\`es
compl\`ete, il propose des algorithmes pr{\^e}ts \`a
l'emploi pour les op\'erations de groupes ou le calcul
d'accouplement. Il explore les m\'ethodes pour compter des
nombres de points et construire des courbes avec
multiplication complexe, et propose des algorithmes
explicites. Il donne aussi un panorama sur les m\'ethodes
g\'en\'eriques pour la r\'esolution du logarithme discret et
d\'etaille les m\'ethodes de type ``index-calculus'' pour
les courbes hyperelliptiques. Pour des courbes tr\`es
sp\'eciales, le probl\`eme du logarithme discret peut-\^etre
transf\'er\'e vers un probl\`eme plus facile. Les
cons\'equences sont expliqu\'ees et les suggestions pour de
bons choix sont donn\'es. Les auteurs pr\'esentent des
applications clientes de protocoles \`a base de logarithmes
discrets (incluant les structures bilin\'eaires) et explique
l'utilisation de courbes elliptiques et hyperelliptiques
pour la factorisation ou la primalit\'e d'entiers. Deux
chapitres explorent leur mise en \oe{}uvre pour des
applications efficaces sur cartes \`a puce. Les aspects
pratiques et th\'eoriques des attaques par canaux
auxiliaires, des contremesures et un chapitre sur les
g\'en\'erateurs pseudo-al\'eatoires termine l'ouvrage. },
urlout = {http://www.crcpress.com/shopping_cart/products/product_detail.asp?sku=C5181&parent_pg=&pc=}
}
@article{LM00,
author = {Lercier, R. and Morain, F.},
title = {{Computing isogenies between elliptic curves over
GF$({p^n})$ using Couveignes's algorithm}},
journal = {Mathematics of Computation},
year = 2000,
volume = 69,
number = 229,
pages = {351--370},
month = jan,
abstract = { Le coeur des am\'eliorations d'Elkies \`a l'algorithme de
Schoof pour calculer la cardinalit\'e de courbes elliptiques
d\'efinies sur un corps fini est le calcul d'isog\'enies
entre courbes. L'approche d'Elkies est bien adapt\'ee au cas
o\`u la caract\'eristique du corps est grande. Couveignes a
montr\'e comment calculer des isog\'enies en petite
caract\'eristique. Le but de cet article est de d\'ecrire la
premi\`ere implantation r\'eussie de l'algorithme de
Couveignes. En particulier, on d\'ecrit l'utilisation
d'algorithmes rapides pour r\'ealiser des op\'erations
incr\'ementales sur des s\'eries. On insiste aussi sur le
cas particulier de la caract\'eristique 2. },
urlin = {../file/LM00.pdf},
urlout = {http://dx.doi.org/10.1090/S0025-5718-99-01081-9}
}
@inproceedings{LM95,
author = {Lercier, R. and Morain, F.},
title = {{Counting the Number of Points on Elliptic Curves over
Finite Fields: Strategies and Performances}},
booktitle = {Advances in Cryptology - EUROCRYPT '95: International
Conference on the Theory and Application of Cryptographic
Techniques, Saint-Malo, France, May 1995. Proceedings},
pages = {79--94},
year = 1995,
editor = {Guillou, L.C. and Quisquater, J.-J.},
volume = 921,
series = {Lecture Notes in Computer Science},
month = may,
publisher = {Springer Berlin / Heidelberg},
abstract = { Les sch\'emas cryptographiques utilisant des courbes
elliptiques sur des corps finis n\'ecessitent le calcul de
la cardinalit\'e de ces courbes. Des progr\`es importants
ont \'et\'e r\'ealis\'es r\'ecemment dans ce domaine. Le but
de cet article est de mettre en lumi\`ere ces
am\'eliorations et de d\'ecrire une implantation efficace de
celles-ci dans le cas particulier des corps GF$({2^n})$,
pour $n \leq 500$. },
urlin = {../file/LM95.pdf},
urlout = {http://dx.doi.org/10.1007/3-540-49264-X_7}
}
@techreport{LM95a,
author = {Lercier, R. and Morain, F.},
title = {{Counting points on elliptic curves over GF$({p^n})$ using
Couveignes's algorithm}},
institution = {Laboratoire d'Informatique de l'{\'E}cole polytechnique
(LIX)},
year = 1995,
type = {Research report},
number = {LIX/RR/95/09},
abstract = { L'am\'elioration apport\'ee par Elkies \`a l'algorithme de
Schoof qui calcule la cardinalit\'e d'une courbe elliptique
sur un corps fini repose sur le calcul d'isog\'enies entre
courbes. L'approche d'Elkies est tr\`es bien adapt\'ee au
cas o\`u la caract\'eristique du corps est grande,
Couveignes a montr\'e comment calculer ces isog\'enies quand
cette caract\'eristique est petite. Cet article a pour but
de d\'ecrire la premi\`ere implantation efficace de cet
algorithme et de donner de nombreux exemples de
calculs. Nous d\'ecrivons en particulier l'utilisation
d'algorithmes rapides de calculs incr\'ementaux sur les
s\'eries. Nous insistons \'egalement sur le cas particulier
de la caract\'eristique 2. },
urlin = {../file/LM95a.pdf}
}
@inproceedings{LM98,
author = {Lercier, R. and Morain, F.},
title = {{Algorithms for computing isogenies between elliptic
curves}},
booktitle = {{Computational Perspectives on Number Theory: Proceedings of
a Conference in Honor of A. O. L. Atkin}},
pages = {77--96},
year = 1998,
editor = {Buell, D.A. and Teitelbaum, J.T.},
volume = 7,
series = {AMS/IP Studies in Advanced Mathematics},
publisher = {American Mathematical Society \& Internationnal Press},
address = {Providence},
note = {Tenu en 1995 {\`a} l'Universit{\'e} de l'Illinois, Chicago},
abstract = { Une implantation efficace de l'algorithme de Schoof pour
calculer la cardinalit\'e de courbes elliptiques d\'efinies
sur des corps finis n\'ecessite le calcul d'isog\'enies
entre courbes elliptiques. Nous faisons un survol des
algorithmes utilis\'es pour r\'ealiser cette t\^ache. Quand
la caract\'eristique du corps est grande, la fonction
P-Weierstrass peut \^etre utilis\'ee. Quand la
caract\'eristique du corps est petite, nous avons maintenant
trois algorithmes \`a notre disposition, deux dus \`a
Couveignes et un du premier auteur. Nous traitons le m\^eme
exemple en utilisant ces trois algorithmes et effectuons
quelques comparaisons entre eux. },
urlin = {../file/LM98.pdf},
urlout = {
http://www.ams.org/bookstore?fn=20&arg1=amsipseries&item=AMSIP-7
}
}
@article{LR12,
author = {Lercier, R. and Ritzenthaler, C.},
title = {Hyperelliptic curves and their invariants: Geometric,
arithmetic and algorithmic aspects},
publisher = {Elsevier},
journal = {Journal of Algebra},
month = dec,
year = 2012,
volume = 372,
number = 0,
pages = {595--636},
abstract = {Nous nous appuyons sur la théorie classique des invariants
des formes binaires pour caractériser explicitement à
isomorphisme prêt les courbes hyperelliptiques de petit
genre, et inversement, nous proposons des algorithmes de
reconstruction de modèles hyperelliptiques à partir
d'invariants donnés. Nous nous concentrons sur le cas du
genre 3. À la fois les aspects géométriques et arithmétiques
sont considérés.
Certaines des équations citées dans cet
article sont disponibles ici : \url{../file/hg3data.txt}},
urlin = {../file/LR11.pdf},
urlout = {http://dx.doi.org/10.1016/j.jalgebra.2012.07.054}
}
@inproceedings{LRS12,
author = {Lercier, R. and Ritzenthaler, C. and Sijsling, J.},
title = {Fast computation of isomorphisms of hyperelliptic curves and
explicit descent},
booktitle = {Actes de tenth Algorithmic Number Theory Symposium ANTS-X},
year = 2012,
editor = {K. Kedlaya},
month = jul,
publisher = {Mathematical Sciences Publishers},
note = {À paraître.},
abstract = {Nous montrons comment accélérer le calcul d'isomorphismes de
courbes hyperelliptiques en utilisant des covariants. Nous
obtenons ainsi de nouveaux résultats théoriques et pratiques
concernant le modèle de ces courbes au dessus de leurs corps
des modules.},
urlin = {../file/LRS12.pdf},
urlout = {http://msp.org/publications/books/}
}
@article{LRS13,
author = {Lercier, R. and Ritzenthaler, C. and Sijsling, J.},
title = {Explicit Galois obstruction and descent for hyperelliptic
curves with tamely cyclic reduced automorphism group},
year = 2013,
month = jan,
note = {Soumis pour publication},
abstract = {Cet article est consacré à la description explicite des
obstructions à la descente galoisienne de courbes
hyperelliptiques de genre arbitraire dont le groupe
d'automorphismes réduit est cyclique d'ordre premier avec la
caractéristique du corps de définition. Incidemment, nous
obtenons un critère arithmétique pour l'existence d'une
descente hyperelliptique. L'obstruction est décrite par les
invariants dihédraux arithmétiques des courbes en
question. Dans le cas où cette obstruction disparaît, ces
mêmes invariants permettent de déterminer d'un modèle au
dessus du corps des modules; sinon on obtient un modèle
hyperelliptique au dessus d'une extension de degré deux.},
urlin = {../file/LRS13.pdf},
urlout = {http://arxiv.org/abs/1301.0695}
}
@article{LS08,
author = {Lercier, R. and Sirvent, T.},
title = {On Elkies subgroups of $l$-torsion points in elliptic curves
defined over a finite field},
journal = {Journal de {T}h{\'e}orie des {N}ombres de {B}ordeaux},
year = 2008,
month = dec,
volume = 20,
number = 3,
pages = {783--797},
abstract = { En sous-r\'esultat de l'algorithme de Schoof-Elkies-Atkin
pour compter le nombre de points d'une courbe elliptique
d\'efinie sur un corps fini de caract\'eristique $p$, il
existe un algorithme qui, pour $l$ un nombre premier
d'Elkies, calcule des points de $l$-torsion dans une
extension de degr\'e $l-1$ \`a l'aide de $O${\~{}}$(l \,
\max(l, \log q)^2)$ op\'erations \'el\'ementaires \`a
condition que $l\le p/2$. Nous combinons ici un algorithme
rapide d\^u \`a Bostan, Morain, Salvy et Schost avec
l'approche $p$-adique suivie par Joux et Lercier pour
obtenir un algorithme valide sans limitation sur $l$ et $p$
et de complexit\'e similaire. Par soucis de simplification,
nous d\'ecrivons précisément ici l'algorithme dans le cas
des corps finis de caract\'eristique $p\ge 5$. Nous
l'illustrons aussi avec quelques exp\'erimentations. },
urlin = {../file/LS08.pdf},
urlout = {http://dx.doi.org/10.5802/jtnb.650}
}
@inproceedings{Ler04,
author = {Lercier, R.},
title = {{Courbes Elliptiques et cryptographie}},
booktitle = {Direction des Centres d'Expertise et d'Essais},
pages = {59--66},
publisher = {D\'el\'egation g\'en\'erale pour l'armement},
year = 2004,
number = 64,
series = {Revue Scientifique et Technique de la Defense},
month = jun,
abstract = {Cet article dresse un panorama sur l'utilisation de courbes
elliptiques en cryptographie. L'approche suivie est
chronologique. On commence par rappeler les articles
scientifiques fondateurs. On poursuit par un \'etat de l'art
sur les m\'ethodes algorithmiques pour calculer le nombre de
points sur courbes elliptiques. On termine par quelques
applications. },
urlin = {../file/Ler04.pdf}
}
@unpublished{Ler05,
author = {Lercier, R.},
title = {{Contributions {\`a} l'arithm{\'e}tique de la
cryptographie}},
note = {Manuscrit soumis pour l'``Habilitation \`a diriger des
recherches'', Universit{\'e} d'Aix-Marseille II, U.F.R. de
Science. Campus de Luminy, Marseille},
month = nov,
year = 2005,
abstract = {Ce document constitue le document soumis en vue de
l'obtention du dipl\^ome d'habilitation \`a diriger des
recherches.},
urlin = {../file/Ler05.pdf}
}
@mastersthesis{Ler93,
author = {Lercier, R.},
title = {{Factoriser des entiers par la m{\'e}thode des courbes
elliptiques}},
school = {{\'E}cole polytechnique},
year = 1993,
address = {Palaiseau},
month = jul,
abstract = { Implantation et optimisation de l'algorithme de Lenstra
pour factoriser des entiers avec des courbes elliptiques. },
urlin = {../file/Ler93.pdf}
}
@inproceedings{Ler96,
author = {Lercier, R.},
title = {{Computing isogenies in GF$({2^n})$}},
booktitle = {Algorithmic Number Theory: Second International Symposium,
ANTS-II Talence, France, May 18--23, 1996 Proceedings},
pages = {197--212},
year = 1996,
editor = {Cohen, H.},
volume = 1122,
series = {Lecture Notes in Computer Science},
month = may,
publisher = {Springer Berlin / Heidelberg},
abstract = { Contrairement \`a ce qui se passe dans les corps finis
premiers de grande caract\'eristique, le co\^ut majeur
lorsque l'on compte le nombre de points d'une courbe
elliptique E d\'efinie sur GF$({2^n})$ est le calcul
d'isog\'enies de degr\'e premier $l$. La meilleure m\'ethode
connue jusqu'\`a pr\'esent est due \`a Couveignes et
n\'ecessite asymptotiquement $O(l^3)$ op\'erations dans le
corps. Nous soulignons dans cet article quelques
propri\'et\'es remarquables satisfaites par ces isog\'enies
et montrons comment on peut obtenir d'elles un nouvel
algorithme qui semble meilleur en pratique que celui de
Couveignes avec la m\^eme complexit\'e. Sur un probl\`eme
repr\'esentatif, on gagne un facteur 5 sur le calcul total.},
urlin = {../file/Ler96.pdf},
urlout = {http://dx.doi.org/10.1007/3-540-61581-4_55}
}
@inproceedings{Ler97,
author = {Lercier, R.},
title = {{Finding Good Random Elliptic Curves for Cryptosystems
Defined Over GF$({{2}^{n}})$}},
booktitle = {Advances in Cryptology - EUROCRYPT '97: International
Conference on the Theory and Application of Cryptographic
Techniques, Konstanz, Germany, May 1997. Proceedings},
pages = {379--392},
year = 1997,
editor = {Fumy, W.},
volume = 1233,
series = {Lecture Notes in Computer Science},
month = may,
publisher = {Springer Berlin / Heidelberg},
abstract = { L'une des difficult\'es principales pour implanter des
sch\'emas cryptographiques bas\'es sur des courbes
elliptiques d\'efinies sur des corps finis est le
n\'ecessaire calcul de la cardinalit\'e de ces courbes. Dans
le cas de corps finis GF$({2^n})$, des avanc\'ees
th\'eoriques ont amen\'e \`a une acc\'el\'eration
significative des calculs. Une fois d\'ecrit certaine de ces
id\'ees dans la premi\`ere partie de cet article, nous
montrons que notre nouvelle implantation fonctionne de 2 \`a
10 fois plus rapidement que ce qui a \'et\'e fait
auparavant. Dans la seconde partie, nous exhibons une
l\'eg\`ere modification de l'algorithme de Schoof pour
choisir des courbes avec un nombre de points "presque
premier" et ainsi des sch\'emas cryptographiques elliptiques
bas\'es sur des courbes al\'eatoires au lieu de courbes
sp\'ecifiques comme c'\'etait le cas jusqu'\`a pr\'esent. },
urlin = {../file/Ler97.pdf},
urlout = {http://dx.doi.org/10.1007/3-540-69053-0_26}
}
@phdthesis{Ler97a,
author = {Lercier, R.},
title = {{Algorithmique des Courbes Elliptiques dans les Corps
Finis}},
school = {{\'E}cole polytechnique},
year = 1997,
address = {Palaiseau},
month = jun,
abstract = { Cette th\`ese est consacr\'ee au calcul du nombre de points
d'une courbe elliptique d\'efinie sur un corps fini. Nous
\'etudions dans une premi\`ere partie l'algorithme de Schoof
et ses variantes dues \`a Atkin et \`a Elkies. Nous montrons
ainsi en quelle mesure ces algorithmes, initialement
pr\'evus pour des corps de grande caract\'eristique, peuvent
s'appliquer \`a ceux de petite caract\'eristique.\\\\ Il
s'av\`ere que la majeure partie des id\'ees d'Atkin et
Elkies sont applicables \`a cette derni\`ere famille de
corps, \`a quelques modifications mineures pr\`es, except\'e
le calcul d'isog\'enies entre courbes elliptiques. C'est
pourquoi, nous \'etudions dans une deuxi\`eme partie cinq
algorithmes de calcul d'isog\'enies. Le premier algorithme
est l'algorithme original d'Atkin pour le cas des corps de
grande caract\'eristique. Les deuxi\`eme et troisi\`eme
algorithme sont ceux de Couveignes pour les corps de petite
caract\'eristique. Enfin, nous proposons \`a notre tour un
quatri\`eme algorithme pour le cas sp\'ecifique de la
caract\'eristique deux et montrons dans un cinqui\`eme
algorithme comment ces id\'ees peuvent se g\'en\'eraliser
\`a des corps de caract\'eristique $p$ impaire pour des
isog\'enies de degr\'e $l$ born\'e par $2p$.\\\\ D'un point
de vue plus pratique, nous explicitons dans une troisi\`eme
partie les m\'ethodes de programmation mises en oeuvre pour
implanter les algorithmes pr\'ec\'edents. Nous y
pr\'esentons notamment ZEN, une librairie de calcul qui
permet une programmation efficace en langage C de toute
extension alg\'ebrique d'un anneau fini. Enfin, nous
expliquons comment nous utilisons le programme obtenu pour
calculer efficacement le nombre de points de courbes
d\'efinies dans tout corps finis \`a moins de $10^{100}$
\'el\'ements. En particulier, nous montrons comment trouver
ainsi des courbes elliptiques ayant de bonnes propri\'et\'es
cryptographiques.},
urlin = {../file/Ler97a.pdf}
}
|
![[fr]](../inc/img/skin/medicis/fr.gif)
![[en]](../inc/img/skin/medicis/en.gif)
