Monday November 23, 2015

Chenqi Mou (School of Mathematics and Systems Science, Beihang University, China)
Sparse FGLM algorithms for solving polynomial systems
B013, 14:00
Groebner basis is an important tool in computational ideal theory, and the term ordering plays an important role in the theory of Groebner bases. In particular, the common strategy to solve a polynomial system is to first compute the basis of the ideal defined by the system w.r.t. DRL, change its ordering to LEX, and perhaps further convert the LEX Groebner basis to triangular sets.
Given a zero-dimensional ideal I ⊂ 𝕂[x1,...,xn] 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 top-level algorithm that automatically detects which method to use depending on the input. As a by-product, 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(N1+n log(D)2)), where N1 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 Berlekamp-Massey-Sakata algorithm from Coding Theory to handle the multi-dimensional 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 π)D2+(n-1)/n).
This talk is based on joint work with Jean-Charles Faugere.

Monday November 16, 2015

Frédéric Bihan (Université de Savoie Mont Blanc)
Polynomial systems with many positive solutions from bipartite triangulations
A006, 10:30
We use a version of Viro's method to construct polynomial systems with many positive solutions. We show that if a polytope admits an unimodular regular triangulation whose dual graph is bipartite, then there exists an unmixed polynomial system with this polytope as Newton polytope and which is maximally positive in that all its toric complex solutions are in fact real positive solutions. We present classical families of polytopes which admit such triangulations. These examples give evidence in favor of a conjecture due to Bihan which characterizes affine relations inside the support of a maximally polynomial system. We also use our construction to get polynomial systems with many positive solutions considering a simplicial complex contained in a regular triangulation of the cyclic polytope. This is joint work with Pierre-Jean Spaenlehauer (INRIA Nancy).

Wednesday October 14, 2015

Jan Tuitman (Department of Mathematics, KU Leuven, Belgium)
Counting points on curves: the general case
B013, 10:30
slides: pdf (208 kb)
Kedlaya's algorithm computes the zeta function of a hyperelliptic curve over a finite field using the theory of p-adic cohomology. We have recently dev eloped and implemented a generalisation of this algorithm that works for (almost) any curve. First, we will outline the theory involved. Then we will describe our algorithm and illustrate the main ideas by giving some examples. Finally, if time permits, we will talk about some current and future work of ours with various coauthors on improving the algorithm and applying it in other settings.

Wednesday September 9, 2015

Roland Wen (Univ. of New South Wales, Sydney)
Engineering Cryptographic Applications: Leveraging Recent E-Voting Experiences in Australia to Build Failure-Critical Systems
A006, 10:30
Advanced, bespoke cryptographic applications are emerging for large-scale use by the general population. A good example is cryptographic electronic voting systems, which make extensive use of sophisticated cryptographic techniques to help attain strong security properties (such as secrecy and verifiability) that are required due to the failure-critical nature of public elections. Recently in Australia, cryptographic e-voting systems were used in two state elections: iVote, an Internet voting system, was used in New South Wales, and vVote, a polling place voting system, was used in Victoria.
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, large-scale system, there were barriers to applying appropriately rigorous engineering practices in the two Australian e-voting systems. But since these e-voting 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 e-voting experiences.

Thursday February 5, 2015

Matthieu Rambaud (Télécom ParisTech)
Comment trouver de bons algorithmes de multiplication par interpolation ?
A006, 10:30

Thursday November 20, 2014

Sebastian Kochinke (Universität Leipzig)
The Discrete Logarithm Problem on non-hyperelliptic Curves of Genus g > 3.
A006, 14:00
We consider the discrete logarithm problem in the degree-0 Picard group of non-hyperelliptic curves of genus g > 3. A well known method to tackle this problem is by index calculus. In this talk we will present two algorithms based on the index calculus method. In both of them linear systems of small degree are generated and then used to produce relations. Analyzing these algorithms leads to several geometric questions. We will discuss some of them in more detail and state further open problems. At the end we will show some experimental results.

Thursday November 20, 2014

Enea Milio (LFANT team, Institut de Mathématiques de Bordeaux)
Calcul des polynômes modulaires en genre 2
A006, 10:30

Monday November 17, 2014

Thomas Richard (CARAMEL team, LORIA)
Cofactorization strategies for NFS
B013, 14:00
Nowadays, when we want to factor large numbers, we use sieve algorithms like the number field sieve or the quadratic sieve. In these algorithms, there is an expensive part called the relation collection step. In this step, one searches a wide set of numbers to identify those which are smooth, i.e. integers where all prime divisors are less than a particular bound. In this search, a first step finds the smallest prime divisors with a sieving procedure and a second step tries to factor the remaining integers which are no longer divisible by small primes, using factoring methods like P-1, P+1 and ECM. This talk will introduce a procedure, following Kleinjung, to optimize the second step!

Thursday October 23, 2014

Andrea Miele (LACAL, EPFL, Lausanne)
Post-sieving on GPUs
A006, 10:30
slides: pdf (930 kb)
The number field sieve (NFS) is the fastest publicly known algorithm for factoring RSA moduli. We show how the post sieving step, a compute-intensive part of the relation collection phase of NFS, can be farmed out to a graphics processing unit. Our implementation on a GTX 580 GPU, which is integrated with a state-of-the-art NFS implementation, can serve as a cryptanalytic co-processor for several Intel i7-3770K quad-core CPUs simultaneously. This allows those processors to focus on the memory-intensive sieving and results in more useful NFS-relations found in less time.

Thursday September 11, 2014

Christian Eder (Department of Mathematics, University of Kaiserslautern)
Computing Groebner Bases
B013, 10:30
slides: pdf (7607 kb)
In 1965 Buchberger introduced a first algorithmic approach to the computation of Groebner Bases. Over the last decades optimizations to this basic attempt were found. In this talk we discuss two main aspects of the computation of Groebner Bases: Predicting zero reductions is essential to keep the computational overhead and memory usage at a low. We show how Faugère's idea, initially presented in the F5 algorithm, can be generalized and further improved. The 2nd part of this talk is dedicated to the exploitation of the algebraic structures of a Groebner Basis. Thus we are not only able to replace polynomial reduction by linear algebra (Macaulay matrices, Faugère's F4 algorithm), but we can also specialize the Gaussian Elimination process for our purposes.

Thursday July 3, 2014

Nicholas Coxon (CARAMEL team, LORIA)
Nonlinear polynomials for NFS factorisation
B013, 10:30
slides: pdf (596 kb)
To help minimise the running time of the number field sieve, it is desirable to select polynomials with balanced degrees in the polynomial selection phase. I will discuss algorithms for generating polynomial pairs with this property: those based on Montgomery's approach, which reduce the problem to the construction of small modular geometric progressions; and an algorithm which draws on ideas from coding theory.

Thursday June 19, 2014

Irene Márquez-Corbella (GRACE team, LIX, École Polytechnique)
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

Guillaume Moroz (Vegas team, LORIA)
Évaluation et composition rapide de polynômes
A006, 10:30

Thursday March 13, 2014

Pierre-Jean Spaenlehauer (CARAMEL team, LORIA)
A Newton-like iteration and algebraic methods for Structured Low-Rank Approximation
A006, 10:30
Given an linear/affine space of matrices E with real entries, a data matrix UE and a target rank r, the Structured Low-Rank Approximation Problem consists in computing a matrix ME which is close to U (with respect to the Frobenius norm) and has rank at most r. This problem appears with different flavors in a wide range of applications in Engineering Sciences and symbolic/numeric computations.
We propose an SVD-based 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 low-rank matrix completion (which are instances of Structured Low-Rank Approximation).
In a second part of the talk, we focus on the algebraic structure and on exact methods to compute symbolically the nearest structured low-rank matrix M to a given matrix UE 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

Armand Lachand (Équipe Théorie des Nombres, IECL)
Quelques perspectives mathématiques sur la sélection polynomiale dans le crible algébrique NFS
A006, 10:30

Thursday December 19, 2013

Luca De Feo (CRYPTO, PRiSM, Univ. Versailles Saint-Quentin)
Algorithms for Fp
A006, 10:30
Realizing in software the algebraic closure of a finite field Fp is equivalent to construct so called “compatible lattices of finite fields”, i.e. a collection of finite extensions of Fp together with embeddings FpmFpn whenever m | n.
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 quasi-optimal time.

Friday December 6, 2013

Cécile Pierrot (PolSys team, LIP6)
Crible Spécial sur Corps de Nombres (SNFS) – Application aux courbes elliptiques bien couplées.
A006, 13:00

Thursday November 28, 2013

Clément Pernet (AriC team, LIP, ENS Lyon)
Calcul de formes echelonnées et des profils de rang
A006, 10:30

Thursday November 7, 2013

Julia Pieltant (GRACE team, LIX, École Polytechnique)
Algorithme de type Chudnovsky pour la multiplication dans les extensions finies de Fq.
A006, 10:30

Friday July 19, 2013

Bastien Vialla (LIRMM)
Un peu d'algèbre linéaire
A006, 14:00

Wednesday July 17, 2013

Alice Pellet-Mary (CARAMEL team, LORIA)
Test rapide de cubicité modulaire
B013, 14:00

Tuesday July 16, 2013

Svyatoslav Covanov (CARAMEL team, LORIA)
Implémentation efficace d'un algorithme de multiplication de grands nombres
A006, 15:00

Monday July 15, 2013

Hamza Jeljeli (CARAMEL team, LORIA)
RNS Arithmetic for Linear Algebra of FFS and NFS-DL algorithms
B013, 15:30
Computing discrete logarithms in large cyclic groups using index-calculus-based methods, such as the number field sieve or the function field sieve, requires solving large sparse systems of linear equations modulo the group order. In this talk, we present how we use the Residue Number System (RNS) arithmetic to accelerate modular operations. The first part deals with the FFS case, where the matrix contains only small values. The second part discusses how we treat for NFS-DL, the particular dense columns corresponding to Schirokauer's maps, where the values are large.

Tuesday May 28, 2013

Mourad Gouicem (PEQUAN team, LIP6)
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

François Morain (GRACE team, LIX)
ECM using number fields
B200, 13:30

Thursday March 28, 2013

Antoine Joux (CryptoExperts / CRYPTO, PRiSM, Univ. Versailles Saint-Quentin)
Logarithmes discrets dans les corps finis. Application en caractéristique "moyenne".
A006, 10:30

Friday March 15, 2013

Adeline Langlois (AriC, LIP, ENS Lyon)
Classical Hardness of Learning with Errors
A006, 14:00
The decision Learning With Errors (LWE) problem, introduced by Regev in 2005 has proven an invaluable tool for designing provably secure cryptographic protocols. We show that LWE is classically at least as hard as standard worst-case lattice problems, even with polynomial modulus. Previously this was only known under quantum reductions.
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

Jérémy Parriaux (CRAN, Univ. de Lorraine)
Contrôle, synchronisation et chiffrement
A006, 13:30

Wednesday February 13, 2013

Emmanuel Jeandel (Équipe CARTE, LORIA)
Quête du plus petit jeu de tuiles apériodique
A006, 10:30

Thursday January 31, 2013

Maike Massierer (Mathematisches Institut, Universität Basel)
An Efficient Representation for the Trace Zero Variety
A006, 10:30
The hardness of the (hyper)elliptic curve discrete logarithm problem over extension fields lies in the trace zero variety. A compact representation of the points of this abelian variety is needed in order to accurately assess the hardness of the discrete logarithm problem there. Such representations have been proposed by Lange for genus 2 curves and by Silverberg for elliptic curves. We present a new approach for elliptic curves. It is made possible by a new equation for the variety derived from Semaev's summation polynomials. The new representation is optimal in the sense that it reflects the size of the group, it is compatible with the structure of the variety, and it can be computed efficiently.

Thursday January 17, 2013

Pierre-Jean Spaenlehauer (ORCCA, University of Western Ontario)
Résolution de systèmes polynomiaux structurés et applications en Cryptologie
B013, 13:00
slides: pdf (853 kb)

Thursday December 20, 2012

Alin Bostan (Projet SpecFun, INRIA Saclay)
Computer algebra for the enumeration of lattice walks
A008, 14:00
Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, computer algebra methods have been used to explore and solve a number of difficult questions related to lattice walks. In this talk, we will give an overview of recent results on structural properties and explicit formulas for generating functions of walks in the quarter plane, with an emphasis on the algorithmic methodology.

Thursday December 20, 2012

Mohab Safey El Din (Projet PolSys, LIP6, UPMC-IUF-INRIA)
Computer Algebra Algorithms for Real Solving Polynomial Systems: the Role of Structures
A008, 10:30
Real solving polynomial systems is a topical issue for many applications. Exact algorithms, using computer algebra techniques, have been deployed to answer various specifications such that deciding the existence of solutions, answer connectivity queries or one block-real quantifier elimination. In this talk, we will review some recent on-going works whose aims are to exploit algebraic and geometric properties in order to provide faster algorithms in theory and in practice.

Thursday November 29, 2012

Paul Zimmermann (Projet CARAMEL, LORIA)
Sélection polynomiale dans CADO-NFS
C005, 10:30

Friday November 23, 2012

Alexandre Benoit (Lycée Alexandre Dumas, Saint Cloud)
Multiplication quasi-optimale d'opérateurs différentiels
A006, 10:30
slides: pdf (422 kb)

Thursday November 15, 2012

Christophe Petit (Crypto Group, Université Catholique de Louvain)
On polynomial systems arising from a Weil descent
A006, 14:00
slides: pdf (713 kb)
Polynomial systems of equations appearing in cryptography tend to have special structures that simplify their resolution. In this talk, we discuss a class of polynomial systems arising after deploying a multivariate polynomial equation over an extension field into a system of polynomial equations over the ground prime field (a technique commonly called Weil descent).
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, 2n) 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(2c n2/3 log n) over the binary field GF(2n), where c is a constant smaller than 2.
Based on joint work with Jean-Charles Faugère, Ludovic Perret, Jean-Jacques Quisquater and Guénaël Renault.

Tuesday November 6, 2012

Hugo Labrande (ENS de Lyon)
Accélération de l'arithmétique des corps CM quartiques
A006, 14:00

Thursday September 27, 2012

Laura Grigori (Projet Grand Large, INRIA Saclay-Île de France, LRI)
Recent advances in numerical linear algebra and communication avoiding algorithms
B013, 10:30
Numerical linear algebra operations are ubiquitous in many challenging academic and industrial applications. This talk will give an overview of the evolution of numerical linear algebra algorithms and software, and the major changes such algorithms have undergone following the breakthroughs in the hardware of high performance computers. A specific focus of this talk will be on communication avoiding algorithms. This is a new and particularly promising class of algorithms, which has been introduced in the late 2008 as an attempt to address the exponentially increasing gap between computation time and communication time - one of the major challenges faced today by the high performance computing community. I will also discuss novel preconditioning techniques for accelerating the convergence of iterative methods.

Friday July 20, 2012

Francisco Rodríguez-Henríquez (CINVESTAV, IPN, México)
Computing square roots over prime extension fields
A006, 10:30
Taking square roots over finite fields is a classical number theoretical problem that has capture the attention of researchers across the centuries. Nowadays, the computation of square roots is especially relevant for elliptic curve cryptosystems, where hashing an arbitrary message to a random point that belongs to a given elliptic curve, point compression and point counting over elliptic curves, are among its most relevant cryptographic applications.
In this talk, we present two new algorithms for computing square roots over finite fields of the form Fq, with q = pm 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

Răzvan Bărbulescu (Projet CARAMEL, LORIA)
Finding Optimal Formulae for Bilinear Maps
B013, 14:00
We describe a unified framework to search for optimal formulae evaluating bilinear or quadratic maps. This framework applies to polynomial multiplication and squaring, finite field arithmetic, matrix multiplication, etc. We then propose a new algorithm to solve problems in this unified framework. With an implementation of this algorithm, we prove the optimality of various published upper bounds, and find improved upper bounds.

Friday June 29, 2012

Cyril Bouvier (Projet CARAMEL, LORIA)
Finding ECM-Friendly Curves through a Study of Galois Properties
A006, 10:00
In this paper we prove some divisibility properties of the cardinality of elliptic curves modulo primes. These proofs explain the good behavior of certain parameters when using Montgomery or Edwards curves in the setting of the elliptic curve method (ECM) for integer factorization. The ideas of the proofs help us to find new families of elliptic curves with good division properties which increase the success probability of ECM.

Wednesday June 20, 2012

Aurore Guillevic (Équipe Crypto, ENS / Laboratoire Chiffre, Thales)
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

Olivier Levillain (ANSSI)
SSL/TLS: état des lieux et recommandations
A008, 10:30

Tuesday April 3, 2012

Luc Sanselme (Lycée Henri Poincaré, Nancy)
Algorithmique des groupes en calcul quantique
A006, 14:00

Friday March 30, 2012

Jean-Charles Faugère (Projet PolSys, LIP6)
Gröbner Bases and Linear Algebra
A006, 10:30
There is a strong interplay between computing efficiently Gröbner bases and linear algebra. In this talk, we focus on several aspects of this convergence:
  • 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 F2; 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.
Joint works with S. Lachartre, C. Mou, P. Gaudry, L. Huot, G. Renault, M. Bardet, B. Salvy, P.J. Spaenlehauer and M. Safey El Din.

Tuesday March 20, 2012

Peter Schwabe (Academia Sinica, Taiwan)
EdDSA signatures and Ed25519
A217, 15:00
slides: pdf (1050 kb)
One of the most widely used applications of elliptic-curve cryptography is digital signatures. In this talk I will present the EdDSA signature scheme that improves upon previous elliptic-curve-based signature schemes such as ECDSA or Schnorr signatures in several ways. In particular it makes use of fast and secure arithmetic on Edwards curves, it is resilient against hash-function collisions and it supports fast batch verification of signatures. I will furthermore present performance results of Ed25519, EdDSA with a particular set of parameters for the 128-bit security level.

Wednesday March 14, 2012

Karim Khalfallah (ANSSI)
Les canaux auxiliaires, approche sous l'angle du rapport signal-à-bruit
A006, 10:30

Wednesday March 7, 2012

Jérémie Detrey (Projet CARAMEL, LORIA)
Implémentation efficace de la recherche de formules pour applications bilinéaires
A006, 10:30

Wednesday February 29, 2012

Marion Videau (Projets CARAMEL, LORIA)
Codes d'authentification de message (suite et fin)
A006, 10:30

Thursday February 2, 2012

Stéphane Glondu (Projets CASSIS/CARAMEL, LORIA)
Tutoriel Coq (suite et fin)
B013, 10:00

Friday January 20, 2012

Charles Bouillaguet (CRYPTO, PRiSM, Univ. Versailles Saint-Quentin)
Presumably hard problems in multivariate cryptography
A006, 10:30
slides: pdf (2437 kb)
Public-key cryptography relies on the existence of computationaly hard problems. It is not widely accepted that a public-key scheme is worthless without a "security proof", i.e., a proof that if an attacker breaks the scheme, then she solves in passing an instance of an intractable computational problem. As long as the hard problem is intractable, then the scheme is secure. The most well-known hardness assumptions of this kind are probably the hardness of integer factoring, or that of taking logarithms in certain groups.
In this talk we focus on multivariate cryptography, a label covering all the (mostly public-key) 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 well-known to be NP-complete. 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 well-known, computational assumption, the hardness of Polynomial Linear Equivalence (PLE), which is a higher-degree 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 faster-than-before, sometimes practical algorithms for various flavors of PLE.

Wednesday November 30, 2011

Cyril Bouvier (Projet CARAMEL, LORIA)
A006, 10:30
In this talk, I will present a new implementation of the Elliptic Curve Method algorithm (ECM) for graphic cards (GPU). This implementation uses Montgomery's curve, like GMP-ECM, but uses a different implementation and a different algorithm for the scalar multiplication. As there is no modular arithmetic library (like GMP) available for GPU, it was necessary to implement a modular arithmetic using array of unsigned integers from scratch, while taking into account constraints of GPU programming. The code, written for NVIDIA GPUs using CUDA, was optimized for factoring 1024 bits integers.

Friday October 28, 2011

Sorina Ionica (Projet CARAMEL, LORIA)
Pairing-based algorithms for Jacobians of genus 2 curves with maximal endomorphism ring
A006, 11:00
Using Galois cohomology, Schmoyer characterizes cryptographic non-trivial self-pairings of the ℓ-Tate pairing in terms of the action of the Frobenius on the ℓ-torsion of the Jacobian of a genus 2 curve. We apply similar techniques to study the non-degeneracy of the ℓ-Tate pairing restrained to subgroups of the ℓ-torsion which are maximal isotropic with respect to the Weil pairing. First, we deduce a criterion to verify whether the jacobian of a genus 2 curve has maximal endomorphism ring. Secondly, we derive a method to construct horizontal (ℓ, ℓ)-isogenies starting from a jacobian with maximal endomorphism ring. This is joint work with Ben Smith.

Thursday October 6, 2011

Paul Zimmermann (Projet CARAMEL, LORIA)
Short Division of Long Integers (with David Harvey)
A006, 10:30
slides: pdf (1764 kb)
We consider the problem of short division — i.e., approximate quotient — of multiple-precision integers. We present ready-to-implement algorithms that yield an approximation of the quotient, with tight and rigorous error bounds. We exhibit speedups of up to 30% with respect to GMP division with remainder, and up to 10% with respect to GMP short division, with room for further improvements. This work enables one to implement fast correctly rounded division routines in multiple-precision software tools.

Thursday September 29, 2011

Diego F. Aranha (Universidade de Brasília)
Efficient Software Implementation of Binary Field Arithmetic Using Vector Instruction Sets
B011, 10:30
slides: pdf (402 kb)
In this talk, we will describe an efficient software implementation of characteristic 2 fields making extensive use of vector instruction sets commonly found in desktop processors. Field elements are represented in a split form so performance-critical field operations can be formulated in terms of simple operations over 4-bit sets. In particular, we detail techniques for implementing field multiplication, squaring, square root extraction, half-trace and inversion and present a constant-memory lookup-based multiplication strategy. We illustrate performance with timings for scalar multiplication on a 251-bit curve and compare our results with publicly available benchmarking data.

Wednesday July 13, 2011

Benoît Gaudel (Projet CARAMEL, LORIA)
Étude de stratégies de cofactorisation pour l'algorithme Function Field Sieve
A006, 10:30
slides: pdf (657 kb)

Thursday June 30, 2011

Cyril Bouvier (Projet CARAMEL, LORIA)
B013, 10:00
slides: pdf (371 kb)

Thursday June 9, 2011

Alain Couvreur (Projet COCQ, Institut de Mathématiques de Bordeaux)
Une nouvelle construction géométrique de codes sur de petits corps
B013, 10:30

Tuesday June 7, 2011

Christophe Mouilleron (Projet Arénaire, LIP, ENS Lyon)
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

Marion Videau (ANSSI)
Cryptanalyse d'ARMADILLO2
A217, 14:00

Monday May 30, 2011

Hamza Jeljeli (LACAL, EPFL, Lausanne)
RNS on Graphic Processing Units
A213, 09:30

Wednesday May 18, 2011

Benjamin Smith (Projet TANC, LIX, École Polytechnique)
Middlebrow Methods for Low-Degree Isogenies in Genus 2
A006, 10:30
In 2008, Dolgachev and Lehavi published a method for constructing (ℓ,ℓ)-isogenies of Jacobians of genus 2 curves. The heart of their construction requires only elementary projective geometry and some basic facts about abelian varieties. In this talk, we put their method into practice, and consider what needs to be done to transform their method into a practical algorithm for curves over finite fields.

Thursday May 5, 2011

Xavier Pujol (Projet Arénaire, LIP, ENS Lyon)
Analyse de BKZ
B013, 10:30
slides: pdf (870 kb)
Strong lattice reduction is the key element for most attacks against lattice-based cryptosystems. Between the strongest but impractical HKZ reduction and the weak but fast LLL reduction, there have been several attempts to find efficient trade-offs. Among them, the BKZ algorithm introduced by Schnorr and Euchner in 1991 seems to achieve the best time/quality compromise in practice. However, no reasonable time complexity upper bound was known so far for BKZ. We give a proof that after Õ(n3/k2) calls to a k-dimensional HKZ reduction subroutine, BKZk returns a basis such that the norm of the first vector is at most ≈ γkn/2(k-1) × det(L)1/n. The main ingredient of the proof is the analysis of a linear dynamic system related to the algorithm.

Thursday April 21, 2011

Răzvan Bărbulescu (Projet CARAMEL, LORIA)
Améliorations au problème du logarithme discret dans Fp*
B013, 10:30
slides: pdf (306 kb)

Thursday April 14, 2011

Alin Bostan (Projet ALGORITHMS, INRIA Paris-Rocquencourt)
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

Martin Albrecht (Projet SALSA, LIP6)
The M4RI & M4RIE libraries for linear algebra over GF(2) and small extensions
A006, 10:30
slides: pdf (1881 kb)
In this talk we will give an overview of the M4RI and M4RIE libraries. These open-source libraries are dedicated to efficient linear algebra over small finite fields with characteristic two. We will present and discuss implemented algorithms, implementation issues that arise for these fields and also some ongoing and future work. We will also demonstrate the viability of our approach by comparing the performance of our libraries with the implementation in Magma.

Thursday February 17, 2011

Bogdan Pasca (Projet Arénaire, LIP, ENS Lyon)
FPGA-specific arithmetic pipeline design using FloPoCo
B013, 10:30
slides: pdf (869 kb)
In the last years the capacity of modern FPGAs devices has increased to the point that they can be used with success for accelerating various floating-point computations. However, ease of programmability has never rhymed with FPGAs. Obtaining good accelerations was most of the time a laborious and error-prone process.
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 frequency-directed pipelining the designed circuits and a flexible test-bench 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 floating-point square-root, 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

Christophe Arène (Institut de Mathématiques de Luminy)
Complétude des lois d'addition sur une variété abélienne
B013, 10:30

Friday January 21, 2011

Frederik Vercauteren (ESAT/COSIC, KU Leuven)
Fully homomorphic encryption via ideals in number rings
A006, 10:30
In this talk, I will review the concept of fully homomorphic encryption, describe its possibilities and then give a construction based on principal ideals in number rings. This is joint work with Nigel Smart.

Thursday January 20, 2011

Junfeng Fan (ESAT/COSIC, KU Leuven)
ECC on small devices
B013, 10:30
The embedded security community has been looking at the ECC ever since it was introduced. Hardware designers are now challenged by limited area (<15 kGates), low power budget (<100 μW) and sophisticated physical attacks. This talk will report the state-of-the-art ECC implementations for ultra-constrained devices. We take a passive RFID tag as our potential target. We will discuss the known techniques to realize ECC on such kind of devices, and what are the challenges we face now and in the near future.

Thursday December 9, 2010

Sylvain Collange (Arénaire, LIP, ENS Lyon)
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

Guillaume Batog (VEGAS, LORIA)
Sur le type d'intersection de deux quadriques de P3(R)
A006, 10:30

Thursday November 25, 2010

Vanessa Vitse (CRYPTO, PRiSM, Univ. Versailles Saint-Quentin)
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

Mehdi Tibouchi (Équipe Cryptographie, Laboratoire d'Informatique de l'ENS)
Hachage vers les courbes elliptiques et hyperelliptiques
A006, 10:30
slides: pdf (396 kb)

Thursday November 4, 2010

Marcelo Kaihara (LACAL, EPFL, Lausanne)
Implementation of RSA 2048 on GPUs
A006, 10:30
slides: pdf (2765 kb)
Following the NIST recommendations for Key Management (SP800-57) and the DRAFT recommendation for the Transitioning of Cryptographic Algorithms and Key Sizes (SP 800-131), the use of RSA-1024 will be deprecated from January 1, 2011. Major vendors and enterprises will start the transition to the next minimum RSA key size of 2048 bits, which is computationally much more expensive. This talk presents an implementation of RSA-2048 on GPUs and explores the possibility to alleviate the computationally overhead by offloading the operations on GPUs.

Thursday October 14, 2010

Louise Huot (Équipe SALSA, LIP6)
É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

Thomas Prest (Équipe CARAMEL, LORIA)
Sélection polynomiale pour le crible NFS
B013, 11:00

Thursday July 15, 2010

Peter Montgomery (Microsoft Research & CWI)
Attempting to Run NFS with Many Linear Homogeneous Polynomials
A213, 16:00

Thursday July 15, 2010

Julie Feltin (Équipe CARAMEL, LORIA)
Implantation de l'algorithme ECM sur GPU
A213, 14:00

Thursday June 17, 2010

Fabrice Rouillier (Projet SALSA, LIP6)
Quelques astuces pour résoudre les systèmes polynomiaux dépendant de 2 variables
A008, 10:30

Thursday June 3, 2010

Xavier Goaoc (Projet VEGAS, LORIA)
Influence du bruit sur le nombre de points extrêmes
C005, 10:30
slides: pdf (365 kb)

Friday May 28, 2010

Paul Zimmermann (Projet CARAMEL, LORIA)
1,82 ?
A006, 10:30
slides: pdf (308 kb)

Wednesday April 28, 2010

Francesco Sica (Department of Mathematics and Statistics, University of Calgary)
Une approche analytique au problème de la factorisation d'entiers
A006, 10:30
slides: pdf (471 kb)

Monday April 26, 2010

Jean-François Biasse (Projet TANC, LIX, École Polytechnique)
Calcul de groupe de classes d'idéaux de corps de nombres.
A006, 10:30

Friday April 9, 2010

Mioara Joldeş (Projet Arénaire, LIP, ENS Lyon)
Chebyshev Interpolation Polynomial-based Tools for Rigorous Computing
A006, 10:30
slides: pdf (690 kb)
Performing numerical computations, yet being able to provide rigorous mathematical statements about the obtained result, is required in many domains like global optimization, ODE solving or integration. Taylor models, which associate to a function a pair made of a Taylor approximation polynomial and a rigorous remainder bound, are a widely used rigorous computation tool. This approach benefits from the advantages of numerical methods, but also gives the ability to make reliable statements about the approximated function.
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 well-established 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

Peter Schwabe (Department of Mathematics and Computer Science, TU Eindhoven)
Breaking ECC2K-130
A006, 14:00
slides: pdf (280 kb)
In order to "increase the cryptographic community's understanding and appreciation of the difficulty of the ECDLP", Certicom issued several elliptic-curve discrete-logarithm challenges. After these challenges were published in 1997 the easy ones of less than 100 bits were soon solved — the last one in 1999.
In 2004 also all challenges of size 109 bits were solved but the 131-bit challenges have so far all not been successfully targeted.
Since end of 2009 a group of several institutions is trying to solve the challenge ECC2K-130, a discrete-logarithm problem on a Koblitz curve over the field F2131. 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

Romain Cosset (Projet CARAMEL, LORIA)
Formules de Thomae et isogénies
A006, 10:00
slides: pdf (392 kb)

Friday March 19, 2010

Luca De Feo (Projet TANC, LIX, École Polytechnique)
Isogeny computation in small characteristic
A006, 10:30
Isogenies are an important tool in the study of elliptic curves. As such their applications in Elliptic Curve Cryptography are numerous, ranging from point counting to new cryptographic schemes.
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

Wouter Castryck (Department of Mathematics, KU Leuven)
The probability that a genus 2 curve has a Jacobian of prime order
A006, 10:00
slides: pdf (744 kb)
To generate a genus 2 curve that is suitable for use in cryptography, one approach is to repeatedly pick a curve at random until its Jacobian has prime (or almost prime) order. Naively, one would expect that the probability of success is comparable to the probability that a randomly chosen integer in the according Weil interval is prime (or almost prime). However, in the elliptic curve case it was observed by Galbraith and McKee that large prime factors are disfavoured. They gave a conjectural formula that quantifies this effect, along with a heuristic proof, based on the Hurwitz–Kronecker class number formula. In this talk, I will provide alternative heuristics in favour of the Galbraith–McKee formula, that seem better-suited for generalizations to curves of higher genus. I will then elaborate this for genus 2. This is joint (and ongoing) research with Hendrik Hubrechts and Alessandra Rigato.

Tuesday March 2, 2010

Osmanbey Uzunkol (KANT Group, Institute of Mathematics, TU Berlin)
Shimura's reciprocity law, Thetanullwerte and class invariants
A006, 10:30
In the first part of my talk I am going to introduce the classical class invariants of Weber, and their generalizations, as quotients of values of "Thetanullwerte", which enables to compute them more efficiently than as quotients of values of the Dedekind η-function. Moreover, the proof that most of the invariants introduced by Weber are actually units in the corresponding ring class fields will be given, which allows to obtain better class invariants in some cases, and to give an algorithm that computes the unit group of corresponding ring class fields.
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

Fabien Laguillaumie (Algorithmique, GREYC, Univ. Caen Basse-Normandie)
Factorisation des entiers N = pq2 et applications cryptographiques
A006, 10:30
slides: pdf (537 kb)

Monday February 1, 2010

Pascal Molin (Institut de Mathématiques de Bordeaux)
Intégration numérique rapide et prouvée — Application au calcul des périodes de courbes hyperelliptiques
A006, 10:30

Thursday December 10, 2009

Éric Brier (Ingenico)
Familles de courbes pour factorisation par ECM des nombres de Cunningham
A208, 10:30

Friday September 25, 2009

Iram Chelli (CACAO)
Fully Deterministic ECM
A006, 10:30
slides: pdf (589 kb)

We present a FDECM algorithm allowing to remove — if they exist — all prime factors less than 232 from a composite input number n. Trying to remove those factors naively either by trial-division or by multiplying together all primes less than 232, 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 well-chosen elliptic curves, which can be very fast in an optimized ECM implementation with optimized B1 and B2 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 implementation-independent possible by choosing a widespread elliptic-curve 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

Răzvan Bărbulescu (CACAO)
Familles de courbes elliptiques adaptées à la factorisation des entiers
B100, 10:30

Thursday September 17, 2009

Tadanori Teruya (LCIS, University of Tsukuba, Japan)
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 Cocks-Pinch method. Cocks-Pinch method is a general method to obtain elliptic curve parameters with rho-value 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

Andy Novocin (ANR LareDa, LIRMM, Montpellier)
Gradual Sub-Lattice 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 sub-lattice 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

Nicolas Guillermin (Centre d'électronique de l'armement (CELAR), DGA)
Architecture matérielle pour la cryptographie sur courbes elliptiques et RNS
C103, 16:00
slides: pdf (1027 kb)

Thursday April 30, 2009

Judy-anne Osborn (Australian National University)
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

Jérémie Detrey (CACAO)
Hardware Operators for Pairing-Based 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 identity-based 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 double-talk, we will focus on the other end of the hardware design spectrum. While the first part (given by Jean-Luc Beuchat) presented a co-processor 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 co-processor architecture, designed to achieve much lower computation times, at the expense of hardware resources.

Thursday February 26, 2009

Jean-Luc Beuchat (Tsukuba)
Hardware Operators for Pairing-Based 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 identity-based 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 co-processor 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

Nicolas Estibals (ENS Lyon)
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

Marc Mezzarobba (Projet Algo)
Suites et fonctions holonomes : évaluation numérique et calcul automatique de bornes
A006, 10:30

Thursday June 26, 2008

Éric Schost (University of Western Ontario.)
Deformation techniques for triangular arithmetic
B200, 14:00
Triangular representations are a versatile data structure; however, even basic arithmetic operations raise difficult questions with such objects. I will present an algorithm for multiplication modulo a triangular set that relies on deformation techniques and ultimately evaluation and interpolation. It features a quasi-linear running time (without hidden exponential factor), at least in some nice cases. More or less successful applications include polynomial multiplication, operations on algebraic numbers and arithmetic in Artin-Schreier extensions.

Friday May 23, 2008

Joerg Arndt (Australian National University)
arctan relations for computing pi.
A006, 10:00
slides: pdf (89 kb)

Wednesday May 14, 2008

Joerg Arndt (Australian National University)
Binary polynomial irreducibility tests avoiding GCDs.
A006, 14:00

Thursday April 10, 2008

Mathieu Cluzeau (INRIA Rocquencourt, équipe SECRET)
Reconnaissance d'un code linéaire en bloc
A006, 10:30

Tuesday March 25, 2008

Nicolas Meloni (Université de Toulon)
Chaines d'additions différentielles et multiplication de point sur les courbes elliptiques
A006, 10:30

Thursday February 14, 2008

Laurent Imbert (LIRMM)
Quelques systèmes de numération exotiques (et applications)
A006, 10:30

Thursday February 7, 2008

Guillaume Melquiond (MSR-INRIA)
L'arithmétique flottante comme outil de preuve formelle
A006, 10:30

Thursday January 31, 2008

Aurélie Bauer (Université de Versailles Saint-Quentin-en-Yvelines, Laboratoire PRISM,)
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

Nicolas Julien (Project-team Marelle, INRIA Sophia Antipolis.)
Arithmétique réelle exacte certifiée
A006, 10:30

Wednesday December 5, 2007

Christophe Doche
DBNS et cryptographie sur courbes elliptiques
A006, 10:30

Thursday November 29, 2007

Clément Pernet
Algèbre linéaire dense dans des petits corps finis: théorie et pratique.
B13, 10:30

Thursday November 8, 2007

Thomas Sirvent
Schéma de diffusion efficace basé sur des attributs
A006, 10:30

Monday June 18, 2007

Jean-Luc Beuchat
Arithmetic Operators for Pairing-Based 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 Virtex-II 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

Ley Wilson
Quaternion Algebras and Q-curves
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 non-cyclic 2-Sylow subgroup, the simplest possible examples occuring when K has class number 4. In this case, investigating when W_{H/K}(E) has a non-abelian 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

Jeremie Detrey
Évaluation en virgule flottante de la fonction exponentielle sur FPGA
B13, 10:30

Tuesday June 5, 2007

David Kohel (Université de Sydney et UHP-Nancy 1)
Complex multiplication and canonical lifts
B200, 14:00

The $j$-invariant of an elliptic curve with complex multiplication by $K$ is well-known 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 one-dimensional $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

David Lubicz
Relèvement canonique en caractéristique impaire.
B200, 10:30

Tuesday April 17, 2007

Paul Zimmermann
Fast Multiplication over GF(2)[x]
B200, 14:00

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

Richard Brent
A Multi-level Blocking Algorithm for Distinct-Degree Factorization of Polynomials over GF(2).
B200, 10:30

Abstract: We describe a new multi-level blocking algorithm for distinct-degree 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

Ben Smith
Explicit isogenies of hyperelliptic Jacobians
B011, 10:30

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 well-known, but in higher dimensions, the situation is more complicated, and few explicit examples of non-trivial 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

Guillaume Hanrot
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

Guillaume Melquiond (Project-team Arénaire, INRIA Rhône-alpes.)
De l'arithmétique d'intervalles à la certification de programmes
C010, 11:00

Tuesday January 16, 2007

Sylvain Chevillard (speaker), Christoph Lauter (Project-team Arénaire, INRIA Rhône-alpes.)
Une norme infinie certifiée pour la validation d'algorithmes numériques
B200, 14:45

Tuesday January 16, 2007

Christoph Lauter (Project-team Arénaire, INRIA Rhône-alpes.)
Automatisation du contrôle de précision et de la preuve pour les formats double-double et triple-double
B200, 14:00

Tuesday January 16, 2007

Sylvain Chevillard (Project-team Arénaire, INRIA Rhône-alpes.)
Approximation polynomiale de fonctions continues et nombres flottants
B200, 11:00

Wednesday November 29, 2006

Cédric Lauradoux (Project-team Codes, INRIA Rocquencourt.)
Shift Registers Synthesis
A208, 09:00
Shift registers are very common hardware devices. They are always associated with a combinatorial/sequential feedback. Linear Feedback Shift Registers (LFSRs) are certainly the most famous setup amongst those circuits. LFSRs are used everywhere in communication systems: scramblers, stream-ciphers, spread spectrum, Built-in Self Test (BIST)... Despite their popularity, the impact of LFSRs characteristics has never been clearly studied. I have studied the LFSRs synthesis on Xilinx Spartan2E FPGA with several goals (area, critical path, throughput). Studying high throughtput synthesis is particularly interesting since it is a circuitous way to study software synthesis. I will describe which properties can be observed for both synthesis. In conclusion, other shift registers setups will be considered like Feedback with Carry Shift Registers (FCSRs) or Non Linear Feedback Shift Registers (NLFSRs).

Tuesday October 10, 2006

Marcus Wagner (Technische Universität Berlin)
On Deuring correspondences of algebraic function fields
B200, 14:00
Using Deurings theory of correspondences we are able to construct homomorphisms between the degree zero classgroups of function fields. Correspondences are divisors of function fields with transcendent constant fields of degree one. They form an entire ring which is for example in the case of elliptic function fields isomorphic to an order of an imaginary quadratic number field. In this talk we show how to compute endomporphisms of elliptic and hyperelliptic curves using correspondences.

Friday April 14, 2006

Michael Quisquater
Cryptanalyse lineaire des algorithmes de chiffrement par bloc.
B200, 10:00

Thursday April 6, 2006

Stef Graillat
Évaluation précise de polynômes en précision finie
B200, 10:00

Monday March 27, 2006

Christopher Wolf
Division without Multiplication in Factor Rings
B200, 11:00
In a factor ring, i.e., in a polynomial ring F[z]/(m) or the integer ring Z_n, the conventional way of performing division a/b consists of two steps: first, the inverse b^{-1} is computed and then the product ab^{-1}. In this talk we describe a technique called "direct division" which computes the division a/b for given a,b directly, only using addition and multiplication in the underlying structure, i.e., finite field operations in F for the polynomial ring F[z]/(m) and addition and multiplication by 2 in the integer ring Z_n. This technique requires that the module m is not divisible by z, and the module n is odd.

Thursday March 23, 2006

Benoît Daireaux
Analyse dynamique des algorithmes euclidiens
B200, 14:00
slides: pdf (522 kb)

Thursday March 16, 2006

Frederik Vercauteren
The Number Field Sieve in the Medium Prime Case
B200, 14:00

Thursday February 16, 2006

Thomas Plantard
Arithmétique modulaire pour la cryptographie.
A208, 10:00
slides: pdf (966 kb)

Thursday January 5, 2006

Marion Videau (Project-team Codes, INRIA Rocquencourt.)
Propriétés cryptographiques des fonctions booléennes symétriques.
A208, 11:00

Thursday November 24, 2005

Alexander Kruppa (Technische Universität München)
Optimising the enhanced standard continuation of P-1, P+1 and ECM
B200, 10:00
The enhanced standard continuation of the P-1, P+1 and ECM factoring methods chooses pairs (a,b), where a is a multiple of a suitably chosen d, so that every prime in the desired stage 2 interval can be written as a-b. Montgomery [1] showed how to include more than one prime per (a,b) pair by instead evaluating f(a)-f(b) so that this bivariate polynomial has algebraic factors. However, he restricts his analysis to the algebraic factors a-b and a+b, and considers only prime values taken by these factors. We present a framework for generalising Montgomery's ideas by choosing (a,b) pairs as nodes in a partial cover of a bipartite graph, which allows utilising large prime factors of composite values, and algebraic factors of higher degree.
[1] P. L. Montgomery, Speeding the Pollard and elliptic Curve Methods of factorization, Math. Comp. 48 (177), 1987.

Wednesday November 23, 2005, informal workgroup

Sebastian Pauli (Technische Universität Berlin)
Construction Class Fields of Local Fields
B200, 10:00
Let K be a p-adic field. We give an explicit characterization of the abelian extensions of K of degree p by relating the coefficients of the generating polynomials of extensions L/K of degree p to the norm group N_{L/K}(L^*). This is applied in the construction of class fields of degree p^m.

Tuesday November 8, 2005, informal workgroup

to be announced
B200, 16:00
to be announced

Thursday October 13, 2005

Andreas Enge ( project-team TANC, INRIA Futurs, LIX)
Computing Hilbert class polynomials by floating-point approximations
B013, 16:00

Thursday October 6, 2005

Florian Hess (Technische Universität Berlin)
Arithmetic on general curves
B200, 10:00
The talk surveys various algorithms for computing in the divisor class groups of general non singular curves and gives a running time discussion.

Thursday September 29, 2005, informal workgroup

On finit l'exposé d'il y a deux semaines.
B200, 11:00

Thursday September 29, 2005, informal workgroup

On finit l'exposé de la semaine dernière.
B200, 10:00

Thursday September 22, 2005, informal workgroup

Calcul de fonctions holonomes en O(M(n) log(n)3)
A006, 10:00

Thursday September 15, 2005, informal workgroup

Fonctions thétas et formules efficaces pour loi de groupe en genre 2.
B200, 10:30

Tuesday June 21, 2005

Benjamin Werner ( LogiCal project-team, INRIA Futurs, LIX)
A propos de la preuve formelle du théorème des quatre couleurs
B13, 11:00

Tuesday June 21, 2005

Roland Zumkeller (Projet LogiCal, INRIA Futurs, LIX)
Traitement d'inégalités réelles en Coq
B200, 14:00

Friday June 3, 2005, informal workgroup

Julien Cochet
à préciser
B200, 11:00

Thursday April 14, 2005

Damien Vergnaud (LMNO, CNRS / Université de Caen.)
On the decisional xyz-Diffie 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 Diffie-Hellman 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

Jean-Yves Degos
Study of Basiri-Enge-Faugère-Gurel paper on arithmetic of C3,4 curves.
B200, 14:00

Wednesday March 23, 2005, informal workgroup

Study of P. L. Montgomery's paper: "Five, Six, and Seven-Term Karatsuba-Like Formulae".
B200, 14:00

Thursday March 10, 2005, informal workgroup

Study of the security proofs of OAEP and OAEP+
B200, 14:00

Thursday March 3, 2005

Régis Dupont ( project-team TANC, INRIA Futurs, LIX)
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 Cg/(Zg.1⊕Zg.τ), τ 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 arithmetico-geometric 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, …).

Last modification: Mon 01 Feb 2016 10:42:01 PM CET
© 2006– members of the project-team ; valid XHTML 1.0, valid CSS