2024-07-02
11:00
Salle 2
Bruno Sterner (INRIA GRACE)
Finding large smooth twins
We discuss the computational problem of finding pairs of consecutive smooth integers, also known as smooth twins. Such twins have had some relevance in isogeny-based cryptography and reducing the smoothness bound of these twins aids the performance of these cryptosystems. However searching for such twins with a small smoothness bound is the most challenging aspect of this problem especially since the set of smooth twins with a fixed smoothness bound is finite. This talk presents new large smooth twins which have a smaller smoothness bound compared to twins found with prior approaches.
2024-06-25
11:00
Salle 2
SQIsign verification in higher dimensions
SQIsign is an isogeny-based signature scheme in Round 1 of NIST’s recent alternate call for signature schemes. In this talk, we will take a closer look at SQIsign verification and demonstrate that it can be performed completely on Kummer surfaces. In this way, one-dimensional SQIsign verification can be viewed as a two-dimensional isogeny between products of elliptic curves. Curiously, the isogeny is then defined over Fp rather than Fp2. Furthermore, we will introduce new techniques that enable verification for compression signatures using Kummer surfaces, in turn creating a toolbox for isogeny-based cryptography in dimension 2.This is based on joint work with Krijn Reijnders.
2024-06-18
11:00
Salle 2
Massey products and class field towers
I will present recent joint work with Magnus Carlson, where we provide formulas for 3-fold Massey products in the étale cohomology of the ring of integers of a number field. Using these formulas, we identify the first known examples of imaginary quadratic fields with a class group of p-rank 2 possessing an infinite p-class field tower, where p is an odd prime. Furthermore, we establish a necessary and sufficient condition, in terms of class groups of p-extensions, for the vanishing of 3-fold Massey products. As a consequence, we offer an elementary and sufficient condition for the infinitude of class field towers of imaginary quadratic fields. Additionally, we disprove McLeman’s (3,3)-conjecture.
2024-06-11
11:00
Salle 2
Isomorphism classes of polarised abelian varieties and Drinfeld modules over finite fields
We will discuss computable descriptions of isomorphism classes in a fixed isogeny class of both polarised abelian varieties over finite fields (joint work with Bergström-Marseglia) and Drinfeld modules over finite fields (joint work with Katen-Papikian). More precisely, in the first part of the talk we will describe all polarisations of all abelian varieties over a finite field in a fixed isogeny class corresponding to a squarefree Weil polynomial, when one variety in the isogeny class admits a canonical lifting to characteristic zero. The computability of the description relies on applying categorical equivalences, due to Deligne and Centeleghe-Stix, between abelian varieties over finite fields and fractional ideals in étale algebras. In the second part, we will use an action of fractional ideals, inspired by work of Hayes, to compute isomorphism classes of Drinfeld modules. As a first step and a problem of independent interest, we prove that an isogeny class contains a Drinfeld module whose endomorphism ring is minimal if and only if the class is either ordinary or defined over the prime field. We obtain full descriptions in these cases, that can be compared to the Drinfeld analogues of those of Deligne and Centeleghe-Stix, respectively.
2024-06-04
11:00
Salle 2
SDP hierarchies for distance-avoiding sets on compact spaces
Witsenhausen's problem asks for the maximum fraction α_n of the n-dimensional unit sphere that can be covered by a measurable set containing no pairs of orthogonal points. We extended well known optimization hierarchies based on the Lovász theta number, like the Lasserre hierarchy, to Witsenhausen's problem and similar problems. We then showed that these hierarchies converge to α_n, and used them to compute the best upper bounds known for α_n in low dimensions.
2024-05-28
11:00
Salle 2
Algorithms for Gröbner bases change of order
Gröbner bases lie at the forefront of the algorithmic treatment of polynomial systems and ideals in symbolic computation. They are defined as special generating sets of polynomial ideals which allow to decide the ideal membership problem via a multivariate version of polynomial long division. Given a Gröbner basis for a polynomial ideal, a lot of geometric and algebraic information about the polynomial ideal at hand can be extracted, such as the degree, dimension or Hilbert function. Notably, Gröbner bases depend on two parameters: The polynomial ideal which they generate and a monomial order, i.e. a certain kind of total order on the set of monomials of the underlying polynomial ring. Then, the geometric and ideal-theoretic information that can be extracted from a Gröbner basis depends on the chosen monomial order. In particular, the lexicographic one allows us to solve a polynomial system. Such a lexicographic Gröbner basis is usually computed through a change of order algorithm, for instance the seminal FGLM algorithm. In this talk, I will present progress made to change of order algorithms: faster variants in the generic case, complexity estimates for system of critical values, computation of colon ideals or of generic fibers. This is based on different joint works with A. Bostan, Ch. Eder, A. Ferguson, R. Mohr, V. Neiger and M. Safey El Din.
2024-05-14
11:00
Salle 2
Bielliptic Shimura curves X_0^D(N) with nontrivial level
In this talk, I explain how we work towards completely classifying all bielliptic Shimura curves X_0^D(N) with nontrivial level N, extending a result of Rotger that provided such a classification for level 1. This allows us to determine the list of all pairs (D,N) for which X_0^D(N) has infinitely many degree 2 points, up to three explicit possible exceptions. This is joint work with Frederick Saia.
2024-05-07
11:00
Salle 2
From entanglement detection to trace polynomials
We will make a tour of related concepts whose motivation lies in quantum information theory. We consider the detection of entanglement in unitarily-invariant states, a class of positive (but not completely positive) multilinear maps, and the construction of tensor polynomial identities. The results are established through the use of commutative and noncommutative Positivstellensätze and the representation theory of the symmetric group.
2024-04-30
11:00
Salle 2
Lars Ran (Radboud University)
Analysing multi-graded polynomial systems; a step towards more precise security estimations
Generally, polynomial systems that arise in algebraic cryptanalysis have extra structure compared to generic systems, which comes from the algebraic modelling of the cryptographic scheme. Sometimes, part of this extra structure can be caught with polynomial rings with non-standard grading. For example, in the Kipnis-Shamir modelling of MinRank one considers the system over a bi-graded polynomial ring instead. This allows for better approximations of the solving degree of such systems when using Gröbner basis algorithms.
In this talk, I will present ongoing work in which this idea is extended to multi-graded polynomial rings. Furthermore, I will show how we can use this grading to tailor existing algorithms to use this structure and speed up computation.
2024-04-16
11:00
Salle 2
Computing Class Groups With an Inductive Algorithm
In this talk, first, I will present a method by Biasse, Fieker, Hofman and Page to compute the class group of some number fields inductively. This method uses the properties of norm relations, which are some relations in R[G] where R is a commutative ring and G a finite group. Then, I will discuss about how we can generalise the notion of norm relations and use this new kind of relations to obtain a similar method for computing class groups, that is more effective than the previous one.
2024-04-09
11:00
Salle 2
Asymptotics and Improvements of Sieving for Codes
In 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-02
11:00
Salle 2
Dmitrii Koshelev (Ethereum Foundation)
Generation of "independent" points on elliptic curves by means of Mordell-Weil lattices
This 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-26
11:00
Salle 2
Bastien Pacifico (LIRMM, Université de Montpellier)
From Chudnovsky-type algorithms to locally recoverable codes
Chudnovsky'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-19
11:00
Salle 2
A new approach based on quadratic forms to attack the McEliece cryptosystem
In 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-12
11:00
Salle 2
Polynômes linéarisés et cryptographie en métrique rang
Le 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-05
11:00
Salle 2
Skolem meets Schanuel
A 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-27
11:00
Salle 2
Variants of the Decoding Problem and algebraic cryptanalysis
The 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-20
11:00
Salle 2
Discussion autour du Générateur Sac à dos
Le 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-13
11:00
Salle 2
Approx-SVP in multiquadratic ideal lattices
Multiquadratic 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-07
15:00
Salle 2
The IEEE 1788-2015 standard for interval arithmetic: introduction, tests for compliance, revision
During 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-06
11:00
Salle 2
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-30
11:00
Salle 2
Algorithmic aspects of isogeny-based cryptography
One 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-23
11:00
Salle 2
Faster modular composition of polynomials
This 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-16
11:00
Salle 2
Effective aspects of Riemann-Roch spaces in the Hilbert class field
Let 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-19
11:00
Salle 2
Pairings, class groups, and how (not) to break isogeny-based cryptography
Maps 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-12
11:00
Salle 2
Computing 2-isogenies between Kummer lines
One 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-05
11:00
Salle 2
Yining Hu (Harbin Institute of Technology)
Automatic algebraic continued fractions in characteristic 2
In 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-28
11:00
Salle 2
Disorientation faults in CSIDH
In 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-21
11:00
Salle 2
Galois representations attached to elliptic curves and Serre's uniformity question
The 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-14
11:00
Salle 2
Computing isomorphism classes and polarisations of abelian varieties over finite fields
We 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-07
11:00
Salle 2
Pseudorandom Correlation Generators from the Hardness of Decoding Codes over Group Algebras
The 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-24
11:00
Salle 2
Donghyeok Lim (Yonsei University, Korea)
On the Galois structure of units of totally real p-rational fields
The 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-10
11:00
Salle 2
Wouter Rozendaal (IMB)
A Renormalisation Decoder for Kitaev's Toric Quantum Code
Kitaev'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-03
11:00
Salle 2
An Algebraic Point of View on the Generation of Pairing-Friendly Elliptic Curves
In 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-26
11:00
Salle 2
Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals
The 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-19
11:00
Salle 2
Drinfeld modules in SageMath
In 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-12
11:00
Salle 2
SQISignHD : Signing with higher dimensional isogenies
The 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.
