André Chailloux

Presentation

I am a researcher in quantum computing computer science at Inria de Paris in the COSMIQ team since 2013. My research interest are the following

Post-quantum Cryptography. Quantum cryptanalysis for cryptography based on error-correcting codes as well as Euclidean lattices, quantum algorithms for collision problems, security proofs in the quantum random oracle model.
Quantum Cryptography and Information Theory. Theoretical limits of quantum cryptographic primitives, entanglement and non-local games, relativistic cryptography.

I defended my PhD entitled Quantum Coin Flipping and Bit Commitment: Optimal Bounds, Practical Constructions and Computational Security in June 2011 at LRI under the supervision of Iordanis Kerenidis. My thesis got the Gilles Kahn thesis prize award. I also defender in 2025 my Habilitation à Diriger les Recherches entitled Quantum information theory for relativistic cryptography and quantum algorithms in January 2025.

Research projects

As a coordinator

DEREC Development of Relativistic Cryptography, ANR JCJC (2017-2022)
QMON Quantum Money, Emergence(s) Project (2019-2023)

Participation

EPiQ ANR PEPR (2022-2027)
PQ-TLS ANR PEPR (2022-2028)
HQI Plan Quantique France 2030 (2022-2027)
QUANTAGENOMICS QuantERA ERA-NET Cofund (2022-2025)
QUASYMODO Participation in the ERC grant of Maria Naya-Plasencia (2017-2022)

Supervision

PhD Students

Johanna Loyer (2020-2023), PhD supervision on quantum algorithms for Euclidean lattices and error-correcting codes. Johanna defended her thesis entitled Quantum cryptanalysis of lattices and codes in December 2023.
Simona Etinski (2019-2023), PhD supervision on quantum algorithms and quantum security proofs for cryptography based on error-correcting codes. Simona defended her thesis entitled Generalized syndrome decoding problem and applications to cryptography in June 2023.
Andrea Olivo (2018-2022), co-supervision with Frédéric Grosshans (main supervisor) on position-based quantum cryptography. Andrea defended his thesis entitled On the utility of small quantum states: applications to linear optics and position verification in June 2022.
André Schrottenloher (2017-2021), co-supervision with Maria Naya-Plasencia (main supervisor) on various topics related to quantum cryptanalysis, both in public-key and symmetric cryptography. André defended his thesis entitled Quantum Algorithms for Cryptanalysis and Quantum-safe Symmetric Cryptography in February 2021.
Rémi Bricout (2017-2021): Rémi worked on quantcum algorithms for problems, particularly to study the computational assumptions behind code-based cryptography. I was his main supervisor. Rémi defended his thesis entitled How to use quantum algorithms to fill your backpack and decode syndromes in January 2021.

Interns

Roman Randrianarisoa}, M1 internship (2 months) for the QUANTAGENOMICS project, 2023.
Julien du Crest, M2 internship (6 months) on relativistic cryptography, 2021
Sristy Agrawal, M1 internship (3 months) on entangled games, 2017

Moreover, Johanna Loyer, André Schrottenloher and Rémi Bricout who later continued to PhD, did a 5-month internship that I supervised or co-supervised.

Publications

A. Chailloux and J.-P. Tillich, Quantum advantage from soft decoders. STOC 2025 (To appear). PDF (ArXiv)
A. Chailloux and T. Debris-Alazard, New Solutions to Delsarte's Dual Linear Programs. IEEE IT 2025. PDF (ArXiv) Journal link
A. Chailloux and J.-P. Tillich, The Quantum Decoding Problem. TQC 2024. PDF (Arxiv) Conference Proceedings
A. Chailloux and S. Etinski, On the (in)security of optimized Stern-like signature schemes. DCC 2024. pdf (Arxiv) Journal link
R. Bhaumik, A. Chailloux, P. Frixons, and M. Naya-Plasencia, Block Cipher Doubling for a Post-Quantum World. CIC 2024. pdf (eprint) Journal link
X. Bonnetain, A. Chailloux, A. Schrottenloher and Y. Shen, Finding Many Collisions via Reusable Quantum Walks: Application to Lattice Sieving. EUROCRYPT 2023. pdf (Arxiv) Conference proceedings
A. Chailloux and J. Loyer, Classical and Quantum 3 and 4-Sieves to Solve SVP with Low Memory. PQCRYPTO 2023. pdf (eprint) Conference Proceedings
A. Chailloux and J. Loyer, Lattice sieving via quantum random walks. ASIACRYPT 2021. PDF (Arxiv) Conference Proceedings
A. Chailloux, T. Debris-Alazard, and S. Etinski, Classical and quantum algorithms for generic syndrome decoding problems and applications to the lee metric. PQCRYPTO 2021. PDF (Arxiv) Conference proceedings
R. Bhaumik, X. Bonnetain, A. Chailloux, G. Leurent, M. Naya-Plasencia, A. Schrottenloher, and Y. Seurin, QCB: efficient quantum-secure authenticated encryption. ASIACRYPT 2021. PDF (eprint) Conference proceedings
A. Chailloux and T. Debris-Alazard, Tight and optimal reductions for signatures based on average trapdoor preimage sampleable functions and applications to code-based signatures. PKC 2020. PDF (eprint) Conference Proceedings
R. Bricout, A. Chailloux, T. Debris-Alazard, and M. Lequesne, Ternary syndrome decoding with large weight. SAC 2019. PDF (Arxiv) Conference Proceedings
A. Chailloux, A note on the quantum query complexity of permutation symmetric functions. ITCS 2019. PDF (Arxiv) Conference Proceedings
A. Chailloux, M. Naya-Plasencia, and A. Schrottenloher, An efficient quantum collision search algorithm and implications on symmetric cryptography. ASIACRYPT 2017. PDF (eprint) Conference Proceedings
A. Chailloux and A. Leverrier, Relativistic (or 2-prover 1-round) zero-knowledge protocol for NP secure against quantum adversaries. EUROCRYPT 2017. PDF (Arxiv) Conference Proceedings
R. Bricout and A. Chailloux, Recursive cheating strategies for the relativistic FQ bit commitment protocol. MDPI Cryptogr. 2017. PDF (Arxiv) Journal link
K. Chakraborty, A. Chailloux, and A. Leverrier, Robust relativistic bit commitment. PRA 2016. PDF (Arxiv) Journal link
W. McCutcheon, A. Pappa, B. A. Bell, A. McMillan, A. Chailloux, T. Lawson, M. Mafu, D. Markham, E. Diamanti, I. Kerenidis, J. G. Rarity, and M. S. Tame, Experimental verification of multipartite entanglement in quantum networks. Nature Comm. 2016. PDF (Arxiv) Journal link
A. Chailloux, G. Gutoski, and J. Sikora, Optimal bounds for semi-honest quantum oblivious transfer. CJTCS 2016. PDF (Arxiv) Journal link
A. Chailloux, I. Kerenidis, and B. Rosgen, Quantum commitments from complexity assumptions. Comput. Complex. 2016. PDF (Arxiv) Journal link
D. Aharonov, A. Chailloux, M. Ganz, I. Kerenidis, and L. Magnin, A simpler proof of the existence of quantum weak coin flipping with arbitrarily small bias. SICOMP 2016. PDF (Arxiv) Journal link
K. Chakraborty, A. Chailloux, and A. Leverrier, Arbitrarily long relativistic bit commitment. PRL 2015. PDF (Arxiv) Journal link
A. Chailloux, L. Mancinska, G. Scarpa, and S. Severini, Graph-theoretical bounds on the entangled value of non-local games. TQC 2014. PDF (Arxiv) Conference Proceedings
A. Chailloux, I. Kerenidis, S. Kundu, and J. Sikora, Optimal bounds for parity-oblivious random access codes with applications. TQC 2014. PDF (Arxiv) Conference Proceedings
A. Chailloux and G. Scarpa, Parallel repetition of entangled games with exponential decay via the superposed information cost. ICALP 2014. PDF (Arxiv) Conference Proceedings
J. Sikora, A. Chailloux, and I. Kerenidis, Strong connections between quantum encodings, nonlocality, and quantum cryptography. PRA 2014. PDF (Arxiv) Journal link
A. Pappa, P. Jouguet, T. Lawson, A. Chailloux, M. Legré, P. Trinkler, I. Kerenidis, and E. Diamanti, Experimental plug and play quantum coin flipping. Nature Comm. 2014. PDF (Arxiv) Journal link
A. Chailloux, I. Kerenidis, and J. Sikora, Lower bounds for quantum oblivious transfer. QIC 2013. PDF (Arxiv) Journal link
A. Chailloux and O. Sattath, The complexity of the separable hamiltonian problem. CCC 2012. PDF (Arxiv) Journal link
A. Pappa, A. Chailloux, S. Wehner, E. Diamanti, and I. Kerenidis, Multipartite entanglement verification resistant against dishonest parties. Phys. Rev. Lett. 2012. PDF (Arxiv) Journal link
A. Chailloux and I. Kerenidis, Optimal bounds for quantum bit commitment. FOCS 2011. PDF (Arxiv) Journal link
A. Pappa, A. Chailloux, E. Diamanti, and I. Kerenidis, Practical quantum coin flipping. Phys. Rev. A 2011. PDF (Arxiv) Journal link
J. Silman, A. Chailloux, N. Aharon, I. Kerenidis, S. Pironio, and S. Massar, Fully distrustful quantum bit commitment and coin flipping. Phys. Rev. Lett. 2011. PDF (Arxiv) Journal link
A. Chailloux, I. Kerenidis, and B. Rosgen, Quantum commitments from complexity assumptions. ICALP 2011. PDF (Arxiv) Journal link
A. Chailloux and I. Kerenidis, Optimal quantum strong coin flipping. FOCS 2009. PDF (Arxiv) Journal link
A. Chailloux and I. Kerenidis, Increasing the power of the verifier in quantum zero knowledge. FSTTCS 2008. PDF (Arxiv) Journal link
A. Chailloux, D. F. Ciocan, I. Kerenidis, and S. P. Vadhan, Interactive and noninteractive zero knowledge are equivalent in the help model. TCC 2008.

PDF

Journal link

Preprints

Y. Barsamian and A. Chailloux, Compressing integer lists with contextual arithmetic trits. Submitted. PDF (ArXiv)
A. Chailloux and Y. Barsamian, Relativistic zero-knowledge protocol for NP over the internet unconditionally secure against quantum adversaries. Submitted. PDF (ArXiv)

Teaching

Master Parisien de Recherche en Informatique

Since 2016, I teach various topics in quantum computing at the MPRI. I provide below some information about the most current course.

Course: Quantum Information Theory and Cryptography 2024-2025

The course will cover quantum information, quantum cryptography and advanced quantum algorithms. I am the person in charge of this course and I teach it with Simon Apers. The course is on Tuesdays from 12:45 to 15:45 in room 1004. You can also find the course webpage here

Lectures notes

Lectures 1-4 (Simon Apers) webpage link
Lectures 5-8 (André Chailloux) pdf

Detailed schedule

Dec 10 (SA) Quantum walks
Dec 17 (SA) Quantum walk search
Jan 07 (SA) Quantum adiabatic algorithm
Jan 14 (SA) Hamiltonian simulation
Jan 28 (AC) Mixed states, POVMs, distance measures, Helstrom measurement, Unambiguous State Discrimination
Feb 04 (AC) Quantum key distribution
Feb 11 (AC) Quantum cryptography beyond QKD
Feb 18 (AC) Quantum information theory, Shannon entropy, Holevo's bound
FINAL EXAM: March 11 from 12:45 to 15:45

Exercice sessions with and without solutions td1 td1(Sol) td2 td2(Sol) td3 td3(Sol)
Exam of previous year Exam With Solutions

QI Master, Sorbonne Université

From 2021 to 2023, I taught two courses at the QI Master at Sorbonne Université. The content here was more furnished than the course I give at the MPRI so I give the lecture notes as well as the exercice sessions

Course: Quantum Circuits and Logic Gates 2021-2023

Lecture notes pdf
Exercice Sheets Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9

Course: Quantum Information Introduction 2021-2023

This is more an overall lecture in various topics in quantum computing rather than really a course on quantum information. It is a follow-up of the previous course.

Lecture notes pdf
Exercice Sheets Sheet 1 Sheet 2 Sheet 3 Sheet 4 Sheet 5 Sheet 6 Sheet 7 Sheet 8 Sheet 9 Sheet 10 Sheet 11-12 Sheet 13 Sheet 14 Sheet 15 Sheet 16 Sheet 17 Sheet 18

Contact

André Chailloux

Inria de Paris, COSMIQ team
46 rue Barrault, 75013 Paris
Office B319
Phone: +33 (0)180494217