# 2023/2024

- 2024-04-0911:00Salle 2Simona Etinski (CWI)Asymptotics and Improvements of Sieving for CodesIn this talk, I am going to present a joint work with Léo Ducas, Andre Esser, and Elena Kirshanova on sieving for codes. In this work, we provide an asymptotic analysis of the sieving for codes originally introduced in the paper by Guo, Johansson, and Nguyen (Eprint’23), after which we rely on a well-established lattice-based NNS machinery, known as Locality Sensitive Hashing and Filtering (LSH/F), to obtain a more systematic analysis of the sieving for codes. We thus introduce a baseline for the sieving approach for codes with a decoding complexity of 2^0.117n for the conventional worst parameters (full distance decoding, where complexity is maximized over all code rates). Our cumulative improvements eventually enable us to lower the hardest parameter decoding complexity for SievingISD algorithms to 2^0.101n. This approach outperforms the BJMM algorithm (Eurocrypt’12) but falls behind the most advanced conventional ISD approach by Both and May (PQCrypto’18). As in the case of lattices, we found that the Random-Spherical-Code-Product (RPC) gives the best asymptotic complexity. Moreover, we consider an alternative that seems specific to the Hamming Sphere, which we believe could be of practical interest as it plausibly hides less sub-exponential overheads than RPC. For more details, refer to the full version of the paper given at https://eprint.iacr.org/2023/1577.
- 2024-04-0211:00Salle 2Dmitrii Koshelev (Ethereum Foundation)Generation of "independent" points on elliptic curves by means of Mordell-Weil latticesThis talk is devoted to a novel method of generating "independent" points on an ordinary elliptic curve over a finite field of large characteristic. Such points are actively used, e.g., in the Pedersen vector commitment scheme and its modifications. The conventional generation consists in sampling points successively via a hash function to the elliptic curve. The new generation method equally satisfies the NUMS (Nothing Up My Sleeve) principle, but it works faster on average. In other words, instead of finding each point separately, it is suggested to sample several points at once with a non-small success probability. This means that in practice the new method finishes in polynomial time, unless one is mysteriously unlucky. More precisely, some explicit formulas participate in deriving up to four "independent" points on any curve of j-invariant 0. Such curves are known to be very popular in elliptic curve cryptography.
- 2024-03-2611:00Salle 2Bastien Pacifico (LIRMM, Université de Montpellier)From Chudnovsky-type algorithms to locally recoverable codesChudnovsky's method makes it possible to construct multiplication algorithms in finite fields with good bilinear complexity, i.e. a small number of bilinear multiplications in the base field. However, their total complexity and the difficulty of efficiently constructing these algorithms are unfavorable. Historically, these are evaluation/interpolation algorithms using rational points of algebraic curves/rational places of function fields. Using asymptotically optimal towers, the existence of algorithms with bilinear complexity that is linear in the degree of extension has been proven. But these algorithms are not constructible in polynomial time. Another approach is a recursive construction using places of increasing degrees. It provides algorithms with a quasi-linear bilinear complexity, but constructible in polynomial time. We will introduce a hybrid construction, taking the best of both strategies to obtain algorithms with linear bilinear complexity that can be constructed in polynomial time. Secondly, we will see that some locally recoverable codes, where the recovery of a corrupted symbol is possible using a small amount of other symbols, appear naturally in the recursive construction of Chudnovsky-type algorithms. We will define and study these codes.
- 2024-03-1911:00Salle 2Rocco Mora (CISPA)A new approach based on quadratic forms to attack the McEliece cryptosystemIn this talk, I will present a novel algebraic approach for attacking the McEliece cryptosystem which is currently at the 4-th round of the NIST post-quantum standardization process. The contributions are twofold. (1) A new distinguisher on alternant and Goppa codes working in a much broader range of parameters than previous distinguishers is introduced and its complexity analysed; (2) With this approach, a polynomial-time key recovery attack on alternant and Goppa codes of high-rate and under some conditions on their field size and degree is also provided.
- 2024-03-1211:00Salle 2Olivier Ruatta (Université de Limoges)Polynômes linéarisés et cryptographie en métrique rangLe lien entre polynômes linéarisés et codes en métrique rang est connu depuis longtemps puisque les codes de Gabidulin peuvent être vu comme codes d’évaluation de certains de ces polynômes. Nous donnerons d’autres constructions et verrons comment la “géométrisation” des corps finis grâce aux polynômes linéarisés permet de fournir des problèmes qui pourraient être appliqués dans des contextes cryptographiques.
- 2024-03-0511:00Salle 2Yuri Bilu (IMB)Skolem meets SchanuelA linear recurrence of order r over a number field K is a map U:Z→K satisfying a relation of the form U(n+r)=a_{r−1}U(n)+⋯+a_0U(n)(n∈Z), where a_0,…,a_{r−1}∈K and a_0≠0. A linear recurrence is called simple if the characteristic polynomial X^r−a_{r−1}X^{r−1}−…−a_0 has only simple roots, and non-degenerate if λ/λ′ is not a root of unity for any two distinct roots λ,λ′ of the characteristic polynomial. The classical Theorem of Skolem-Mahler-Lech asserts that a non-degenerate linear recurrence may have at most finitely many zeros. However, all known proofs of this theorem are non-effective and do not produce any tool to determine the zeros. In this talk I will describe a simple algorithm that, when terminates, produces the rigorously certified list of zeros of a given simple linear recurrence. This algorithm always terminates subject to two celebrated conjectures: the p-adic Schanuel Conjecture, and the Exponential Local-Global Principle. We do not give any running time bound (even conditional to some conjectures), but the algorithm performs well in practice, and was implemented in the Skolem tool https://skolem.mpi-sws.org/ that I will demonstrate. This is a joint work with Florian Luca, Joris Nieuwveld, Joël Ouaknine, David Purser and James Worrell.
- 2024-02-2711:00Salle 2Pierre Briaud (Simula UiB)Variants of the Decoding Problem and algebraic cryptanalysisThe intractability of decoding generic linear codes is at the core of an important branch of post-quantum cryptography. In this context, the code is random by design or it is assumed to be so in the security reduction. This talk will focus on versions of the Decoding Problem where the error vector is structured, in general to achieve better performance. While combinatorial techniques such as Information Set Decoding are often the method of choice to attack these versions, I will describe the potential of algebraic algorithms. I will mostly consider the Regular Syndrome Decoding Problem and a paper presented at Eurocrypt 2023. I will also mention ongoing work on an assumption used in the CROSS submission to new call for signature schemes launched by NIST.
- 2024-02-2011:00Salle 2Fleurette Martinez (LIP6, Paris)Discussion autour du Générateur Sac à dosLe Générateur Sac à dos, proposé en 1985 par Rueppel et Massey, est un générateur pseudo-aléatoire (PRNG) qui combine un premier PRNG faible, le LFSR, et un problème dur, le problème de la somme de sous-ensemble, dérivé du problème du sac à dos. Ce générateur a été attaqué avec succès par Knellwolf et Meyer en 2011. Je discuterai ici d'une variante plus efficace de cette attaque et des différentes attaques que j'ai pu proposer avec Damien Vergnaud et Charles contre des variantes de ce générateur.
- 2024-02-1311:00Salle 2Semyon Novoselov (University of Kaliningrad)Approx-SVP in multiquadratic ideal latticesMultiquadratic fields are exceptional objects in computational number theory. Many hard computational problems are significantly simpler there. This includes unit/class group and discrete logarithm computations, as well as computing short generators of principal ideals. However, there are still many open questions in the area. In this talk, I describe recent progress towards the next milestone – the approximate shortest vector problem in non-principal ideal lattices. In particular, I present an algorithm for a central subroutine – the discrete logarithm computation based on reduction of the problem to subfields.
- 2024-02-0715:00Salle 2Nathalie Revol (Télécom Paris)The IEEE 1788-2015 standard for interval arithmetic: introduction, tests for compliance, revisionDuring this talk, I will focus on interval arithmetic, and more specifically on IEEE 1788-2015, the standard for interval arithmetic. After introducing the most prominent features of the standard, I will discuss what needs to be tested to increase our confidence in a library that implements interval arithmetic, insisting on IEEE 1788-2015 requirements. As this standard, adopted in 2015, approaches its 10th birthday, it is time to revise it: I will suggest two main directions for clarification and modification.Comments and suggestions will be welcome, as they will be useful for testing issues and for the revision of the standard.
- 2024-02-0611:00Salle 2Christophe Levrat (Télécom Paris)l-adic point counting on surfaces: nearly almost halfway there?While point counting algorithms on algebraic curves over finite fields have been around for decades and seen considerable progress in the meantime, the question of counting points on algebraic surfaces without additional structure seems much more challenging. In this talk, we will present results concerning the classical l-adic method for surfaces fibered over the projective line, which was conjectured by Edixhoven and Couveignes to admit a polynomial-time complexity. This method boils down to computing the étale cohomology of a constructible sheaf: we will describe how to compute this cohomology once such a sheaf has been given, and outline a possible strategy that might allow to compute a usable description of this particular sheaf.
- 2024-01-3011:00Salle 2Thomas Decru (KU Leuven)Algorithmic aspects of isogeny-based cryptographyOne of the main struggles of isogeny-based cryptographic protocols is that they are still relatively slow compared to other post-quantum candidate schemes. In this talk we will provide some info on why this is, and elaborate on some of the recent results and ongoing work in this direction.
- 2024-01-2311:00Salle 2Vincent Neiger (Sorbonne Université)Faster modular composition of polynomialsThis talk is about algorithms for modular composition of univariate polynomials, and for computing minimal polynomials. For two univariate polynomials a and g over a commutative field, modular composition asks to compute h(a) mod g for some given h, while the minimal polynomial problem is to compute h of minimal degree such that h(a) = 0 mod g. We propose algorithms whose complexity bound improves upon previous algorithms and in particular upon Brent and Kung's approach (1978); the new complexity bound is subquadratic in the degree of g and a even when using cubic-time matrix multiplication. Our improvement comes from the fast computation of specific bases of bivariate ideals, and from efficient operations with these bases thanks to fast univariate polynomial matrix algorithms. We will also report on experimental results using the Polynomial Matrix Library. Contains joint work with Seung Gyu Hyun, Bruno Salvy, Eric Schost, Gilles Villard.
- 2024-01-1611:00Salle 2Jean-Marc Couveignes (CANARI)Effective aspects of Riemann-Roch spaces in the Hilbert class fieldLet K be a finite field, X and Y two curves over K, and Y→X an unramified abelian cover with Galois group G. Let D be a divisor on X and E its pullback on Y. Under mild conditions the linear space associated with E is a free K[G]-module. We study the algorithmic aspects and applications of these modules.
- 2023-12-1911:00Salle 2Marc Houben (Leiden University)Pairings, class groups, and how (not) to break isogeny-based cryptographyMaps between elliptic curves, also called isogenies, are fixed once the image on sufficiently many points is known. Last year, a method was discovered that computationally recovers isogenies just by knowing information about their image points, leading to the break of the key-exchange scheme SIDH. Isogeny-based key-exchange proposals relying on class group actions, such as CSIDH, remain unaffected, because such image information is not directly available. Using the theory of pairings on elliptic curves, we show that sometimes one may recover such information anyway, and classify when this approach results in a key-recovery attack.
- 2023-12-1211:00Salle 2Nicolas Sarkis (CANARI)Computing 2-isogenies between Kummer linesOne of the best arithmetics on elliptic curves involves Montgomery xz-coordinates, which are used in several cryptographic protocols such as ECDSA or ECDH. These coordinates also offer fast computations of 2- and 4-isogenies, used in several protocols like it was the case with SIDH, both for doubling and images of points, so improving isogeny formulas also improves scalar products on an elliptic curve. We realized there was a more general theory of Kummer lines under which xz-coordinates fall. In this talk, we will describe the general framework of Kummer lines, based on two families of examples: Montgomery xz-coordinates and theta models. We will then explain how to find 2-isogeny formulas, whether they were already known or new, and how we mixed them to improve elliptic curve arithmetic.
- 2023-12-0511:00Salle 2Yining Hu (Harbin Institute of Technology)Automatic algebraic continued fractions in characteristic 2In this talk I will first introduce automatic sequences and their link with algebraicity. Then I will present two families of automatic algebraic continued fractions in characteristic 2.
- 2023-11-2811:00Salle 2Monika Trimoska (Eindhoven University of Technology)Disorientation faults in CSIDHIn this work, we investigate a new class of fault-injection attacks against the CSIDH family of cryptographic group actions. Our disorientation attacks effectively flip the direction of some isogeny steps, resulting in an incorrect output curve. The placement of the disorientation fault during the algorithm influences the distribution of the output curve in a key-dependent manner. We explain how an attacker can post-process a set of faulty outputs to fully recover the private key. We provide full details for attacking the original CSIDH proof-of-concept software as well as the CTIDH constant-time implementation. Finally, we present a set of lightweight countermeasures against the attack and discuss their security. This presentation will focus on analysing the graph of faulty curves formed in the post-processing stage and getting an intuition on how it can be used to infer constraints on the secret key. This is joint work with Gustavo Banegas, Juliane Krämer, Tanja Lange, Michael Meyer, Lorenz Panny, Krijn Reijnders and Jana Sotáková.
- 2023-11-2111:00Salle 2Lorenzo Furio (Università di Pisa)Galois representations attached to elliptic curves and Serre's uniformity questionThe study of Galois representations attached to elliptic curves is a very fruitful branch of number theory, which led to the solution of very tough problems, such as Fermat's Last Theorem. Given a rational elliptic curve E, the representation \rho_{E,p} is described by the action of the absolute Galois group of \mathbb{Q} on the p-torsion points of E. In 1972 Serre proved that for every rational elliptic curve E without CM there is a constant N_E such that, for every prime p>N_E, the Galois representation \rho_{E,p} is surjective. In the same article, he asked whether the constant N_E is independent of the curve, and this became known as Serre's Uniformity Question. In this talk, I will discuss the current progress towards the answer to this question, in particular the Runge method for modular curves, developed by Bilu and Parent, and the recent improvements obtained via this method by Le Fourn–Lemos and Lombardo and the speaker.
- 2023-11-1411:00Salle 2Stefano Marseglia (Utrecht University)Computing isomorphism classes and polarisations of abelian varieties over finite fieldsWe consider abelian varieties over a finite field which are ordinary, or over a prime field, and which have commutative endomorphism algebra. Works of Deligne and Centeleghe-Stix allow us to describe these abelian varieties in terms of fractional ideals of an order in an étale algebra. I will explain how such descriptions can be exploited to explictly compute the abelian varieties up to isomorphism. Moreover, results by Howe give us a way to compute principal polarisations of the abelian varieties in the ordinary case. In a joint work with Bergström and Karemaker we extend these results to the prime field case.
- 2023-11-0711:00Salle 2Maxime Bombar (CWI)Pseudorandom Correlation Generators from the Hardness of Decoding Codes over Group AlgebrasThe main bottleneck of secure multiparty computation is the cost of the communication between all the parties. Nevertheless, it is known for a long time that if prior to the actual MPC protocol, all the parties share random field elements having a useful correlation such as random multiplication triples, or the so-called random Oblivious Linear Evaluations (OLE's), the parties can engage in a very efficient protocol. The goal is therefore to generate this large amount of correlated randomness. To achieve this goal, Boyle et al. recently introduced a new tool which they called "Pseudorandom Correlation Generators" (PCG's) and demonstrated how it can be used to generate and distribute a large amount of (pseudo)random OLE's to two parties, using minimal interactions, followed solely by local computations. This enables secure two-party computation with "silent preprocessing" which can be extended to N-party using "programmable" PCG's. Previous constructions of programmable PCG's for OLE's suffer from two downsides: (1) They only generate OLE's over large fields, and (2) They rely on a rather recent "splittable Ring-LPN" assumption which lacks from strong security foundations. In this talk, I will present a way to overcome both limitation by introducing the "Quasi-Abelian Decoding Problem" which generalises the well-known decoding problem of quasi-cyclic codes, and show how its hardness allows to build programmable PCG's for the OLE correlation over any field Fq (with q>2). Finally, if time permits, I will evoke some ideas towards the q=2 case, which involves some elements from the theory of Carlitz modules over F2(T). This is based on a joint work with Geoffroy Couteau, Alain Couvreur and Clément Ducros.
- 2023-10-2411:00Salle 2Donghyeok Lim (Yonsei University, Korea)On the Galois structure of units of totally real p-rational fieldsThe Galois module structure of algebraic units is fundamental in number theory. However, its investigation is difficult because we need to understand arithmetic of number fields, and the integral representations of finite groups are difficult to classify. A number field is called p-rational if the Galois group of the maximal pro-p p-ramified extension is free pro-p. The p-rationality is known to be a condition that reduces the complexities in problems in number theory. In this talk, we explain our results on the implication of the existing theories on integral representations of finite groups (factor equivalence, regulator constant, Yakovlev diagram) on the algebraic units of totally real p-rational fields. This talk is based on the joint works with Z. Bouazzaoui, D. Burns, A. Kumon, and C. Maire.
- 2023-10-1011:00Salle 2Wouter Rozendaal (IMB)A Renormalisation Decoder for Kitaev's Toric Quantum CodeKitaev's toric code is expected to be at the core of the first generation of quantum computers that will incorporate error protection. To make full use of the toric code, one requires an efficient decoding scheme that will process the classical information obtained from quantum syndrome measurements, so as to be able to regularly put arrays of qubits back into their intended states. The renormalisation decoders introduced by Duclos-Cianci and Poulin exhibit one of the best trade-offs between efficiency and speed. One feature that remained a mystery however, is their behaviour over adversarial channels, i.e. their worst-case behaviour. In this talk, we introduce a relatively natural and deterministic version of a renormalisation decoder and bound its error-correcting radius.
- 2023-10-0311:00Salle 2Jean Gasnier (CANARI)An Algebraic Point of View on the Generation of Pairing-Friendly Elliptic CurvesIn 2010, Freeman, Scott, and Teske published a well-known taxonomy compiling the best known families of pairing-friendly elliptic curves. Since then, the research effort mostly shifted from the generation of pairing-friendly curves to the improvement of algorithms or the assessment of security parameters to resist the latest attacks on the discrete logarithm problem. Consequently, very few new families were discovered. However, the need of pairing-friendly curves of prime order in some new applications such as SNARKs has reignited the interest in the generation of pairing-friendly curves, with hope of finding families similar to the one discovered by Barreto and Naehrig. Building on the work of Kachisa, Schaefer, and Scott, we show that some elements of extensions of a cyclotomic field have a higher probability of generating a family of pairing-friendly curves. We present a general framework which embraces the KSS families and many of the other families in the taxonomy paper. We finally introduce a new family with embedding degree k=20 which we estimate to provide a faster Miller loop compared to KSS16 and KSS18 at the 192-bit security level.
- 2023-09-2611:00Salle 2Joël Felderhoff (ARIC and ENS Lyon)Ideal-SVP is Hard for Small-Norm Uniform Prime IdealsThe presumed hardness of the Shortest Vector Problem for ideal lattices (Ideal-SVP) has been a fruitful assumption to understand other assumptions on algebraic lattices and as a security foundation of cryptosystems. Gentry [CRYPTO’10] proved that Ideal-SVP enjoys a worst-case to average-case reduction, where the average-case distribution is the uniform distribution over the set of inverses of prime ideals of small algebraic norm (below d^O(d) for cyclotomic fields, where d refers to the field degree). De Boer et al. [CRYPTO’20] btained another random self-reducibility result for an average-case distribution involving integral ideals of norm 2^O(d^2). In this work, we show that Ideal-SVP for the uniform distribution over inverses of small-norm prime ideals reduces to Ideal-SVP for the uniform distribution over small-norm prime ideals. Combined with Gentry’s reduction, this leads to a worst-case to average-case reduction for the uniform distribution over the set of small-norm prime ideals. Using the reduction from Pellet-Mary and Stehlé [ASIACRYPT’21], this notably leads to the first distribution over NTRU instances with a polynomial modulus whose hardness is supported by a worst-case lattice problem.
- 2023-09-1911:00Salle 2Xavier Caruso (CANARI)Drinfeld modules in SageMathIn this talk, I will briefly introduce Drinfeld modules which, in some sense, appears as a arithmetically meaningful analogue of elliptic curves in the context of function fields. I will then discuss an implementation of Drinfeld modules which was recently included in SageMath. (Joint work with David Ayotte, Antoine Leudière and Joseph Musleh.)
- 2023-09-1211:00Salle 2Pierrick Dartois (CANARI)SQISignHD : Signing with higher dimensional isogeniesThe SQISign isogeny-based post-quantum digital signature scheme introduced by De Feo, Kohel, Leroux, Petit and Wesolowski outputs very compact signatures at the expense of a high signature time. In this presentation, we recall how SQISign works and introduce a new scheme based on SQISign and the polynomial time torsion point attacks against SIDH due to Castryck, Decru, Maino, Martindale and Robert to sign with higher dimensional isogenies. This scheme remains to be implemented but we expect a significant signature time improvement, better security properties and signatures even more compact than in the original SQISign scheme.