6.1.1 snark-2-chains

• Name:
  Families of SNARK-friendly 2-chains of elliptic curves
• Keywords:
  Cryptography, Cryptocurrency, Blockchain
• Functional Description:
  This small library implements finite field and elliptic curve arithmetic for BN curves (Barreto-Naehrig), BLS curves (Barreto-Lynn-Scott), and 2-chains made of BW6 (Brezing-Weng curves of embedding degree 6), CP8, CP12 (Cocks-Pinch curves of embedding degree 8 and 12) for use with zk-snarks (zero-knowledge succinct non-interactive argument of knowledge). The cryptographic applications are: pairing, scalar multiplication on the curves, hashing on the curves. The code is a proof of concept tied to a preprint and is not optimized.
• News of the Year:
  The library was first released in October 2021.
• URL:
  https://­gitlab.­inria.­fr/­zk-curves/­snark-2-chains
• Publication:
  hal-03371573
• Contact:
  Aurore Guillevic

7.1.1 Improved decoding of Gabidulin codes for various noise models

Participants: Maxime Bombar, Alain Couvreur.

When considering error correcting codes, one usually endows the ambient space with the Hamming metric. However, other metrics have been considered, and in particular, codes endowed with the rank metric have found applications in cryptography, in network communications or in data storage. Com- pared to the Hamming world, only few families of codes endowed with the rank metric are known to have efficient decoding algorithms. As the rank metric analogues of Reed-Solomon codes, $[n,k]$ Gabidulin codes are of particular interest because they are somehow optimal: they reach the rank-metric Singleton bound and benefit from efficient decoders uniquely correcting any error pattern of weight up to $\frac{n-k}{2}$. However, in general, there exists no known decoders in polynomial time beyond this bound, even probabilistic ones. Nonetheless, previous works have considered different noise models for which decoders can be given. For instance, when considering $u$ codewords in parallel such that the channel corrupts all of them at once (this process is known as interleaving), it is possible to give a probabilistic decoder correcting up to $\frac{u}{u+1}(n-k)$ rank errors, or when the error has a specific symmetric structure (more precisely when the row and column spaces of the error are equal), it is possible correct errors up to rank $\frac{3}{2}(n-k)$.

In 42, A. Couvreur and M. Bombar build on their previous work 67 to give a new decoder of interleaved Gabidulin codes, working on the right-hand side, which gives a simpler point of view on the decoding of such error patterns.

In 67, A. Couvreur proves that when the codes have rate $\frac{k}{n}<\frac{1}{2}$, it is possible to correct any symmetric error pattern, whatever its rank, without failure. This algorithm works for a broad family of codes which includes the aforementioned Gabidulin codes. Moreover, when the rate is larger than $\frac{1}{2}$, it achieves the best decoding radius conjectured in the literature for such noise model.

7.1.2 Search-to-decision reductions in code–based cryptography

Participants: A. Couvreur, M. Bombar, T. Debris–Alazard.

The security of most code–based cryptosystem relies on the hardness of the so–called Decoding Problem. If its search version (Given a random linear code, and a noisy codeword, it should be hard to decode, i.e. to remove the error and recover the original message) is quite well understood, many proposals actually rely on the decision version which can be formulated as follows: Given a random linear code it should be hard to distinguish between a uniformly random vector of the ambiant space, and a noisy codeword. This decision version can be thought as the code–based analogue of the Decisional Diffie Hellman problem, and for general random linear codes both search and decision problem are known to be equivalent. Such a result is known as a search to decision reduction. However, for efficiency purposes, it is very appealing to use algebraically structured codes such as quasi-cyclic codes, that can be represented more compactly. In this situation, the hardness of the decision Decoding problem is only conjectured. On the other hand, one of the reasons of the success of lattice–based cryptography is that it benefits from a rich literature of security reductions for both general lattices and so–called structured lattices, i.e. lattices arising from orders of number fields.

In 29, based on a strong analogy between number fields and function fields, and especially using Carlitz modules which can be somehow considered as an analogue of cyclotomic number fields in positive characteristics, we introduce a new generic problem that we call Function Field Decoding Problem, and derive the first search to decision reduction in this context.

7.1.3 New algorithm to solve the generic decoding problem

Participants: T. Debris–Alazard.

The security of code-based cryptography relies primarily on the hardness of generic decoding with linear codes. The best generic decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoders (ISD). A while ago, a generic decoding algorithm which does not belong to this family was proposed: statistical decoding. It is a randomized algorithm that requires the computation of a large set of parity-checks of moderate weight, and uses some kind of majority voting on these equations to recover the error we are looking for in the decoding problem. This algorithm was long forgotten because even the best variants of it performed poorly when compared to the simplest ISD algorithm. In 31, we revisit this old algorithm by using parity-check equations in a more general way. Here the parity-checks are used to get LPN samples with a secret which is part of the error and the LPN noise is related to the weight of the parity-checks we produce. The corresponding LPN problem is then solved by standard Fourier techniques. By properly choosing the method of producing these low weight equations and the size of the LPN problem, we are able to outperform in this way significantly information set decoders at code rates smaller than 0.3. It gives for the first time after 60 years, a better decoding algorithm for a significant range which does not belong to the ISD family. >>>>>>> 5a27469fe7075e10a50ee82951408ab3de01783b

In 42, A. Couvreur and M. Bombar build on their previous work 66 to give a new decoder of interleaved Gabidulin codes, working on the right-hand side, which gives a simpler point of view on the decoding of such error pattern.

In 55, A. Couvreur proves that when the codes have rate $\frac{k}{n}<1/2$, it is possible to correct any symmetric error pattern, whatever its rank, without failure. This algorithm works for a broad family of codes which includes the aformentioned Gabidulin codes. Moreover, when the rate is larger than $1/2$, he achieves the best decoding radius conjectured in the litterature for such noise model.

7.1.4 Quantum reduction

Participants: Thomas Debris-Alazard.

We give a quantum reduction from finding short codewords in a random linear code to decoding for the Hamming metric. This is the first time such a reduction (classical or quantum) has been obtained. Our reduction adapts to linear codes Stehlé-Steinfield-Tanaka- Xagawa’s re-interpretation of Regev’s quantum reduction from finding short lattice vectors to solving the Closest Vector Problem. The Hamming metric is a much coarser metric than the Euclidean metric and this adaptation has needed several new ingredients to make it work. For instance, in order to have a meaningful reduction it is necessary in the Hamming metric to choose a very large decoding radius and this needs in many cases to go beyond the radius where decoding is unique. Another crucial step for the analysis of the reduction is the choice of the errors that are being fed to the decoding algorithm. For lattices, errors are usually sampled according to a Gaussian distribution. However, it turns out that the Bernoulli distribution (the analogue for codes of the Gaussian) is too much spread out and can not be used for the reduction with codes. Instead we choose here the uniform distribution over errors of a fixed weight and bring in orthogonal polynomials tools to perform the analysis and an additional amplitude amplification step to obtain the aforementioned result.

The result is presented in the preprint 56.

7.1.5 LLL like algorithm for codes

Participants: Thomas Debris-Alazard.

In 18, we have proposed an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as the Nearest Plane Algorithm of Babai (1986). Interestingly, the adaptation of LLL to binary codes can be interpreted as an algorithmic version of the bound of Griesmer (1960) on the minimal distance of a code. Using these algorithms, we demonstrate —both with a heuristic analysis and in practice— a small polynomial speed-up over the Information-Set Decoding algorithm of Lee and Brickell (1988) for random binary codes. This appears to be the first such speed-up that is not based on a time-memory trade-off. The above speed-up should be read as a very preliminary example of the potential of a reduction theory for codes, for example in cryptanalysis.

7.1.6 Wavelet: Code-based postquantum signatures with fast verification on microcontrollers

Participants: Gustavo Banegas, Thomas Debris-Alazard, Benjamin Smith.

This work 63 has presented the first full implementation of Wave, a postquantum code-based signature scheme. We define Wavelet, a concrete Wave scheme at the 128-bit classical security level (or NIST postquantum security Level 1) equipped with a fast verification algorithm targeting embedded devices. Wavelet offers 930- byte signatures, with a public key of 3161 kB. We include implementation details using AVX instructions, and on ARM Cortex-M4, including a solution to deal with Wavelet’s large public keys, which do not fit in the SRAM of a typical embedded device. Our verification algorithm is approximately 4.65 times faster then the original, and verifies in 1 087 538 cycles using AVX instructions, or 13 172 ticks in an ARM Cortex-M4.

7.1.7 Quantum-resistant software update security on low-power networked embedded devices

Participants: Gustavo Banegas, Benjamin Smith.

Bringing practical post-quantum security to low-end IoT devices is a pressing challenge. In 64 we evaluate a range of pre- and post-quantum secure signature schemes in the context of SUIT software updates (specified by the IETF), on three popular, off-the-shelf microcontroller boards (ARM Cortex-M4, ESP32, and RISC-V) that are representative of the 32-bit landscape. We show that upgrading to postquantum security is practical now, and reflect on the best choices for various use cases. This work was selected for presentation at Real World Crypto 2022, and was published at ACNS 2022.

7.1.8 On Using RSA/ECC Coprocessor for Ideal Lattice-Based Key Exchange

Participants: Guenael Renault, Simon Montoya.

Polynomial multiplication is one of the most costly operations of ideal lattice-based cryptosystems. In 71, with Aurélien Greuet (Idemia), we study its optimizations when one of the operands has coefficients close to 0. We focus on this structure since it is at the core of lattice-based Key Encapsulation Mechanisms submitted to the NIST call for post-quantum cryptography. In particular, we propose optimization of this operation for embedded devices by using a RSA/ECC coprocessor that provides efficient and secure large-integer arithmetic. In this context, we compare Kronecker Substitution, with two specific algorithms that we introduce: KSV, a variant of this substitution, and an adaptation of the schoolbook multiplication, denoted Shift&Add. All these algorithms rely on the transformation of polynomial multiplication to large-integer arithmetic. Then, thanks to these algorithms, existing secure coprocessors dedicated to large-integer can be re-purposed in order to speed-up post-quantum schemes. The efficiency of these algorithms depends on the component specifications and the cryptosystem parameters set. Thus, we establish a methodology to determine which algorithm to use, for a given component, by only implementing basic large-integer operations. Moreover, the three algorithms are assessed on a chip ensuring that the theoretical methodology matches with practical results.

7.1.9 Security Assessment of NTRU Against Non-Profiled SCA

Participants: Guenael Renault, Simon Montoya.

NTRU was first introduced by J. Hoffstein, J. Pipher and J.H Silverman in 1998. Its security, efficiency and compactness properties have been carefully studied for more than two decades. A key encapsulation mechanism (KEM) version was even submitted to the NIST standardization competition and made it to the final round. Even though it has not been chosen to be a new standard, NTRU remains a relevant, practical and trustful post-quantum cryptographic primitive. In 25, with Luk Bettale (Idemia), Julien Eynard (ANSSI) and Rémi Strullu (ANSSI), we investigate the side-channel resistance of the NTRU Decrypt procedure. In contrast with previous works about side-channel analysis on NTRU, we consider a weak attacker model and we focus on an implementation that incorporates some side-channel countermeasures. The attacker is assumed to be unable to mount powerful attacks by using templates or by forging malicious ciphertexts for instance. In this context, we show how a non-profiled side-channel analysis can be done against a core operation of NTRU decryption. Despite the considered countermeasures and the weak attacker model, our experiments show that the secret key can be fully retrieved with a few tens of traces.

7.1.10 Post-quantum Public Key Encryption from Isogenies

Participants: Luca De Feo, Antonin Leroux.

Together with Cyprien Delpech de Saint Guilhem (KU Leuven), Tako Boris Fouotsa (Universit`a Degli Studi Roma Tre), Peter Kutas (University of Birmingham), Christophe Petit (Université Libre de Bruxelles), Javier Silva ( Universitat Pompeu Fabra)and Benjamin Wesolowski (Institut Mathématiques de Bordeaux), Luca de Feo and Antonin Leroux have introduced a new post-quantum public key encryption scheme that uses constructively the torsion point attack against the SIDH key exchange. The publication includes an implementation in C of this new construction. Another contribution of this work is the "uber-isogeny assumption" which aims at generalizing some computational assumption encountered in various scheme of the literature.

7.1.11 High-speed supersingularity testing for elliptic curves

Participants: Gustavo Banegas, Benjamin Smith.

7.1.12 The suborder isogeny representation and pSIDH

Participants: Antonin Leroux.

7.1.13 The supersingular isogeny graph of abelian surfaces

Participants: Benjamin Smith.

7.1.14 New isogeny-based key exchange algorithms

Participants: Benjamin Smith.

7.3.1 Verifiable computation based on coding theory

Participants: Daniel Augot, Sarah Bordage, Jade Nardi.

In the coding theoretic setting, these protocols are made popular, in particular in the blockchain area, under the name of (ZK-)STARKS, Scalable Transparent Arguments of Knowledge, introduced in 2018. The short non interactive proofs are derived for protocols which are called IOPs Interactive Oracle Proofs, which are combination of IPs Interactive Proofs and PCPs Probabilistically Checkable Proofs, for combining the best of both worlds, and making PCPs pratical.

At the core of these protocols lies the following coding problem: how to decide, with high confidence, that a very long ambient word is close to a given code, while looking at very few coordinates of it.

These protocols were originally designed for the simplest algebraic codes, Reed-Solomon codes. Daniel Augot and Sarah Bordage provided a generalization of these protocols to multivariate codes, i.e. product of Reed-Solomon codes and Reed-Muller codes. The performance does not degrade badly with respect to the basic Reed-Solomon case 12. It remains to assert the revelance of these codes for building proof systems and to compare to litterature, where product of Reed-Solomon codes have been studied for more than twenty years.

A very important issue is to have a smaller alphabet, and this can be done using algebraic-geometric codes. This was done by Sarah Bordage , Matthieu Lhotel, Jade Nardi and Hugues Randriambololona 30, using curves with a resoluble automorphims group, which enable to build codes which are foldable in way similar to the Reed-Solomon codes with are folded in the "FRI" protocol  65. Their protocol has very good perfomance, akin to the Reed-Solomon case. Towers of curves are considered for this construction, to enable good asymptotic results.

7.3.2 Verifiable computation based on elliptic curves

Participants: Daniel Augot, Youssef El Housni, François Morain.

Verifiable computation can also be built using the theory of ellitpic curves, the hardness of the discrete logarithms, and pairings, as introduced in  72 and made practical in  73. These proofs are much more shorter than the ones provided by the STARKS, with a higher cost for the prover. Furthermore, these systems are not post-quantum, and there are important issues in the setting of the proof system, where a trusted third party is required.

The verifiable computation problems leads to several new questions in elliptic curves cryptographic, since the required operations depart from the standard ones used for instance in signature algorithms.

A very interesting topic is the notion of "proof of proofs". Essentially, verifying a proof is a computation, and a proof that a proof has been verified can be given. The same idea applies for verifying hundreds of proofs. A single proof can report that hundred of proofs have been checked.

This is very strong in the elliptic curve setting because the size of a proof is a constant (a few hundred bytes, only depending on the security parameter, not the computation). This means that the above hundred of statements admits a very short proof. In the blockchain world, this translates into a very short proof that many offchain transactions are correct.

To achieve this goal, this requires an ellitpic curve for proving computations done over an other elliptic curve. The problem is that there is an arithmetic mismatch: the statement which is to be proved is defined over ${𝔽}_r$, for a prime $r$ which is a size of a cyclic group provided by an elliptic curve defined over ${𝔽}_q$. Verifying the proof requires to do computations over ${𝔽}_q$, and thus, for the above recursion, one needs another curve over ${𝔽}_{q^{\text{'}}}$ providing a group of prime order $q$. Furthermore both curves must be pairing-friendly. This raises quite challenging questions, which are solved using the theory of complex multiplication.

In collaboration with Aurore Guillevic, Youssef El Housni provided curves which are very efficient for this recursion  7033. These curves beat the competition, an implementation has been provided here. Some other blockchain players CELO, Consensys also have used these curves in their implentations of verifiable computation and zero-knowledge proofs. A. Guillevic and Y. El Housni made a survey of relevant curves for recursive SNARKS 11.

Once the curves are built, it remains to do other ellitpic curves operations, which are particular to SNARKS, for instance doing a sum of a lot of scalar multiplication with differents points. Y. El Housni produced such multiscalar operations for SNARKS 54. Other technicalites also have been improved 34.

7.6.1 Fast Cornacchia algorithm

Participants: François Morain.

7.6.2 Pre-quantum factoring using elliptic curves

Participants: François Morain.

7.6.3 Trustless unknown-order groups

Participants: Benjamin Smith.

9.1.1 H2020 projects

9.2.1 ANR CIAO

Participants: Benjamin Smith, Luca De Feo, Antonin Leroux, Mathilde Chenu.

9.2.2 ANR CBCRYPT

Participants: Alain Couvreur, Olivier Blazy.

9.2.3 ANR COLA

Participants: Alain Couvreur, Thomas Debris–Alazard.

9.2.4 ANR BARRACUDA

Participants: Daniel Augot, Alain Couvreur, Françoise Levy-dit-Vehel.

BARRACUDA is a collaborative ANR project accepted in 2021 and led by A. Couvreur .

Website : barracuda.inria.fr

The project gathers specialists of coding and cryptology on one hand and specialists of number theory and algebraic geometry on the other hand. The objectives concern problems arising from modern cryptography which require the use of advanced algebra based objects and techniques. It concerns for instance mathematical problems with applications to distributed storage, multi-party computation or zero knowledge proofs for protocols.

9.2.5 ANR SANGRIA

Participants: Olivier Blazy.

SANGRIA is a collaborative ANR project accepted in 2021.

Website : lip6.fr/Damien.Vergnaud/projects/sangria/

The main scientific challenge of the SANGRIA (Secure distributed computAtioN - cryptoGRaphy, combinatorIcs and computer Algebra) project are (1) to construct specific protocols that take into account practical constraints and prove them secure, (2) to implement them and to improve the efficiency of existing protocols significantly. The SANGRIA project (for Secure distributed computAtioN: cryptoGRaphy, combinatorIcs and computer Algebra) aims to undertake research in these two aspects while combining research from cryptography, combinatorics and computer algebra. It is expected to impact central problems in secure distributed computation, while enriching the general landscape of cryptography.

9.2.6 ANR MobiS5

Participants: Olivier Blazy.

MobiS5 is a collaborative ANR project accepted in 2018.

Website : mobis5.limos.fr/

MobiS5 will aim to foresee and counter the threats posed in 5G architectures by the architectural modifications suggested in TR 22.861-22.864. Concretely, we will provide a provably-secure cryptographic toolbox for 5G networks, validated formally and experimentally, responding to the needs of 5G architectures at three levels:

* Challenge 1: security in the network infrastructure and end points: including core network security and attack detection and prevention; * Challenge 2: cryptographic primitives and protocols, notably : a selection of basic primitives, an authenticated key-exchange protocol, tools to compute on encrypted data, and post-quantum cryptographic countermeasures * Challenge 3: mobile applications, specifically in the use-case of a secure server that aids or processes outsourced computation; and the example of a smart home.

9.2.7 ANR CryptiQ

Participants: Olivier Blazy.

CryptiQ is a collaborative ANR project accepted in 2018.

The goal of the CryptiQ project is to major changes due to Quantum Computing by considering three plausible scenarios, from the closest to the furthest foreseeable future, depending on the means of the adversary and the honest parties. In the first scenario, the honest execution of protocols remains classical while the adversary may have oracle access to a quantum computer. This is the so-called post-quantum cryptography, which is the best known setting. In the second scenario (quantum-enhanced classical cryptography), we allow honest parties to have access to quantum technologies in order to achieve enhanced properties, but we restrict this access to those quantum technologies that are currently available (or that can be built in near-term). The adversary is still allowed to use any quantum technology. Finally, in the third scenario (cryptography in a quantum world), we allow the most general quantum operations to an adversary and we consider that anybody can now have access to both quantum communication and computation.

9.2.8 PEPR sur les technologues quantiques - Projet intégré "Un cadenas post-quantique pour les navigateurs web"

Participants: Alain Couvreur, Thomas Debris–Alazard, Benjamin Smith, Anaëlle Le Devehat, Matthieu Lequesne.

This projet intégré aims to develop post quantum cryptographic primitives in 5 years which would be implemented in an open source web browser. The evolution of cryptographic standards has already begun. The choice of new primitives will be made soon and the transition should be operated in a few years. The objective of the project is to play a crucial role in this evolution so that french researchers, which are already strongly implied in this process could influence the choice of cryptographic standards in the next years.

9.2.9 Inria Défi RIOT-fp: Reconcile IoT and Future-Proof Security

Participants: Benjamin Smith, Gustavo Banegas.

1. developing high-speed, high-security, low-memory IoT crypto primitives,
2. providing guarantees for software execution on low-end IoT devices, and
3. enabling secure IoT software updates and supply-chain, over the network.

Beyond academic outcomes, the output of RIOT-fp is open source code published, maintained and integrated in the open source ecosystem around RIOT. As such, RIOT-fp strives to contribute usable building blocks for an open source IoT solution improving the typical functionality vs. risk tradeoff for end-users.

9.2.10 Inria AEx CACHAÇA

Participants: Benjamin Smith, Guenael Renault, Anaelle Le Devehat.

10.1.1 Scientific events: organisation

• O. Blazy and A. Couvreur participated in the organisation of the Journées Codage et Cryptographie (C2) 2022.
• A. Couvreur organised the CIMPA Summer School SUmmer School in Applied Arithmetic at Nesin (SUSAAN) in Nesin math Village (Sirince, Turkey).
• D. Augot is member of the programm committee of the seminar of the “groupe de travail codage et cryptographie (GT C2) du groupement de recherche informatique mathématique (GDR IM)”

10.1.2 Scientific events: selection

10.1.3 Journal

10.1.4 Invited talks

• A. Couvreur has been invited to give a lecture at the Algebraic Coding Theory (ACT) summer school 2022. 62.
• O. Blazy has been an invited panelist at Conference Privacy, Data Protection (CPDP) 2022.
• T. Debris–Alazard has been invited to give lectures at the Summer school in post-quantum cryptography 2022.
• M. Bombar has been invited to give tutorials in code–based cryptography at the Summer school in post-quantum cryptography 2022.

10.1.5 Leadership within the scientific community

• O. Blazy and A. Couvreur lead the CNRS' Groupe de travail Codage et Cryptographie of Groupes de recherche Sécurité Informatique and Informatique Mathématique.
• A. Couvreur was member of the Commité de Culture Mathématiques (CCM) of Institut Henri Poincaré.
• A. Couvreur is coordinator for Inria of the projet intégré “Un cadenas post–quantique pour les navigateurs web” (PQ-TLS) of the PEPR quantique.
• A. Couvreur is the principal investigator of the collaborative ANR project Barracuda.

10.1.6 Scientific expertise

• A. Couvreur was referee of the PhD thesis of Leonardo Landi (Danmarks Tekniske Universitet, Lyngby, Danemark).
• A. Couvreur was referee of the PhD of Étienne Marcatel (Université de Grenoble Alpes).
• A. Couvreur was referee of the PhD of Amaury Durand (Université de Bordeaux).
• A. Couvreur was referee of the PhD of Maxime Bros (Université de Limoges).
• O. Blazy was a referee of the PhD of Meryem Cherkaoui Semmouni (Ecole Nationale d'Informatique et d'Analyse des Systèmes, Rabat, Morocco).
• O. Blazy was a referee for the PhD of Tang Khai Hanh (Nanyang Technological University, Singapore, Singapore)
• G. Renault was referee for the PHD of Mohamed Traore (Université Grenoble Alpes)
• G. Renault was referee for the PHD of Davide Poggi (Université de Montpellier)
• G. Renault was referee for the PHD of Simon Landry (Sorbonne Université)
• G. Renault was referee for the PHD of Axel Mathieu-Mahias (Université Paris-Saclay)
• T. Debris–Alazard has been mandated as an expert for the ANR.
• B. Smith served as a scientific expert for Bpifrance.

10.1.7 Research administration

• A. Couvreur is elected member of Inria's Commission d'évaluation.
• A. Couvreur is member of the Comité scientifique du programme Maths et IA of the Labex Mathématiques Jacques Hadamard.
• O. Blazy was appointed référent europe for the GDR sécurité informatique
• O. Blazy was appointed as one of the academic member of the PostQuantum Cryptography Workgroup at Campus Cyber.
• B. Smith is a member of the Post-Quantum Cryptography working group at Campus Cyber.
• B. Smith was a member of the Research and Innovation Committee of Labex Digicosme
• B. Smith is a member of the Commission Scientifique of Inria Saclay.

10.2.1 Teaching

• Licence : F. Morain , Lectures for INF361: “Introduction à l'informatique”, 15h (equiv TD), 1st year (L3), École polytechnique. Coordinator of this module (350 students).
• Licence : T. Debris–Alazard , Exercises for INF361: “Introduction à l'informatique”, 15h (equiv TD), 1st year (L3), École polytechnique.
• Licence : M. Bombar : INF361: Introduction à l'informatique (tutorials), 40h (equiv TD), 1st year (L3), École polytechnique.
• Licence : B. Smith : CSE101: Introduction to Computer Programming, 42h, L1, École polytechnique, France
• Licence : O. Blazy : CSE101: Introduction to Computer Programming (Tutorials), 58h, L1, École polytechnique, France
• Master : T. Debris–Alazard , Lectures for "Post-quantum cryptography", 8h, 4th year, ENS Lyon,
• Master : A. Couvreur : MPRI 2-13-2: Error Correcting codes and applications to cryptography.
• Master : T. Debris–Alazard : MPRI 2-13-2: Error Correcting codes and applications to cryptography.
• Master A. Couvreur : Master QDCS Calcul quantique avancé et codes correcteurs. 10h.
• Master: D. Augot : lectures and labs on crypto in blockchains, 24h, M2, École polytechnique, France.
• Master: D. Augot designed with Julien Prat the cursus of a course in blockchains and economics, and made lectures on zero-knowledge.
• Master : F. Morain is the scientific leader of the Master of Science and Technology Cybersecurity: Threats and Defense of École Polytechnique.
• Master : F. Morain , INF558, Introduction to cryptology, 36h, M1, École Polytechnique. This special year included video making of all his courses.
• Master : M. Bombar : INF558 : Introduction to cryptology (tutorials), 22.5h (equiv TD), M1, École Polytechnique.
• Master : M. Bombar : INF550 : Advanced algorithms (tutorials), 18h (equiv TD), M1, École Polytechnique.
• Master : B. Smith : INF568: Advanced Cryptography, 45h, M1, École polytechnique, France
• Master : B. Smith and F. Morain : MPRI 2-12-2: Algorithmes Arithmétiques pour la Cryptologie, 22.5h, M2, Master Parisien de Recherche en Informatique, France. The lectures were all given in live video.
• Master : F. Levy-dit-Vehel , Lectures on discrete maths, 21h, M1, ENSTA.
• Master : F. Levy-dit-Vehel , Lectures on cryptography, 24h, M2, ENSTA.
• Master Cybersecurity: D. Augot , cryptography in blockchains, 24h, M2.
• Master : G. Renault : Lectures and Labs for INF565: Information Systems Security, 60h, M1, École polytechnique, France
• Master : G. Renault : Lectures and Labs for INF648: Embedded security: side-channel attacks; javacard, 60h, M2, École polytechnique, France
• Master : G. Renault : Coordinator for INF637: Reverse engineering vs Obfuscation, 2h, M2, École polytechnique, France
• Master : O. Blazy : Lectures and Labs for INF646: Introduction to formal methods, 20h, M2, École polytechnique, France
• Master : O. Blazy : Lectures and Labs for Authentification, VPN et Chiffrement, 6h, M2, Telecom Sud Paris, France
• Professionnal training: D. Augot gave a two hours lecture at System-X.

10.2.2 Juries

• A. Couvreur was president of the PhD jury of Simon Montoya (Institut Polytechnique de Paris).
• O. Blazy and A. Couvreur were members of the PhD Jury of Maxime Bros (Université de Limoges).
• A. Couvreur was member of the PhD jury of Manon Bertin (Université de Rouen Normandie).
• O. Blazy was president of the PhD jury of Manon Bertin (Université de Rouen Normandie).
• A. Couvreur was member of the PhD jury of Étienne Marcatel (Université Grenoble Alpes).
• A. Couvreur was member of the PhD jury of Christophe Levrat (Sorbonne université).
• A. Couvreur was member of the PhD jury of Amaury Durand (Université de Bordeaux)
• A. Couvreur was member of the PhD jury of Leonardo Landi (Danmarks Tekniske Universitet, Lyngby, Danemark).
• O. Blazy was president of the PhD jury of Octavio Perez Kempner (Ecole Normale Supérieure-PSL, Paris, France).
• O. Blazy was member of the PhD jury of Souha Masmoudi (Telecom Sud Paris, Evry, France).
• D. Augot was member of the HDR jury of Pascal Véron (Université de Toulon)
• D. Augot was member of the PhD jury of Marina Dehez-Clementi (Université de Toulouse)
• B. Smith was a member of the PhD jury of Natalia Kulatova (ENS/PSL Université Paris).
• G. Renault was member of the HDR jury of Charles Bouillaguet (Sorbonne Université)
• G. Renault was member of the PHD jury of Mohamed Traore (Université Grenoble Alpes)
• G. Renault was member of the PHD jury of Davide Poggi (Université de Montpellier)
• G. Renault was member of the PHD jury of Simon Landry (Sorbonne Université)
• G. Renault was member of the PHD jury of Axel Mathieu-Mahias (Université Paris-Saclay)
• G. Renault was member of the PHD jury of Gabriel Destouet (Université Grenoble Alpes)

10.3.1 Internal or external Inria responsibilities

• A. Couvreur is the référent médiation scientifique of Saclay's research center.
  • He organised the Rendez-vous des Jeunes Mathématiciennes et Informaticiennes on February 21 and 22th 2022. The event happened online due to the pandemic.
  • He participated in the organisation of Fête de la science 2022.

International journals

• 8 articleS.Simon Abelard, E.Elena Berardini, A.Alain Couvreur and G.Grégoire Lecerf. Computing Riemann-Roch spaces via Puiseux expansions.Journal of ComplexityApril 2022
  HALDOI
• 9 articleS.Simon Abelard, A.Alain Couvreur and G.Grégoire Lecerf. Efficient computation of Riemann-Roch spaces for plane curves with ordinary singularities.Applicable Algebra in Engineering, Communication and ComputingDecember 2022
  HALDOI
• 10 articleN.Nicolas Aragon, O.Olivier Blazy, J.-C.Jean-Christophe Deneuville, P.Philippe Gaborit and G.Gilles Zemor. Ouroboros An efficient and provably secure KEM family.IEEE Transactions on Information TheoryApril 2022, 1-1
  HALDOI
• 11 articleD. F.Diego F. Aranha, Y.Youssef El Housni and A.Aurore Guillevic. A survey of elliptic curves for proof systems.Designs, Codes and CryptographyDecember 2022, 46
  HALDOIback to text
• 12 articleD.Daniel Augot, S.Sarah Bordage and J.Jade Nardi. Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes.Designs, Codes and Cryptography2022
  HALDOIback to text
• 13 articleG.Gustavo Banegas, V.Valerie Gilchrist and B.Benjamin Smith. Efficient supersingularity testing over F_p and CSIDH key validation.Mathematical Cryptology21October 2022, 21-35
  HALback to text
• 14 articleS.Slim Bettaieb, L.Loïc Bidoux, O.Olivier Blazy, Y.Yann Connan and P.Philippe Gaborit. A gapless code-based hash proof system based on RQC and its applications.Designs, Codes and CryptographyAugust 2022
  HALDOI
• 15 articleO.Olivier Blazy, L.Laura Brouilhet, E.Emmanuel Conchon and M.Mathieu Klingler. Anonymous attribute-based designated verifier signature.Journal of Ambient Intelligence and Humanized Computing689September 2022, 6233-6244
  HALDOI
• 16 articleA.Anne Canteaut, A.Alain Couvreur and L.Léo Perrin. Recovering or Testing Extended-Affine Equivalence.IEEE Transactions on Information Theory689September 2022, 6187 - 6206
  HALDOI
• 17 articleM.Mathilde Chenu and B.Benjamin Smith. Higher-degree supersingular group actions.Mathematical Cryptology12March 2022, 85-101
  HALback to text
• 18 articleT.Thomas Debris-Alazard, L.Leo Ducas and W. P.Wessel P.J. van Woerden. An Algorithmic Reduction Theory for Binary Codes: LLL and more.IEEE Transactions on Information TheoryJanuary 2022
  HALDOIback to text
• 19 articleS.Samuel Dobson, S.Steven Galbraith and B.Benjamin Smith. Trustless unknown-order groups.Mathematical Cryptology12March 2022, 25-39
  HALback to text
• 20 articleE.Enric Florit and B.Benjamin Smith. An atlas of the Richelot isogeny graph.RIMS Kôkyûroku BessatsuB90June 2022, 195-219
  HALback to text
• 21 articleF.François Morain. Modular curves over number fields and ECM.Research in Number Theory2022
  HAL
• 22 articleN.Natkamon Tovanich, N.Nicolas Soulié, N.Nicolas Heulot and P.Petra Isenberg. The evolution of mining pools and miners’ behaviors in the Bitcoin blockchain.IEEE Transactions on Network and Service Management193September 2022, 3633-3644
  HALDOI

International peer-reviewed conferences

• 23 inproceedingsA.Anaïs Barthoulot, O.Olivier Blazy and S.Sébastien Canard. (Augmented) Broadcast Encryption from Identity Based Encryption with Wildcard.Cryptology and Network Security. 21st International Conference, CANS 2022 Dubai, United Arab Emirates, November 13–16, 2022, Proceedings.CANS 2022 - 21st International Conference on Cryptology and Network SecurityLNCS-13641Cryptology and Network SecurityDubai, United Arab EmiratesSpringer International PublishingNovember 2022, 143-164
  HALDOI
• 24 inproceedingsS.Slim Bettaieb, L.Loïc Bidoux, O.Olivier Blazy, B.Baptiste Cottier and D.David Pointcheval. Post-Quantum and UC-secure Oblivious Transfer from SPHF with Grey Zone.15th International Symposium on Foundations & Practice of Security (FPS--2022)15th International Symposium on Foundations & Practice of Security (FPS – 2022).Ottawa, CanadaDecember 2022
  HAL
• 25 inproceedingsL.Luk Bettale, J.Julien Eynard, S.Simon Montoya, G.Guénaël Renault and R.Rémi Strullu. Security Assessment of NTRU Against Non-Profiled SCA.CARDIS 2022Birmingham, United KingdomNovember 2022
  HALback to text
• 26 inproceedingsO.Olivier Blazy, I.Ioana Boureanu, P.Pascal Lafourcade, C.Cristina Onete and L.Léo Robert. How fast do you heal? A taxonomy for post-compromise security in secure-channel establishment.USENIX 2023 - The 32nd USENIX Security SymposiumUSENIX 2023 - The 32nd USENIX Security SymposiumAnaheim, United StatesAugust 2023
  HAL
• 27 inproceedingsO.Olivier Blazy, P.-A.Pierre-Alain Fouque, T.Thibaut Jacques, P.Pascal Lafourcade, C.Cristina Onete and L.Léo Robert. MARSHAL: Messaging with Asynchronous Ratchets and Signatures for faster HeALing.Symposium on Applied Computing (SAC)The 37th ACM/SIGAPP Symposium on Applied Computing, SAC (2022)Virtual, Czech RepublicACMApril 2022, 1-8
  HALDOI
• 28 inproceedingsO.Olivier Blazy and S.Saqib Kakvi. Identity-Based Encryption in DDH Hard Groups.Lecture Notes in Computer ScienceAFRICACRYPT 2022 - 13th International Conference on Cryptology in AfricaLNCS-13503Progress in Cryptology - AFRICACRYPT 2022Fes, MoroccoSpringer Nature Switzerland; Springer Nature SwitzerlandOctober 2022, 81-102
  HALDOI
• 29 inproceedingsM.Maxime Bombar, A.Alain Couvreur and T.Thomas Debris-Alazard. On Codes and Learning With Errors over Function Fields.Lecture Notes in Computer ScienceCRYPTO 202213508Advances in Cryptology – CRYPTO 2022Santa Barbara (CA), United StatesSpringer Nature SwitzerlandOctober 2022, 513-540
  HALDOIback to text
• 30 inproceedingsS.Sarah Bordage, M.Mathieu Lhotel, J.Jade Nardi and H.Hugues Randriam. Interactive Oracle Proofs of Proximity to Algebraic Geometry Codes.CCC '22: Proceedings of the 37th Computational Complexity ConferenceCCC 2022 - 37th Computational Complexity ConferencePhiladelphie, United StatesSeptember 2022, 30:1--30:45
  HALDOIback to text
• 31 inproceedingsK.Kévin Carrier, T.Thomas Debris-Alazard, C.Charles Meyer-Hilfiger and J.-P.Jean-Pierre Tillich. Statistical Decoding 2.0: Reducing Decoding to LPN.ASIACRYPT 2022 - 28th Annual International Conference on the Theory and Application of Cryptology and Information SecurityTaipei, TaiwanDecember 2022
  HALback to text
• 32 inproceedingsA.Alexis Challande, R.Robin David and G.Guénaël Renault. Building a Commit-level Dataset of Real-world Vulnerabilities.CODASPY 2022 - 12th ACM Conference on Data and Application Security and PrivacyBaltimore MD USA, United StatesACMApril 2022, 101-106
  HALDOI
• 33 inproceedingsY.Youssef El Housni and A.Aurore Guillevic. Families of SNARK-friendly 2-chains of elliptic curves.LNCSAdvances in Cryptology - EUROCRYPT 2022 - 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques13276EUROCRYPT 2022Trondheim / Hybrid, NorwaySpringerMay 2022, 367-396
  HALDOIback to text
• 34 inproceedingsY.Youssef El Housni, A.Aurore Guillevic and T.Thomas Piellard. Co-factor clearing and subgroup membership testing on pairing-friendly curves.AFRICACRYPT 2022 - 13th International Conference on Cryptology13503LNCSFes, MoroccoSpringerOctober 2022, 518--536
  HALDOIback to text
• 35 inproceedingsY.Youssef El Housni. Pairings in Rank-1 Constraint Systems.ACNS2023 - 21st International Conference on Applied Cryptography and Network SecurityKyoto, JapanJune 2023
  HAL
• 36 inproceedingsK.Karim Eldefrawy, T.Tancrède Lepoint and A.Antonin Leroux. Communication-Efficient Proactive MPC for Dynamic Groups with Dishonest Majorities.ACNS 2022ACNS 2022Rome, Italy2021
  HAL
• 37 inproceedingsA.Antonin Leroux. A New Isogeny Representation and Applications to Cryptography.ASIACRYPT 2022Taipei, TaiwanDecember 2022
  HALback to text
• 38 inproceedingsA.Antonin Leroux. An Effective Lower Bound on the Number of Orientable Supersingular Elliptic Curves.SAC 2022 - Selected Areas in CryptographyWindsor, CanadaAugust 2022
  HAL
• 39 inproceedingsF.Françoise Levy-Dit-Vehel and M.Maxime Roméas. A Framework for the Design of Secure and Efficient Proofs of Retrievability.LNCSInternational Conference on Cryptology, Coding Theory, and Cybsersecurity, I4CSCasablanca, Morocco, MoroccoOctober 2022
  HALback to text
• 40 inproceedingsF.Françoise Levy-Dit-Vehel and M.Maxime Roméas. Efficient Proofs of Retrievability using Expander Codes.Cryptography and Network Security, CANS 2022Abu Dhabi, United Arab EmiratesNovember 2022
  HALback to text
• 41 inproceedingsF.François Morain. Implementing the Thull-Yap algorithm for computing Euclidean remainder sequences.ISSAC2022Villeneuve-d’Ascq, FranceJuly 2022
  HAL

Conferences without proceedings

• 42 inproceedingsM.Maxime Bombar and A.Alain Couvreur. Right-hand side decoding of Gabidulin codes and applications.WCC 2022 : The Twelfth International Workshop on Coding and CryptographyRostock, GermanyMarch 2022
  HALback to textback to text
• 43 inproceedingsA.Alexis Challande, R.Robin David and G.Guénaël Renault. Quokka: A Fast and Accurate Binary Exporter.GreHack 2022 - 10th International Symposium on Research in Grey-Hat HackingGrenoble, FranceNovember 2022
  HAL

Edition (books, proceedings, special issue of a journal)

• 44 proceedingsG.Gustavo BanegasK.Koen ZandbergE.Emmanuel BaccelliA.Adrian HerrmannB.Benjamin SmithQuantum-Resistant Software Update Security on Low-Power Networked Embedded Devices.13269Lecture Notes in Computer ScienceSpringer International PublishingJune 2022, 872-891
  HALDOI

Doctoral dissertations and habilitation theses

• 45 thesisS.Sarah Bordage. Efficient protocols for testing proximity to algebraic codes.Institut Polytechnique de ParisJune 2022
  HAL
• 46 thesisA.Alexis Challande. Towards 1-day Vulnerability Detection using Semantic Patch Signatures.Institut polytechnique de ParisOctober 2022
  HAL
• 47 thesisY.Youssef El Housni. The Arithmetic of Pairing-Based Proof Systems.Institut Polytechnique de ParisNovember 2022
  HAL
• 48 thesisA.Antonin Leroux. Quaternion Algebra and isogeny-based cryptography.Ecole doctorale de l’Institut Polytechnique de ParisSeptember 2022
  HAL
• 49 thesisS.Simon Montoya. Embedded lattice-based cryptography.Institut polytechnique de ParisOctober 2022
  HAL
• 50 thesisM.Maxime Roméas. Modeling and construction of interactive cryptographic protocols for outsourced storage.Institut Polytechnique de Paris; Ecole PolytechniqueNovember 2022
  HAL

Reports & preprints

• 51 miscR.Razvan Barbulescu, P.Pierrick Gaudry, A.Aurore Guillevic and F.François Morain. Improvements to the number field sieve for non-prime finite fields.August 2022
  HAL
• 52 miscE.Elena Berardini, A.Alain Couvreur and G.Grégoire Lecerf. A proof of the Brill-Noether method from scratch.August 2022
  HAL
• 53 miscJ.Jeremy Booher, R.Ross Bowden, J.Javad Doliskani, T. B.Tako Boris Fouotsa, S.Steven Galbraith, S.Sabrina Kunzweiler, S.-P.Simon-Philipp Merz, C.Christophe Petit, B.Benjamin Smith, K. E.Katherine E. Stange, Y. B.Yan Bo Ti, C.Christelle Vincent, J. F.José Felipe Voloch, C.Charlotte Weitkämper and L.Lukas Zobernig. Failing to hash into supersingular isogeny graphs.July 2022
  HAL
• 54 miscG.Gautam Botrel and Y.Youssef El Housni. EdMSM: Multi-Scalar-Multiplication for recursive SNARKs and more.October 2022
  HALback to text
• 55 miscA.Alain Couvreur. Improved decoding of symmetric rank metric errors.December 2022
  HALback to text
• 56 miscT.Thomas Debris-Alazard, M.Maxime Remaud and J.-P.Jean-Pierre Tillich. Quantum Reduction of Finding Short Code Vectors to the Decoding Problem.January 2022
  HALback to text
• 57 miscC.Clément Ducros and G.Geoffroy Couteau. Pseudorandom Correlation Functions fromVariable-Density LPN, Revisited.January 2023
  HALback to text
• 58 miscE.Eleonora Guerrini, K.Kamel Lairedj, R.Romain Lebreton and I.Ilaria Zappatore. Simultaneous Rational Function Reconstruction with Errors: Handling Multiplicities and Poles.March 2022
  HAL
• 59 miscF.Françoise Levy-Dit-Vehel and M.Maxime Roméas. A Composable Look at Updatable Encryption.January 2022
  HAL
• 60 miscF.François Morain. Some factors of numbers of the form $b^n\pm 1$ found using ECM with new classes of curves.March 2022
  HALback to text

Other scientific publications

• 61 miscD.Daniel Augot, S.Sarah Bordage, Y.Youssef El Housni, G.Gilles Fedak and A.Anthony Simonet. Zero-Knowledge : trust and privacy on an industrial scale.January 2022
  HAL

Educational activities

• 62 unpublishedA.Alain Couvreur. Codes and modular curves.July 2022, DoctoralSwitzerland
  HALback to text