Séminaire de Théorie Algorithmique des Nombres

Responsables : Razvan Barbulescu et Wessel Van Woerden

Le 17 janvier 2023 à 10:00

Wouter Castryck -

Radical isogeny formulas

In several applications one is interested in a fast computation of the codomain curve of a long chain of cyclic $N$-isogenies emanating from an elliptic curve E over a finite field $\mathbb F_q$, where $N = 2, 3, \ldots$ is some small fixed integer coprime to $q$. The standard approach proceeds by finding a generator of the kernel of the first $N$-isogeny, computing its codomain via Vélu's formulas, then finding a generator of the kernel of the second $N$-isogeny, and so on. Finding these kernel generators is often the main bottleneck.In this talk I will explain a new approach to this problem, which was studied in joint work with Thomas Decru, Marc Houben and Frederik Vercauteren. We argue that Vélu's formulas can be augmented with explicit formulas for the coordinates of a generator of the kernel of an $N$-isogeny cyclically extending the previous isogeny. These formulas involve the extraction of an $N$-th root, therefore we call them "radical isogeny formulas". By varying which $N$-th root was chosen (i.e., by scaling the radical with different $N$-th roots of unity) one obtains the kernels of all possible such extensions. Asymptotically, in our main cases of interest this gives a speed-up by a factor 6 or 7 over previous methods.I will explain the existence of radical isogeny formulas, discuss methods to find them (the formulas become increasingly complicated for larger N), and pose some open questions.

Le 24 janvier 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

Razvan Barbulescu CNRS/IMB

The particular case of cyclotomic fields whencomputing unit groups by quantum algorithms

The computation of unit and class groups in arbitrary degree number field is done in polynomial time in a similar fashion to the Shor's factoring algorithm. Contrary to the fixed degree case which was solved in 2001 by Hallgren and a follow-up paper of Schmidt and Vollmer (2005), the arbitrary degree case requires errors estimations and is solved by the conjunction of two papers, Eisenträger et al. (2014) and de Boer et al. (2020).In the particular case of cyclotomic fields we propose a version of the algorithm which makes use of cyclotomic units. Indeed, the Shor-like procedure of Eisenträger et al.'s algorithm produces random approximations of vectors in the dual of the lattice of units. In order to guarantee the correction of the algorithm, they have to do the computations in high precision and hence require a large amount of qubits. Thanks to the lattice of cyclotomic units, one can do the computations in smaller precision and reduce the number of qubits.

Le 31 janvier 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

Wessel van Woerden IMB

An Algorithmic Reduction Theory for Binary Codes, LLL and more

We will discuss an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as the Nearest Plane Algorithm of Babai (1986). Interestingly, the adaptation of LLL to binary codes can be interpreted as an algorithmic version of the bound of Griesmer (1960) on the minimal distance of a code.

Le 7 février 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

Andrea Lesavourey Irisa

Calcul de racines de polynômes dans un corps de nombres

Computing roots of elements is an important step when solving various tasks in computational number theory. It arises for example during the final step of the General Number Field Sieve~(Lenstra et al. 1993). This problem also intervenes during saturation processes while computing the class group or $S$-units of a number field (Biasse and Fieker). It is known from the seminal paper introducing the LLL algorithm that one can recover elements of a given number field $K$ given approximations of one of their complex embeddings. This can be used to compute roots of polynomials. In the first part of this presentation, I will describe an extension of this approach that take advantage of a potential subfield $k$, which replace the decoding of one element of $K$ by the decoding $[K:k]$ elements of $k$, to the cost of search in a set of cardinality $d^{[K:k]}$ where $d$ is the degree of the targetted polynomial equation. We will also describe heuristic observations that are useful to speed-up computations.In the second part of the presentation, we will describe methods to compute $e$-th roots specifically. When $K$ and $e$ are such that there are infinitely many prime integers $p$ such that $\forall mathfrak{p} \mid p, p^{f(\mathfrak{p}\mid p)} ot equiv1 \pmod e$, we reconstruct $x$ from $x \pmod {p_1}, dots, x \pmod {p_r} $ using a generalisation of Thomé's work on square-roots in the context of the NFS~(Thomé). When this good condition on $K$ and $n$ is not satisfied, one can adapt Couveignes' approach for square roots (Couveignes) to relative extensions of number fields $K/k$ provided $[K:k]$ is coprime to $e$ and infinitely many prime integers $p$ are such that each prime ideal $\mathfrak{p}$ of $\mathcal{O}_k$ above $p$ is inert in $K$.

Le 14 février 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

Maxime Plançon IBM Zürich

Exploiting algebraic structure in probing security

The so-called $\omega$-encoding, introduced by Goudarzi, Joux and Rivain (Asiacrypt 2018), generalizes the commonly used arithmetic encoding. By using the additionnal structure of this encoding, they proposed a masked multiplication gadget (GJR) with quasilinear (randomness and operations) complexity. A second contribution by Goudarzi, Prest, Rivain and Vergnaud in this line of research appeared in TCHES 2021. The authors revisited the aforementioned multiplication gadget (GPRV), and brought the IOS security notion for refresh gadgets to allow secure composition between probing secure gadgets.In this paper, we propose a follow up on GPRV. Our contribution stems from a single Lemma, linking algebra and probing security for a wide class of circuits, further exploiting the algebraic structure of $\omega$-encoding. On the theoretical side, we weaken the IOS notion into the KIOS notion, and we weaken the usual $t$-probing security into the RTIK security. The composition Theorem that we obtain by plugging together KIOS, RTIK still achieves region-probing security for composition of circuits.To substantiate our weaker definitions, we also provide examples of competitively efficient gadgets verifying our weaker security notions. Explicitly, we give 1) a refresh gadget that uses $d-1$ random field elements to refresh a length $d$ encoding that is KIOS but not IOS, and 2) multiplication gadgets asymptotically subquadratic in both randomness and complexity. While our algorithms outperform the ISW masked compiler asymptotically, their security proofs require a bounded number of shares for a fixed base field.

Le 21 février 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

Floris Vermeulen KU Leuven

Arithmetic equivalence and successive minima

Two number fields are said to be arithmetically equivalent if they have the same Dedekind zeta function. The central question about arithmetic equivalence is to determine how "similar" arithmetically equivalent number fields are. That is, we would like to determine which arithmetic invariants, such as the degree, discriminant, signature, units, class number, etc., are the same, and which ones can differ. A key result about arithmetic equivalence is Gassmann's theorem, which allows one to answer such questions using Galois theory and representation theory.I will give a general introduction to arithmetic equivalence, discussing some of the main results such as Gassmann's theorem and giving examples. I will then introduce the successive minima of a number field, and show that arithmetically equivalent number fields have approximately the same successive minima. "

Le 8 mars 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

Ross Paterson University of Bristol

Elliptic Curves over Galois Number Fields

As E varies among elliptic curves defined over the rational numbers, a theorem of Bhargava and Shankar shows that the average rank of the Mordell-Weil group $E(\mathbb Q)$ is bounded. If we now fix a Galois number field K, how does the Mordell-Weil group E(K) behave on average as a Galois module? We will report on progress on this question, which is obtained by instead studying the associated p-Selmer groups of E/K as Galois modules.We construct some novel Selmer groups which describe certain invariants of these modules, and go on to study the behaviour of these new Selmer groups. This in turn allows us to give bounds for certain behaviour for the Mordell-Weil groups.

Le 14 mars 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

Leonardo Colô Université Aix-Marseille

Oriented Supersingular Elliptic Curves and Class Group Actions

We recently defined an OSIDH protocol with Kohel (OSIDH) for oriented supersingular isogeny Diffie-Hellman by imposing the data of an orientation by an imaginary quadratic ring $\mathcal{O}$ on the category of supersingular elliptic curves. Starting with an elliptic curve $E_0$ oriented by a CM order $\mathcal{O}_K$ of class number one, we push forward the class group action along an $\ell$-isogeny chains, on which the class group of an order $\mathcal{O}$ of large index $\ell^n$ in $\mathcal{O}_K$ acts. The map from $\ell$-isogeny chains to its terminus forgets the structure of the orientation, and the original base curve $E_0$. For a sufficiently long random $ell$-isogeny chain, the terminal curve represents a generic supersingular elliptic curve.One of the advantages of working in this general framework is that the group action by $\mathrm{Cl}(\mathcal{O})$ can be carried out effectively solely on the sequence of moduli points (such as $j$-invariants) on a modular curve, thereby avoiding expensive generic isogeny computations or the requirement of rational torsion points.The proposed attacks of Onuki (2021) and Dartois-De Feo (2021) and their analyses motivate the idea of enlarging the class group without touching the key space using clouds. In this talk we propose two approaches to augment $\mathrm{Cl}(\mathcal{O}_n(M))$ in a way that no effective data is transmitted for a third party to compute cycle relations. In both cases, it comes down to an extension of the initial chain by the two parties separately. In particular, while the original OSIDH protocol made exclusive use of the class group action at split primes in $\mathcal{O}$, we extend the protocol to include descent in the eddies at non-split primes (inert or ramified) or at large primes which are not cost-effective for use for longer isogeny walks. "

Le 21 mars 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

Mathieu Dutour Institute Rudjer Boskovic\, Croatia

High dimensional computation of fundamental domains

We have developed open-source software in C++ for computing with polyhedra, lattices, and related algebraic structures. We will shortly explain its design. Then we will explain how it was used for computing the dual structure of the $W(H_4)$ polytope.Then we will consider another application to finding the fundamental domain of cocompact subgroups $G$ of $\mathrm{SL}_n(\mathbb{R})$. The approach defines a cone associated with the group and a point $x\in \mathbb{R}^n$. It is a generalization of Venkov reduction theory for $\mathrm{GL}_n(\mathbb{Z})$. We recall the Poincaré Polyhedron Theorem which underlies these constructions.We give an iterative algorithm that allows computing a fundamental domain. The algorithm is based on linear programming, the Shortest Group Element (SGE) problem and combinatorics. We apply it to the Witte cocompact subgroup of $\mathrm{SL}_3(\mathbb{R})$ defined by Witte for the cubic ring of discriminant $49$.

Le 28 mars 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

Shane Gibbons CWI\, Netherlands

Hull attacks on the Lattice Isomorphism Problem

The lattice isomorphism problem (LIP) asks one to find an isometry between two lattices. It has recently been proposed as a foundation for cryptography in independent works. This problem is the lattice variant of the code equivalence problem, on which the notion of the hull of a code can lead to devastating attacks. In this talk I will present the cryptanalytic role of an adaptation of the hull to the lattice setting, which we call the s-hull. Specifically, we show that the hull can be helpful for geometric attacks, for certain lattices the minimal distance of the hull is relatively smaller than that of the original lattice, and this can be exploited. The attack cost remains exponential, but the constant in the exponent is halved.
Our results suggests that one should be very considerate about the geometry of hulls when instantiating LIP for cryptography. They also point to unimodular lattices as attractive options, as they are equal to their own hulls. Remarkably, this is already the case in proposed instantiations, namely the trivial lattice $\mathbb{Z}^n$ and the Barnes-Wall lattices.

Le 4 avril 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

Jean Gillibert Université de Toulouse 2

Finite subgroups of $mathrm{PGL}_2(mathbb{Q})$ and number fields with large class groups

For each finite subgroup $G$ of $\mathrm{PGL}_2(\mathbb{Q})$, and for each integer $n$ coprime to $6$, we construct explicitly infinitely many Galois extensions of $\mathbb{Q}$ with group $G$ and whose ideal class group has $n$-rank at least $#G-1$. This gives new $n$-rank records for class groups of number fields.

Le 11 avril 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

Henry Bambury ENS Ulm

An inverse problem for isogeny volcanoes

Supersingular isogeny graphs are very complicated and intricate, and are used extensively by cryptographers. On the other side of things, the structure of ordinary isogeny graphs is well understood connected components look like volcanoes. Throughout this talk we will explore the ordinary $\ell$-isogeny graph over $\mathbb{F}_p$ for various prime numbers $\ell$ and $p$, and answer the following question, given a volcano-shaped graph, can we always find an isogeny graph in which our volcano lives as a connected component?

Le 25 avril 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

online

Alessandro Languasco University of Padova\, Italy

Computing $L'(1,chi)/L(1,chi)$ using special functions, their reflection formulae and the Fast Fourier Transform

We will show how to combine the Fast Fourier Transform algorithm with the reflection formulae of the special functions involved in the computation of the values of $L(1,chi)$ and $L'(1,chi)$, where $chi$ runs over the Dirichlet characters modulo an odd prime number $q$. In this way, we will be able to reduce the memory requirements and to improve the computational cost of the whole procedure. Several applications to number-theoretic problems will be mentioned, like the study of the distribution of the Euler-Kronecker constants for the cyclotomic field and its subfields, the behaviour of $min_{chie chi_0} | L'(1,chi)/L(1,chi) |$, the study of the Kummer ratio for the first factor of the class number of the cyclotomic field and the ``Landau vs. Ramanujan`` problem for divisor sums and coefficients of cusp forms. Towards the end of the seminar we will tackle open problems both of theoretical and implementative nature.

Le 2 mai 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Sorina Ionica Université de Picardie

Computing bad reduction for genus 3 curves with complex multiplication

Goren and Lauter studied genus 2 curves whose Jacobians are absolutely simple and have complex multiplication (CM) by the ring of integers of a quartic CM-field, and showed that if such a curve has bad reduction to characteristic p then there is a solution to a certain embedding problem. An analogous formulation of the embedding problem for genus 3 does not suffice for explicitly computing all primes of bad reduction. We introduce a new problem called the Isogenous Embedding Problem (IEP), which we relate to the existence of primes of bad reduction. We propose an algorithm which computes effective solutions for this problem and exhibits a list of primes of bad reduction for genus 3 curves with CM. We ran this algorithm through different families of curves and were able to prove the reduction type of some particular curves at certain primes that were open cases in the literature.

Le 9 mai 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Sabrina Kunzweiler IMB

Isogeny-based PAKE protocols

The passwords that we use in our everyday life are often chosen to be easily memorable which evidently makes them vulnerable to attacks. This problem is addressed by password-authenticated key exchange (PAKE). The general idea of such a protocol is to enable two parties who share the same (potentially weak) password to establish a strong session key. Most PAKE protocols used today are based on Diffie-Hellman key exchange in prime order groups, hence they are not secure against quantum attackers. A promising candidate for replacing Diffie-Hellman key exchange in a post-quantum world is the Commutative-Supersingular-Isogeny-Diffie-Hellman (CSIDH) key exchange. In this talk, we introduce two novel PAKE protocols based on CSIDH.

Le 16 mai 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Wessel van Woerden IMB

Perfect Quadratic Forms -- an Upper Bound and Challenges in Enumeration

In 1908 Voronoi introduced an algorithm that solves the lattice packing problem in any dimension in finite time. Voronoi showed that any lattice with optimal packing density must correspond to a so- called perfect (quadratic) form and his algorithm enumerates the finitely many perfect forms up to similarity in a fixed dimension. However, the number of non-similar perfect forms and the comlexity of the algorithm grows quickly in the dimension and as a result Voronoi’s algorithm has only been completely executed up to dimension 8. We discuss an upper bound on the number of perfect forms and the challenges that arise for completing Voronoi's algorithm in dimension 9.

Le 23 mai 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

bâtiment Inria, salle Sophie Germain (304)

Boris Fuoutsa EPFL\, Switzerland

Beyond the SIDH Countermeasures

During summer 2022, a series of three cryptanalysis papers lead to a
polynomial time attack on SIKE, which was in the fourth round of the NIST
standardisation process. In a recent work, we explored countermeasures
avenue to the SIDH attacks, M-SIDH and MD-SIDH.
These countermeasures, despite being slow and less compact (when compared
to SIDH and other post-quantum schemes), come with new insights that may be
of independent interest. In this talk, we will discuss an on-going work in
which we use M-SIDH together with the SIDH attacks to design a trapdoor one
way function. This trapdoor one way function can be leveraged to obtain a
public key encryption scheme, most importantly, it can be used to design an
Identity Based Encryption scheme. The main drawback is that the design is
purely theoretical at the moment, since inverting the one way function
requires computing isogenies in higher dimension of prime degree up to
5000 or even higher.

Le 30 mai 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Sarah Arpin University of Leiden\, Netherlands

Adding Level Structure to Supersingular Elliptic Curve Isogeny Graphs

The classical Deuring correspondence provides a roadmap between supersingular elliptic curves and the maximal orders which are isomorphic to their endomorphism rings. Building on this idea, we add the information of a cyclic subgroup of prime order N to supersingular elliptic curves, and prove a generalisation of the Deuring correspondence for these objects. We also study the resulting ell-isogeny graphs supersingular elliptic curve with level-N structure, and the corresponding graphs in the realm of quaternion algebras. The structure of the supersingular elliptic curve ell-isogeny graph underlies the security of a new zero-knowledge proof of isogeny knowledge.

Le 6 juin 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Daan van Gent (University of Leinden\, Netherlands

The Closest Vector Problem for the lattice of algebraic integers

Any number field comes with a natural inner product as in the theory of the geometry of numbers, so that any order becomes a lattice.
We extend the definition of the inner product to $\overline{\mathbb{Q}}$, the algebraic closure of the rationals, and consider its maximal order $\overline{\mathbb{Z}}$, which has infinite rank, as an intrinsically interesting `lattice'.
We will compute several lattice invariants and attempt to solve the Closest Vector Problem through proofs inspired by capacity theory.
Adjacent to CVP is the problem of finding the Voronoi-relevant vectors, and we pose the challenge to compute all such vectors of degree 3.

Le 13 juin 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Mahshid Riahinia ENS de Lyon

Constrained Pseudorandom Functions from Homomorphic Secret Sharing

A Constrained pseudorandom function (CPRF) is a pseudorandom function that provides fine-grained access to the evaluation of the function. In other words, for a (possibly super-polynomial) subset of inputs, a constrained pseudorandom function allows us to derive a constrained key that enables evaluating the function on that subset of inputs while learning nothing beyond. We propose and analyze a simple strategy for constructing 1-key constrained pseudorandom functions from homomorphic secret sharing (HSS) protocols. This relation, in particular, leads to instantiations of CPRFs for various constraints and from various assumptions. In this talk, I present this strategy and briefly go over one of the instantiations.

Le 20 juin 2023 à 10:30

Séminaire de Théorie Algorithmique des Nombres

INRIA building, room George Bool 2

Canari team INRIA

Meeting Canari team and Inria Bordeaux head team

The LFANT seminar is canceled. Instead, there will be a recurrent meeting between the team members and the administrative direction. The meeting is not compulsory for the PdD students.

Le 27 juin 2023 à 10:00

Séminaire de Théorie Algorithmique des Nombres

salle 1

Agathe Houzelot Labri

White-Box Implementations of ECDSA

Cryptographic algorithms are primarily designed to be secure in the black-box model, where an attacker can only observe their input/output behavior. However
in practice, algorithms are rarely executed in a completely isolated environment
and additional information is often leaked. In the context of mobile applications or connected objects, devices often lack secure storage to protect secret keys, and their generally open execution environment exposes a large attack surface. This hostile environment is captured by the white-box attack model.
While many white-box implementation of block ciphers have been published since 2002, asymmetric cryptosystems have been very little studied. In my PhD thesis, we got interested in white-box implementations of ECDSA. This led us to participate in the WhibOx Contest that was organized as part of the TCHES workshops in 2021. During three months, developpers were invited to submit ECDSA white-box implementations and attackers to try to break them.
In this talk, I will introduce the white-box model before explaining the specificities of the ECDSA algorithm in this context. I will then present the different attacks that we used to break almost all the challenges of the WhibOx Contest.

Le 12 septembre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Pierrick Dartois IMB

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.

Le 19 septembre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Xavier Caruso IMB

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.)

Le 26 septembre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Joël Felderhoff ENS Lyon

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.

Le 3 octobre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Jean Gasnier IMB

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.

Le 10 octobre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

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.

Le 24 octobre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Donghyeok Lim 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.

Le 7 novembre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Maxime Bombar CWI

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

Le 14 novembre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Stefano Marseglia Utrecht University

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.

Le 21 novembre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Lorenzo Furio University of Pisa

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.

Le 28 novembre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Monika Trimoska Eindhoven University of Technology

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á.

Le 5 décembre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Yining HU Harbin Institut of Technology\, China

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.

Le 12 décembre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Nicolas Sarkis IMB

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.

Le 19 décembre 2023 à 11:00

Séminaire de Théorie Algorithmique des Nombres

salle 2

Marc Houben Leiden University Netherlands

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.

Afficher 2023 - 2022 - 2021 - 2020 - 2019 - 2018 - 2017 - 2016 - 2015 - antérieurs

Séminaire de Théorie Algorithmique des Nombres

Institut de Mathématiques de Bordeaux UMR 5251