Christophe Petit

Published and Accepted Work
Preprints and Technical Reports

Links to my Google Scholar page, DBLP page, ORCID page, Scopus publications page.


Published and Accepted Work

Better Path Finding Algorithms in LPS Ramanujan graphs
Eduardo Carvalho Pinto, Christophe Petit
To appear in Journal of Mathematical Cryptology.

Quasi-subfield polynomials and the Elliptic Curve Discrete Logarithm Problem.
Ming-Deh A. Huang, Michiel Kosters, Christophe Petit, Sze Ling Yeo, Yang Yun.
Accepted for presentation at MathCrypt 2018. To appear in Journal of Mathematical Cryptology.

An improvement to the quaternion analogue of the L-isogeny path problem
Christophe Petit, Spike Smith.
Accepted for presentation at MathCrypt 2018 (extended abstract).

Hard and Easy Problems in Supersingular Isogeny Graphs
Christophe Petit, Kristin Lauter
To appear at EUROCRYPT 2018 as a merge under the title "Supersingular isogeny graphs and endomorphism rings: reductions and solutions"
I recommend reading the
original paper rather than the proceedings version. See also here.

A practical cryptanalysis of WalnutDSA
Daniel Hart, DoHoon Kim, Giacomo Micheli, Guillermo Pascual Perez, Christophe Petit and Yuxuan Quek
To appear at PKC 2018.
Eprint. Code. Oxford's Mathematical Institute's account of the story
.
Faster algorithms for isogeny problems using torsion point images
Christophe Petit.
ASIACRYPT 2017 - Advances in Cryptology
Eprint. Proceedings.

Identification Protocols and Signature schemes based on supersingular isogeny problems (BEST PAPER AWARD)
Steven Galbraith, Christophe Petit, Javier Silva Velon.
ASIACRYPT 2017 - Advances in Cryptology
Extended version to appear in Journal of Cryptology.
Eprint. Proceedings.

Full Cryptanalysis of Hash Functions Based on Cubic Ramanujan Graphs
Hyungrok Jo, Christophe Petit, Tsuyoshi Takagi
IEICE Transactions, Volume E100.A, No. 9, pp.1891-1899, 2017.
Paper.

On the Security of Supersingular Isogeny Cryptosystems
Steven Galbraith, Christophe Petit, Barak Shani, Yan Bo Ti
ASIACRYPT 2016 - Advances in Cryptology
Eprint. Proceedings.

A Generalized Successive Resultant Algorithm
James Davenport, Christophe Petit, and Benjamin Pring
WAIFI 2016 - Arithmetic of Finite Fields
Proceedings

Efficient Zero-Knowledge Protocols for Arithmetic Circuits in the Discrete Log Setting
Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, Christophe Petit
EUROCRYPT 2016 - Advances in Cryptology
Eprint. Proceedings.

Algebraic approaches for the elliptic curve discrete logarithm problem over prime fields
Christophe Petit, Michiel Kosters, Ange Messeng
PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography
Eprint. Proceedings.

Cryptographic Hash Functions and Expander Graphs: The End of the Story ?
Christophe Petit and Jean-Jacques Quisquater
The New Codebreakers - Essays Dedicated to David Kahn on the Occasion of His 85th Birthday. 2016.

Short Accountable Ring Signatures from the DDH Assumption
Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Essam Ghadafi, Jens Groth, Christophe Petit
ESORICS 2015 - 20th European Symposium on Research in Computer Security
Eprint.

First fall degree and Weil Descent
Tim Hodges, Christophe Petit and Jacob Schlather
Finite Fields and their Applications, Volume 30, November 2014, Pages 155-177.
Preliminary version presented at YACC2012 conference under the title Degree of Regularity for Systems arising from Weil Descent
Paper.

On the quaternion $\ell$-isogeny path problem
David Kohel, Kristin Lauter, Christophe Petit, Jean-Pierre Tignol
LMS Journal of Computation and Mathematics, Volume 17, Issue A, pp 418-432, 2014. Special issue for ANTS, Algorithmic Number Theory Symposium conference.
Preprint. LMS link.

Finding Roots in GF(p^n) with the Successive Resultant Algorithm
Christophe Petit
LMS Journal of Computation and Mathematics, Volume 17, Issue A, pp 203-217, 2014. Special issue for ANTS, Algorithmic Number Theory Symposium conference.
Preprint. LMS link.

On a particular case of the bisymmetric equation for quasigroups
Christophe Petit, François-Xavier Standaert, Mathieu Renauld
Acta Mathematica Hungarica, Volume 143, Issue 2, pp 330-336, July 2014.
Preprint. Springer link

Rubik's for cryptographers
Christophe Petit and Jean-Jacques Quisquater
Mathematical Advance in Translation, Volume 33, Number 1, pp 5-13, April 2014.
NB: Chinese translation of the AMS Notices paper with the same title, with permission of the AMS.

Improvement of Faugère et al.'s method to solve ECDLP (BEST STUDENT PAPER AWARD)
Huang Yun-Ju, Christophe Petit, Naoyuki Shinohara, and Tsuyoshi Takagi
IWSEC 2013 - Advances in Information and Computer Security
Paper.

Rubik's for cryptographers
Christophe Petit and Jean-Jacques Quisquater
Notices of the American Mathematical Society, Volume 60, Number 6, pp 733-739, June/July 2013.
Paper. Extended version.

On polynomial systems arising from a Weil descent
Christophe Petit and Jean-Jacques Quisquater
ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security
Paper. Extended version.

Towards factoring in SL(2,2^n)
Christophe Petit
Design, Codes and Cryptography, Volume 71, Issue 3, pp 409-431, 2012.
Preprint. Springer link.

Improving the complexity of index calculus algorithms in elliptic curves over binary fields
Jean-Charles Faugère, Ludovic Perret, Christophe Petit, Guénaël Renault
EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques
Paper.

Masking with Randomized Look Up Tables (Towards Preventing Side-Channel Attacks of All)
François-Xavier Standaert, Christophe Petit, Nicolas Veyrat-Charvillon
Cryptography and Security: From Theory to Applications - Essays Dedicated to Jean-Jacques Quisquater on the Occasion of His 65th Birthday.
Paper.

Fresh Re-Keying II: Securing Multiple Parties against Side-Channel and Fault Attacks
Marcel Medwed, Christophe Petit, Francesco Regazzoni, Mathieu Renauld, and François-Xavier Standaert
CARDIS 2011 - 10th Smart Card Research and Advanced Application Conference
Paper.

Cayley hash functions
Christophe Petit, and Jean-Jacques Quisquater
Encyclopedia of cryptography and security - 2nd edition, 2011.

One-time trapdoor one-way functions
Julien Cathalo, Christophe Petit
ISC 2010 - 13th Information Security Conference
Paper. Extended version. Slides.

Preimage algorithms for the Tillich-Zémor hash function
Christophe Petit, and Jean-Jacques Quisquater
SAC 2010 - Selected areas in Cryptography
Paper. Slides.

Equitable Cake Cutting without Mediator
Sophie Mawet, Olivier Pereira and Christophe Petit
IT Bénélux 2010 - 5th Benelux Workshop on Information and System Security
Paper.

Cryptographic hash functions from expander graphs
Christophe Petit
PhD thesis, UCL (2009)
Text. Slides of the private defense. Slides of the public defense.

Hard and easy Components of Collision Search in the Zémor-Tillich Hash Function : New Instances and Reduced Variants with equivalent Security
Christophe Petit, Jean-Jacques Quisquater, Jean-Pierre Tillich and Gilles Zémor
CT-RSA 2009 - Topics in Cryptology, The Cryptographers' Track at the RSA Conference 2009
Paper. Slides at CT-RSA.

Full Cryptanalysis of LPS and Morgenstern Hash Functions
Christophe Petit, Kristin Lauter, and Jean-Jacques Quisquater
SCN 2008 - Sixth Conference on Security and Cryptography for Networks
Paper. Slides at SCN08.

Efficiency and Pseudo-Randomness of a Variant of Zémor-Tillich Hash Function
Christophe Petit, Nicolas Veyrat-Charvillon, and Jean-Jacques Quisquater
WIC'2008 - Symposium on Information Theory and Communication in the Bénélux
ISECS'2008 - The 15th IEEE International Conference on Electronics, Circuits and Systems (invited paper)

Paper. Slides at WIC08.

Fault Attacks on Public Key Elements: Application to DLP based Schemes
Chong Hee Kim, Philippe Bulens, Christophe Petit, and Jean-Jacques Quisquater
EUROPKI 2008 - Fifth European PKI Workshop
Paper. Slides.

A Block Cipher based Pseudo Random Number Generator Secure Against Side-Channel Key Recovery
Christophe Petit, François-Xavier Standaert, Olivier Pereira, Tal G. Malkin, Moti Yung
ASIACCS'08 - ACM Symposium on Information, Computer and Communications Security
Paper. Slides.


Preprints and Technical Reports

Secure Oblivious Transfer from Semi-Commutative Masking
Cyprien Delpech de Saint Guilhem, Emmanuela Orsini, Christophe Petit and Nigel Smart
Preprint.

Application of the affine geometry of GF(q^n) to root finding
Luca De Feo, Christophe Petit, and Michael Quisquater
Preprint

On Generalized First Fall Degree Assumptions
Huang Yun-Ju, Christophe Petit, Naoyuki Shinohara, and Tsuyoshi Takagi
Paper.

Bounding HFE with SRA
Christophe Petit
Preprint
Paper.

New subexponential algorithms for factoring in SL(2,2^n)
Jean-Charles Faugère, Ludovic Perret, Christophe Petit, Guénaël Renault
Paper.

Hardware Implementations of a Variant of the Zémor-Tillich Hash Function
Giacomo de Meulenaer, Christophe Petit and Jean-Jacques Quisquater
Preprint
Paper.

ZesT : an all-purpose hash function based on Zémor-Tillich
Christophe Petit, Giacomo de Meulenaer, Jean-Jacques Quisquater, Jean-Pierre Tillich, Nicolas Veyrat-Charvillon and Gilles Zémor
Preprint (2009)
Paper.

Hardware Implementations of a Variant of the Zémor-Tillich Hash Function
Giacomo de Meulenaer, Christophe Petit and Jean-Jacques Quisquater
Preprint (2009)
Paper.

Cayley Hashes: A Class of Efficient Graph-based Hash Functions
Christophe Petit, Kristin Lauter, and Jean-Jacques Quisquater
Preprint (2007)
Paper.

Anticipation des crises d'épilepsie par analyse dynamique des signaux électroencéphalographiques (in French)
Christophe Petit
UCL-FSA Master thesis (2005)