3.1 Quantum algorithms and cryptanalysis

The current state-of-the-art asymmetric cryptography would become insecure in a post-quantum world, and the community is actively searching for alternatives. Symmetric cryptography, essential for enabling secure communications, used to seem much less affected at first sight: the biggest known threat was Grover's algorithm, which allows exhaustive key searches in the square root of the search space. Thus, it was believed that doubling key-lengths suffices to maintain an equivalent security in the post-quantum world. This conventional wisdom was contradicted by Kuwakado and Morii in 2012 when they proposed for the first time to use Simon's algorithm in symmetric cryptanalysis 81, proving the popular Even-Mansour construction to be insecure in a strong security model called the superposition model.

This model allows an attacker to query quantumly the block cipher. Simon's algorithm 83 contrarily to Grover's algorithm gives an exponential speedup and can therefore be devastating in this setting.

In the framework of our ERC QUASYModo, we studied in detail this algorithm and possible applications, and we were able to show that Simon's algorithm applies to other schemes as well, such as for instance to the CAESAR candidate AEZ 76. It also allows to break some well-known modes of operation for MACs and authenticated encryption and provides devastating quantum slide attacks  9. Other quantum algorithms turned out be useful in this model, such as for instance Kuperberg's algorithm 80. It allowed to break a tweak  71 to counter the previous attack of 9 or to devise a quantum attack in the superposition model on the Poly1305 MAC primitive 74, which is largely used and claimed to be quantumly secure.

All these results show that in symmetric (and asymmetric) cryptography, the impact of quantum computers goes well beyond Grover's and Shor's algorithms and has to be studied carefully in order to understand if a given cryptographic primitive is secure or not in a quantum world. To correctly evaluate the security of cryptographic primitives in the post-quantum world, it is really desirable to elaborate a quantum cryptanalysis toolbox. This is precisely the first objective of the ERC QUASYModo regarding symmetric cryptanalysis. We plan in the coming years to continue to actively contribute to this toolbox. This goes together with improving or finding new quantum algorithms for cryptanalysis, possibly adapted to some particular situations or scenarios that have not been studied before, like the $k$-XOR problem. This whole thread of research, that needs to combine techniques from symmetric or asymmetric cryptanalysis together with quantum algorithmic tools, came naturally in our team. We are namely composed of symmetric and asymmetric cryptologists as well as of experts in quantum computing and we are in a privileged position to perform this kind of research.

3.2 Symmetric cryptology

Symmetric techniques are widely used because they are the only ones that can achieve some major features such as high-speed or low-cost encryption, fast authentication, and efficient hashing. It is a very active research area which is stimulated by a pressing industrial demand for low-cost implementations. Even if the block cipher standard AES remains unbroken 20 years after its design, it clearly appears that it cannot serve as a Swiss Army knife in all environments. In particular an important challenge raised by several new applications is the design of symmetric encryption schemes with some additional properties compared to the AES, either in terms of implementation performance (low-cost hardware implementation, low latency, resistance against side-channel attacks...) or in terms of functionalities. The past decade has then been characterized by a multiplicity of new proposals and evaluating their security has become a primordial task which requires the attention of the community.

This proliferation of symmetric primitives has been amplified by public competitions, including the recent NIST lightweight standardization effort, which have encouraged innovative but unconventional constructions in order to answer the harsh implementation constraints. These promising but new designs need to be carefully analyzed since they may introduce unexpected weaknesses in the ciphers. Our research work captures this conflict for all families of symmetric ciphers. It includes new attacks and the search for new building blocks which ensure both a high resistance to known attacks and a low implementation cost. This work, which combines cryptanalysis and the theoretical study of discrete mathematical objects, is essential to progress in the formal analysis of the security of symmetric systems.

Our specificity, compared to most groups in the area, is that our research work tackles all aspects of the problem, from the practical ones (new attacks, concrete constructions of primitives and low-cost building-blocks) to the most theoretical ones (study of the algebraic structure of underlying mathematical objects, definition of optimal objects). We study these aspects not separately but as several sides of the same domain.

3.3 Post-quantum asymmetric cryptology

Current public-key cryptography is particularly threatened by quantum computers, since almost all cryptosystems used in practice rely on related number-theoretic security problems that can be easily solved on a quantum computer as shown by Shor in 1994. This very worrisome situation has prompted NIST to launch a standardization process in 2017 for quantum-resistant alternatives to those cryptosystems. This concerns all three major asymmetric primitives, namely public-key encryption schemes, key-exchange protocols and digital signatures. The NIST has made it clear that for each primitive there will be several selected candidates relying on different security assumptions. It publicly admits that the evaluation process for these post-quantum cryptosystems is significantly more complex than the evaluation of the SHA-3 and AES candidates for instance.

There were 69 (valid) submissions to this call in November 2017, with numerous lattice-based, code-based and multivariate-cryptography submissions and some submissions based either on hashing or on supersingular elliptic curve isogenies. In January 2019, 26 of these submissions were selected for the second round and 7 of them are code-based submissions. In July 2020, 15 schemes were selected as third round finalists/alternate candidates, 3 of them are code-based. NIST has anounced in 2021 that this call for postquantum primitives would be extended specifically for digital signatures based on techniques other than lattices. This new call should be released in the first quarter of 2022.

The research of the project-team in this field is focused on the design and cryptanalysis of cryptosystems making use of coding theory and we have proposed code-based candidates to the NIST call for the first two types of primitives, namely public-key encryption and key-exchange protocols and have two candidates among the finalists/alternate candidates. We are also preparing proposals of code-based signatures schemes for the call which is expected in 2022.

3.4 Quantum information

The field of quantum information and computation aims at exploiting the laws of quantum physics to manipulate information in radically novel ways. There are two main applications:

• (i)
  quantum computing, that offers the promise of solving some problems that seem to be intractable for classical computers such as for instance factorization or solving the discrete logarithm problem;
• (ii)
  quantum cryptography, which provides new ways to exchange data in a provably secure fashion. For instance it allows key distribution by using an authenticated channel and quantum communication over an unreliable channel with information-theoretic security, in the sense that its security can be proven rigorously by using only the laws of quantum physics, even with all-powerful adversaries.

Our team deals with quantum coding theoretic issues related to building a large quantum computer and with quantum cryptography. If these two questions may seem at first sight quite distinct, they are in fact closely related in the sense that they both concern the protection of (quantum) information either against an adversary in the case of quantum cryptography or against the environment in the case of quantum error-correction. This connection is actually quite deep since an adversary in quantum cryptography is typically modeled by a party having access to the entire environment. The goals of both topics are then roughly to be able to measure how much information has leaked to the environment for cryptography and to devise mechanisms that prevent information from leaking to the environment in the context of error correction.

While quantum cryptography is already getting out of the labs, this is not yet the case of quantum computing, with large quantum computers capable of breaking RSA with Shor's algorithms maybe still decades away. The situation is evolving very quickly, however, notably thanks to massive public investments in the past couple of years and all the major software or hardware companies starting to develop their own quantum computers. One of the main obstacles towards building a quantum computer is the fragility of quantum information: any unwanted interaction with the environment gives rise to the phenomenon of decoherence which prevents any quantum speedup from occurring. In practice, all the hardware of the quantum computer is intrinsically faulty: the qubits themselves, the logical gates and the measurement devices. To address this issue, one must resort to quantum fault-tolerance techniques which in turn rely on the existence of good families of quantum error-correcting codes that can be decoded efficiently. Our expertise in this area lies in the study of a particularly important class of quantum codes called quantum low-density parity-check (LDPC) codes. The LDPC property, which is well-known in the classical context where it allows for very efficient decoding algorithms, is even more crucial in the quantum case since enforcing interactions between a large number of qubits is very challenging. Quantum LDPC codes solve this issue by requiring each qubit to only interact with a constant number of other qubits.

4.1 Designing, Analyzing and Choosing Cryptographic Standards

The research community is strongly involved in the development and evolution of cryptographic standards. Many standards are developed through open competitions (e.g. AES, SHA-3) where multiple teams propose new designs, and a joint cryptanalysis effort allows to select the most suitable proposals. The analysis of established standards is also an important work, in order to depreciate weak algorithms before they can be exploited. Several members of the team have been involved in this type of effort and we plan to continue this work to ensure that secure algorithms are widely available. We believe that good cryptographic standards have a large socio-economic impact, and we are active in proposing schemes to future competitions, and in analyzing schemes proposed to current or future competitions, as well as widely-used algorithms and standards.

At the moment, we are involved in the two standardization efforts run by NIST for post-quantum cryptography and lightweight cryptography. We have also uncovered potential backdoors in two algorithms from the Russian Federation (Streebog and Kuznyechik), and successfully presented the standardization of the latter by ISO. We have also implemented practical attacks against SHA-1 to speed-up its deprecation.

NIST post-quantum competition.

The NIST post-quantum competition1 aims at standardizing quantum-safe public-key primitives. It is really about offering a credible quantum-safe alternative for the schemes based on number theory which are severely threatened by the advent of quantum computers. It is expected to have a huge and long-term impact on all public-key cryptography. It has received 69 proposals in November 2017, among which five have been co-designed by the project-team. Four of them have made it to the second round in January 2019. One of them was chosen in July 2020 for the third round and another one was chosen as an alternate third round finalist. We have also broken two first round candidates Edon-K  82 and RankSign  79, and have devised a partial break of the RLCE encryption scheme 77. In 2020, we obtained a significant breakthrough in solving more efficiently the MinRank problem and the decoding problem in the rank metric 72, 73 by using algebraic techniques. This had several consequences: all second round rank metric candidates were dismissed from the third round (including our own candidate) and it was later found out that this algebraic algorithm could also be used to attack the third round multivariate finalist, namely Rainbow and the alternate third round finalist GeMSS.

NIST competition on lightweight symmetric encryption.

The NIST lightweight cryptography standardization process2 is an initiative to develop and standardize new authenticated encryption algorithms suitable for constrained devices. As explained in Subsection 3.2, there is a real need for new standards in lightweight cryptography, and the selected algorithms are expected to be widely deployed within the Internet of Things, as well as on more constrained devices such as contactless smart cards, or medical implants. The NIST received 56 submissions in February 2019, three of which have been co-designed by members of the team.

Monitoring Current Standards

While we are very involved in the design phase of new cryptographic standards (see above), we also monitor the algorithms that are already standardized. In practice, this work has two sides.

First, we work towards the deprecation of algorithms known to be unsage. Unfortunately, even when this fact is known in the academic community, standardizing bodies can be slow to implement the required changes to their standards. This prompted for example G. Leurent to implement even better attacks against SHA-1 to illustrate its very practical weakness, and L. Perrin and X. Bonnetain (then a COSMIQ member) to find simple arguments proving that a subfunction used by the current Russian standards was not generated randomly, despite the claims of its authors.

Second, it also means that we participate to the relevant ISO meetings discussing the standardization of cryptographic primitives (JC27/WG2), and that we follow the discussions of the IETF and IRTF on RFCs. We have also provided technical assistance to members of other standardizing bodies such as the ETSI.

4.2 Large scale deployment of quantum cryptography

Major academic and industrial efforts are currently underway to implement quantum key distribution at large scale by integrating this technology within existing telecommunication networks. Colossal investments have already taken place in China to develop a large network of several thousand kilometers secured by quantum cryptography, and there is little doubt that Europe will follow the same strategy, as testified by the current European projects CiViQ (in which we are involved), OpenQKD and the future initiative Euro-QCI (Quantum Communication Infrastructure). While the main objectives of these actions are to develop better systems at lower cost and are mainly engineering problems, it is crucial to note that the security of the quantum key distribution protocols to be deployed remains far from being completely understood. For instance, while the asymptotic regime of these protocols (where one assumes a perfect knowledge of the quantum channel for instance) has been thoroughly studied in the literature, it is not the case of the much more relevant finite-size regime accounting for various sources of statistical uncertainties for instance. Another issue is that compliance with the standards of the telecommunication industry requires much improved performances compared to the current state-of-the-art, and this can only be achieved by significantly tweaking the original protocols. It is therefore rather urgent to better understand whether these more efficient protocols remain as secure as the previous ones. Our work in this area is to build upon our own expertise in continuous-variable quantum key distribution, for which we have developed the most advanced security proofs, to give security proofs for the protocols used in this kind of quantum networks.

5.1 Oversight of COVID Digital Tools

During the course of the COVID-19 pandemic, several digital tools were developped to help mitigating the pandemic. We have not been involved in the developpement of these tools, but we took an active role in analyzing them, and contributing to the political debate.

• Digital Contact Tracing:

  During the first wave of the COVID-19 pandemic, several efforts were initiated to develop smartphone applications intended to contribute to contact tracing. The core idea consists in using Bluetooth signal to estimate the distance and the duration of a contact between two app users.

  Later, venue tracking was implemented in several countries. The core idea is to warn patrons when a public place is detected to be a cluster: patrons scan a QR-code with a random identifier when entering the venue, and a list of identifiers with known clusters is published daily.

  In France Bluetooth tracing was implemented in the StopCovid application launched on June 2 2020, and renamed TousAntiCovid on October 22 2020. Venue tracking was added on June 9 2021.

• Covid Certificates:

  At the end of 2020, discussions began in the European Union about vaccine passports and covid certificates, and the first guidelines from European institutions were published in January 2021. A Covid Certificate is a machine-readable document (usually in the form of a QR-code) containing health information with a cryptographic signature from a health autority.

  Covid certificates started to be used in France on June 9 2021, and the European version was put in place on July 1st 2021.

Members of the COSMIQ team began to be involved in this topic in April 2020. As several contact tracing projects became public, an inter-disciplinary collaboration between researchers in cryptography, in security and in technology law, involving the COSMIQ, CARAMBA, PESTO project-teams and other academic institutions, was initiated in order to investigate the consequences of the deployment of such applications in terms of privacy and security. Indeed, a public (and often external) security analysis is always expected for applications dealing with sensitive data such as, in this instance, medical information and each user's social graph. As mentioned in the introduction of Inria's white book on cybersecurity, "the first step in cybersecurity is to identify threats and define a corresponding attacker model. [...] Since zero risk cannot exist, the early detection and mitigation of attacks is as important as the attempt to reduce the risk of successful attacks." Understanding the limits of a system is then necessary to improve its security and to decide whether it can be deployed without taking ill-considered risks, exactly as the side effects of a drug should be documented.

As political discussions and decisions were taking place, we contributed to these debates by providing an easy to understand description of the security pitfalls that are inherent to bluetooth-based contact tracing: "le traçage anonyme, un bel oxymore"  75. The analysis presented in  75 is, in most cases, independent of the subtleties of the privacy-preserving mechanism, and in particular can be applied to both so-called "centralized" and "decentralized" systems. As a consequence, its authors also worked with researchers based in the UK to provide an English translation https://­tracing-risks.­com/.

This work had a significant impact (the website received more than 100K unique visitors) and led to further contributions from researchers from the COSMIQ team.

• Anne Canteaut was invited to present the results of  75 to the Commission de la Culture, de l'Education et de la Communication of the Sénat on May 27, 2020 (see https://­www.­senat.­fr/­compte-rendu-commissions/­20200525/­cult.­html).
• Gaëtan Leurent identified inconsistencies between the specification of Stopcovid and its implementation pertaining to the amount of data sent to the central server. This was notified to the StopCovid project-team using the bug tracking system3, and the CNIL required the issue to be fixed in a formal notice4.
• Anne Canteaut, as the program co-chair of Eurocrypt'20, organized a panel discussion on bluetooth-based contact tracing at this conference. Among the speakers invited at this discussion were designers of such contact tracing applications, including Stopcovid (France), and Swisscovid (Switzerland). This panel discussion was attended by approximately 1900 persons.
• Léo Perrin was invited to present contact tracing applications, their principle, and the corresponding debates at two venues: the seminar of the working group Maths4Covid of the Jacques-Louis Lions lab, and to students of the law faculty of Cergy-Pontoise.5
• Léo Perrin was invited to a panel on contact tracing at the summer school of the Haifa Technion (Israel)6 along with designers of the Swiss and Israeli contact tracing applications.
• Anne Canteaut contributed to the definition of an outreach activity for high-school students devoted to epidemics and contact tracing, and initiated by the French Academy of Sciences https://­www.­academie-sciences.­fr/­pdf/­rapport/­guide_module_tracage.­pdf.
• Gaëtan Leurent wrote an analysis of the TAC-W protocol, which was meant to be used for venue tracking7 in France. TAC-W had serious issues, and was replaced by CLÉA.
• Gaëtan Leurent contributed to an analysis of the statistics collection in TousAntiCovid8. This functionality was leaking a lot of private data and has been partially fixed.
• Gaëtan Leurent made several Freedom of Information requests for documents related to those digitals tools and their evaluation:
  • https://­madada.­fr/­demande/­analytics_tousanticovid
  • https://­madada.­fr/­demande/­aipd_des_outils_numeriques_de_lu
  • https://­madada.­fr/­demande/­rapport_sur_le_fonctionnement_de
  • https://­madada.­fr/­demande/­statistiques_sur_lutilisation_de

5.2 Footprint of research activities

During this second year of the COVID-19 pandemic, most conferences and workshops have been either cancelled or modified to be online events. Anne Canteaut played a significant role in enabling this transition as the program chair of Eurocrypt 2020 and Eurocrypt 2021. Eurocrypt 2021 was the first flagship conference in cryptography held in a hybrid format. The concomitance of remote talks and of in-person talks required to adapt the format of the conference, the lengths of the talks... This very first experience will motivate discussions on the future format of conferences in our area.

5.3 Impact of research results on standardisation

Our cryptanalysis results on SHA-1 10 and GEA 28 have helped convince users and industry to deprecate those obsolete standards. Publication of those attacks and discussion with industry has resulted in concrete actions to reduce usage of those ciphers.

Our project is also involved in two NIST competitions: the competition for lightweight cryptography and the competition for standardizing quantum safe cryptosystems. In the first competition, our team has still one candidate in the third round of the competition, while in the second competition we have one candidate that is a third round finalist and another one which is an alternate third round finalist. The outcome of these two competitions will have a strong impact since the standardized solutions will likely replace large parts of the world’s infrastructure underpinning secure global communication.

6.1 Awards

• Laureate of the Woman Cyber Researcher award 2021:

   

  Anne Canteaut https://cyberwomenday-cefcys.com/en/

• Prix de thèse Gilles Kahn 2020:

   

  Thomas Debris-Alazard, Cryptographie fondée sur les codes: nouvelles approches pour constructions et preuves; contribution en cryptanalyse,   78

  Sorbonne Universités, UPMC University of Paris 6, 2019, https://www.societe-informatique-de-france.fr/2021/01/recherche-prix-de-these-gilles-kahn-laureats-2020/

• Eurocrypt best paper award:
  40 Clara Pernot, Gaëtan Leurent, New Representations of the AES Key Schedule, EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, Jun 16, 2021.

7.1 New software

8.1 Quantum algorithms and cryptanalysis

Participants: Ritam Bhaumik, Rémi Bricout, André Chailloux, Nicolas David, Simona Etinski, Antonio Flórez-Gutiérrez, Paul Frixons, Gaëtan Leurent, Johanna Loyer, María Naya-Plasencia, Maxime Remaud, André Schrottenloher.

We have kept on working on symmetric quantum cryptanalysis and generic quantum algorithms related to cryptanalysis, and in addition, started looking at some asymmetric cryptanalysis problems:

• André Schrottenloher PhD thesis
  This thesis 53 contains major results:

  • the first proof of an actual quantum time speedup for collision search in case of polynomially bounded quantum memory, solving here a long standing open question;
  • optimal quantum algorithms for solving fundamental problems such as k-XOR or k-SUM;
  • a general methodology for converting classical research problems into nested quantum research problems, with many applications in cryptanalysis;
  • an off-line Simon algorithm which enables to use for the first time Simon's algorithm in the standard attack model;
  • a distinguisher on the Gimli lightweight permutation.
• Quantum Linearization Attacks.
  In 2016, we have shown that many modes widely used in symmetric cryptography are completely broken by quantum superposition queries, using Simon's period-finding algorithm 9. In a new work published at Asiacrypt this year 30, we generalized those attacks to quantum linearization attacks, and broke several modes that were not yet known to be broken in this model (LightMAC, PMAC, OCB, ZMAC ...). We also describe variants of attacks using other quantum algorithms that had not been used previously in symmetric cryptanalysis: Deutsch’s, Bernstein-Vazirani’s, and Shor’s algorithms.
• QCB.
  Since many widely used modes are not secure against quantum superposition queries, we have proposed a new authenticated encryption mode with security against quantum adversaries: QCB 29. QCB is inspired by TAE and OCB, and is the first mode offering quantum security with high efficiency: it is parallelizable and has rate one.
• Quantum Boomerang Attacks and Some Applications.
  We give in 38 for the first time a quantum speedup for Boomerang attacks. In certain cases, we even obtain quadratic speedups, which results in a similar speedup as for differential attacks. This enlarges the toolbox for attacking quantumly symmetric primitives and results in a better general understanding of the resistance of symmetric ciphers against quantum computers.
• Lattice sieving via quantum walks.
  Lattice-based cryptography is one of the most promising solutions for post-quantum cryptography. For many of the proposed cryptosystems, the best algorithm to attack them is the BKZ algorithm which uses as its core several calls to an algorithm that solves the Shortest Vector Problem. This year, in the Asiacrypt paper 35 André Chailloux and Johanna Loyer improved the best quantum algorithms for SVP using quantum walks. As a direct consequence, this work reduces the quantum security of all lattice-based schemes proposed at the post-quantum NIST competition which must increase their parameters if they want to maintain the level of security they announced.
• Quantum Security of the Legendre PRF.
  In 39, we study the security of the Legendre PRF against quantum attackers, given classical queries only, and without quantum random-access memories. We give two algorithms that recover the key of a shifted Legendre symbol with unknown shift, with a complexity smaller than the exhaustive search of the key. The first one is a quantum variant of the table-based collision algorithm. The second one is an offline variant of Kuperberg's abelian hidden shift algorithm.

8.2 Symmetric cryptology

Participants: Augustin Bariant, Jules Baudrin, Ritam Bhaumik, Clémence Bouvier, Anne Canteaut, Pascale Charpin, Daniel Coggia, Nicolas David, Gaëtan Leurent, María Naya-Plasencia, Clara Pernot, Léo Perrin, André Schrottenloher.

Our recent results in symmetric cryptography concern either the security analysis of existing primitives, or the design of new primitives. This second topic includes some work on the construction and properties of suitable building-blocks for these primitives, e.g. on the search of highly nonlinear functions.

8.3 Post-quantum asymmetric cryptology

Participants: Magali Bardet, Pierre Briaud, Rémi Bricout, Etienne Burle, André Chailloux, Loïc Demange, Matthieu Lequesne, Charles Meyer-Hilfiger, Rocco Mora, Maxime Remaud, Nicolas Sendrier, Jean-Pierre Tillich, Valentin Vasseur.

Our work in this area is mainly focused on code-based cryptography, but some of our contributions, namely algebraic attacks, have applications in multivariate cryptography or in algebraic coding theory. Many contributions relate to the NIST call for postquantum primitives, either cryptanalysis or design.

We have also been organizing since 2015 a working group held every month or every two months on code-based cryptography that structures the French efforts on this topic: every meeting is attended by most of the groups working in France on this topic (project-team GRACE, University of Bordeaux, University of Limoges, University of Rennes and University of Rouen).

Our main contributions during the period are given below

• Algebraic attacks
  A series of works are related to algebraic attacks and Gröbner basis. An effective attack on the SIDON cryptosystem 31, an improvement on the best known attacks against the RSL (Rank Support Learning) problem 26, and also other cryptanalytic works in progress which relate to the NIST competition, either rank metric-based or multivariate cryptography 55, 56. This research also has applications in algebraic coding theory 27.
• NIST competition
  Two of our NIST candidates are still in the third round of the competition. First ClassicMcEliece, which is a KEM (Key Encapsulation Mechanism) finalist and is a stabilized system which does not require further research work. Also BIKE, which is a KEM alternative candidate. The state-of-the-art about the decoding failure rate (DFR) of BIKE 68 is part of Valentin Vasseur's PhD 54, and is one of the key points to estimate the the security of the scheme. Another work in progress about BIKE 67 considers the protection against some side-channel attacks (timing, cache).
• Follow-up of the NIST competition on signatures
  We are also working to prepare the extension of the NIST call to digital signatures. Code-based signatures were not ready in 2017 when the first call was made, and all code-based signatures were discarded. There has been considerable progress since then. The project-team has been preparing to submit new proposals using Wave  6, or other techniques60.
• Fundamental issues in code-based cryptography
  We have also been working on fundamental and prospective topics. For instance, we have devised a general framework 34 for the computation of the complexity of classical and quantum information set decoding techniques, and have applied for the Lee metric in particular, or through various fundamental works exploring the weaknesses involved by the use of codes with algebraic structure in cryptography 19, 52. Some of this work was motivated by effective attacks on existing cryptosystems, but the scope of the results often went beyond that. Another fundamental problem, especially if one wants to build signature schemes is to understand the difficulty of the low weight codeword search problem. One possible path for achieving this is to relate it to the decoding problem. In lattice-based cryptography, this is analoguous to relate the LWE problem to the SIS problem. A fundamental tool is here Regev's quantum reduction from SIS to LWE. We have obtained a similar reduction in the context of coding theory in 66 for various code-based metrics.

8.4 Quantum information

Participants: Ivan Bardet, Rémi Bricout, André Chailloux, Aurélie Denys, Shouvik Gorai, Lucien Grouès, Anthony Leverrier, Andrea Olivo, Jean-Pierre Tillich.

Most of our work in quantum information deals with either quantum algorithms, quantum error correction or cryptography.

• Security of continuous-variable protocols
  A major question in the field of quantum key distribution is to prove the security of practical continuous-variable protocols. The main advantage of these protocols is that they can be implemented with standard equipment from optical telecommunications, and do not require specific hardware such as single-photon detectors. Up until now, all security proofs were restricted to protocols exploiting Gaussian modulation of coherent states. In contrast, practical protocols rely on discrete modulation where the coherent states are chosen from a finite constellation. In 20, Aurélie Denys, Peter Brown and Anthony Leverrier establish for the first time the security of such protocols in the asymptotic regime, and give explicit closed-form expressions for the secret key rate of these protocols for arbitrary constellations. This work was presented at QCrypt 2021 43 and ICQOM 2021 44.
• Feasibility of quantum key distribution with satellites
  Another major challenge in the field of quantum key distribution is to improve the range of the protocols, and communication via satellites offers a promising approach compared to fiber-based implementations. We have studied the feasibility of continuous-variable quantum key distribution with satellites in 21 and found that low-orbit satellites can indeed realistically help distribute secret keys.
• Decoding algorithms for quantum error correcting codes
  In the context of quantum error correcting codes, we have been developing several new decoding algorithms for constant rate quantum LDPC codes. A theoretical result demonstrating that quantum fault-tolerance can be obtained with constant overhead was invited as a research highlight of the Communications of the ACM 23. We have tested numerically the corresponding codes and decoder in 25 and found them to be competitive with the state-of-the-art decoders for quantum LDPC codes, while displaying a reduced complexity. Recently, we considered an alternative decoder consisting in formulating the decoding problem as a linear program, and also obtained encouraging numerical results 37.
• Locally testable quantum LDPC codes
  Our work on quantum error correction also focuses on the construction of interesting quantum LDPC codes. In particular, we have devised a family of locally testable quantum codes with a record soundness parameter 42.
• Quantum information theory
  We also study very fundamental questions in quantum information theory and have derived new quantum information theoretic inequalities such as the approximate tensorization of the relative entropy 15. We also provide there estimates on the constants in terms of conditions of clustering of correlations in the setting of quantum lattice spin systems. A related functional approach is also used to get estimations of the decoherence times, of private and quantum capacities, of entanglement-assisted classical capacities, as well as estimation of entanglement breaking times 16 or a better understanding of the heat-bath dynamics of 1D systems 14.

9.1 Bilateral contracts with industry

• LOTUS:(01/2021 -> 30/06/2021) Contract with Thales for a survey on the implementation of code-based post-quantum cryptosystems.

  45 kEuros.

9.2 Bilateral grants with industry

• Orange Labs Caen (11/2019 -> 11/2022) Funding for the supervision of Paul Frixon's PhD.

  30 kEuros.

• Bull-ATOS (07/2020 -> 06/2023) Funding for the supervision of Maxime Rémaud's PhD.

  60 kEuros.

• Thalès (11/2020 -> 10/2023) Funding for the supervision of Loïc Demange's PhD.

  45 kEuros.

10.1 International initiatives

10.2 International research visitors

10.3 European initiatives

10.4 National initiatives

• ANR DEREC (10/16→03/22)

  Relativistic cryptography

  ANR Program: jeunes chercheurs

  244 kEuros

  The goal of project DEREC is to demonstrate the feasibility of guaranteeing the security of some cryptographic protocols using the relativistic paradigm, which states that information propagation is limited by the speed of light. We plan to study some two party primitives such as bit commitment and their security against classical and quantum adversaries in this model. We then plan to the integration of those primitives into larger cryptosystems. Finally, we plan on performing a demonstration of those systems in real life conditions.

• ANR CBCRYPT (10/17→03/22)

  Code-based cryptography

  ANR Program: AAP Générique 2017

  Partners: Inria COSMIQ (coordinator), XLIM, Univ. Rouen, Univ. Bordeaux.

  197 kEuros

  The goal of CBCRYPT is to propose code-based candidates to the NIST call aiming at standardizing public-key primitives which resist to quantum attacks. These proposals are based either on code-based schemes relying on the usual Hamming metric or on the rank metric. The project does not deal solely with the NIST call. We also develop some other code-based solutions: these are either primitives that are not mature enough to be proposed in the first NIST call or whose functionalities are not covered by the NIST call, such as identity-based encryption, broadcast encryption, attribute based encryption or functional encryption. A third goal of this project is of a more fundamental nature: namely to lay firm foundations for code-based cryptography by developing thorough and rigorous security proofs together with a set of algorithmic tools for assessing the security of code-based cryptography.

• ANR quBIC (10/17→03/22)

  Quantum Banknotes and Information-Theoretic Credit Cards

  ANR Program: AAP Générique 2017

  Partners: Univ. Paris-Diderot (coordinator), Inria COSMIQ, UPMC (LIP6), CNRS (Laboratoire Kastler Brossel)

  87 kEuros

  For a quantum-safe future, classical security systems as well as quantum protocols that guarantee security against all adversaries must be deployed. Here, we will study and implement one of the most promising quantum applications, namely unforgeable quantum money. A money scheme enables a secure transaction between a client, a vendor and a bank via the use of a credit card or via the use of banknotes, with maximal security guarantees. Our objectives are to perform a theoretical analysis of quantum money schemes, in realistic conditions and for encodings in both discrete and continuous variables, and to demonstrate experimentally these protocols using state-of-the-art quantum memories and integrated detection devices.

• ANR SWAP (02/22→01/26)

  Sboxes for Symmetric-Key Primitives

  ANR Program: AAP Générique 2021

  Partners: UVSQ (coordinateur), Inria COSMIQ, ANSSI, CryptoExperts, Univ. of Rouen, Univ. of Toulon.

  172 kEuros

  Sboxes are small nonlinear functions that are crucial components of most symmetric-key designs and their properties are highly related to the security of the overall construction. The development of new attacks has given rise to many Sbox design criteria. However, the emerge of new contexts, applications and environments requires the development of new design criteria and strategies. The SWAP project aims first at investigating such criteria for emerging use cases like whitebox cryptography, fully homomorphic encryption and side-channel resistance. Then, we wish for analyzing the impact of these particular designs on cryptanalysis and see how the use of Sboxes with some special mathematical structures can accelerate some known attacks or introduce new ones. Finally, we aim at studying Sboxes from a mathematical point of view and provide new directions to the Big APN problem, an old conjecture on the existence of a particular type of optimal permutations.

10.5 Regional initiatives

DIM SIRTEQ The SIRTEQ project labeled Major Interest Domain (DIM) is funded by the Ile-de-France Region. SIRTEQ brings together the largest European concentration of academic teams in the field of quantum technologies. Its main objective is to promote an excellent academic research in the field of quantum technologies in Ile de France, taking into account the actual current societal challenges and the importance of the transfer of knowledge and technologies.

We are involved in this project in the quantum communications (quantum cryptography) and quantum computation (quantum error codes, quantum cryptanalysis) themes.

11.1 Promoting scientific activities

11.2 Teaching - Supervision - Juries

11.3 Popularization

12.1 Major publications

• 1 inproceedingsC.Christof Beierle, A.Anne Canteaut, G.Gregor Leander and Y.Yann Rotella. Proving Resistance Against Invariant Attacks: How to Choose the Round Constants..Crypto 2017 - Advances in Cryptology10402LNCS - Lecture Notes in Computer ScienceSteven MyersSanta Barbara, United StatesSpringerAugust 2017, 647--678
  HALDOI
• 2 articleA.Anne Canteaut and L.Léo Perrin. On CCZ-Equivalence, Extended-Affine Equivalence, and Function Twisting.Finite Fields and Their Applications56March 2019, 209-246
  HALDOI
• 3 inproceedingsA.André Chailloux, M.María Naya-Plasencia and A.André Schrottenloher. An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography.Asiacrypt 2017 - Advances in Cryptology10625 LNCS - Lecture Notes in Computer ScienceHong Kong, ChinaSpringerDecember 2017, 211--240
  HALDOI
• 4 articleK.Kaushik Chakraborty, A.André Chailloux and A.Anthony Leverrier. Arbitrarily Long Relativistic Bit Commitment.Physical Review Letters115December 2015
  HALDOI
• 5 articleP.Pascale Charpin, G. M.Gohar M. Kyureghyan and V.Valentin Suder. Sparse Permutations with Low Differential Uniformity.Finite Fields and Their Applications28March 2014, 214-243
  HALDOI
• 6 inproceedingsT.Thomas Debris-Alazard, N.Nicolas Sendrier and J.-P.Jean-Pierre Tillich. Wave: A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes.ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security11921LNCSKobe, JapanSpringerDecember 2019, 21-51
  HALDOIback to text
• 7 inproceedingsO.Omar Fawzi, A.Antoine Grospellier and A.Anthony Leverrier. Constant overhead quantum fault-tolerance with quantum expander codes.FOCS 2018 - 59th Annual IEEE Symposium on Foundations of Computer ScienceParis, FranceOctober 2018, 743-754
  HALDOI
• 8 inproceedingsA.Antonio Flórez Gutiérrez, G.Gaëtan Leurent, M.María Naya-Plasencia, L.Léo Perrin, A.André Schrottenloher and F.Ferdinand Sibleyras. New results on Gimli: full-permutation distinguishers and improved collisions.Asiacrypt 2020 - 26th Annual International Conference on the Theory and Application of Cryptology and Information SecurityDaejeon / Virtual, South KoreaDecember 2020
  HALback to textback to text
• 9 inproceedingsM.Marc Kaplan, G.Gaëtan Leurent, A.Anthony Leverrier and M.María Naya-Plasencia. Breaking Symmetric Cryptosystems Using Quantum Period Finding.Crypto 2016 - 36th Annual International Cryptology Conference9815LNCS - Lecture Notes in Computer ScienceSanta Barbara, United StatesSpringerAugust 2016, 207-237
  HALDOIback to textback to textback to text
• 10 inproceedingsG.Gaëtan Leurent and T.Thomas Peyrin. SHA-1 is a Shambles.USENIX 2020 - 29th USENIX Security SymposiumBoston / Virtual, United StatesAugust 2020
  HALback to textback to text
• 11 articleA.Anthony Leverrier. Security of Continuous-Variable Quantum Key Distribution via a Gaussian de Finetti Reduction.Physical Review Letters11820May 2017, 1--24
  HALDOI
• 12 inproceedingsR.Rafael Misoczki, J.-P.Jean-Pierre Tillich, N.Nicolas Sendrier and P. S.Paulo S. L. M. Barreto. MDPC-McEliece: New McEliece Variants from Moderate Density Parity-Check Codes.IEEE International Symposium on Information Theory - ISIT 2013Istanbul, TurkeyJuly 2013, 2069-2073
  HAL
• 13 articleL.Léo Perrin. Partitions in the S-Box of Streebog and Kuznyechik.IACR Transactions on Symmetric Cryptology20191March 2019, 302-329
  HALDOI

12.2 Publications of the year

12.3 Cited publications

• 71 inproceedingsG.Gorjan Alagic and A.Alexander Russell. Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts.Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part III10212Lecture Notes in Computer Science2017, 65--93URL: https://doi.org/10.1007/978-3-319-56617-7_3
  DOIback to text
• 72 inproceedingsM.Magali Bardet, P.Pierre Briaud, M.Maxime Bros, P.Philippe Gaborit, V.Vincent Neiger, O.Olivier Ruatta and J.-P.Jean-Pierre Tillich. An Algebraic Attack on Rank Metric Code-Based Cryptosystems.EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques12107Lecture Notes in Computer ScienceZagreb / Virtual, CroatiaSpringerMay 2020, 64--93
  HALDOIback to text
• 73 inproceedingsM.Magali Bardet, M.Maxime Bros, D.Daniel Cabarcas, P.Philippe Gaborit, R.Ray Perlner, D.Daniel Smith-Tone, J.-P.Jean-Pierre Tillich and J.Javier Verbel. Improvements of Algebraic Attacks for Solving the Rank Decoding and MinRank Problems.ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security12491Lecture Notes in Computer ScienceDaejeon / Virtual, South KoreaSpringerDecember 2020, 507--536
  HALDOIback to text
• 74 inproceedingsD. J.Daniel J. Bernstein. The Poly1305-AES Message-Authentication Code.Fast Software Encryption: 12th International Workshop, FSE 2005, Paris, France, February 21-23, 2005, Revised Selected Papers3557Lecture Notes in Computer ScienceSpringer2005, 32--49URL: https://doi.org/10.1007/11502760_3
  DOIback to text
• 75 unpublishedX.Xavier Bonnetain, A.Anne Canteaut, V.Véronique Cortier, P.Pierrick Gaudry, L.Lucca Hirschi, S.Steve Kremer, S.Stéphanie Lacour, M.Matthieu Lequesne, G.Gaëtan Leurent, L.Léo Perrin, A.André Schrottenloher, E.Emmanuel Thomé, S.Serge Vaudenay and C.Christophe Vuillot. Le traçage anonyme, dangereux oxymore.April 2020, working paper or preprint
  HALback to textback to textback to text
• 76 inproceedingsX.Xavier Bonnetain. Quantum Key-Recovery on full AEZ. SAC 2017 - Selected Areas in CryptographyOttawa, CanadaAugust 2017
  HALback to text
• 77 inproceedingsA.Alain Couvreur, M.Matthieu Lequesne and J.-P.Jean-Pierre Tillich. Recovering short secret keys of RLCE encryption scheme in polynomial time.PQCrypto 2019 - International Conference on Post-Quantum CryptographyChongqing, ChinaMay 2019
  HALDOIback to text
• 78 phdthesisT.Thomas Debris-Alazard. Cryptographie fondée sur les codes : nouvelles approches pour constructions et preuves ; contribution en cryptanalyse.Sorbonne UniversitéDecember 2019
  HALback to text
• 79 inproceedingsT.Thomas Debris-Alazard and J.-P.Jean-Pierre Tillich. Two attacks on rank metric code-based schemes: RankSign and an IBE scheme.ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security11272LNCS - Lecture Notes in Computer ScienceBrisbane, AustraliaSpringerDecember 2018, 62-92
  HALDOIback to text
• 80 articleG.Greg Kuperberg. A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem.SIAM J. Comput.3512005, 170--188URL: https://doi.org/10.1137/S0097539703436345
  DOIback to text
• 81 inproceedingsH.Hidenori Kuwakado and M.Masakatu Morii. Security on the quantum-type Even-Mansour cipher.Proceedings of the International Symposium on Information Theory and its Applications, ISITA 2012, Honolulu, HI, USA, October 28-31, 2012IEEE2012, 312--316URL: http://ieeexplore.ieee.org/document/6400943/
  back to text
• 82 inproceedingsM.Matthieu Lequesne and J.-P.Jean-Pierre Tillich. Attack on the Edon-K Key Encapsulation Mechanism.ISIT 2018 - IEEE International Symposium on Information TheoryVail, United StatesJune 2018, 981-985
  HALDOIback to text
• 83 inproceedingsD. R.Daniel R. Simon. On the Power of Quantum Computation.35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994IEEE Computer Society1994, 116--123URL: https://doi.org/10.1109/SFCS.1994.365701
  DOIback to text