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

Faster algorithms for isogeny computations over extensions of finite fields
Shiping Cai, Mingjie Chen, Christophe Petit
NuTMic 2024, to appear in LNCS 14966.

Attacking trapdoors from matrix products
Thomas Decru, Tako Boris Fouotsa, Paul Frixons, Valerie Gilchrist, Christophe Petit
To appear in IACR Communications in Cryptology, Issue 3.

Improved algorithms for finding fixed-degree isogenies between supersingular elliptic curves
Benjamin Bencina, Péter Kutas, Simon-Philipp Merz, Miha Stopar, Charlotte Weitkämper
To appear at CRYPTO 2024

Solving the Tensor Isomorphism Problem for special orbits with low rank points: Cryptanalysis and repair of an Asiacrypt 2023 commitment scheme
Valerie Gilchrist and Laurane Marco and Christophe Petit and Gang Tang
To appear at CRYPTO 2024

Failing to hash into supersingular isogeny graphs
Jeremy Booher, Ross Bowden, Javad Doliskani, Tako Boris Fouotsa, Steven D. Galbraith, Sabrina Kunzweiler, Simon-Philipp Merz, Christophe Petit, Benjamin Smith, Katherine E. Stange, Yan Bo Ti, Christelle Vincent, José Felipe Voloch, Charlotte Weitkämper, Lukas Zobernig
To appear in the Computer Journal (2024)

Shorter quantum circuits
Vadym Kliuchnikov and Kristin Lauter and Romy Minko and Christophe Petit and Adam Paetznick
Quantum 7, 1208. Paper.

Hidden Stabilizers, the Isogeny To Endomorphism Ring Problem and the Cryptanalysis of pSIDH
Péter Kutas and Christophe Petit and Gábor Ivanyos and Mingjie Chen and Antonin Leroux and Muhammad Imran
To appear at ASIACRYPT 2023

Malleable Commitments from Group Actions and Zero-Knowledge Proofs for Circuits based on Isogenies
Mingjie Chen and Yi-Fu Lai and Abel Laval and Laurane Marco and Christophe Petit
To appear at INDOCRYPT 2023

Proving knowledge of isogenies: a survey
Ward Beullens and Luca de Feo and Steven Galbraith and Christophe Petit
To appear in Designs, Codes and Cryptography

Torsion point attacks on 'SIDH-like' cryptosystems.
Péter Kutas and Christophe Petit
IET Inf. Secur. 17(2): 161-170 (2023)

M-SIDH and MD-SIDH: Countering SIDH Attacks by Masking Information
Tako Boris Fouotsa and Tomoki Moriya and Christophe Petit
EUROCRYPT 2023.

Stronger bounds on the cost of computing Groebner bases for HFE systems
Elisa Gorla, Daniela Mueller and Christophe Petit
Journal of Symbolic Computation, 109 (2022), pp 386-398. Special issue for MEGA 2019 conference.

A New Adaptive Attack on SIDH
Boris Fouotsa and Christophe Petit
CT-RSA 2022.

Cryptanalysis of an oblivious PRF from supersingular isogenies
Andrea Basso and Péter Kutas and Simon-Philipp Merz and Christophe Petit and Antonio Sanso
ASIACRYPT 2021.

SHealS and HealS: isogeny-based PKEs from a key validation method for SIDH
Boris Fouotsa and Christophe Petit
ASIACRYPT 2021.

Séta: Supersingular encryption from torsion attacks
Luca De Feo, Boris Fouotsa, Cyprien Delpech de Saint-Guilhem, Antonin Leroux, Péter Kutas, Christophe Petit, Javier Silva, Benjamin Wesolowski
ASIACRYPT 2021.

New results on Quasi-Subfield Polynomials
Marie Euler and Christophe Petit
Finite Fields and Applications, 75 (2021).

Improved torsion point attacks on SIDH variants
Victoria de Quehen, Péter Kutas, Chris Leonardi, Chloe Martindale, Lorenz Panny, Christophe Petit, Katherine E. Stange
CRYPTO 2021.

SimS: a simplification of SiGamal
Boris Fouotsa and Christophe Petit
PQ Crypto 2021.

One-way functions and malleability oracles: Hidden shift attacks on isogeny-based protocols
Péter Kutas, Simon-Philipp Merz, Christophe Petit, Charlotte Weitkämper
EUROCRYPT 2021.

Trapdoor DDH groups from pairings and isogenies
Péter Kutas, Christophe Petit, Javier Silva
SAC 2020.

On Index Calculus Algorithms for Subfield Curves
Steven Galbraith, Robert Granger, Simon-Philipp Merz, Christophe Petit
SAC 2020.

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

SQISign: Compact Post-Quantum signatures from Quaternions and Isogenies (BEST PAPER AWARD)
Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, Benjamin Wesolowski
ASIACRYPT 2020.

On Adaptive Attacks against Jao-Urbanik's Isogeny-Based Protocol
Andrea Basso, Péter Kutas, Simon-Philipp Merz, Christophe Petit, and Charlotte Weitkämper
Africacrypt 2020.
Proceedings. Preprint.

Another look at some isogeny hardness assumptions
Simon-Philipp Merz, Romy Minko, Christophe Petit
CT-RSA 2020.
Proceedings. Preprint.

Verifiable Delay Functions from Supersingular Isogenies and Pairings
Luca De Feo, Simon Masson, Christophe Petit and Antonio Sanso
ASIACRYPT 2019.
Proceedings.. Preprint..

Identification Protocols and Signature schemes based on supersingular isogeny problems (extended version of Asiacrypt 2017 best paper)
Steven Galbraith, Christophe Petit, Javier Silva Velon.
Journal of Cryptology, 33.
Eprint. Paper. ASIACRYPT 2017 version. Implementation by Benjamin Diamond.

Supersingular graphs in Cryptography
Kristin Lauter, Christophe Petit.
Surveys in Combinatorics 2019, LMS Lecture Note Series 456.

Factoring Products of Braids via Garside Normal Form
Simon-Philipp Merz, Christophe Petit
PKC 2019.
Proceedings. Eprint.

Better Path Finding Algorithms in LPS Ramanujan graphs
Eduardo Carvalho Pinto, Christophe Petit
Journal of Mathematical Cryptology, 12(4).
Paper.

Quasi-subfield polynomials and the Elliptic Curve Discrete Logarithm Problem.
Ming-Deh A. Huang, Michiel Kosters, Christophe Petit, Sze Ling Yeo, Yang Yun.
MathCrypt 2018 and Journal of Mathematical Cryptology, 14 (1).
Paper.

Hard and Easy Problems in Supersingular Isogeny Graphs
Christophe Petit, Kristin Lauter
Appeared at EUROCRYPT 2018 as a merge under the title "Supersingular isogeny graphs and endomorphism rings: reductions and solutions"
Eprint.

A practical cryptanalysis of WalnutDSA
Daniel Hart, DoHoon Kim, Giacomo Micheli, Guillermo Pascual Perez, Christophe Petit and Yuxuan Quek
PKC 2018 - 21st IACR International Conference on Practice and Theory in Public-Key Cryptography.
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

Trapdoor attacks on Cayley hash function parameters
Alexander Allin, Woojoo Na and Christophe Petit
Accepted for presentation at IMACC2019 conference.

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

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.

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)