Friday June 24, 2022
A survey of elliptic curves for proof systems
Big Blue Button, 10:30
slides: pdf (1028 kb)
Elliptic curves have become key ingredients for instantiating zeroknowledge proofs and more generally proof systems. Recently, there have been many tailored constructions of these curves that aim at efficiently implementing different kinds of proof systems. This survey provides a comprehensive view on existing work and revisits the contributions in terms of efficiency and security. We present an overview at three stages of the process: curves to instantiate a SNARK, curves to instantiate a recursive SNARK, and also curves to express an ellipticcurve related statement. We provide new constructions of curves for SNARKs and generalize the stateoftheart constructions for recursive SNARKs. We also exhaustively document the existing work and opensource implementations.
Joint work with Diego F. Aranha, Aarhus University, and Youssef El Housni, Consensys, GRACE, Ecole Polytechnique.
Preprint at hal03667798 and ePrint 2022/586.
Python implementation at gitlab.
Wednesday June 8, 2022
Correctly rounded pow in double precision
B013, 10:00
slides: pdf (170 kb)
Tuesday May 3, 2022
On Codes and Learning with Errors over Function Fields
B013, 10:30
slides: pdf (461 kb)
In cryptography, one can often define two versions of a hard problem: A computational version, or search version, that asks to compute something (e.g. a discrete logarithm, a prime factor), and a decisional version, that asks to distinguish between some specific probability distribution and the uniform. More often, the search problem can be shown to be computationally hard, but the decision version might be more difficult to handle. Informally, the hardness of the decision version means that the distribution is pseudorandom.
In codebased cryptography, one natural search version is the decoding problem, which has been shown to be equivalent to the decision version in the case of purely random codes. However, it is a long standing problem to find a search to decision reduction for structured versions of the decoding problem (e.g. the decoding of quasicyclic codes). In the latticebased setting though, such reductions have been carried out using number fields for structured variants of the Learning With Errors problem: PolynomialLWE, RingLWE, ModuleLWE and so on.
In this talk I will present a function field version of the LWE problem that we called Function Field Decoding Problem. This new framework leads to another point of view on structured codes, strengthening the connection between latticebased and codebased cryptography. In particular, it permits to obtain the first search to decision reduction for structured codes.
Following the historical constructions in latticebased cryptography, this framework can be instantiated with function fields analogue of the cyclotomic number fields, namely Carlitz extensions, leading to search to decision reductions on various versions of RingLPN, which have applications to secure multi party computation, and to an authentication protocol.
This is a joint work with Alain Couvreur and Thomas DebrisAlazard (ePrint 2022/269)
Tuesday April 5, 2022
SIKE Channels : ZeroValue SideChannel Attacks on SIKE
B013, 10:30
slides: pdf (1025 kb)
Friday February 25, 2022
Polynomial systems, sparsity, and applications
TBA, 10:30
slides: pdf (1622 kb)
Thursday December 16, 2021
New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems
A008, 10:30
slides: pdf (1959 kb)
Wednesday November 24, 2021
Quantum cryptanalysis of block ciphers: quadratic speedups and beyond
A008, 10:30
slides: pdf (965 kb)
The security of modern cryptosystems relies on computational assumptions, which may be challenged by the advent of largescale quantum computing devices. While Shor's algorithm is known to break today's most popular publickey schemes, secretkey cryptosystems are generally expected to retain half of their prequantum bits of security, corresponding to a (generic) quadratic time speedup.
In this talk, we will focus on keyrecovery attacks against block ciphers. These attacks are often categorized in two scenarios, depending on the type of blackbox access allowed to the adversary: either a classical query access, or a "quantum" query access where the blackbox is part of the adversary's quantum algorithm. In the first part of the presentation, we will see that most quantum attacks known so far actually comply with the rule of halving security levels, though in the "quantum" query model, some classically secure designs have shown to be broken due to their strong algebraic structure (Kuwakado & Morii, ISIT 2010).
In the second part, we will see how these vulnerabilities can lead to better attacks in the classical query model. In particular, we will present an extension of the offlineSimon algorithm (Bonnetain et al., ASIACRYPT 2019) that, against some specific block cipher constructions, reaches a more than quadratic speedup in keyrecovery. This is a joint work with Xavier Bonnetain and Ferdinand Sibleyras (ePrint 2021/1348).
Tuesday June 29, 2021
The knapsack algorithm in analytical chemistry
Big Blue Button https://webconf.math.cnrs.fr/b/aurfvcjr6, 15:00
slides: pdf (1977 kb)
Friday June 25, 2021
L'IA peutelle battre les cryptographes ?
Big Blue Button https://greenlight.lal.cloud.math.cnrs.fr/b/marryrr4y, 14:00
slides: pdf (2548 kb)
Monday June 14, 2021
On algorithms for solving Euclidean lattice problems in cryptography
https://rendezvous.renater.fr/carambaseminar, 14:00
slides: pdf (543 kb)
In this talk, we will try to review the stateoftheart of the algorithms for solving the Euclidean lattice problems underlying cryptography. In more details, this talk contains two parts. In the first part, we will focus on the lattice problems such as approximate Shortest Vector Problem (approxSVP) and the lattice reduction algorithms as the best known solving algorithms so far. In particular, I will present an improved enumerationbased lattice reduction algorithm, which is shown to be (potentially) relevant to cryptanalysis. In the second part, we will instead consider a quantum problem that is computationally equivalent to approxSVP. By directly solving a quantum problem, we may expect to have a more powerful use of the quantum computation. However, the best known algorithms for solving approxSVP via solving this quantum problem, is not better than lattice reduction yet.
Tuesday April 13, 2021
Sampling relatively factorizable elements in ideals of number fields (and application to computing classgroups)
https://rendezvous.renater.fr/carambaseminar, 14:00
slides: pdf (581 kb)
In this talk, we will be interested in the following problem: given an ideal I of a number field, one wants to find an element x in I such that the relative ideal (x)*I^{1} is smooth/prime/nearprime/... This algorithmic problem happens naturally in multiple number theoretic algorithms, for instance in an algorithm computing the power residue symbol (de BoerPagano 2017) or in algorithms computing classgroups and unit groups of number fields (Buchmann 1988/ BiasseFieker 2014). The usual way to solve this problem is *heuristic*, and consists in sampling random elements x in I until a good x is found (the heuristic part comes when estimating the probability that a random x is good).
In this talks, I will present an algorithm that finds a good x in a *provable* way. The idea is still to sample random x's until a good one is found, but our sampling procedure is slightly different from what was done before, and this enables us to obtain a provable lower bound on the probability to obtain a good x. This allows us to remove one heuristic (among others) of the algorithms mentioned above.
This is a joint work with Koen de Boer, Léo Ducas and Benjamin Wesolowski.
Tuesday March 30, 2021
Analyse fine de la complexité asymptotique du crible algébrique.
https://rendezvous.renater.fr/carambaseminar, 14:00
slides: pdf (414 kb)
Friday March 12, 2021
Cryptanalyse logique du problème du logarithme discret sur courbes elliptiques
https://rendezvous.renater.fr/carambaseminar, 09:00
slides: pdf (897 kb)
Tuesday February 16, 2021
Constructing Secure & Efficient STNFSSecure Pairings.
https://rendezvous.renater.fr/carambaseminar, 14:00
slides: pdf (254 kb)
The recent improvements of the tower number field sieve (TNFS) attacks on the DLP in finite fields extensions of composite degree have caused serious complications in pairingbased cryptography. In particular, the secure and efficient examples of pairings we had in the preTNFS period are no longer safe for implementations and hence key sizes should be updated. The purpose of this talk is to present ways for constructing efficient elliptic curve pairings that are resistant against the improved TNFS attacks and to address the main challenges and difficulties that occur as a result of these attacks. In addition, I will present a theoretical study on the best elliptic curve options that are available today, with respect to security and efficiency, and highlight a certain pairingrelated topics for future work.
Tuesday February 9, 2021
On choosing suitable elliptic curves for ZKSNARKs.
https://bbb.lix.polytechnique.fr/b/thorfboxzstv, 13:30
slides: pdf (378 kb)
A zeroknowledge proof is a method by which one can prove knowledge of general nondeterministic polynomial (NP) statements. SNARKs are in addition noninteractive, short and cheap to verify. They use bilinear pairings over elliptic curves to achieve succinctness. This property makes them suitable for recursive proof composition, that is proofs attesting to the validity of other proofs. Recursive proof composition has been empirically demonstrated for pairingbased SNARKs via tailored constructions of expensive pairingfriendly elliptic curves. This presentation is about these tailored constructions. This is a joint work with Aurore Guillevic from CARAMBA team (Nancy).
Monday January 18, 2021
SQISign: Compact PostQuantum Signature from Quaternions and Isogenies.
https://rendezvous.renater.fr/carambaseminar, 14:00
slides: pdf (490 kb)
We introduce a new signature scheme, SQISign, (for Short Quaternion and Isogeny Signature) from isogeny graphs of supersingular elliptic curves. The signature scheme is derived from a new oneround, high soundness, interactive identification protocol. Targeting the postquantum NIST1 level of security, our implementation results in signatures of 204 bytes, secret keys of 16 bytes and public keys of 64 bytes. In particular, the signature and public key sizes combined are an order of magnitude smaller than all other postquantum signature schemes. On a modern workstation, our implementation in C takes 0.6s for key generation, 2.5s for signing, and 50ms for verification.
While the soundness of the identification protocol follows from classical assumptions, the zeroknowledge property relies on the second main contribution of this paper. We introduce a new algorithm to find an isogeny path connecting two given supersingular elliptic curves of known endomorphism rings. A previous algorithm to solve this problem, due to Kohel, Lauter, Petit and Tignol, systematically reveals paths from the input curves to a `special' curve. This leakage would break the zeroknowledge property of the protocol. Our algorithm does not directly reveal such a path, and subject to a new computational assumption, we prove that the resulting identification protocol is zeroknowledge.
Thursday February 13, 2020
The famous RSA public key cryptosystem is one of the most studied topic in cryptology research. In Eurocrypt 1996, Coppersmith proposed a new method to find small roots of polynomial equations using lattice. After that many cryptanalyses have been proposed on RSA and its variants using this technique. In this talk, we will discuss Coppersmith's attack and some of applications on RSA.
Thursday February 6, 2020
Computing isogenies from modular equations in genus 2
B013, 10:30
Given two lisogenous elliptic curves over a field k of large characteristic, an algorithm by Elkies uses modular polynomials to compute this isogeny explicitly. It is an essential primitive in the wellknown SEA point counting algorithm.
In this talk, we generalize Elkies's algorithm to compute isogenies between Jacobians of genus 2 curves: we compute either lisogenies or, in the RM case, cyclic betaisogenies. The algorithm uses modular equations of Siegel or Hilbert type respectively. As in genus 1, there are two main steps:
 Use derivatives of modular equations to compute the action of the isogeny on differential forms;
 Solve a differential system to find the isogeny.
This algorithm has implications for point counting in genus 2: Elkies's method is now available, and could improve on the SchoofPila approach.
Monday January 27, 2020
Making (near) Optimal Choices for the Design of Block Ciphers
B013, 10:30
slides: pdf (872 kb)
When designing block ciphers, we need to make decisions on which specific components to use such as which Sbox, which linear layer etc. These decisions are made by taking into account the security of the resulting block cipher, but also the underlying cost in term of performances. In this talk, I will present two different works aiming at finding optimal components w.r.t a given criteria, while also trying to keep a very cheap implementation cost. I will show how the use of automatic tools (either already existing or specifically designed) can help us to make (near) optimal decisions while the initial search space is very large.
The first part of my talk will be focused on a block cipher construction called Generalized Feistel Networks, which is a very efficient construction in general. The idea of this construction is to split the plaintext into an even number of blocks, apply a Feistel transformation in parallel to those blocks, and then permute them. In a recent paper accepted at FSE 2020, we showed how to choose this permutation to be optimal w.r.t a certain criterion (called "diffusion round"), which also allowed us to solve a 10year old problem.
The second part of my talk will be based on a paper accepted at SAC 2018, which aims at replacing the keyschedule of AES by a more efficient one (namely a permutation). AES is the current symmetric encryption standard, and its keyschedule (i.e. the algorithm allowing to transform the master key into several round keys) is quite intricate and costly. We thus studied what would happen if we replace this keyschedule by a permutation, and especially we show that we can get better security arguments even though we have a much simpler keyschedule.
Friday January 17, 2020
Improved LowMemory Subset Sum and LPN Algorithms via Multiple Collisions
B013, 10:30
slides: pdf (6288 kb)
For enabling postquantum cryptanalytic experiments on a meaningful scale, there is a strong need for lowmemory algorithms. We show that the combination of techniques from representations, multiple collisions finding, and the SchroeppelShamir algorithm leads to improved lowmemory algorithms. For random subset sum instances (a_{1}, ..., a_{n}, t) defined modulo 2^{n}, our algorithms improve over the Dissection technique for small memory M < 2^{0.02n} and in the midmemory regime 2^{0.13n} < M < 2^{0.2n}. An application of our technique to LPN of dimension k and constant error p yields significant time complexity improvements over the DissectionBKW algorithm from Crypto 2018 for all memory parameters M < 2^{0.35 k/log k}. This is joint work with Andre Esser and Alexander May, published at IMACC 2019.
Monday January 13, 2020
A group signature scheme in the generic group model
B013, 14:00
slides: pdf (1021 kb)
Group signatures, introduced by Chaum and van Heyst in 1991, enable members of a group to sign on behalf of the group, thanks to a certificate delivered by a group manager. The point is that the signature is anonymous: it cannot be traced back to its issuer, except for a specific entity, the opening authority, which can "open" any valid group signature.
Bellare, Micciancio and Warinschi provided the first security model where they defined the requirements for a group signature: anonymity, traceability and nonframeability.
Combining seemingly contradictory properties such as anonymity and traceability can be done through the SignEncryptProve (SEP) framework: after signing a message, a group member encrypts both the signature and the certificate then proves in a noninteractive zeroknowledge fashion that everything is well formed (the opening authority still has a way to rescind the anonymity).
In this talk, we will construct a group signature that uses the nice interaction between Pointcheval and Sanders signatures and Fuchsbauer, Hanser and Slamanig equivalenceclass signatures. Group members then remain anonymous by simply randomizing their signatures and certificates: there is no longer the need for encryption and proving.
Thursday December 12, 2019
Quantum cryptanalysis using hidden structures
B013, 10:30
slides: pdf (1308 kb)
Quantum cryptanalysis studies how to break cryptographic primitives using a quantum computer. Multiple quantum algorithms for the hidden shift and hidden period problems have been proposed, which are vastly more efficient than their classical counterpart. In this talk, I will present some of them, with their applications to cryptanalyze multiple symmetric constructions and some isogenybased key exchanges.
In more details, I will present Simon's algorithm and its use to attack multiple symmetric constructions using quantum queries, the offline approach which allows to apply it even if we restrict to classical queries, and some abelian hidden shift algorithms and their applications against some symmetric constructions and the key exchange CSIDH.
Thursday July 4, 2019
Verifiable delay functions from supersingular isogenies and pairings
Amphi C, 10:15
slides: pdf (5992 kb)
Tuesday June 4, 2019
Applying Exact Real Arithmetic to Solving Nonlinear Constraints
B013, 10:00
slides: pdf (595 kb)
Exact Real Arithmetic describes implementations of Computable Analysis (TTE), which can be considered as a foundation of reliable computations on continuous data. TTE is a framework which allows to express and reason about real number computations on digital computers or Turing machines in a rigorous manner.
In this talk we report on recent applications of ERA to check satisfiability of nonlinear constraints over real numbers in the setting of SMT. In particular, we present a CDCL style calculus and a prototypical implementation for this concrete problem. The procedure is based on symbolical methods to resolve linear conflicts and on exact real computations to construct linearisations of nonlinear constraints local to conflicts. This approach allows the treatment of a large number of computable nonlinear real functions such as polynomials, rational or trigonometrical functions and beyond. The implementation has been evaluated on several nonlinear SMTLib examples and the results have been compared with stateoftheart SMT solvers.
Friday May 24, 2019
Implement all the pairings in software!
B011, 10:00
slides: pdf (7230 kb)
Thursday May 23, 2019
Fast polynomial reduction for generic bivariate ideals
A008, 10:30
slides: pdf (1741 kb)
Let A, B in K[X,Y] be two bivariate polynomials over an effective field K, and let G be the reduced Gröbner basis of the ideal I := ⟨A,B⟩ generated by A and B, with respect to some weighteddegree lexicographic order. Under some genericity assumptions on A,B, we will see how to reduce a polynomial with respect to G with quasioptimal complexity, despite the fact that G is much larger than the intrinsic complexity of the problem. For instance, if A,B have total degree n, that is O(n^{2}) coefficients, then G has O(n^{3}) coefficients but reduction can be done in time O(n^{2}).
We will consider two situations where these new ideas apply, leading to different algorithms:
 First, there is a class called "vanilla Gröbner bases" for which there is a socalled terse representation that, once precomputed, allows to reduce any polynomial P in time O(n^{2}). In this setting, assuming suitable precomputation, multiplication and change of basis can therefore be done in time O(n^{2}) in the quotient algebra K[X,Y] / ⟨A,B⟩.
 Then, we assume that A and B are given in total degree and we consider the usual degree lexicographic order. Although the bases are not vanilla in this case, they admit a socalled concise representation with similar properties. Actually, the precomputation can also be done efficiently in this particular setting: from the input A,B, one can compute a Gröbner basis in concise representation in time O(n^{2}). As a consequence, multiplication in K[X,Y] / ⟨A,B⟩ can be done in time O(n^{2}) including the cost of precomputation.
Tuesday May 14, 2019
Progress and hard problems in commutative isogenybased cryptography
B013, 13:30
slides: pdf (189 kb)
Tuesday April 2, 2019
Gröbner bases and sparse polynomial systems
B013, 14:00
slides: pdf (1684 kb)
Gröbner bases are one the most powerful tools in algorithmic nonlinear algebra. Their computation is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. For example, several problems in computeraided design, robotics, vision, biology, kinematics, cryptography, and optimization involve sparse systems where the input polynomials have a few nonzero terms.
An approach to exploit sparsity is to embed the systems in a semigroup algebra and to compute Gröbner bases over this algebra. Prior to our work, the algorithms that follow this approach benefited from the sparsity only in the case where all the polynomials have the same sparsity structure, that is the same Newton polytope. In this talk, I will present the first algorithm that overcomes this restriction. Under regularity assumptions, it performs no redundant computations. Further, I will use it to compute Gröbner basis in the standard algebra and solve sparse polynomials systems over the torus. The complexity of the algorithm depends on the Newton polytopes and it is similar to the complexity of the solving techniques involving the sparse resultant. Hence, this algorithm closes a 25years gap between the strategies to solve systems using resultants and Gröbner bases. Additionally, for particular families of sparse systems, I will use the multigraded CastelnuovoMumford regularity to improve the complexity bounds.
This is joint work with JeanCharles Faugère and Elias Tsigaridas.
Thursday February 14, 2019
MDS and almostMDS matrices with lightweight circuits
B013, 10:30
slides: pdf (489 kb)
MDS matrices are essential in symmetrickey cryptography since they provide optimal diffusion in block ciphers. Many MDS matrices are known, but a problem remains which gathers a lot of attention: finding lightweight MDS matrices.
Several approaches exist, namely reducing the cost of alreadyknown MDS matrices (to improve existing ciphers) and finding new MDS matrices lighter than the known ones (to make new ciphers).
We focus on the second case and, contrarily to the usual approach, we will not look for matrices whose coefficients are lightweight to implement. Rather than this local optimization, we will prefer a global optimization of the whole matrix, which allows reusing of intermediate values.
We propose an algorithm to search for lightweight formal MDS matrices on a polynomial ring, by enumerating circuits until we reach an MDS matrix. This approach allows us to get much better results than previous works. We also adapt this algorithm to look for almostMDS matrices, which offer a tradeoff between cost and security.
Thursday January 31, 2019
On the Security of Goldreich's Pseudorandom Generator
B013, 10:30
slides: pdf (155 kb)
Almost two decades ago, Goldreich proposed a oneway function construction where output bits depends in a constant number of input bits. Afterwards, this oneway function construction was extended to Pseudo Random Generators.
In the polynomial regime, where the seed is of size n and the output of size n^{s} for s > 1, the only known solution, commonly known as Goldreich's PRG, proceeds by applying a simple dary predicate (Boolean function of d variables) to public random sized subsets of the bits of the seed.
The security of this PRG has been widely investigated, and was proven to be secure against a large class of attacks. However, by applying symmetric cryptanalysis techniques such as Guessanddetermine and Gröbner Basis, we were able to find subexponential time algorithms that recover the seed of this PRG. Moreover, as the predicate can be identified as a Boolean function, we also derive new security criteria that rely on the predicate that is used in this PRG. Finally, the complexity of our algorithms is counted in a nonasymptotic way, leading to a better understanding of the security of this PseudoRandom Generator.
The results of this work were published at ASIACRYPT 2018, and a full version of the paper can be found at this link.
Joint work with Geoffroy Couteau and Aurélien Dupin and Pierrick Méaux and Mélissa Rossi.
Monday January 28, 2019
SBox Decompositions and some Applications
B013, 10:30
slides: pdf (4804 kb)
Sboxes are components used by many symmetric cryptographic algorithms, most prominently the AES. They are small nonlinear functions whose properties are crucial in ensuring the security of the whole cipher against some attacks.
In this talk, I will present my work on the decomposition of Sboxes. Intuitively, a decomposition is a "simple" algorithm evaluating the Sbox. The knowledge of a decomposition can allow a significantly improved implementation but, on the other hand, it can also reveal cryptographic flaws as particular decompositions can allow attacks. In fact, we could imagine that a malevolent designer would purposefully hide such a "backdooring" decomposition in their Sbox. As an illustration, I will present some results on the Sbox used by the last two Russian standards in symmetric cryptography. It turns out to exhibit very strong algebraic properties that warrant further investigation into the security of these algorithms.
Then, I will present a more surprising application of these techniques to a more theoretical problem. We were able to find a decomposition of the only known solution of a longstanding open problem in the design of Sboxes, namely the big APN problem (it deals with constructing Sboxes with optimal resistance against differential attack). This allowed us to find the first generalization of this functionthough we could not use them to solve the big APN problem. On the bright side, the type of decomposition we found in this permutation has a deeper meaning than we first expected as it turns out to play a key role in "CCZequivalence" (a form of equivalence between Sboxes).
I will conclude with several open problems that have been opened by this line of research.
Thursday December 13, 2018
A complete classification of ECMfriendly families using modular curves
B013, 10:30
The elliptic curve method (ECM) is a factorization algorithm widely used in cryptography. It was proposed in 1985 by Lenstra and improved a couple of months later by Montgomery using wellchosen families of curves.
Algorithm succeeds in factoring if the elliptic curves it uses have desirable smoothness properties. These smoothness properties can be quantified using the mean valuation of a prime l in the cardinality of an elliptic curve E modulo random primes.
In this joint work with Razvan Barbulescu, we present a brief survey of previous works in this regard and then present two approaches to find these ECMfriendly elliptic curves. Combined with recent works of [1] and [2], we obtain a complete list of 1540 such families.
Thursday November 29, 2018
Faster cofactorization with ECM using mixed representations
B013, 10:30
slides: pdf (644 kb)
The Elliptic Curve Method (ECM) is the asymptotically fastest known method for finding mediumsize prime factors of large integers. It is also a core ingredient of the Number Field Sieve (NFS) for integer factorization and its variants for computing discrete logarithms. In NFS and its variants, ECM is extensively used in the cofactorization step (a subroutine of the sieving phase) which consists of breaking into primes billions of composite integers of a hundredish bits.
In this talk, we propose a novel implementation of ECM in the context of NFS that requires fewer modular multiplications than any other publicly available implementation. The main ingredients are: Dixon and Lenstra's idea on primes combination, fast point tripling, optimal doublebase decompositions and Lucas chains, and a good mix of Edwards and Montgomery representations.
Friday September 7, 2018
Pointcounting on hyperelliptic curves defined over finite fields of large characteristic: algorithms and complexities (PhD defense)
C005, 14:30
Counting points on algebraic curves has drawn a lot of attention due to its many applications from number theory and arithmetic geometry to cryptography and coding theory. In this thesis, we focus on counting points on hyperelliptic curves over finite fields of large characteristic p. In this setting, the most suitable algorithms are currently those of Schoof and Pila, because their complexities are polynomial in log q. However, their dependency in the genus g of the curve is exponential, and this is already painful even in genus 3.
Our contributions mainly consist of establishing new complexity bounds with a smaller dependency in g of the exponent of log p. For hyperelliptic curves, previous work showed that it was quasiquadratic, and we reduced it to a linear dependency. Restricting to more special families of hyperelliptic curves with explicit real multiplication (RM), we obtained a constant bound for this exponent.
In genus 3, we proposed an algorithm based on those of Schoof and GaudryHarleySchost whose complexity is prohibitive in general, but turns out to be reasonable when the input curves have explicit RM. In this more favorable case, we were able to count points on a hyperelliptic curve defined over a 64bit prime field.
Monday June 11, 2018
A New Family of PairingFriendly Elliptic Curves
A006, 14:00
slides: pdf (277 kb)
Joint work with Michael Scott (Miracl).
Tuesday June 5, 2018
Multiplication algorithms: bilinear complexity and fast asymptotic methods (PhD defense)
C005, 14:00
The two previous examples fall in the category of bilinear maps: these are functions of the form Phi : K^{m} x K^{n} > K^{l}, given a field K, linear in each variable. Among the most classical bilinear maps, we have the multiplication of polynomials, matrices, or even elements of algebraic extension of finite fields. Given a bilinear map Phi, computing the minimal number of multiplications necessary to the evaluation of this map is a NPhard problem. The purpose of this thesis is to propose algorithms minimizing this number of multiplications. Two angles of attack have been studied.
The first aspect of this thesis is to study the problem of the computation of the bilinear complexity under the angle of the reformulation of this problem in terms of research of matrix subspaces of a given rank. This work led to an algorithm taking into account intrinsic properties of the considered products such as matrix or polynomial products over finite fields. This algorithm allows one to find all the possible decompositions, over F_{2}, for the product of polynomials modulo X^{5} and the product of matrices 3x2 by 2x3.
Another aspect of this thesis was the development of fast asymptotic methods for the integer multiplication. There is a particular family of algorithms that has been proposed after an article by Fürer published in 2007. This article proposed a first algorithm, relying on fast Fourier transform (FFT), allowing one to multiply nbit integers in O(n log n 2^{O(log*n)}), where log^{*} is the iterated logarithm function. In this thesis, an algorithm, relying on a number theoretical conjecture, has been proposed, involving the use of FFT and generalized Fermat primes. With a careful complexity analysis of this algorithm, we obtain a complexity in O(n log n 4^{log*n}).
Monday June 4, 2018
Optimizing multiplications with vector instructions
C103, 15:00
slides: pdf (325 kb)
Friday June 1, 2018
cryptanalyse de systèmes de chiffrement symétrique
B013, 10:30
Thursday March 29, 2018
On the harvesting phase in Indexcalculus over algebraic curves
B013, 10:30
Joint work with Vanessa Vitse and JeanCharles Faugère.
Thursday February 1, 2018
Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time
C103, 10:30
This is a joint work with Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev.
Monday December 11, 2017
Dense families of curves over prime fields with many points after field extension
B013, 14:00
(i) the genera tend to infinity;
(ii) the ratio of two successive genera tends to 1 (density condition) and
(iii) after field extension to F_{p2t}, the asymptotic number of points reaches the Ihara bound.
The only cases known so far are for t=1, with the classical modular curves X_{0}(N) over F_{p}. We present here an explicit family of Shimura curves solving the case p=3 and 2t=6.
The talk will recall facts on the descent of covering maps, and illustrate recent numerical methods of SijslingVoight.
Tuesday November 7, 2017
Enumeration in Lattices for the Number Field Sieve
B013, 10:00
Thursday September 21, 2017
Randomized MixedRadix Scalar Multiplication
A006, 10:30
Wednesday July 5, 2017
Isogeny graphs, modular polynomials, and point counting for higher genus curves.
A006, 10:30
We then recap the algorithm of Schoof, Elkies, and Atkin for efficient point counting on elliptic curves over finite fields, and show how to generalise the algorithm to genus 2 curves over finite fields (with maximal real multiplication), using our generalisation of modular polynomials to genus 2. Under some heuristic assumptions, this is the fastest known algorithm to count points on genus 2 curves over large prime fields. This is joint work with Sean Ballentine, Aurore Guillevic, Elisa LorenzoGarcia, Maike Massierer, Ben Smith, and Jaap Top.
Thursday November 10, 2016
Fast computation of normal forms of polynomial matrices
A006, 10:30
For Popov or Hermite forms of m x m nonsingular matrices with entries of degree < d, the previous fastest algorithms use O~(m^w d) operations, where w is the exponent of Klinear algebra. We will discuss improvements in three directions: (1) improving the cost bound to O~(m^w D/m), where D/m is a type of average degree of the input matrix; (2) derandomizing Hermite form computation [*]; (3) achieving fast computation for arbitrary shifts. The last point will lead us to consider the problem of solving systems of linear modular equations over K[X], which generalizes HermitePade approximation and rational reconstruction.
[*] joint work with George Labahn and Wei Zhou (U. Waterloo, ON, Canada).
Friday June 17, 2016
Génération d'aléa public et Bitcoin
A006, 10:30
Tuesday April 19, 2016
Calcul modulaire en RNS pour des implantations de cryptographie à clef publique
A006, 15:00
Monday November 23, 2015
Sparse FGLM algorithms for solving polynomial systems
B013, 14:00
Given a zerodimensional ideal I ⊂ 𝕂[x_{1},...,x_{n}] of degree D, the transformation of the ordering of its Groebner basis from DRL to LEX turns out to be the bottleneck of the whole solving process. Thus it is of crucial importance to design efficient algorithms to perform the change of ordering.
In this talk we present several efficient methods for the change of ordering which take advantage of the sparsity of multiplication matrices in the classical FGLM algorithm. Combining all these methods, we propose a deterministic toplevel algorithm that automatically detects which method to use depending on the input. As a byproduct, we have a fast implementation that is able to handle ideals of degree over 60000. Such an implementation outperforms the Magma and Singular ones, as shown by our experiments.
First for the shape position case, two methods are designed based on the Wiedemann algorithm: the first is probabilistic and its complexity to complete the change of ordering is O(D(N_{1}+n log(D)^{2})), where N_{1} is the number of nonzero entries of a multiplication matrix; the other is deterministic and computes the LEX Groebner basis of $√I$ via Chinese Remainder Theorem. Then for the general case, the designed method is characterized by the BerlekampMasseySakata algorithm from Coding Theory to handle the multidimensional linearly recurring relations. Complexity analyses of all proposed methods are also provided.
Furthermore, for generic polynomial systems, we present an explicit formula for the estimation of the sparsity of one main multiplication matrix, and prove that its construction is free. With the asymptotic analysis of such sparsity, we are able to show that for generic systems the complexity above becomes O(√(6/n π)D^{2+(n1)/n}).
This talk is based on joint work with JeanCharles Faugere.
Monday November 16, 2015
Polynomial systems with many positive solutions from bipartite triangulations
A006, 10:30
Wednesday October 14, 2015
Counting points on curves: the general case
B013, 10:30
slides: pdf (208 kb)
Wednesday September 9, 2015
Engineering Cryptographic Applications: Leveraging Recent EVoting Experiences in Australia to Build FailureCritical Systems
A006, 10:30
However developing and deploying such complex and critical cryptographic applications involves a range of engineering challenges that have yet to be addressed in practice by industry and the research community. As with any complex, largescale system, there were barriers to applying appropriately rigorous engineering practices in the two Australian evoting systems. But since these evoting systems are critical national infrastructure, such engineering practices are needed to provide high assurance of the systems and their required properties.
In this talk I will discuss some of the engineering challenges, practical barriers and issues, and what can be learned from the two recent Australian evoting experiences.
Thursday February 5, 2015
Comment trouver de bons algorithmes de multiplication par interpolation ?
A006, 10:30
Thursday November 20, 2014
The Discrete Logarithm Problem on nonhyperelliptic Curves of Genus g > 3.
A006, 14:00
Thursday November 20, 2014
Calcul des polynômes modulaires en genre 2
A006, 10:30
Monday November 17, 2014
Cofactorization strategies for NFS
B013, 14:00
Thursday October 23, 2014
Thursday September 11, 2014
Computing Groebner Bases
B013, 10:30
slides: pdf (7607 kb)
Thursday July 3, 2014
Nonlinear polynomials for NFS factorisation
B013, 10:30
slides: pdf (596 kb)
Thursday June 19, 2014
Une attaque polynomiale du schéma de McEliece basé sur les codes géométriques
A006, 10:30
slides: pdf (1036 kb)
Thursday April 24, 2014
Évaluation et composition rapide de polynômes
A006, 10:30
Thursday March 13, 2014
A Newtonlike iteration and algebraic methods for Structured LowRank Approximation
A006, 10:30
We propose an SVDbased numerical iterative method which converges locally towards such a matrix M. This iteration combines features of the alternating projections algorithm and of Newton's method, leading to a proven local quadratic rate of convergence under mild tranversality assumptions. We also present experimental results which indicate that, for some range of parameters, this general algorithm is competitive with numerical methods for approximate univariate GCDs and lowrank matrix completion (which are instances of Structured LowRank Approximation).
In a second part of the talk, we focus on the algebraic structure and on exact methods to compute symbolically the nearest structured lowrank matrix M to a given matrix U ∈ E with rational entries. We propose several ways to compute the algebraic degree of the problem and to recast it as a system of polynomial equations in order to solve it with algebraic methods.
The first part of the talk is a joint work with Eric Schost, the second part is a joint work with Giorgio Ottaviani and Bernd Sturmfels.
Wednesday February 26, 2014
Quelques perspectives mathématiques sur la sélection polynomiale dans le crible algébrique NFS
A006, 10:30
Thursday December 19, 2013
Algorithms for F_{p}
A006, 10:30
There are known algorithms to construct compatible lattices in deterministic polynomial time, but the status of the most practically efficient algorithms is still unclear. This talk will review the classical tools available, then present some new ideas towards the efficient construction of compatible lattices, possibly in quasioptimal time.
Friday December 6, 2013
Crible Spécial sur Corps de Nombres (SNFS) – Application aux courbes elliptiques bien couplées.
A006, 13:00
Thursday November 28, 2013
Calcul de formes echelonnées et des profils de rang
A006, 10:30
Thursday November 7, 2013
Algorithme de type Chudnovsky pour la multiplication dans les extensions finies de F_{q}.
A006, 10:30
Wednesday July 17, 2013
Test rapide de cubicité modulaire
B013, 14:00
Tuesday July 16, 2013
Implémentation efficace d'un algorithme de multiplication de grands nombres
A006, 15:00
Monday July 15, 2013
RNS Arithmetic for Linear Algebra of FFS and NFSDL algorithms
B013, 15:30
Tuesday May 28, 2013
Fractions continues et systèmes de numérations : applications à l'implémentation de fonctions élémentaires et à l'arithmétique modulaire
A006, 10:30
slides: pdf (1269 kb)
Friday April 5, 2013
ECM using number fields
B200, 13:30
Thursday March 28, 2013
Logarithmes discrets dans les corps finis. Application en caractéristique "moyenne".
A006, 10:30
Friday March 15, 2013
Classical Hardness of Learning with Errors
A006, 14:00
Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.
This work has been done with Z. Brakerski, C. Peikert, O. Regev and D. Stehlé.
Friday February 22, 2013
Contrôle, synchronisation et chiffrement
A006, 13:30
Wednesday February 13, 2013
Quête du plus petit jeu de tuiles apériodique
A006, 10:30
Thursday January 31, 2013
An Efficient Representation for the Trace Zero Variety
A006, 10:30
Thursday January 17, 2013
Résolution de systèmes polynomiaux structurés et applications en Cryptologie
B013, 13:00
slides: pdf (853 kb)
Thursday December 20, 2012
Computer algebra for the enumeration of lattice walks
A008, 14:00
Thursday December 20, 2012
Computer Algebra Algorithms for Real Solving Polynomial Systems: the Role of Structures
A008, 10:30
Thursday November 29, 2012
Sélection polynomiale dans CADONFS
C005, 10:30
Friday November 23, 2012
Multiplication quasioptimale d'opérateurs différentiels
A006, 10:30
slides: pdf (422 kb)
Thursday November 15, 2012
On polynomial systems arising from a Weil descent
A006, 14:00
slides: pdf (713 kb)
We provide theoretical and experimental evidence that the degrees of regularity of these systems are very low, in fact only slightly larger than the maximal degrees of the equations.
We then discuss cryptographic applications of (particular instances of) these systems to the hidden field equation (HFE) cryptosystem, to the factorization problem in SL(2, 2^{n}) and to the elliptic curve discrete logarithm over binary fields. In particular, we show (under a classical heuristic assumption in algebraic cryptanalysis) that an elliptic curve index calculus algorithm due to Claus Diem has subexponential time complexity O(2^{c n2/3 log n}) over the binary field GF(2^{n}), where c is a constant smaller than 2.
Based on joint work with JeanCharles Faugère, Ludovic Perret, JeanJacques Quisquater and Guénaël Renault.
Tuesday November 6, 2012
Accélération de l'arithmétique des corps CM quartiques
A006, 14:00
Thursday September 27, 2012
Recent advances in numerical linear algebra and communication avoiding algorithms
B013, 10:30
Friday July 20, 2012
Computing square roots over prime extension fields
A006, 10:30
In this talk, we present two new algorithms for computing square roots over finite fields of the form F_{q}, with q = p^{m} and where p is a large odd prime and m an even integer. The first algorithm is devoted to the case when q ≡ 3 (mod 4), whereas the second handles the complementary case when q ≡ 1 (mod 4). We include numerical comparisons showing the efficiency of our algorithms over the ones previously published in the open literature.
Friday June 29, 2012
Finding Optimal Formulae for Bilinear Maps
B013, 14:00
Friday June 29, 2012
Finding ECMFriendly Curves through a Study of Galois Properties
A006, 10:00
Wednesday June 20, 2012
Familles de courbes hyperelliptiques de genre 2, calcul explicite de l'ordre de la jacobienne et constructions pour les couplages
A006, 10:30
slides: pdf (656 kb)
Wednesday April 25, 2012
SSL/TLS: état des lieux et recommandations
A008, 10:30
Tuesday April 3, 2012
Algorithmique des groupes en calcul quantique
A006, 14:00
Friday March 30, 2012
Gröbner Bases and Linear Algebra
A006, 10:30

Algorithmic point of view: algorithms for computing efficiently Gröbner bases
(F4, F5, FGLM, ...) rely heavily on efficient linear algebra.
 The matrices generated by these algorithms have unusual properties: sparse, almost block triangular. We present a dedicated algorithm for computing Gaussian elimination of Gröbner bases matrices.
 By taking advantage of the sparsity of multiplication matrices in the classical FGLM algorithm we can design an efficient algorithm to change the ordering of a Gröbner basis. The algorithm is a related to multivariate generalization of the Wiedemann algorithm. When the matrices are not sparse, for generic systems, the complexity is Õ(D^{ω}) where D is the number of solutions and ω ≤ 2.3727 is the linear algebra constant.
 Mixing Gröbner bases methods and linear algebra technique for solving sparse linear systems leads to an efficient algorithm to solve Boolean quadratic equations over F_{2}; this algorithm is faster than exhaustive search by an exponential factor
 Application point of view: for instance, a generalization of the eigenvalue problem to several matrices – the MinRank problem – is at the heart of the security of many multivariate public key cryptosystems.
 Design of C library: we present a multi core implementation of these new algorithms; the library contains specific algorithms to compute Gaussian elimination as well as specific internal representation of matrices.The efficiency of the new software is demonstrated by showing computational results for well known benchmarks as well as some crypto applications.
Tuesday March 20, 2012
EdDSA signatures and Ed25519
A217, 15:00
slides: pdf (1050 kb)
Wednesday March 14, 2012
Les canaux auxiliaires, approche sous l'angle du rapport signalàbruit
A006, 10:30
Wednesday March 7, 2012
Implémentation efficace de la recherche de formules pour applications bilinéaires
A006, 10:30
Wednesday February 29, 2012
Codes d'authentification de message (suite et fin)
A006, 10:30
Thursday February 2, 2012
Tutoriel Coq (suite et fin)
B013, 10:00
Friday January 20, 2012
Presumably hard problems in multivariate cryptography
A006, 10:30
slides: pdf (2437 kb)
In this talk we focus on multivariate cryptography, a label covering all the (mostly publickey) schemes explicitly relying on the hardness of solving systems of polynomial equations in several variables over a finite field. The problem, even when restricted to quadratic polynomials, is wellknown to be NPcomplete. In the quadratic case, it is called MQ. Interestingly, most schemes in this area are not "provably secure", and a lot of them have been broken because they relied on another, less wellknown, computational assumption, the hardness of Polynomial Linear Equivalence (PLE), which is a higherdegree generalization the problem testing whether two matrices are equivalent.
In this talk I will present the algorithms I designed to tackle these two hard problems. I will show that 80 bits of security are not enough for MQ to be practically intractable, and I will present fasterthanbefore, sometimes practical algorithms for various flavors of PLE.
Wednesday November 30, 2011
ECM sur GPU
A006, 10:30
Friday October 28, 2011
Pairingbased algorithms for Jacobians of genus 2 curves with maximal endomorphism ring
A006, 11:00
Thursday October 6, 2011
Short Division of Long Integers (with David Harvey)
A006, 10:30
slides: pdf (1764 kb)
Thursday September 29, 2011
Efficient Software Implementation of Binary Field Arithmetic Using Vector Instruction Sets
B011, 10:30
slides: pdf (402 kb)
Wednesday July 13, 2011
Étude de stratégies de cofactorisation pour l'algorithme Function Field Sieve
A006, 10:30
slides: pdf (657 kb)
Thursday June 30, 2011
Thursday June 9, 2011
Une nouvelle construction géométrique de codes sur de petits corps
B013, 10:30
Tuesday June 7, 2011
Génération de schémas d'évaluation avec contraintes pour des expressions arithmétiques
A006, 10:30
slides: pdf (445 kb)
Monday May 30, 2011
Cryptanalyse d'ARMADILLO2
A217, 14:00
Monday May 30, 2011
RNS on Graphic Processing Units
A213, 09:30
Wednesday May 18, 2011
Middlebrow Methods for LowDegree Isogenies in Genus 2
A006, 10:30
Thursday May 5, 2011
Thursday April 21, 2011
Améliorations au problème du logarithme discret dans F_{p}^{*}
B013, 10:30
slides: pdf (306 kb)
Thursday April 14, 2011
Algébricité de la série génératrice complète des chemins de Gessel
B013, 10:30
slides: pdf (249 kb)
Wednesday March 30, 2011
The M4RI & M4RIE libraries for linear algebra over GF(2) and small extensions
A006, 10:30
slides: pdf (1881 kb)
Thursday February 17, 2011
FPGAspecific arithmetic pipeline design using FloPoCo
B013, 10:30
slides: pdf (869 kb)
This talk is addressing the programmability of arithmetic circuits on FPGAs. We present FloPoCo, a framework facilitating the design of custom arithmetic datapaths for FPGAs. Some of the features provided by FloPoCo are: an important basis of highly optimized arithmetic operators, a unique methodology for separating arithmetic operator design from frequencydirected pipelining the designed circuits and a flexible testbench generation suite for numerically validating the designs.
The framework is reaching maturity, so far being tested with success for designing several complex arithmetic operators including the floatingpoint squareroot, exponential and logarithm functions. Synthesis results capture the designed operator's flexibility: automatically optimized for several Altera and Xilinx FPGAs, wide range of target frequencies and several precisions ranging from single to quadruple precision.
Thursday January 27, 2011
Complétude des lois d'addition sur une variété abélienne
B013, 10:30
Friday January 21, 2011
Fully homomorphic encryption via ideals in number rings
A006, 10:30
Thursday January 20, 2011
ECC on small devices
B013, 10:30
Thursday December 9, 2010
Enjeux de conception des architectures GPGPU : unités arithmétiques spécialisées et exploitation de la régularité
A006, 10:30
slides: pdf (1216 kb)
Thursday December 2, 2010
Sur le type d'intersection de deux quadriques de P^{3}(R)
A006, 10:30
Thursday November 25, 2010
Calcul de traces de l'algorithme F4 et application aux attaques par décomposition sur courbes elliptiques
A006, 10:30
slides: pdf (1243 kb)
Monday November 8, 2010
Hachage vers les courbes elliptiques et hyperelliptiques
A006, 10:30
slides: pdf (396 kb)
Thursday November 4, 2010
Implementation of RSA 2048 on GPUs
A006, 10:30
slides: pdf (2765 kb)
Thursday October 14, 2010
Étude des systèmes polynomiaux intervenant dans le calcul d'indice pour la résolution du problème du logarithme discret sur les courbes
B200, 14:00
Friday July 30, 2010
Sélection polynomiale pour le crible NFS
B013, 11:00
Thursday July 15, 2010
Attempting to Run NFS with Many Linear Homogeneous Polynomials
A213, 16:00
Thursday July 15, 2010
Implantation de l'algorithme ECM sur GPU
A213, 14:00
Thursday June 17, 2010
Quelques astuces pour résoudre les systèmes polynomiaux dépendant de 2 variables
A008, 10:30
Thursday June 3, 2010
Influence du bruit sur le nombre de points extrêmes
C005, 10:30
slides: pdf (365 kb)
Friday May 28, 2010
Wednesday April 28, 2010
Une approche analytique au problème de la factorisation d'entiers
A006, 10:30
slides: pdf (471 kb)
Monday April 26, 2010
Calcul de groupe de classes d'idéaux de corps de nombres.
A006, 10:30
Friday April 9, 2010
Chebyshev Interpolation Polynomialbased Tools for Rigorous Computing
A006, 10:30
slides: pdf (690 kb)
A natural idea is to try to replace Taylor polynomials with better approximations such as minimax approximation, Chebyshev truncated series or interpolation polynomials. Despite their features, an analogous to Taylor models, based on such polynomials, has not been yet wellestablished in the field of validated numerics. In this talk we propose two approaches for computing such models based on interpolation polynomials at Chebyshev nodes.
We compare the quality of the obtained remainders and the performance of the approaches to the ones provided by Taylor models. We also present two practical examples where this tool can be used: supremum norm computation of approximation errors and rigorous quadrature.
This talk is based on a joint work with N. Brisebarre.
Wednesday March 31, 2010
Breaking ECC2K130
A006, 14:00
slides: pdf (280 kb)
In 2004 also all challenges of size 109 bits were solved but the 131bit challenges have so far all not been successfully targeted.
Since end of 2009 a group of several institutions is trying to solve the challenge ECC2K130, a discretelogarithm problem on a Koblitz curve over the field F_{2131}. In my talk I will describe the approach taken to solve this challenge and give details of the Pollard rho iteration function. Furthermore I will give implementation details on two different platforms, namely the Cell Broadband Engine and NVIDIA GPUs.
Friday March 26, 2010
Formules de Thomae et isogénies
A006, 10:00
slides: pdf (392 kb)
Friday March 19, 2010
Isogeny computation in small characteristic
A006, 10:30
The problem of finding explicit formulae expressing an isogeny between two elliptic curves has been studied by many. Vélu gave formulae for the case where the curves are defined over C; these formulae have been extended in works by Morain, Atkin and Charlap, Coley & Robbins to compute isogenies in the case where the characteristic of the field is larger than the degree of the isogeny.
The small characteristic case requires another treatment. Algorithms by Couveignes, Lercier, Joux & Lercier, Lercier & Sirvent give solutions to different instances of the problem. We review these strategies, then we present an improved algorithm based over Couveignes' ideas and we compare its performance to the other ones.
Friday March 5, 2010
The probability that a genus 2 curve has a Jacobian of prime order
A006, 10:00
slides: pdf (744 kb)
Tuesday March 2, 2010
Shimura's reciprocity law, Thetanullwerte and class invariants
A006, 10:30
In the second part, using higher degree reciprocity law I am going to introduce the possibility of generalizing the algorithmic approach of determining class invariants for elliptic curves with CM, to determining alternative class invariant systems for principally polarized simple abelian surfaces with CM.
Thursday February 11, 2010
Factorisation des entiers N = pq^{2} et applications cryptographiques
A006, 10:30
slides: pdf (537 kb)
Monday February 1, 2010
Intégration numérique rapide et prouvée — Application au calcul des périodes de courbes hyperelliptiques
A006, 10:30
Thursday December 10, 2009
Familles de courbes pour factorisation par ECM des nombres de Cunningham
A208, 10:30
Friday September 25, 2009
We present a FDECM algorithm allowing to remove — if they exist — all prime factors less than 2^{32} from a composite input number n. Trying to remove those factors naively either by trialdivision or by multiplying together all primes less than 2^{32}, then doing a GCD with this product both prove extremely slow and are unpractical. We will show in this article that with FDECM it costs about a hundred wellchosen elliptic curves, which can be very fast in an optimized ECM implementation with optimized B_{1} and B_{2} smoothness bounds. The speed varies with the size of the input number n. Special attention has also been paid so that our FDECM be the most implementationindependent possible by choosing a widespread ellipticcurve parametrization and carefully checking all results for smoothness with Magma. Finally, we have considered possible optimizations to FDECM first by using a rational family of parameters for ECM and then by determining when it is best to switch from ECM to GCD depending on the size of the input number n. To the best of our knowledge, this is the first detailed description of a fully deterministic ECM algorithm.
Wednesday September 23, 2009
Familles de courbes elliptiques adaptées à la factorisation des entiers
B100, 10:30
Thursday September 17, 2009
Generating elliptic curves with endomorphisms suitable for fast pairing computation
A006, 10:00
This presentation is about a kind of ordinary elliptic curves introduced by Scott at INDOCRYPT 2005. These curves' CM discriminant is 3 or 1, then they have endomorphism for reducing Miller's loop length to half. These curves are also restricted in terms of the form of group order. Therefore, these are generated by CocksPinch method. CocksPinch method is a general method to obtain elliptic curve parameters with rhovalue approximately 2. This method enables to fix group order, CM disciminant and embedding degree in advance as long as they meet the requirements. Elliptic curves introduced by Scott with CM discriminant 3, they were investigated by Scott and Takashima but CM discriminant 1 are not. In this presentation, we show the result of generating curve parameters with CM discriminant 1 and what amount of parameters meet the requirements.
Tuesday June 23, 2009
Gradual SubLattice Reduction and Applications
B011, 10:30
One of the primary uses of lattice reduction algorithms is to
approximate short vectors in a lattice. I present a new algorithm
which produces approximations of short vectors in certain lattices.
It does this by generating a reduced basis of a sublattice which is
guaranteed to contain all short vectors in the given lattice. This
algorithm has a complexity which is less dependent on the size of the
input basis vectors and more dependent on the size of the output
vectors.
To illustrate the usefulness of the new algorithm I will show how it
can be used to give new complexity bounds for factoring polynomials in
Z[x] and reconstructing algebraic numbers from
approximations.
Monday May 18, 2009
Architecture matérielle pour la cryptographie sur courbes elliptiques et RNS
C103, 16:00
slides: pdf (1027 kb)
Thursday April 30, 2009
On Hadamard's Maximal Determinant Problem
A006, 11:00
slides: pdf (3142 kb)
The Maximal Determinant Problem was first posed around 1898. It asks for
a square matrix of largest possible determinant, with the entries of the
matrix restricted to be drawn from the set {0, 1}, or equivalently {+1,
1}.
Emperical investigations show an intriguing amount of structure in this
problem, both in the numerical sequence of maximal determinants, and in
the corresponding maximal determinant matrices themselves. But naive
brute force search becomes infeasible beyond very small orders, due to
the exponential nature of the search space.
High and maximal determinant matrices are useful in applications,
particularly in statistics, which is one reason why it is desirable to
have at hand a means of constructing these matrices. For certain sparse
infinite subsequences of orders, constructive algorithms have been found
 some relating to finite fields. However progress over the last one
hundred years has been distinctly patchy, depending on elementary number
theoretic properties of the matrix order: particularly its remainder upon
division by four.
We discuss ways of setting up computations which may be feasible with
current computing power and yet still yield new maximal determinant
matrices that would not be accessible to a naive search.
Thursday March 26, 2009
Hardware Operators for PairingBased Cryptography – Part II: Because speed also matters –
A006, 10:30
slides: pdf (684 kb)
Originally introduced in cryptography by Menezes, Okamoto and Vanstone
(1993) then Frey and Rück (1994) to attack the discrete logarithm problem
over a particular class of elliptic curves, pairings have since then been
put to a constructive use in various useful cryptographic protocols such
as short digital signature or identitybased encryption. However,
evaluating these pairings relies heavily on finite field arithmetic, and
their computation in software is still expensive. Developing hardware
accelerators is therefore crucial.
In the second part of this doubletalk, we will focus on the other end of
the hardware design spectrum. While the first part (given by JeanLuc
Beuchat) presented a coprocessor which, although quite slow, would
strive to minimize the amount of hardware resources required to compute
the Tate pairing, in this second part we will describe another
coprocessor architecture, designed to achieve much lower computation
times, at the expense of hardware resources.
Thursday February 26, 2009
Hardware Operators for PairingBased Cryptography – Part I: Because size matters –
A208, 10:00
slides: pdf (676 kb)
Originally introduced in cryptography by Menezes, Okamoto and Vanstone
(1993) then Frey and Rück (1994) to attack the discrete logarithm problem
over a particular class of elliptic curves, pairings have since then been
put to a constructive use in various useful cryptographic protocols such
as short digital signature or identitybased encryption. However,
evaluating these pairings relies heavily on finite field arithmetic, and
their computation in software is still expensive. Developing hardware
accelerators is therefore crucial.
In this talk, we will then present a hardware coprocessor designed to
accelerate the computation of the Tate pairing in characteristics 2 and
3. As the title suggests, this talk will emphasize on reducing the
silicon footprint (or in our case the usage of FPGA resources) of the
circuit to ensure scalability, while trying to minimize the impact on the
overall performances.
Thursday November 6, 2008
Multiplieurs parallèles et pipelinés pour le calcul de couplage en caractéristiques 2 et 3
A006, 11:00
slides: pdf (872 kb)
Thursday October 16, 2008
Suites et fonctions holonomes : évaluation numérique et calcul automatique de bornes
A006, 10:30
Thursday June 26, 2008
Deformation techniques for triangular arithmetic
B200, 14:00
Friday May 23, 2008
arctan relations for computing pi.
A006, 10:00
slides: pdf (89 kb)
Wednesday May 14, 2008
Binary polynomial irreducibility tests avoiding GCDs.
A006, 14:00
Thursday April 10, 2008
Reconnaissance d'un code linéaire en bloc
A006, 10:30
Tuesday March 25, 2008
Chaines d'additions différentielles et multiplication de point sur les courbes elliptiques
A006, 10:30
Thursday February 14, 2008
Quelques systèmes de numération exotiques (et applications)
A006, 10:30
Thursday February 7, 2008
L'arithmétique flottante comme outil de preuve formelle
A006, 10:30
Thursday January 31, 2008
Toward a Rigorous Variation of Coppersmith's Algorithm on Three Variables
A006, 10:30
In 1996, Coppersmith introduced two lattice reduction based techniques to
find small roots in polynomial equations. One technique works for modular
univariate polynomials, the other for bivariate polynomials
over the integers. Since then, these methods have been used in a huge
variety of cryptanalytic applications. Some applications also use
extensions of Coppersmith's techniques on more variables. However, these
extensions are heuristic methods.
In this presentation, we present and analyze a new variation of
Coppersmith's algorithm on three variables over the integers. We also study
the applicability of our method to short RSA exponents
attacks. In addition to lattice reduction techniques, our method also uses
Gröbner bases computations. Moreover, at least in principle, it can be
generalized to four or more variables.
Thursday January 17, 2008
Arithmétique réelle exacte certifiée
A006, 10:30
Wednesday December 5, 2007
DBNS et cryptographie sur courbes elliptiques
A006, 10:30
Thursday November 29, 2007
Algèbre linéaire dense dans des petits corps finis: théorie et pratique.
B13, 10:30
Thursday November 8, 2007
Schéma de diffusion efficace basé sur des attributs
A006, 10:30
Monday June 18, 2007
Arithmetic Operators for PairingBased Cryptography
B13, 10:30
slides: pdf (625 kb)
Since their introduction in constructive cryptographic applications,
pairings over (hyper)elliptic curves are at the heart of an ever
increasing number of protocols. Software implementations being rather
slow, the study of hardware architectures became an active research
area. In this talk, we first describe an accelerator for the $\eta_T$
pairing over $\mathbb{F}_3[x]/(x^{97}+x^{12}+2)$. Our architecture is
based on a unified arithmetic operator which performs addition,
multiplication, and cubing over $\mathbb{F}_{3^{97}}$. This design
methodology allows us to design a compact coprocessor ($1888$ slices on
a VirtexII Pro~$4$ FPGA) which compares favorably with other solutions
described in the open literature. We then describe ways to extend our
approach to any characteristic and any extension field.
The talk will be based on the following research reports:
Thursday June 14, 2007
Quaternion Algebras and Qcurves
B13, 10:30
Let K be an imaginary quadratic field with Hilbert class field H and
maximal order OK. We consider elliptic curves E defined over H with the
properties that the endomorphism ring of E is isomorphic to OK and E is
isogenous to E over H for all \sigma\in Gal(H/K). Taking the Weil
restriction W_{H/K} of such an E from H to K, one obtains an abelian
variety whose endomorphism ring will be either a field or a quaternion
algebra. The question of which quaternion algebras may be obtained in
this way is one of our motivations.
For quaternion algebras to occur, the class group of K must have
noncyclic 2Sylow subgroup, the simplest possible examples occuring when
K has class number 4. In this case, investigating when W_{H/K}(E) has a
nonabelian endomorphism algebra is closely related to finding extensions
L/H such that Gal(L/K) is either the dihedral or quaternion group of
order 8.
Thursday June 7, 2007
Évaluation en virgule flottante de la fonction exponentielle sur FPGA
B13, 10:30
Tuesday June 5, 2007
Complex multiplication and canonical lifts
B200, 14:00
The $j$invariant of an elliptic curve with complex multiplication by $K$ is wellknown to generate the Hilbert class field of $K$. Such $j$invariants, or rather their minimal polynomials in $\ZZ[x]$, can be determined by means of complex analytic methods from a given CM lattice in $\CC$. A construction of CM moduli by $p$adic lifting techniques was introduced by Couveignes and Henocq. Efficient versions of onedimensional $p$adic lifting were developed by Br\"oker. These methods provide an alternative application of $p$adic canonical lifts, as introduced by Satoh for determining the zeta function of an elliptic curves $E/\FF_{p^n}$.
Construction of such defining polynomials for CM curves is an area of active interest for use in cryptographic constructions. Together with Gaudry, Houtmann, Ritzenthaler, and Weng, we generalised the elliptic curve CM construction to genus 2 curves using $2$adic canonical lifts. The output of this algorithm is data specifying a defining ideal for the CM Igusa invariants $(j_1,j_2,j_3)$ in $\ZZ[x_1,x_2,x_3]$. In contrast to Mestre's AGM algorithm for determining zeta functions of genus 2 curves $C/\FF_{2^n}$, this construction pursues the alternative application of canonical lifts to CM constructions. With Carls and Lubicz, I developed an analogous $3$adic CM construction using theta functions. In this talk I will report on recent progress and challenges in extending and improving these algorithms.
Thursday April 26, 2007
Relèvement canonique en caractéristique impaire.
B200, 10:30
Tuesday April 17, 2007
Schönhage proposed in the paper "Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2" (Acta Informatica, 1977) an O(n log(n) log(log(n))) algorithm to multiply polynomials over GF(2)[x]. We describe that algorithm and report on its implementation in NTL.
Tuesday April 17, 2007
A Multilevel Blocking Algorithm for DistinctDegree Factorization of Polynomials over GF(2).
B200, 10:30
Abstract: We describe a new multilevel blocking algorithm for distinctdegree factorization of polynomials over GF(2). The idea of the algorithm is to use one level of blocking to replace most GCD computations by multiplications, and a finer level of blocking to replace most multiplications by squarings (which are much faster than multiplications over GF(2)). As an application we give an algorithm that searches for all irreducible trinomials of given degree. Under plausible assumptions, the expected running time of this algorithm is much less than that of the classical algorithm. For example, our implementation gives a speedup of more than 60 over the classical algorithm for trinomials of degree 6972593 (a Mersenne exponent). [Joint work with Paul Zimmermann.]
Thursday March 15, 2007
Isogenies — surjective homomorphisms of algebraic groups with finite kernel — are of great interest in number theory and cryptography. Algorithms for computing with isogenies of elliptic curves are wellknown, but in higher dimensions, the situation is more complicated, and few explicit examples of nontrivial isogenies are known. We will discuss some of the computational issues, and describe some examples and applications of isogenies of Jacobians of hyperelliptic curves.
Thursday March 8, 2007
Problème du vecteur le plus court dans un réseau : analyse de l'algorithme de Kannan (travail commun avec D. Stehlé).
B011, 11:00
Thursday February 8, 2007
De l'arithmétique d'intervalles à la certification de programmes
C010, 11:00
Tuesday January 16, 2007
Une norme infinie certifiée pour la validation d'algorithmes numériques
B200, 14:45
Tuesday January 16, 2007
Automatisation du contrôle de précision et de la preuve pour les formats doubledouble et tripledouble
B200, 14:00
Tuesday January 16, 2007
Approximation polynomiale de fonctions continues et nombres flottants
B200, 11:00
Wednesday November 29, 2006
Tuesday October 10, 2006
On Deuring correspondences of algebraic function fields
B200, 14:00
Friday April 14, 2006
Cryptanalyse lineaire des algorithmes de chiffrement par bloc.
B200, 10:00
Thursday April 6, 2006
Évaluation précise de polynômes en précision finie
B200, 10:00
Monday March 27, 2006
Division without Multiplication in Factor Rings
B200, 11:00
Thursday March 23, 2006
Thursday March 16, 2006
The Number Field Sieve in the Medium Prime Case
B200, 14:00
Thursday February 16, 2006
Thursday January 5, 2006
Propriétés cryptographiques des fonctions booléennes symétriques.
A208, 11:00
Thursday November 24, 2005
Optimising the enhanced standard continuation of P1, P+1 and ECM
B200, 10:00
[1] P. L. Montgomery, Speeding the Pollard and elliptic Curve Methods of factorization, Math. Comp. 48 (177), 1987.
Wednesday November 23, 2005, informal workgroup
Construction Class Fields of Local Fields
B200, 10:00
Thursday October 13, 2005
Computing Hilbert class polynomials by floatingpoint approximations
B013, 16:00
Thursday October 6, 2005
Thursday September 29, 2005, informal workgroup
Thursday September 29, 2005, informal workgroup
Thursday September 22, 2005, informal workgroup
Thursday September 15, 2005, informal workgroup
Tuesday June 21, 2005
A propos de la preuve formelle du théorème des quatre couleurs
B13, 11:00
Tuesday June 21, 2005
Traitement d'inégalités réelles en Coq
B200, 14:00
Friday June 3, 2005, informal workgroup
à préciser
B200, 11:00
Thursday April 14, 2005
On the decisional xyzDiffie Hellman problem.
A006, 16:00
Digital signatures have the sometimes unwanted property of being universally verifiable by anybody having access to the signer's public key. In recent work with F. Laguillaumie and P. Pailler, we have proposed a signature scheme where the verification requires interaction with the signer. Its security relies on the « xyz » variant of the classical DiffieHellman problem. We present in this talk the underlying algorithmical problem within its cryptographical context, and give some assessment of its difficulty
Thursday April 7, 2005, informal workgroup
Study of BasiriEngeFaugèreGurel paper on arithmetic of C_{3,4} curves.
B200, 14:00
Wednesday March 23, 2005, informal workgroup
Study of P. L. Montgomery's paper: "Five, Six, and SevenTerm KaratsubaLike Formulae".
B200, 14:00
Thursday March 10, 2005, informal workgroup
Thursday March 3, 2005
Theta constants and Borchardt mean, applications.
B11, 10:30
A curve of genus g defined over the complex field C is isomorphic to a torus with g holes, or equivalently to a quotient of the form C^{g}/(Z^{g}.1⊕Z^{g}.τ), τ being a g×g matrix called a Riemann matrix.
When the genus g equals one, the computation of τ from the equation of an elliptic curve is one of the classical applications of the arithmeticogeometric mean (AGM). The AGM can be interpreted using functions called theta constants.
We show how this special case extends to higher genus, using a generalization of the AGM known as the Borchardt mean.
In particular, we develop an algorithm for computing genus 2 Riemann matrices in almost linear time. This algorithm can be implemented easily.
As we also show, this technique allows for rapid computation of modular forms and functions, and we discuss the applications thereof (construction of CM curves, explicit computation of isogenies, …).
© 2006– members of the projectteam ; valid XHTML 1.0, valid CSS