Some computations require more precision than the 53 bits provided by the IEEE 754 double precision arithmetic (binary64), widely available in hardware. When an arbitrarily large precision is required, multi-precision floating point libraries, such as MPFR, are particularly useful. However, MPFR is implemented using only integer arithmetic, which is not as much optimized as floating point arithmetic on modern processors. If only a few hundreds bits are needed, faster alternatives using only floating point arithmetic exist, such as the well known qd library developed by Bailey and his co-authors. This library provides both double-double and quad-double arithmetics that roughly simulate twice (106 bits) and four times (212 bits) the IEEE 754 double precision, respectively. Double-double and quad-double numbers are a special case of floating point expansions, which consists in representing a rational number as an unevaluated sum of floating point numbers. Another alternative is the use of error-free transformations and compensation techniques to simulate an increased working precision, and we used this approach in this work.

In this talk, we focus on the computation of dot products between vectors of floating point expansions. We present alternatives to the algorithms obtained using directly double-double and quad-double arithmetics from the qd library: our aim is to trade off speed against a moderate loss of accuracy. Of course, we always keep the loss of accuracy under control by providing forward error bounds for our algorithms. The algorithm we present provides a speedup of 2 compared to the qd library, while maintaining roughly the same accuracy. This speedup is obtained using only basic programming techniques, and even higher speedups can be obtained by using vector instruction sets (AVX2 or AVX512 in particular) available on modern computers.

On a computer, real numbers are usually represented by a finite set of numbers called floating-point numbers. When one performs an operation on these numbers, such as an evaluation by a function, one returns a floating-point number, hopefully close to the mathematical result of the operation. Ideally, the returned result should be the exact rounding of this mathematical value. If we’re only allowed a unique and fast evaluation (a constraint often met in practice), one knows how to guarantee such a quality of results for arithmetical operations like \(+, -, x, /\) and square root but, as of today, it is still an issue when it comes to evaluate an elementary function such as cos, exp, cube root for instance. This problem, called Table Maker’s Dilemma, is actually a diophantine approximation problem. It was tackled, over the last fifteen years, by V. Lefèvre, J.M. Muller, D. Stehlé, A. Tisserand and P. Zimmermann (LIP, ÉNS Lyon and LORIA, Nancy), using tools from algorithmic number theory. Their work made it possible to partially solve this question but it remains an open problem. In this talk, I will present an ongoing joint work with Guillaume Hanrot (ÉNS Lyon, LIP, AriC) that improve on a part of the existing results.

Finding a short non zero vector in an Euclidean lattice is a well-studied problem which has proven useful to construct many cryptographic primitives. The current best asymptotic algorithm to find a relatively short vector in an arbitrary lattice is the BKZ algorithm. This algorithm recovers a vector which is at most \(2^{n^{\alpha}}\) times larger than the shortest non zero vector in time \(2^{n^{1-\alpha}}\) for any \(\alpha\) between 0 and 1.

In order to gain in efficiency, it is sometimes interesting to use structured lattices instead of general lattices. An example of such structured lattices are principal ideal lattices. One may then wonder whether, on the security front, it is easier to find short vectors in a structured lattice or not. Until 2016, there was no known algorithm which would perform better on principal ideal lattices than the BKZ algorithm (either classically or quantumly). In 2016, Cramer et al. proposed a quantum algorithm that finds a \(2^{\sqrt n}\) approximation of the shortest non zero vector in polynomial time. However, the BKZ algorithm remained the best algorithm in the classical setting or for approximation factor smaller than \(2^{\sqrt n}\) in the quantum setting.

In this talk, I will present an algorithm that generalizes the one of Cramer et al. and improves upon the BKZ algorithm for principal ideal lattices, both quantumly and classically. This algorithm is heuristic and non uniform (or equivalently it needs an exponential pre-processing time).

The security of most public-key cryptography relies on the difficulty of mathematical problems, among which the discrete logarithm problem in finite fields. The number field sieve (NFS) is the most efficient known algorithm for this problem for a large range of finite fields. Since its introduction in the 90’s, NFS has evolved, both theoretically and practically. These improvements force cryptographers to reassess key-sizes of cryptosystems.

In this talk, we will first introduce the key notions of the index-calculus algorithms, the family of algorithms to which NFS belongs. Then, we will describe recent progress related to NFS. Finally, we will conclude by giving ideas of how pairing-based cryptography is assessed, based on the works of Menezes—Sarkar—Singh and Barbulescu—Duquesne.

In some situations the result of a linear algebra computation may be known to be almost correct – that is, correct except in a few positions of the output matrix. One example is in distributed computing, where some nodes in a cluster may return incorrect results; another is in integer computations where only a few entries may be large enough to require an additional prime’s worth of Chinese remaindering. We present new algorithms to use the almost-correct result of a matrix product or inverse to recover the completely-correct result, whose running time is softly-linear in the size of the matrix when the number of errors is sufficiently small. Our algorithms build on the prior work by Gasieniec et al (Algorithmica 2017) for error-correcting matrix multiplication, and we are now able to effectively handle sparsity in the inputs and outputs, as well as incorporate fast matrix multiplication so that the cost scales well even with a large number of errors. The key underlying tools come from sparse polynomial interpolation and sparse low-rank linear algebra.

Floating-point or fixed-point computations are an integral part of many embedded and scientific computing applications, as are the roundoff errors they introduce. They expose an interesting tradeoff between efficiency and accuracy: the more precision we choose, the closer the results will be to the ideal real arithmetic, but the more costly the computation becomes. Unfortunately, the unintuitive and complex nature of finite-precision arithmetic makes manual optimization infeasible such that automated tool support is indispensable.

This talk presents an overview of Daisy, a framework for sound accuracy analysis and optimization of finite-precision programs. We will provide a high-level view of its main features: roundoff error analysis as well as rewriting and mixed-precision optimization.

Short talks (10’ + 5’ for questions) when people are back from a conference, on talks they attended and found interesting. We will have, by alphabetical order :

• Elena Kirshanova on «A practical cryptanalysis of Walnat» by Daniel Hart, Do Hoon Kim, Giacomo Micheli, Guillermo Pascual Perez, Christophe Petit, Yuxuan Quek; presented at PKC18;
• Fabrice Mouhartem on «Post-Quantum Security of Fiat-Shamir» by Dominique Unruh; presented at Asiacrypt 2017;
• Bruno Salvy on «Arctic curves in path models from the tangent method» by Philippe Di Francesco and Matthew F. Lapa; presented at a Workshop on “Computer Algebra in Combinatorics”, Vienna 2017;
• Wen Weiqiang on «Fully Homomorphic Encryption from the Finite Field Isomorphism Problem» by Yarkın Doröz, Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, Berk Sunar, William Whyte, Zhenfei Zhang; presented at PKC’18.

The asymptotic behaviour of a solution to a linear recurrence with polynomial coefficients can be decomposed into a not-so-difficult part that depends on the recurrence but not on the initial conditions and a more difficult part depending on the initial conditions. For the first one, several algorithms exist. In general, the second part can be dealt with numerically and in a certified way rather efficiently. Diagonals of rational functions form an important class of sequences solutions of such recurrences for which more is possible. This class generalizes that of sequences of coefficients of algebraic power series, which it contains. It enjoys very special arithmetic and analytic properties. Its elements appear frequently in combinatorics, notably as multiple binomial sums, as well as in number theory, e.g., Apéry’s sequences in his proof of the irrationality of \(\zeta(3)\). The asymptotic analysis of diagonals, in simple but frequent cases, can be performed automatically using the technology of Analytic Combinatorics in Several Variables of Pemantle and Wilson, together with modern tools of computer algebra. The talk will give an overview of the context and of recent work in this area.

We discuss arbitrary-precision numerical integration with rigorous error bounds in the framework of ball arithmetic. A new implementation has recently been added to the Arb library. Rapid convergence is ensured for piecewise complex analytic integrals by use of the Petras algorithm, which combines adaptive bisection with degree-adaptive Gaussian quadrature where error bounds are determined via complex magnitudes without evaluating derivatives. The code is general, easy to use, and efficient, often outperforming existing non-rigorous software. We discuss the pros and cons of this approach and consider some applications to special functions and computational number theory.

The notion of displacement rank provides a uniform way to deal with various classical matrix structures (such as Toeplitz, Hankel, Vandermonde, Cauchy) and allows for various generalizations. In this talk, we will review some recent progress in the design of asymptotically fast algorithms for multiplying and inverting such matrices. In particular, for \(n\) by \(n\) matrices of displacement rank \(\alpha\), we will see that the arithmetic cost of such operations can be reduced from about \(\alpha^2 n\) (up to log factors) down to \(\alpha^{\omega-1} n\), where \(\omega < 2.373\) is the exponent of (dense, unstructured) matrix multiplication.

(Based on joint work with A. Bostan, C. Mouilleron, and E. Schost.)

In this talk, we will continue our exposition of validated numerics, and focus on solving systems of nonlinear equations. We will state and prove the properties of the set-valued Newton operator, and show a nice variant of it (the Krawczyk operator). We will also talk about weaker methods based on the implicit function theorem that work in harder situations such as when a bifurcation of the solutions takes place. Again – the talk will be based upon concrete examples, and some small computer demo will illustrate the presented methods.

An algorithm is presented for computing the resultant of two generic bivariate polynomials over a field \(\mathbb{K}\).

For such \(p\) and \(q\) in \(\mathbb{K}[x,y]\) of degree \(d\) in \(x\) and \(n\) in \(y\), the algorithm computes the resultant with respect to \(y\) using \((n^{2 – 1/\omega} d) ^{1+o(1)}\) arithmetic operations in \(\mathbb{K}\), where two \(n\times n\) matrices are multiplied using \(O(n^{\omega})\) operations. Previous algorithms from the early 1970’s required time \((n^{2} d) ^{1+o(1)}\).

We also discuss some extensions of the approach to the computation of characteristic polynomials of generic structured matrices and in univariate quotient algebras.

My interest in minimax approimation started with my undergraduate thesis with Garrett Birkhoff at Harvard in 1977 and continues strong with the exciting new algorithm developed with Filip, Nakatsukasa, and Beckermann. This talk will collect observations about many aspects of this problem — both real and complex, polynomial and rational.

Aggarwal, Joux, Prakash and Santha recently introduced a new potentially quantum-safe public-key cryptosystem, and suggested that a brute-force attack is essentially optimal against it. They consider but then dismiss both Meet-in-the-Middle attacks and LLL-based attacks. Very soon after their paper appeared, Beunardeau et al. proposed a practical LLL-based technique that seemed to significantly reduce the security of the AJPS system.

We do two things. First, we show that a Meet-in-the-Middle attack can also be made to work against the AJPS system, using locality-sensitive hashing to overcome the difficulty that Aggarwal et al. saw for such attacks. We also present a quantum version of this attack. Second, we give a more precise analysis of the attack of Beunardeau et al., confirming and refining their results.

We study the accuracy of a classical approach to computing complex square-roots in floating-point arithmetic.
Our analyses are done in binary floating-point arithmetic in precision \(p\), and we assume that the (real) arithmetic operations \(+\), \(-\), \(\times\), \(\div\), \(\sqrt{ }\) are rounded to nearest, so the unit roundoff is \(u = 2^{-p}\).
We show that in the absence of underflow and overflow, the componentwise and normwise relative errors of this approach are at most \(\frac{7}{2}u\) and \(\frac{\sqrt{37}}{2}u\), respectively, and this without having to neglect terms of higher order in \(u\). We then provide some input examples showing that these bounds are reasonably sharp for the three basic binary interchange formats (binary32, binary64, and binary128) of the IEEE 754 standard for floating-point arithmetic. Finally, we consider another, slightly more accurate algorithm.

E-functions are power series with algebraic Taylor coefficients at the origin (satisfying certain growth conditions) and solutions of linear differential equations with polynomial coefficients. Siegel defined them in 1929 to generalize the diophantine properties of the exponential function, which takes transcendental values at any non-zero algebraic point. The situation is more complicated in general, as an E-function may sometimes return an algebraic value when evaluated at a non-zero algebraic point. In this talk, I will first explain the classical Diophantine results for E-functions. I will then present an algorithm which, given an E-function \(F(z)\) as input, outputs the finite list of algebraic numbers \(A\) such that \(F(A)\) is algebraic.

This is a joint work with Boris Adamczewski (CNRS et Université Lyon 1).

Learning With Errors is a popular security assumption for post-quantum cryptographic schemes: informally, an integer solution of a “noisy” linear system must be found. It is based on hard problems on Euclidean lattices, and it allows for a lot of functionalities in cryptography. Structured variants based on algebraic number theory have been introduced to improve time and memory efficiency. However, the addition of new mathematical objects such as number fields/rings has led to several possible security assumptions, and the link between them is not always clear.

I will present recent results toward the clarification of the situation. For a large familyof number fields, we showed that all versions of the problem are equivalent (up to polynomial increases in the noise, and up to non-uniformity of some of the underlying reductions). Our reductions rely on mathematical tools, some of them being new in the Ring-based LWE context, such as perturbation techniques for polynomials.

Based on a joint work with Miruna Rosca and Damien Stehlé.

See the web page dedicated to this day.

In this talk, we will cover the fundamentals of validated numerics, namely the inclusion principle and its consequences for mathematical proofs. In particular, we will talk about the set-valued Newton operator, and how it comes into play in many computer-assisted proofs. Again – the talk will be based upon concrete examples, and some small computer demo will illustrate the presented methods.

I will begin with a review of rational functions in numerical computation, including a review of twelve applications where they are useful and of two famous problems of rational approximation theory. Then we find ourselves with an “inverse Yogiism”. Although it is mathematically correct that a rational function is a quotient \(r = p/q\) of two polynomials, representations of this form are numerically unstable in precisely the cases where rational functions should be most powerful. A better alternative is a barycentric representation \(r = n/d\) in which \(n\) and \(d\) are partial fraction sums, and this leads to the exciting new “AAA algorithm”, which we will explain and demonstrate. This is joint work with Silviu Filip, Yuji Nakatsukasa, and Olvier Séte.

Short talks (10’ + 5’ for questions) when people are back from a conference, on talks they attended and found interesting. We will have, by alphabetical order :

• Paola Boito on «Solving large scale Lyapunov and Sylvester equations with quasiseparable coefficients» by Stefano Massei at Structured Matrices in Numerical Linear Algebra;Abstract: Let us consider a Sylvester matrix equation \(AX+XB=C\) where the coefficients \(A\), \(B\) and \(C\) are matrices with low-rank off-diagonal blocks. What can be said about the rank structure of the solution \(X\)? It turns out that, under suitable hypotheses, \(X\) inherits a rank structure as well. The main idea of the proof relies on a recent result by Beckermann and Townsend on displacement structured matrices.
• Elena Kirshanova on «Grover Meets Simon – Quantumly Attacking the FX-construction» by Gregor Leander and Alexander May,to be presented at AsiaCrypt’17;
• Benoît Libert on «Asymptotically Compact Adaptively Secure Lattice IBEs and Verifiable Random Functions via Generalized Partitioning Techniques» by Shota Yamada at IACR-CRYPTO-2017;
• Nathalie Revol on «Utah Floating-Point Toolset» by Zvonimir Rakamaric at Dagstuhl Seminar 17352 – Analysis and Synthesis of Floating-point Programs.

See https://raim2017.sciencesconf.org/

See http://perso.ens-lyon.fr/damien.stehle/LATTICE_MEETINGS.html

Chebyshev series are the basic tool for working with functions on a real interval — the equivalent of Fourier series but without the assumption of periodicity. They are also the basis of the software system Chebfun. We review the properties of Chebyshev series, using Chebfun to illustrate them, and then discuss the surprisingly challenging problem of “chopping a Chebyshev series” to obtain a representation to a prescribed precision, which is an analogue for functions of the floating-point rounding of real numbers.
We close with a few words about Faber’s theorem of 1914 and “inverse Yogiisms”.

In this talk, I will give a short introduction to the field of validated numerics. We will take a top-down approach, and begin by studying some natural mathematical problems that arise in the study of dynamical systems. Such problems invariably lead to some numerical challenges, and we will see how they can be addressed in the framework of validated numerics. Everything will be explained from “first principles”, so no prior knowledge of dynamical systems is needed.

Short talks (10’ + 5’ for questions) when people are back from a conference, on talks they attended and found interesting. We will have, by alphabetical order :

• Vincent Lefèvre on « Multiple-precision floating-point arithmetic on SIMD processors » by van der Hoeven at Arith;
• Jean-Michel Muller on « The rise of multi precision computations » by Higham at Arith;
• Bruno Salvy on « A universal ordinary differential equation » by Bournez & Pouly at FoCM;
• Damien Stehlé on « Gaussian Sampling over the Integers: Efficient, Generic, Constant-Time » by Micciancio & Walter at Crypto.

This talk is part of the Monthly Lattice Meetings.

In this work we focus on the solution of shifted quasiseparable systems and of more general parameter dependent matrix equations with quasiseparable representations. We propose an efficient algorithm exploiting the invariance of the quasiseparable structure under diagonal shifting and inversion. This algorithm is applied to compute various functions of matrices. Numerical experiments show the effectiveness of the approach.
This is joint work with Luca Gemignani (Pisa) and Yuli Eidelman (Tel Aviv).

Given a sequence represented by a linear recurrence with polynomial coefficients and sufficiently many initial terms, a natural question is whether the transcendence of its generating function can be decided algorithmically. The question is non trivial even for sequences satisfying a recurrence of first order. An algorithm due to Michael Singer is sufficient, in principle, to answer the general case. However, this algorithm suffers from too high a complexity to be effective in practice. We will present a recent method that we have used to treat a non-trivial combinatorial example. It reduces the question of transcendence to a (structured) linear algebra problem.

Factoring large integers and computing discrete logarithms over finite fields are two difficult problems, efficiently solved by a family of algorithms, the index calculus. The security of some cryptosystems rely on this difficulty.

Since 1982 and the use of the quadratic sieve by Pomerance to factor large integers, it is well known that an important step of these algorithms, called relation collection, can be done quickly using sieving algorithms, basically like the sieve of Eratosthenes to find primes. Among the index calculus algorithms, the number field sieve (NFS) reaches the best complexity. It requires a two-dimensional sieving. In 2005, Franke and Kleinjung described the most efficient algorithm to sieve over two dimensions.

The diversity of finite fields implies that different variants of the NFS, as the one described by Joux–Lercier–Smart–Vercauteren in 2006 or by Kim–Barbulescu in 2016, need to sieve in higher dimensions, basically from 3 to 6. In this talk, we will describe three sieving algorithms in dimension three, some computational results of their implementations and finally an algorithm to sieve in any small dimension.

See the Lattice meetings page.

(Joint work with Mioara Joldes and Valentina Popescu)

We analyze several classical basic building blocks of double-word arithmetic (frequently called “double-double arithmetic” in the literature): the addition of a double-word number and a floating-point number, the addition of two double-word numbers, the multiplication of a double-word number by a floating-point number, the multiplication of two double-word numbers, the division of a double-word number by a floating-point number, and the division of two double-word numbers. For multiplication and division we get better relative error bounds than the ones previously published. For addition of two double-word numbers, we show that the previously published bound was incorrect, and we provide a new relative error bound. We introduce new algorithms for division. We also give examples that illustrate the tightness of our bounds.

In this talk we discuss sigma bases and kernel bases of polynomial matrices and illustrate their role in fast algorithms for arithmetic with polynomial matrices. In particular we focus on the use of kernel bases for triangulation, computing determinants and Hermite normal form computation.

Joint work with Vincent Neiger (Lyon and TU Denmark) and Wei Zhou (Waterloo)

We present an implementation, on top of the SageMath computer algebra system, of a collection of tools for computing numerical values of D-finite functions. Recall that a complex analytic function is D-finite when it satisfies an ordinary differential equation whose coefficients are polynomial in the independent variable. D-finite functions can be viewed as a class of special functions analogous to those of algebraic or hypergeometric functions, but more general. They come up in areas such as analytic combinatorics and mathematical physics, and lend themselves well to symbolic manipulation by computer algebra systems.

The main task our package performs is the “numerical analytic continuation” of D-finite functions. This process results in a numerical approximation of the transition matrix that maps “initial values” of an ODE somewhere on the complex plane to “initial values” elsewhere that define the same solution. Numerical analytic continuation can then be used to compute things like values or polynomial approximations of D-finite functions anywhere on their Riemann surfaces, and monodromy matrices of differential operators. The code supports the important limit case where the (generalized) initial values are provided at regular singular points of the ODE, making it possible in particular to compute connection constants between regular singularities. It is rigorous in the sense that it returns interval results that are guaranteed to enclose the exact mathematical result.

The new package can be considered a successor of NumGfun, a Maple package by the same author with broadly similar features.

Multilinear maps are a powerful cryptographic primitive: a wide array of cryptographic schemes can be built from multilinear maps, including some for which there is no other known construction, such as non-interactive multipartite key exchange, or general program obfuscation. However to this day there is no provable construction of multilinear maps. Moreover both of the original constructions (proposed in 2013 by Garg, Gentry, and Halevi, and by Coron, Lepoint, and Tibouchi) have been broken for their most direct application, namely non-interactive multipartite key exchange. This has led Coron, Lepoint and Tibouchi to introduce an improved variant of their original construction at Crypto 2015. We propose a polynomial attack on this new construction, which fully breaks the scheme. The presentation will of course begin with a general introduction to multilinear maps and the CLT construction, which aims to be accessible to all; and will conclude with a brief overview of the current state of the topic.

Linear digital filters are frequently used in digital signal processing. We are interested in implementation of such algorithms in Fixed-Point Arithmetic. However, on each step of an implementation various issues arise. We propose an automatised filter-to-code generator which encompasses the filter implementation flow and provides a consistent error-analysis of involved algorithms.
In this talk we make an overview of the filter-to-code generator and focus on determining the Fixed-Point formats for an implementation that is optimal with respect to a certain criteria. We consider Linear Time Invariant filters in state-space representation. The computational errors in the intermediate steps of the filter evaluation as well as their accumulation over time are fully taken into account. Our approach is fully rigorous in the way that the output Fixed-Point formats are shown to be free of overflows and that we do not use any (non-exhaustive) filter simulation steps but proofs.

Cf. the Web page of the Crypto and Lattices Days

Cf. the Web page of the Crypto and Lattices Days

Computing the roots of a univariate polynomial is a classical task in computer algebra and numerical analysis and it is often solved via a companion matrix approach. But can we exploit the matrix structures that arise in this problem to devise fast eigensolvers and rootfinding algorithms, without losing accuracy?

Motivated by this problem, we

• review some useful rank structures of Frobenius and Chebyshev companion matrices and pencils,
• introduce the quasiseparable representation for such matrices and pencils,
• show how to adapt suitable versions of the Francis/Kublanovskaya QR algorithm to the quasi separable representation, so that the arithmetic complexity of each iteration is linear in the size of the matrix,
• comment on numerical results, applications, and perspectives for further work.

This is joint work with Luca Gemignani (University of Pisa) and Yuli Eidelman (University of Tel Aviv).

Can you tell me more about that?

The design of function evaluation libraries is a complex task that requires great care and dedication, especially when one wants to satisfy high standards of reliability and performance. In practice, it cannot be correctly performed, as a routine operation, without tools that not only help the designer to find his way in a complex and extended solution space but also guarantee that his solutions are correct and (possibly) optimal.

As of the present state of the art, one has to think in terms of “toolbox” from which he has to smartly mix-and-match the utensils that better fit his goals rather than expect to have at hand a solve-all automatic device.

What is it that you have done?

The work presented here is dedicated to the design and implementation of such specialized tools in two realms:

• the radical consolidation of Ziv’s rounding test that is used, in a more or less empirical way for ages, in the implementation of functions approximation;
• the development of an implementation of the SLZ-algorithm in order to “solve” (in a specific sense that will be made clear) the Table Maker Dilemma; the suitability of this implementation is also challenged for the development of correctly rounded approximations of functions with quad-precision floating-point (aka IEEE-754 Binary128 format) arguments and images.

About the defense, see the report on the intranet of ENS de Lyon.

We are interested in computing the topology of the projection of an algebraic or analytic space curve in the plane. Such a projection is not a smooth curve and has singularities. State of the art approaches to compute the topology of algebraic plane curves use symbolic calculus but in the case of a projection, latter approaches suffer from the size of the implicit representation of the curve as a resultant polynomial.
Using numerical tools to compute the projected curve or its singularities is a challenging problem since the projected curve is not smooth, and state-of-the-art characterizations of the singularities use over-determined systems of equations. We will first propose a new characterization of the singularities of the projection of an algebraic curve using a square system polynomials; its solutions are regular and it can be solved numerically.
However its equations are coefficients of resultant polynomials and are still very large polynomials. The demand in arithmetic precision to carry out numerical calculus with such polynomials makes classical solvers either incomplete or dramatically time consuming. We will propose a multi-precision solver using interval subdivision specially designed to handle large polynomials to compute the solutions of this system. We will then consider the more general case of projections of analytic space curves, and propose a geometric approach to describe its singularities. It results in a square system of equations with only regular solutions, that do not involve resultant theory, and that can be solved with our certified numerical solver. Finally we will present a new approach to compute the topology of the projected curve, i.e. find a graph that has the same topology. We use a certified numerical path tracker to enclose the space curve in a sequence of boxes, allowing both to simplify the research of singularities and to compute smooth branches linking singularities.

Mahler equations relate evaluations of the same function \(f\) at iterated \(b\)th powers of the variable. They arise in particular in the study of automatic sequences and in the complexity analysis of divide-and-conquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with number-theoretic questions.
A difficulty in the manipulation of Mahler equations is the exponential blow-up of degrees when applying a Mahler operator to a polynomial. We present and analyze polynomial-time algorithms for solving linear Mahler equations for series, polynomials, and rational functions.

For almost 35 years, Schönhage-Strassen’s algorithm has been the fastest algorithm known for multiplying integers, with a time complexity \(O(n⋅\log n⋅ \log \log n)\) for multiplying n-bit inputs. In 2007, Fürer proved that there exists \(K>1\) and an algorithm performing this operation in \(O(n⋅\log n⋅K^{(\log^∗ n)})\). Recent work by Harvey, van der Hoeven, and Lecerf showed that this complexity estimate can be improved in order to get \(K=8\), and, via a conjecture on Mersenne primes, \(K=4\).
This presentation will describe an alternative algorithm using generalized Fermat primes for which \(K=4\) conjecturally. This algorithm seems more simple than the algorithm relying on Mersenne primes and can be seen as a fix to an approach proposed by Fürer in 1989 using Fermat primes.

Short presentation (10mn) of the results submitted to a conference on cryptography.

• Shi Bai: A subfield lattice attack for overstretched NTRU.
  Accepted to CRYPTO.
  Joint work with Martin Albrecht and Léo Ducas.
• Benoît Libert: Fully Secure Functional Encryption for Inner Products from Standard Assumptions.
  Accepted to CRYPTO.
  Joint work with Shweta Agrawal and Damien Stehlé
• Fabrice Mouhartem: Lattice-Based Group Encryption.
  In progress.
  Joint work with Benoît Libert.
• Willy Quach: Circular Security and Fully Homomorphic Encryption.
  M2 internship.
• Somindu Ramona: Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions.
  Accepted to ICALP.
  Joint work with Benoît Libert and Moti Yung.

We consider the problem of constructing multivariate polynomial systems with real coefficients, prescribed monomial support and many non-degenerate real solutions with positive coordinates. For some families of monomial supports, we use a version of Viro’s method to construct polynomial systems all complex solutions of which are real and positive. We also use this construction to investigate special cases of the following problem: how many non-degenerate solutions in the positive orthant can a system of n equations in n variables involving at most t distinct monomials have? In particular, we study a family of fewnomial systems obtained by considering a simplicial complex contained in a regular triangulation of the cyclic polytope: using a symbolic-numeric approach to a matrix completion problem, we will present a method to construct a system of 5 equations in 5 variables, involving only 11 distinct monomials and having 38 positive solutions.

Joint work with Frédéric Bihan.

We present a probabilistic polynomial-time reduction from the lattice Bounded Distance Decoding (BDD) Problem with parameter \(1/(\sqrt{2} \cdot \gamma)\) to the unique Shortest Vector Problem (uSVP) with parameter \(\gamma\) for any \(\gamma>1\) that is polynomial in the lattice dimension \(n\). It improves the BDD to uSVP reductions of [Lyubashevsky and Micciancio, CRYPTO, 2009] and [Liu, Wang, Xu and Zheng, Inf. Process. Lett., 2014], which rely on Kannan’s embedding technique. The main ingredient to the improvement is the use of Khot’s lattice sparsification [Khot, FOCS, 2003] before resorting to Kannan’s embedding, in order to boost the uSVP parameter.

3D algebraic parameterizations of curves and surfaces are intensively used in modeling geometry to provide piecewise descriptions of 3D objects. For many purposes it is important to derive implicit representations from parameterizations, for instance visualization or intersection problems. In this talk, I will discuss an elimination method to compute matrix-based implicit representations that can adapt dynamically the geometric properties of a given parameterization, typically its base locus. I will also show how these matrix representations turn several geometric problems into linear algebra problems, allowing a better control of their numerical treatment in the context of approximate data and/or computations.

More information on the page of the thematic school on numerical simulation and polyhedral code optimisations

voir la page de cette journée

At IEEE Security & Privacy 2015, Bos, Costello, Naehrig, and Stebila proposed an instantiation of Peikert’s ring-learning-with-errors–based (Ring-LWE) key-exchange protocol (PQCrypto 2014), together with an implementation integrated into OpenSSL, with the affirmed goal of providing post-quantum security for TLS. In this talk I will present joint work with Alkim, Ducas, and Pöppelmann, in which we revisit their instantiation and stand-alone implementation. Specifically, we propose new parameters and a better suited error distribution, analyze the scheme’s hardness against attacks by quantum computers in a conservative way, introduce a new and more efficient error-reconciliation mechanism, and propose a defence against backdoors and all-for-the-price-of-one attacks. By these measures and for the same lattice dimension, we more than double the security parameter, halve the communication overhead, and speed up computation by more than a factor of 9 in a portable C implementation and by more than a factor of 24 in an optimised implementation targeting current Intel CPUs. These speedups are achieved with comprehensive protection against timing attacks.
The talk will be based on this article.
Joint work with Erdem Alkim, Léo Ducas and Thomas Pöppelmann.

More information on the Web page of the “Monthly lattice and crypto meetings”

see the program

The Coppersmith methods is a family of lattice-based techniques to find small integer roots of polynomial equations. They have found numerous applications in cryptanalysis and, in recent developments, we have seen applications where the number of unknowns and the number of equations are non-constant. In these cases, the combinatorial analysis required to settle the complexity and the success condition of the method becomes very intricate. We provide a toolbox based on analytic combinatorics for these studies. It uses the structure of the considered polynomials to derive their generating functions and applies complex analysis techniques to get asymptotics. The toolbox is versatile and can be used for many different applications, including multivariate polynomial systems with arbitrarily many unknowns (of possibly different sizes) and simultaneous modular equations over different moduli. To demonstrate the power of this approach, we apply it to recent cryptanalytic results on number-theoretic pseudorandom generators for which we easily derive precise and formal analysis. We also present new theoretical applications to two problems on RSA key generation and randomness generation used in padding functions for encryption.

The talk will be based on this article.

Joint work with Céline Chevalier, Adrian Thillard, and Damien Vergnaud.

More information on the Web page of the “Monthly lattice and crypto meetings”

Short presentation (10mn) of the results submitted either to ARITH23 or to ISSAC 2016.

• Claude-Pierre Jeannerod, Nicolas Louvet, Jean-Michel Muller and Antoine Plet: A library for symbolic floating-point arithmetic
• Vincent Lefèvre: Correctly Rounded Arbitrary-Precision Floating-Point Summation
• Julien Le Maire, Nicolas Brunie, Florent de Dinechin and Jean-Michel Muller: Computing floating-point logarithms with fixed-point operations
• Clément Pernet: Computing with Quasi-Separable Matrices
• Stephen Melczer and Bruno Salvy: Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables
• Jean-Guillaume Dumas, Erich Kaltofen, Emmanuel Thomé and Gilles Villard:Linear time interactive certificates for the minimal polynomial and the determinant of a sparse matrix

Short presentation (10mn) of the results submitted either to ARITH23 or to ISSAC 2016:

• Jean-Michel Muller, Valentina Popescu and Peter Tang: A new multiplication algorithm for extended precision using floating-point expansions
• Claude-Pierre Jeannerod, Vincent Neiger, Eric Schost and Gilles Villard: Fast computation of minimal interpolation bases in Popov form for arbitrary shifts
• Vincent Neiger: Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations
• Alin Bostan, Gilles Christol, and Philippe Dumas: Fast computation of the Nth term of an algebraic series in positive characteristic
• Alin Bostan, Louis Dumont and Bruno Salvy: Efficient Algorithms for Mixed Creative Telescoping

Access to encrypted data is often “all-or-nothing” : either one has to decrypt everything, or one cannot read anything. Following Gentry’s work in 2009, fully homomorphic encryption has gained more and more attention, in particular because it allows more flexibility on encrypted data access and process. It is now possible to evaluate functions on encrypted data and get only the result – encrypted as well. This possibility offers numerous applications, especially when building a trustworthy cloud provider where the server cannot access the users’ data. It theoretically reconciles a rich user experience with protection of her sensible data. However, efficiency of fully homomorphic encryption remains seriously undermined by a very costly procedure: the “bootstrapping”. In this talk, we will show how to use graph problems and integer linear programming in order to determine the minimal number of bootstrappings necessary to correctly evaluate a circuit over encrypted data. Our method allows significant efficiency gains in the evaluation process, saving up to 70% bootstrappings calls. This is a joint work with Bastien Vialla.

Reminder: Journées du GDR IM, LIPN, Université Paris 13 (campus de Villetaneuse), 18-20 January 2016.
Lattice Meetings, 21 January 2016 at ENS Paris.

We propose to generalize the SIMT execution model of GPUs to general-purpose processors, and use it to design new CPU-GPU hybrid cores. These hybrid cores will form the building blocks of heterogeneous architectures bringing together CPU-like cores and GPU-like cores that all share the same instruction set and programming model.
The SIMT execution model used on some GPUs binds together multiple threads in parallel applications and run them in lockstep so that multiple threads perform the same instruction at the same time on different data. This allows to execute the dynamic vector instructions on energy-efficient SIMD units.
Unfortunately, current GPU architectures lack the flexibility to work with standard instruction sets like x86 or ARM. Their implementation of SIMT requires special instruction sets with control-flow reconvergence annotations, and they do not support complex control flow like exceptions, context switches and thread migration. This prevents the use of a general-purpose system software stack and breaks compatibility with CPU environments.
We will see how we can overcome all of these limitations and extend the SIMT model to conventional instruction sets by using a PC-based instruction fetch policy. In addition to enabling SIMT execution of conventional instruction sets, this solution enables key improvements that were not possible in the traditional SIMD model, such as simultaneous execution of divergent paths. It also opens the way for a whole spectrum of new architectures, hybrids of latency-oriented superscalar processors and throughput oriented SIMT GPUs.

In this talk I first review the state of the art in basis reduction techniques for lattices (relevant among others in cryptography and in linear integer programming).
Then I describe improved analysis techniques discovered during my current sabbatical at ENS Lyon. They allow one to prove for new variations of traditional reduction algorithms complexity bounds and reduced basis guarantees that are both stronger than the existing results.

In this talk we will look at algorithms designed in Chebfun to compute best approximations of continuous periodic and aperiodic functions. We will also discuss Chebfun’s capabilities to compute best approximations on compact subsets of an interval and how these methods can be used to design FIR digital filters. In addition, we will also look at rational and Fourier-Padé approximations and explore how these methods may be used to design recursive IIR filters.
The talk will also discuss the closely related Caratheodory-Fejer (CF) approximation of a function. The CF approximation is a near best approximation that can be computed numerically by solving an eigenvalue problem. CF approximation for a very modest degree can be within machine precision of the best polynomial and rational approximation of a given smooth function. From a numerical point of view, it is much more interesting to consider the rational as opposed to the polynomial CF approximation problem. In particular, the rational CF approximation can be an excellent initial guess for the true best approximation. We will explore these topics during the talk, however, this is still very much a work in progress.

The Learning with Errors (LWE) problem, proposed by Regev in 2005, has become an ever-popular cryptographic primitive, due mainly to its simplicity, flexibility and convincing theoretical arguments regarding its hardness. Among the main proposed approaches to solving LWE instances — namely, lattice algorithms, combinatorial algorithms, and algebraic algorithms — the last is the one that has received the least attention in the literature, and is the focus of this talk. We present a detailed and refined complexity analysis of the original Arora-Ge algorithm, which reduced LWE to solving a system of high-degree, error-free polynomials. Moreover, we generalise their method and establish the complexity of applying Gröbner basis techniques from computational commutative algebra to solving LWE. As a result, we show that the use of Gröbner basis algorithms yields an exponential speed-up over the basic Arora-Ge algorithm. On the other hand, our results show that such techniques do not yield a sub exponential algorithm for the LWE problem. We also apply our algebraic algorithm to the BinaryError-LWE problem, which was recently introduced by Micciancio and Peikert. We show that BinaryError-LWE in dimension \(n\) can be solved in subexponential time given access to a quasi-linear number of samples \(m\) under a regularity assumption. We also give precise complexity bounds for BinaryError-LWE in function of the number of samples. The results in this work depend crucially on the assumption that the encountered systems have no special structure. We give experimental evidence that this assumption holds and also prove the assumptions in some special cases. Therewith, we also make progress towards proving Froberg’s long-standing conjecture from algebraic geometry.
The talk will be based on this article.

Joint work with Martin R. Albrecht, Carlos Cid and Jean-Charles Faugère.

More information on the Web page of the “Monthly lattice and crypto meetings”

Recent work in the study of analytic combinatorics in several variables has shown how to derive asymptotics for the coefficients of certain families of D-finite functions by representing them as diagonals of multivariate rational functions. Although a theoretical framework has been laid over the last two decades (and before), there are still obstacles which has made the ultimate dream of an effective implementation of these techniques elusive. We begin with an overview of the classical (univariate) theory of analytic combinatorics, followed by a survey of the differences and difficulties present in the multivariate extension. Finally, we look at applications of these methods to the enumeration of lattice paths in restricted regions.

This is joint work with Mark Wilson, George Labahn, Bruno Salvy, and Marni Mishna.

In this talk we provide some lower bounds for the representation of real univariate polynomials as sums of powers of degree 1 polynomials. We present two families of polynomials of degree \( d \) such that the number of powers that are required in such a representation must be at least of order \( d \). This is clearly optimal up to a constant factor. Previous lower bounds for this problem were only of order \( \Omega(\sqrt{d}) \), and were obtained from arguments based on Wronskian determinants and “shifted derivatives”. We obtain this improvement thanks to a new lower bound method based on Birkhoff interpolation (also known as “lacunary polynomial interpolation”).

Preprint available here.

This is a joint work with Pascal Koiran.

The row (resp. column) rank profile of a matrix describes the stair case shape of its row (resp. column) echelon form.
We will first propose a recursive Gaussian elimination algorithm that can compute simultaneously the row and column rank profiles of a matrix, as well as those of all of its leading sub-matrices, in the same time as state of the art Gaussian elimination algorithms. More generally, we will study the conditions making a Gaussian elimination algorithm reveal this information. We propose the definition of a new matrix invariant, the rank profile matrix, summarizing all information on the row and column rank profiles of all the leading sub-matrices. We also explore the conditions for a Gaussian elimination algorithm to compute all or part of this invariant, through the corresponding PLUQ decomposition. As a consequence, we show that the classical iterative CUP decomposition algorithm can actually be adapted to compute the rank profile matrix. Used, in a Crout variant, as a base-case to the recursive algorithm, it delivers a significant improvement in efficiency. Lastly, the row (resp. column) echelon form of a matrix are usually computed via different dedicated triangular decompositions. We show here that, from some PLUQ decompositions, it is possible to recover the row and column echelon forms of a matrix and of any of its leading sub-matrices thanks to an elementary post-processing algorithm.

Joint work with Jean-Guillaume Dumas and Ziad Sultan.

We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands (approx \( 2^{24} \) users). The feasibility of the scheme is supported by implementation results. Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.

The talk will be based on this article. Joint work with Martianus Frederic Ezerman, Hyung Tae Lee, San Ling and Huaxiong Wang.

More information on the Web page of the “Monthly lattice and crypto meetings”

Introduced by Chaum and Van Heyst in 1991, group signatures provide a way for a person to sign messages on behalf of a group he belongs to while remaining anonymous inside this group. At the same time, users remain accountable for their signatures: if necessary, an opening authority is able to trace any signature back to its issuer. The concept has many applications, going from trusted computing to anonymous access control (e.g., to public transportation systems or to the building of a company).
In 2010, Gordon et al. described a first realization based on lattice assumptions, which was subsequently improved in several works. For the time being, all known lattice-based constructions are for static groups, where no new member can be added after the setup phase. Designing a dynamic group signature based on lattices has remained an open problem for the last four years. In this work, we propose a first dynamic group signature based on standard lattice assumptions (in the random oracle model): the Learning-with Errors (LWE) and the Short Integer Solution (SIS) problems. To achieve this, we adapt a construction due to Ling et al. (PKC’15) by introducing a joining mechanism – namely a protocol whereby new members can dynamically join the group – which provides security against framing attacks: a security notion proper to the dynamic case. We design this mechanism by combining the Boyen signature scheme (PKC’10) with the Böhl et al. signature (Eurocrypt’13). In particular, the latter technique makes it possible to introduce a so-called membership secret which is only known to the introduced group member and correspond to a public syndrome that gets certified by the group manager during the joining protocol. Our security proof requires an analysis based on the Rényi divergence (rather than the statistical distance) in order to enable a more efficient choice of parameters.

I will present methods allowing one to derive some lower bounds in rational approximation of given degree to functions in the Hardy space H2 of the disk. The algorithms that solve the problem of best rational approximation to a function usually only find a ‘candidate’, in the sense that they find a local minimum of the criterion, with good hope that this minimum is indeed global. Providing a good lower bound to this problem is thus an interesting complement to such solvers, as it gives an interval of confidence for the true optimal value.
A first method is based on Adamjan-Arov-Krein theory and leads to a lower bound that is fairly easy to compute from a numerical point of view. This bound is also of theoretical interest, as it allowed us to derive asymptotic errors rates in approximation to Blaschke products and to Cauchy integrals on geodesic arcs.
A second method is based on linearized errors and leads to more involved numerical computations, less easily implemented. Yet, results on a few examples show that this method can compute lower bounds that are fairly sharp with respect to the true optimal error.
I will present both methods and discuss the difficulties in their practical implementation. They will be illustrated by numerical results on a few examples.

This is a joint work with Laurent Baratchart and Tao Qian.

The solution of integer least squares problems is closely related to certain lattice problems, in particular the closest vector problem and basis reduction. Applications in parameter estimation problems have different characteristics from those in number theory, computer algebra, or cryptography in that the initial basis is known only to limited accuracy, and the demands on the quality of the solution are therefore moderate only.
In this lecture I’ll give an introduction to the problem, outline methods and their properties. I conclude with a list of lattice-related problems that I am interested in seeing solved.

We present two new strategies for parallel implementation of scalar multiplication over elliptic curves. For curves \(E(\mathbb{F}_{2^m})\), we first introduce a Montgomery-halving algorithm which is a variation of the original Montgomery-ladder for point multiplication. This Montgomery-halving can be run in parallel with the original Montgomery-ladder in order to concurrently compute part of the scalar multiplication. We also present two point thirding formulas in some subfamilies of curves \(E(\mathbb{F}_{3^m})\). We use these thirding formulas to implement scalar multiplication through (Third, Double)-and-add and (Third, Triple)-and-add parallel approaches. We also provide some implementation results of the presented parallel strategies which show a speed-up of 5%-14% on an Intel Core i7 processor and a speed-up of 8%-19% on a Qualcomm Snapdragon processor compared to non-parallelized approaches.

Keywords: Elliptic curve, small characteristic, scalar multiplication, Montgomery, thirding, parallel implementation.

Linear matrices and their loci of rank defects arise as natural algebraic structures both in theoretical and in applicative problems, of particular interest in real algebraic geometry, polynomial optimization, control theory. For example, the feasible region of a semidefinite program, called a spectrahedron, is a convex set whose algebraic boundary is shaped by the determinant of a symmetric linear matrix. Hence the solution to such an optimization problem corresponds to a positive semidefinite linear matrix with rank defects.

In this talk I will show how to design symbolic algorithms whose input is a linear matrix A and an expected maximal rank r, and whose output is a sample set of real points lying in the correspondent locus of rank defect. These algorithms and their complexity take strong advantage of the determinantal structure and of additional relations amongs the entries of A. Moreover, I will show how they can be used to decide the emptiness of low rank real loci and of spectrahedra, and hence to decide the feasibility of semidefinite programs. The techniques involved can represent a basis to build a stronger symbolic approach to semidefinite programming.

The results I will present are joint work with Didier Henrion and Mohab Safey El Din.

We introduce the notion of asymmetric programmable hash functions (APHFs, for short), which adapts Programmable Hash Functions, introduced by Hofheinz and Kiltz at Crypto 2008, with two main differences. First, an APHFs works over bilinear groups. Moreover it is asymmetric in the sense that while only secretly computable, it admits an isomorphic copy which is publicly computable.
Second, in addition to the usual programmability, APHFs may have an alternative property that we call programmable pseudorandomness. In a nutshell, this property states that it is possible to embed a pseudorandom value as part of the function’s output, akin to a random oracle.
In spite of the apparent limitation of being only secretly computable, APHFs turn out to be surprisingly powerful objects. We show that they can be used to generically implement both regular and linearly-homomorphic signature schemes in a simple and elegant way.
More importantly, when instantiating these generic constructions with our concrete realizations of APHFs, we obtain:

(1) the first linearly-homomorphic signature (in the standard model) whose public key is sub-linear in both the dataset size and the dimension of the signed vectors.

(2) short signatures (in the standard model) whose public key is much shorter than those by Hofheinz-Jager-Kiltz from Asiacrypt 2011, and essentially the same as those by Yamada, Hannoka, Kunihiro, (CT-RSA 2012).

This is a joint work with Dario Fiore and Luca Nizzardo (IMDEA Software Institute, Madrid)

We present a block LU factorization with panel rank revealing pivoting (block LU_PRRP), an algorithm based on strong rank revealing QR for the panel factorization.
Block LU_PRRP is more stable than Gaussian elimination with partial pivoting (GEPP), with a theoretical upper bound of the growth factor of \((1+ \tau b)^{(n/ b)-1}\), where \(b\) is the size of the panel used during the block factorization, \(\tau\) is a parameter of the strong rank revealing QR factorization, and \(n\) is the number of columns of the matrix. For example, if the size of the panel is \(b = 64\), and \( \tau = 2\), then \( (1+2b)^{(n/b)-1} = (1.079)^{n-64} \ll 2^{n-1} \), where \( 2^{n-1} \) is the upper bound of the growth factor of GEPP. Our extensive numerical experiments show that the new factorization scheme is as numerically stable as GEPP in practice, but it is more resistant to some pathological cases where GEPP fails. We note that the block LU_PRRP factorization does only \( O(n^2 b) \) additional floating point operations compared to GEPP.

The guaranteed solution of initial value problem of ordinary differential equations is well studied from interval analysis community. In the most of the cases Taylor series are used in this context. In contrast, in numerical analysis community other numerical integration methods, e.g., Runge-Kutta methods, are used. Indeed, these methods have very good stability properties and they can be applied on a wide variety of problems.
We propose a new method to validate the solution of initial value problem of ordinary differential equations based on Runge-Kutta methods. The strength of our contribution is to adapt any explicit and implicit Runge-Kutta methods to make them guaranteed. We experimentally verify our approach against Vericomp benchmark. We hence extend our previous work on explicit Runge-Kutta methods.

The residue number system (RNS) is a number representation based on the Chinese remainder theorem (CRT), which splits large integers into small independent chunks in order to speed up the computations. This representation is more and more used for implementations of asymmetric cryptography, because RNS provides various interesting properties in hardware. As a first step, this talk will recall the elementary properties of RNS, and a few classical algorithms proposed in the state-of-art. Then, some recent algorithmic propositions are presented, on RNS modular inversion, modular multiplication and modular exponentiation, for specific cryptographic applications.

Nowadays, the most common way of representing real numbers in a computer is the binary floating-point (FP) format. The single (binary32) and double (binary64) formats are the most common, specified by the IEEE 754-2008 standard together with basic arithmetic operations (+,-,*,/,sqrt()) or rounding modes. However, many numerical problems require a higher computing precision (several hundred bits) than the one offered by these standard formats. One common way of extending the precision is to represent numbers in a multiple-term format. By using the so-called floating-point expansions, real numbers are represented as the unevaluated sum of standard machine precision FP numbers. Such a representation is possible thanks to the availability of error-free transforms. These are algorithms for computing the error of a FP addition or multiplication exactly, taking the rounding mode into account and using directly available, hardware implemented FP operations.

In this talk, we present CAMPARY (CudA Multiple Precision ARithmetic librarY), a multiple-precision floating-point arithmetic library developed in the CUDA programming language for the NVIDIA GPU platform, that uses the multiple-term approach. We provide support for all basic arithmetic operations, but here we will focus on a new normalization algorithm. This operation is very important when FP expansions are used, since it ensures certain precision related requirements and allows for a more compact representation. Finally, we present a new method for computing the reciprocal and the square root of a FP expansion based on an adapted Newton-Raphson iteration where the intermediate calculations are done using “truncated” operations (additions, multiplications) involving FP expansions.

There are already several mathematical libraries (libms): collections of code to evaluate some mathematical functions. They differ by the result’s accuracy, language, developer teams, etc. The common thing for all existing libms is that they do not give enough choice for user. E.g. you can’t choose between fast or accurate implementations, while for applications on the large sets of data the speed is crucial.
We try to rewrite the existing libm in a more flexible way. As there are plenty of function variations, it is impossible to write all of them manually, and we need the code generator. We pass the implementation parameters e.g. the results accuracy, implementation domain (as well as the function itself!) to the generator to get the corresponding implementation. Our black-box generator produces code for the functions from the standard libms, applies the needed argument reduction and (or) splits the domain. In the last case, there are some attempts to get the reconstruction code without branching.

The diagonal of a multivariate power series F is the univariate power series Diag F generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. We study algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case Diag F is an algebraic function. We propose an algorithm that computes an annihilating polynomial for Diag F. Generically, it is its minimal polynomial and is obtained in time quasi-linear in its size. We show that this minimal polynomial has an exponential size with respect to the degree of the input rational function. We then address the related problem of enumerating directed lattice walks. The insight given by our study leads to a new method for expanding the generating power series of bridges, excursions and meanders. We show that their first N terms can be computed in quasi-linear linear time in N, without first computing a very large polynomial equation.

Many time and space dependent problems from physics, biology etc. have a strong multiscale character. Classical numerical approaches using fixed discretization steps in space and in time cannot solve them, or can give wrong results. I will explain how automatic adaptive methods overcome (partially) these difficulties. I will put the emphasis on modern Runge-Kutta methods for multiscale (aka. stiff) Ordinary Differential Equations and divide and conquer methods (operator splitting).

We discuss methods used for rigorous evaluation of special functions in Arb, a C library for arbitrary-precision real and complex ball (interval) arithmetic. We have implemented many of the familiar special functions such as erf, gamma, zeta, polylogarithms, generalized exponential integrals, Bessel functions, theta and elliptic functions. In most cases, we support complex values of all inputs as well as computation of power series expansions (high-order derivatives). Our implementations are competitive with existing non-interval high-precision software, and often significantly faster. One highlight is a new algorithm for elementary functions, giving up to an order of magnitude speedup at “medium” precision (approximately 200-2000 bits).

Joint work with F. Pereira and his collegues @Univ Mineas Gerais, Bresil. Published at oopsla’14.

The C programming language does not prevent out-of-bounds memory accesses. There exist several techniques to secure C programs; however, these methods tend to slow down these programs substantially, because they populate the binary code with runtime checks. To deal with this problem, we have designed and tested a succession of static analyses to remove the majority of these guards.

We validate these static analyses by incorporating our findings into AddressSanitizer : we generate SPEC CINT 2006 code that is 17% faster and 9% more energy efficient than the code produced originally by this tool.
—

In this talk I will present some of the static analyses that we designed in this paper, focusing on our new “symbolic range” analysis, and also the techniques we use to be able to scale well.

We consider the problem of solving a full rank consistent linear system \(A(u)​ ​x = b(u)\) where \(A \in K[u]^{m×n}\) and \( b \in K[u]^m\). Our algorithm computes the unique solution \(x = f(u)/g(u)\) (a vector of rational functions) by evaluating the parameter \(u\) at distinct points. Those points where the matrix \(A\) evaluates to \(A( x_\lambda)\) of lower rank, or in the numeric setting to an ill-conditioned matrix, are not identified but accounted for by error-correcting code techniques. We also correct true errors where the evaluation at some \(u = x_\lambda\) results in an erroneous, possibly full rank consistent and well-conditioned scalar linear system. We have implemented our algorithm in Maple with floating point arithmetic. For the determination of the exact numerator and denominator degrees and number of errors we use SVD based numeric rank computations. The arising linear systems for the error-corrected parametric solution are shown to be well-conditioned even when the input scalars have noise.

Joint work with Erich L. Kaltofen.

Les réseaux idéaux sont largement utilisés en cryptographie sur les réseaux. Dans de tels réseaux, une base peut être obtenue à partir de \(n\) “translations” d’un seul vecteur. Cette structure permet généralement de gagner un facteur \(\tilde{O}(n)\) en espace et en temps sur de nombreuses opérations cryptographiques.

Cependant, jusqu’à présent, le calcul de l’orthogonalisation de Gram-Schmidt des bases de tels réseaux ne tirait pas parti de cette structure. La procédure de Gaussian Sampling décrite par Gentry, Peikert et Vaikuntanathan, qui est également celle qui produit les plus courts vecteurs, n’en profitait pas non plus.

Les vecteurs des bases utilisées pour les réseaux idéaux sont reliés par une isométrie. Plus précisément, il existe une isométrie \(r\) et un vecteur \(b\) tels qu’une base d’un réseau idéal peut s’écrire sous la forme \((b,r(b),…,r^{n-1}(b))\). Cet exposé montre que si cette isométrie peut être calculée en temps \(O(n)\), alors il est possible de calculer l’orthogonalisation ainsi que la décomposition QR d’une telle base en temps \(O(n^2)\) au lieu de \(O(n^3)\).

Cette amélioration profite également au Gaussian Sampling. Il devient en effet possible de calculer à la volée les \(n\) vecteurs orthogonalisés nécessaires à cette opération, au lieu de les stocker comme cela était auparavant nécessaire. Cela permet alors d’effectuer le Gaussian Sampling décrit par Gentry-Peikert-Vaikuntanathan en espace \(O(n)\) au lieu de \(O(n^2)\) auparavant, et ce en conservant un temps d’exécution en \(O(n^2)\).

Les travaux présentés ont été réalisés en commun avec Vadim Lyubashevsky.

The key operation of iterative algorithms in sparse linear algebra is the sparse matrix vector product (SpMV) or sparse matrix multi-vector product (SpMM) as most of the computation time is spent in those operations.
Nowadays, the peak performance of CPUs is increased by adding more cores and more vector instructions (SIMD), then it is crucial to consider those aspects when designing algorithms and data structures.

In this talk, I will show how to modify current sparse matrix storage and modular arithmetic to take into account SIMD operations. I will also talk about the use of Residue Number System (RNS) to design efficient medium precision arithmetic (< 2048bits) with application to the sparse matrices arising from the discrete logarithm problem over Finite Fields.

As Exascale computing (10¹⁸ operations per second) is likely to be reached within a decade, getting accurate results in floating-point arithmetic on such computers will be a challenge. However, another challenge will be the reproducibility of the results — meaning getting a bitwise identical floating-point result from multiple runs of the same code — due to non-associativity of floating-point operations and dynamic scheduling on parallel computers.

In this talk, I will present a reproducible and accurate (rounding to the nearest) algorithms for the fundamental linear algebra operations — like the ones included in the BLAS library — in parallel environments such as Intel server CPUs, Intel Xeon Phi, and both NVIDIA and AMD GPUs. I will show that the performance of our algorithms is comparable with the classic BLAS routines.

One of the most important cryptographic assumptions is arguably the Decisional Diffie-Hellman Assumption, asking to tell whether a group element is of the form \(g^{ab}\), given \(g\), \(g^a\), \(g^b\). Unfortunately, this assumption is know not to hold in groups that allow a (symmetric) pairing, so we need to replace DDH by other assumptions like the Linear Assumption or, more generally, any matrix assumption. In general, the type of assumption that we consider is of the form that some elementary problems from linear algebra like telling whether a vector is the image of a matrix, is infeasible if we are only given the inputs “in the exponent”.

For assumptions of cryptographic interest, the matrices involved are usually structured. This allows us to identify the vector in the exponent with a polynomial in a meaningful way. This additional structure arising from polynomials then leads to some interesting applications and we will for improvements in efficiency and to gain new insights into existing constructions.

We survey results of the numerical stability of the Gram-Schmidt algorithm. We will consider a variety of variants: Modified Gram-Schmidt, Classical Gram-Schmidt, Iterated Gram-Schmidt, Iterated Gram-Schmidt with a criterion, Gram-Schmidt with a non-Euclidean inner product. We will see various results along the years starting in 1967 and ending in 2014.

In their seminal work on non-malleable cryptography, Dolev, Dwork and Naor, showed how to construct a non-malleable commitment with logarithmically-many “rounds”/”slots”, the idea being that any adversary may successfully maul in some slots but would fail in at least one. Since then new ideas have been introduced, ultimately resulting in constant-round protocols based on any one-way function. Yet, in spite of this remarkable progress, each of the known constructions of non-malleable commitments leaves something to be desired.

In this talk I will present a new technique for constructing non-malleable protocols with only a single “slot”, to improve in at least one aspect over each of the previously proposed protocols. Two direct byproducts of our new ideas are a four round non-malleable commitment and a four round non-malleable zero-knowledge argument, the latter matching the round complexity of the best known zero-knowledge argument (without the non-malleability requirement). The protocols are based on the existence of one-way functions and admit very efficient instantiations via standard homomorphic commitments and sigma protocols.

Our analysis relies on algebraic reasoning, and makes use of error correcting codes in order to ensure that committers’ tags differ in many coordinates. One way of viewing our construction is as a method for combining many atomic sub-protocols in a way that simultaneously amplifies soundness and non-malleability, thus requiring much weaker guarantees to begin with, and resulting in a protocol which is much trimmer in complexity compared to the existing ones.

Joint work with Vipul Goyal, Silas Richelson and Margarita Vald.

Une approche classique au calcul numérique des racines d’un polynôme donné consiste à déterminer les valeurs propres de la matrice compagnon. Cette méthode se décline en plusieurs variantes selon la base polynomiale choisie et peut aussi être formulée en termes de faisceaux de matrices.

Le matrices qui interviennent dans cette approche ont généralement une structure de rang particulière : il s’agit de matrices quasiséparables. La structure quasiséparable permet de développer des versions rapides de l’algorithme QR/QZ pour le calcul des valeurs propres ; la complexité passe de \(O(n^3)\) opérations en virgule flottante pour le QR/QZ classique à \(O(n^2)\) opérations pour la version structurée.

Dans cet exposé, je présenterai les résultats obtenus depuis 2008 sur ce sujet, en collaboration avec Yuli Eidelman et Luca Gemignani. Nous verrons en particulier les aspects théoriques du problème, les propriétés et la représentation des matrices quasiséparables, les implantations réalisées, les questions ouvertes et quelques perspectives futures.

We analyse the complexity of algebraic algorithms for solving systems of linear equations with noise. Such systems arise naturally in the theory of error-correcting codes as well as in computational learning theory. More recently, linear systems with noise have found application in cryptography. The Learning with Errors (LWE) problem has proven to be a rich and versatile source of innovative cryptosystems, such as fully homomorphic encryption schemes. Despite the popularity of the LWE problem, the complexity of algorithms for solving is not very well understood, particularly when variants of the original problem are considered. Here, we focus on and generalise a particular method for solving these systems, due to Arora & Ge, which reduces the problem to non-linear but noise-free system solving. Firstly, we provide a refined complexity analysis for the original Arora-Ge algorithm for LWE. Secondly, we study the complexity of applying algorithms for computing Gröbner basis, the fundamental tool in computational commutative algebra, to solving Arora-Ge-style systems of non-linear equations. We show positive and negative results. On the one hand, we show that the use of Gröbner bases yields an exponential speed-up over the basic Arora-Ge approach. On the other hand, we give a negative answer to the natural question whether the use of such techniques can yield a subexponential algorithm for the LWE problem. Under mild assumptions – which we experimentally verified – we show that it is highly unlikely that such an improvement exists.

We also consider a variant of LWE known as BinaryError-LWE introduced by Micciancio and Peikert recently. By combining Gröbner basis algorithms with the Arora-Ge modelling, we show – under a mild, experimentally verified assumption – that BinaryError-LWE can be solved in subexponential time as soon as the number of samples is quasi-linear, e.g. \(m=O(n\log\log n)\). We also derive precise complexity bounds for BinaryError-LWE with \(m=O(n)\), showing that this new approach yields better results than best currently-known generic (exact) CVP solver as soon as \(m/n ≥ 6.6\). More generally, our results provide a good picture of the hardness degradation of BinaryError-LWE for a number of samples ranging from \(m = n(1 + \Omega(1/\log n))\) (a case for which BinaryError-LWE is as hard as solving some lattice problem in the worst case) to \(m=O(n^2)\) (a case for which it can be solved in polynomial-time). This addresses an open question from Micciancio and Peikert. Whilst our results do not contradict the hardness results obtained by Micciancio and Peikert, they should rule out BinaryError-LWE for many cryptographic applications.

Many digital filters and signal-processing transforms can be expressed as a sum of products with constants (SPC). In this presentation we will address the automatic construction of low-precision, but high accuracy SPC architectures: these architectures are specified as last-bit accurate with respect to a mathematical definition. They behave as if the computation was performed with infinite accuracy, then rounded only once to the low-precision output format. This eases the task of porting double-precision code (e.g. Matlab) to low-precision hardware or FPGA. We will also discuss the construction of the most efficient architectures obeying such a specification, introducing several architectural improvements to this purpose. This approach is demonstrated in a generic, open-source architecture generator tool built upon the FloPoCo framework. It is evaluated on Finite Impulse Response filters for the ZigBee protocol.

NLCertify is a software package for handling formal certification of nonlinear inequalities involving transcendental multivariate functions. The tool exploits sparse semialgebraic optimization techniques with approximation methods for transcendental functions, as well as formal features. Given a box and a transcendental multivariate function as input, NLCertify provides OCaml libraries that produce nonnegativity certificates for the function over the box, which can be ultimately proved correct inside the Coq proof assistant.

Le télescopage créatif est un principe algorithmique développé depuis les années 1990 en combinatoire et en calcul formel, notamment depuis les travaux de Doron Zeilberger, pour calculer avec des sommes et intégrales paramétrées, que ce soit pour trouver des formes explicites ou pour justifier des identités intégrales ou sommatoires. Le procédé est particulièrement adapté à une grande famille de fonctions et suites données par des équations linéaires différentielles et de récurrences, que ce soient des fonctions spéciales de l’analyse, des suites de la combinatoire, ou des familles de polynômes orthogonaux.

Dans cet exposé, je retracerai l’évolution des algorithmes et de mes contributions pour adapter le procédé à des classes de fonctions de plus en plus générales, du cadre initial des suites hypergéométriques, données par des récurrences d’ordre 1, aux cas de fonctions données par des équations d’ordre supérieur, ceci jusqu’aux fonctions données par des idéaux non zéro-dimensionnels.

La difficulté d’obtenir des implantations rapides dans tous ces cas repose sur le calcul d’un certificat justifiant l’application du télescopage créatif, ce certificat étant par nature de grande taille. Ceci m’a motivé dans l’étude de la complexité du procédé. Plusieurs pistes d’amélioration ont été explorées, d’abord en essayant de maintenir compact ce certificat, puis en obtenant des algorithmes validés sans passer par son calcul. Comme souvent, l’estimation des tailles arithmétiques des objets intervenant dans le telescopage créatif a à la fois guidé le développement de nouveaux algorithmes plus efficaces et permis leur estimation théorique de complexité.

Pour finir, j’indiquerai brièvement la direction qu’a prise mes travaux récents sur le sujet, vers la preuve formelle, et qui font ressortir des pistes pour une meilleure justification de l’application du télescopage créatif.

Row/column sampling techniques were initially introduced to compute low-rank approximation of matrices faster than the computation of SVD. In this talk, I will give a quick overview of squared-length sampling, adaptive sampling, relevance-score sampling etc., survey their connections to other topics such as determinantal point processes, rounding Lasserre SDP solutions, graph sparsification, convex geometry, and discuss interesting open problems in these.

Fully homomorphic encryption is an encryption scheme which allows arbirary
computations on encrypted data without decrypting. In spite of significant
improvements, FHEs are still far from practical for most applications. Especially,
large ciphertext size is a big bottleneck for transmission and storage. In this talk,
we introduce a method to reduce the ciphertext size of public key homomorphic
encryption by combining the ciphertext compression technique of symmetric homomorphic
encryption and the key switching technique.

Le calcul de l’infimum global f^* d’un polynôme à n
variables sous contraintes est une question centrale qui apparaît dans
de nombreux domaines des sciences de l’ingénieur. Pour certaines
applications, il est important d’obtenir des résultats fiables. De
nombreuses techniques ont été développées dans le cas où les contraintes
sont données par des inéquations polynomiales.

Dans cet exposé, on se concentre sur le problème d’optimisation d’un
polynôme à n variables sous des contraintes définies par des équations
polynomiales à n variables. Le but est d’obtenir des outils,
algorithmes et implémentations efficaces et fiables pour résoudre ces
problèmes d’optimisation.

La stratégie est de ramener le problème d’optimisation sous des
contraintes qui définissent des ensembles algébriques de dimension
quelconque à un problème équivalent, sous des nouvelles contraintes dont
on maîtrise la dimension. La variété algébrique définie par ces
nouvelles contraintes est l’union du lieu critique du polynôme objectif
et d’un ensemble algébrique de dimension au plus 1. Pour cela, on
utilise des objets géométriques définis comme lieux critiques de
projections linéaires.

Grâce au bon contrôle de la dimension, on prouve l’existence de
certificats pour des bornes inférieures sur f^* sur nos nouvelles
variétés. Ces certificats sont donnés par des sommes de carrés et on ne
suppose pas que f^* est atteint.

De même, on utilise les propriétés de nos objets géométriques pour
concevoir un algorithme exact pour le calcul de f^*. S’il existe,
l’algorithme renvoie aussi un minimiseur. Pour un problème avec s
contraintes et des polynômes de degrés au plus D, la complexité est
essentiellement cubique en (sD)ⁿ et linéaire en la complexité
d’évaluation des entrées. L’implantation, disponible sous forme de
bibliothèque Maple, reflète cette complexité. Elle a permis de résoudre
des problèmes inatteignables par les autres algorithmes exacts.

Les travaux présentés sont issus de collaborations avec Feng Guo, Mohab
Safey El Din et Lihong Zhi.

Randomness is essential to cryptography: cryptographic
security depends on private keys that are unpredictable to an
attacker. But how good are the random number generators that are
actually used in practice? In this talk, I will discuss several
large-scale surveys of cryptographic deployments, including TLS, SSH,
Bitcoin, and secure smart cards, and show that random number
generation flaws are surprisingly widespread. We will see how many of
the most commonly used public key encryption and signature schemes can
fail catastrophically if used with faulty random number generators,
and trace many of the random number generation flaws we
encountered to specific implementations and vulnerable implementation
patterns.

Le télescopage créatif est un principe algorithmique développé depuis les années
1990 en combinatoire et en calcul formel, notamment depuis les travaux de Doron Zeilberger,
pour calculer avec des sommes et intégrales paramétrées, que ce soit pour trouver
des formes explicites ou pour justifier des identités intégrales ou
sommatoires. Le procédé est particulièrement adapté à une grande famille de
fonctions et suites données par des équations linéaires différentielles et de
récurrences, que ce soient des fonctions spéciales de l’analyse, des suites de
la combinatoire, ou des familles de polynômes orthogonaux.

Dans cet exposé, je retracerai l’évolution des algorithmes et de mes
contributions pour adapter le procédé à des classes de fonctions de plus en
plus générales, du cadre initial des suites hypergéométriques, données par des
récurrences d’ordre 1, aux cas de fonctions données par des équations d’ordre
supérieur, ceci jusqu’aux fonctions données par des idéaux non
zéro-dimensionnels.

La difficulté d’obtenir des implantations rapides dans tous ces cas repose sur
le calcul d’un certificat justifiant l’application du télescopage créatif, ce
certificat étant par nature de grande taille. Ceci m’a motivé dans l’étude de
la complexité du procédé. Plusieurs pistes d’amélioration ont été explorées,
d’abord en essayant de maintenir compact ce certificat, puis en obtenant des
algorithmes validés sans passer par son calcul. Comme souvent, l’estimation
des tailles arithmétiques des objets intervenant dans le telescopage créatif a
à la fois guidé le développement de nouveaux algorithmes plus efficaces et
permis leur estimation théorique de complexité.

Pour finir, j’indiquerai brièvement la direction qu’a prise mes travaux
récents sur le sujet, vers la preuve formelle, et qui font ressortir des
pistes pour une meilleure justification de l’application du télescopage
créatif.

We consider a modification of the noisy polynomial interpolation
problem of recovering an unknown polynomial f(X) in Z[X]
from approximate values of the residues of f(t) modulo a
prime p at polynomially many points t taken from a short interval.
Our results are based on lattice algorithms and also on a variety
of some other number theoretic techniques including bounds on
the number of small values of polynomials for arguments from
short intervals. This work is motivated by a recently introduced HIMMO key
distribution scheme.

For an out-of-order CPU, the multi-cycle execution units (e.g., multipliers or dividers or floating-point adders)
consume only a small fraction of the area and power used by the core. By reducing the latency of these units, we
can often complete a task early, saving large amounts of total energy. We describe a simple formula to gauge the
relationship between execution unit power, core power, execution unit latency, and overall energy required for a task.
We then use that formula to argue for lower latency execution, even if the power of the execution units has to be
increased.

Leakage-resilient cryptography aims at extending the guarantees delivered by the provable
security paradigm to physical cryptography. The constructions provided by this new approach
persistently present an Achilles heel: a bounded leakage assumption is needed. A gap exists
hence between the promises and minimal requirements of leakage-resilient designs. Several
important recent works have contributed to close this gap. In this work we take a different
step forward in the same direction, by implementing and analyzing a leakage-resilient pairing-based
ElGamal key encapsulation mechanism (BEG-KEM) proposed by Kiltz and Pietrzak (ASIACRYPT 2010). We show,
empirically, that under the most favorable interpretation of the leakage model (namely, that every bit
leaked corresponds to a single bit – without noise – of the secret input), a naive implementation
of exponentiation in the pairing base group makes impossible to meet the leakage bound. Instead of
tackling the difficult problem of finding the right exponentiation algorithm that meets the leakage
bound, we propose a variation of BEG-KEM decryption that does not use exponentiation, but rather uses
an encoding to the base group, due to Fouque and Tibouchi (LATINCRYPT 2012). We then argue that this
new implementation is likely to meet the required leakage bound. We support this by a careful
examination of the state of the art research. To our knowledge, ours is the first implementation
in an embedded processor of a leakage-resilient primitive using public key cryptography.

Le cadre de cet exposé sera l’étude des systèmes différentiels du type X’ = A(X,Y), Y’=B(X,Y),
où X’ et Y’ représentent les dérivées par rapport au temps t, et A,B sont dans Q[X,Y].

Dans ce contexte, nous souhaitons obtenir (lorsque cela est possible) une fraction rationnelle
dont les lignes de niveaux correspondent aux trajectoires solutions du système différentiel étudié.
Cela permet alors d’avoir une représentation symbolique des solutions du système différentiel.

Nous verrons des algorithmes anciens et d’autres plus récents pour résoudre ce problème.
En particulier, je présenterai un algorithme obtenu en collaboration avec A. Bostan, T. Cluzeau,
et J.-A. Weil qui permet de ramener ce problème à la résolution d’un système linéaire.

The Chebfun project, based at Oxford University, applies ideas from polynomial and rational approximation theory to enable practical computation with functions of a real variable. This talk will survey some of the mathematics and algorithms, with a demonstration of Chebfun.

At the present time, IEEE 64-bit floating-point arithmetic is sufficiently accurate for most
scientific applications. However, for a rapidly growing body of important scientific computing
applications, a higher level of numeric precision is required. Such calculations are facilitated
by high-precision software packages that include high-level language translation
modules to minimize the conversion effort. On the other hand, the use of massive GPU cards
allows extremely fast calculations in low precision simulations
where high-precision is unnecessary. This talk presents an overview of recent
applications of these techniques, specially in computational dynamics, and provides
some mathematical analysis of their numerical requirements.

Les sommes multiples de binomiaux possèdent énormément de structure, ce qui permet de développer des algorithmes
spécifiques pour prouver ou trouver des formes closes ou des récurrences. En particulier, on peut représenter ces
sommes comme diagonales de fractions rationnelles, et alors trouver des récurrences pour ces suites en calculant
une équation différentielle pour une certaine intégrale multiple de fraction rationnelle. Nous étudions cette
approche tant du point de vue de la complexité que du point de vue pratique, et la comparons aux méthodes dérivées
de l’algorithme de Zeilberger. Il s’agit d’un travail en commun avec Alin Bostan et Pierre Lairez.

Given an linear-affine space of matrices E with real entries, a data
matrix U in E and a target rank r, the Structured Low-Rank
Approximation Problem consists in computing a matrix M in E 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 particular 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 U in E with rational entries. We
propose several techniques to recast this problem as a system of polynomial
equations in order to solve with Gröbner bases software.

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.

The optimal fuel impulsive time-fixed rendezvous problem is shortly reviewed in the context of the more general problem of impulsive optimal control. In a linear setting, it may be reformulated as a non convex polynomial optimization problem for a pre-specified fixed number of velocity increments. Some theoretical results are first recalled and different algorithms are presented. In particular, when addressing the problem of a free number of maneuvers, one has to resort to a mixed iterative algorithm involving the solution of a system of polynomial equation at each step. Different numerical issues are finally pointed out. Examples of realistic rendezvous missions will illustrate this talk.

We consider a type of Padé approximations over polynomial rings over fields,
dubbed “2D Padé approximations”, which generalise several known Padé
approximations. These approximations occur frequently in decoding of algebraic
codes (most recently in a preprint coauthored by several members of the AriC
team).

We’ll see how such approximations can be solved using row reduction of polynomial
matrices. We take a closer look at the Mulders–Storjohann for doing this and
show that its complexity is linked to the orthogonality defect of the input
matrix, implying that it is faster than initially guessed when applied to 2D
Padé approximations.

We then present a new algorithm, which essentially carries out the computations
performed by Mulders–Storjohann in a demand-driven manner, yielding an
algorithm which is often even faster. This algorithm has a very
Berlekamp–Massey-like quality, but is derived entirely in the module language.

Novel public-key cryptosystems beyond RSA and ECC are urgently required
to ensure long-term security in the era of quantum computing. One
alternative to such established schemes is lattice-based cryptography
which offers elegant security reductions and versatile tools such as the
learning with errors (LWE) problem. However, a critical issue on the
construction and implementation of such alternative cryptosystems is to
achieve security and practicability at the same time.

In this talk we will give an overview on current research dealing with
the implementation and optimization of efficient ideal lattice-based
signatures and underlying arithmetic. Ideal lattices are used to reduce
the generally very large key sizes of standard lattice construction and
also enable operations in quasi-linear runtime due to the applicability
of the number theoretic transform (NTT). First results are promising and
show that practical ideal lattice-based signatures can achieve high
speed on platforms such as FPGAs and desktop CPUs, especially when
equipped with vector register extensions (AVX).

A non-zero degree-d polynomial has at most d complex roots. But, if we consider a “nice” high-degree polynomial, for example x²⁰⁰⁰-1,
we can notice that the number of real roots is small. This idea is known since Descartes’ work: he showed that if a polynomial has t monomials
(in the example, t=2), then the number of real roots is bounded by 2t-1 (it does not depend on the degree).

What happens now if we consider systems of polynomials? Bézout’s Theorem states that the number of non-degenerated complex roots is bounded
by the product of the degrees. Can we get a similar result for the number of real roots of a system of sparse polynomials?

For solving these problems, Khovanskií developed the Fewnomials Theory. However, the order of magnitude of the bounds is always unknown.
We will consider this theory and the results around these problems and then, we will focus on a particular case, Sevostyanov’s problem:
What is the maximal number of real solutions for a system of one sparse polynomial and of one dense polynomial?

Les formes modulaires se présentent comme des séries de Fourier dont les coefficients
sont riches d’informations (notamment arithmétiques). Nous verrons comment le calcul
d’un objet associé à chaque forme modulaire (plus précisément, une représentation
galoisienne) permet de calculer efficacement ces coefficients modulo un petit nombre premier.

Ore algebras are an algebraic structure used to model many different
kinds of functional relations like differential and recurrence equations. The
elements of an Ore algebra are polynomials for which the multiplication is
defined to be usually non-commutative. As a consequence, Gauß’ lemma
does not hold in many Ore polynomial rings and hence the product of two
primitive Ore polynomials is not necessarily primitive. This observation
leads to the distinction of non-removable and removable singularities. We
present some of the effects of these singularities on computations with Ore
operators.

The set of operators of an Ore algebra that give zero when applied to
a given function forms a left ideal. The cost of computing an element of
this ideal depends on the size of the coefficients (the degree) and the order
of the operator. We show how to derive an order-degree curve based on
the study of removable singularities. For a given Ore operator, this is a
curve in the (r, d)-plane such that for all points (r, d) above this curve,
there exists a left multiple of order r and degree d of the given operator.
When computed for the generator of an operator ideal from applications
like physics or combinatorics, the resulting bound is usually sharp.

The generator of a left ideal in an Ore polynomial ring is the greatest
common right divisor of the ideal elements, which can be computed by the
Euclidean algorithm. Polynomial remainder sequences like the subresul-
tant sequence contain the intermediate results of the Euclidean algorithm
when applied to (non-) commutative polynomials. The running time of
the algorithm is dependent on the size of the coefficients of the remainders.
We show how information about the non-removable singularities can be
used to generalize an improvement of the subresultant sequence to Ore
polynomials.

The great majority of embedded signal processing algorithms is implemented using
digital devices such as DSP or FPGA. For power consumption or area reasons, the
computation on these devices is mainly based on integer arithmetic (rather than
floating-point arithmetic). The fixed-point arithmetic is used as an approximation
of real numbers. Unfortunately the numerical implementation of such algorithms suffers
from a deterioration in performance and characteristics, due to the quantization of
the embedded coefficients and the roundoff errors occurring in the computations.
The main objective of my PhD thesis is to optimize and automate the implementation
of a given filter in fixed-point arithmetic, for these devices. In this talk i
present the main works i realized during the first two years of my PhD thesis. After
a short introduction of fixed-point numbers and digital filter processing, i introduce
the ordered-sum-of-products (oSoP) that represent the different orders for the
computation of a sum-of-products, and then i expose a current work that consists on
removing the « useless » bits of a N-term sum in fixed-point arithmetic.

The FMA operation which computes multiplication and addition
performing with only one rounding is required by IEEE754-2008
standard. However, the norm requires only the inputs and the output
of the same radices. The full set of multiradix FP operations does
not exist for the moment, although there are already several
approaches published [1,2]. This work contains the approaches to
implement the multiradix-FMA and the algorithms for computation the
worst cases.

References:

[1] N. Brisebarre, C. Lauter, M. Mezzarobba, and J.-M. Muller, “Comparison
between binary64 and decimal64 floating-point numbers,” in Proceedings
of the 2013 IEEE 21st Symposium on Computer Arithmetic, April 2013.

[2] O. Kupriianova, Ch. Lauter, J.-M. Muller, “Radix Conversion for
IEEE754-2008 Mixed Radix Floating-Point Arithmetic,” in Procedings of
the 47th Asilomar Conference on Signals, Systems, and Computers,
November 2013.

The Learning with Errors Problem (LWE) is a generalisation of
Learning Parity with Noise (LPN) to larger moduli (and different error
distributions). LWE is at the heart of many recent advances in cryptographic
constructions such as fully homomorphic encryption which means that
establishing the concrete hardness of LWE instances is a pressing issue. Three
families of algorithms are known in the literature for solving LWE: (a)
lattice reduction, (b) reduction noise-free polynomial system solving and (c)
combinatorial algorithms. In this talk we will first revisit the most
prominent of the combinatorial algorithms – the Blum-Kalai-Wasserman (BKW)
algorithm – and connect it to more traditional linear algebra algorithms
such as PLE/CUP decomposition using Gray code tables. In a second part
we then adapt this algorithm to the special but popular case where the secret
we wish to recover is “small”.

Joint work with C. Cid, J.-C. Faugère, R. Fitzpatrick, and L. Perret.

Smooth Projective Hash Functions (SPHF) are one of the base tools to build interactive protocols; and this notion
has lead to the construction of numerous protocols enjoying strong security notions, such as the security
in the Bellare-Pointcheval-Rogaway (BPR) model or even Universal Composability (UC).

Yet, the construction of SPHF has been almost limited to discrete-logarithm or pairing type assumptions up to now.
This stands in contrast with domains such as homomorphic encryption or functional encryption, where Lattice Based
Cryptography has already catched up and overtook discrete-log/pairing based cryptography.

So far, work in the direction of UC based on lattices is almost restricted to a paper from Peikert,
Vaikuntanathan, and Waters (Crypto 2008) dealing with Oblivious Transfer in the UC framework, and work
in the direction of password-authenticated key exchange protocols (PAKE) to one from Katz and Vaikuntanathan
(Asiacrypt 2009) on a 3-round Password-Authenticated Key Exchange, but restraining itself to the BPR model.

It seems that dealing with errors in those contexts is not as easy as it is for encryption.
In this talk, I will show the source of the problem, namely, the lattice version of Diffie-Hellman key
exchange protocol: the key agreement is only approximate, and with a simple trick obtain true, errorless,
one-round key exchange from LWE. And then show that this trick can be adapted to various lattice encryption schemes,
leading, with some technicalities, to errorless SPHF’s.

From there, we derived three new results, namely the first lattice-based following protocols: a one-round PAKE
secure in the BPR model, a 3-round PAKE secure in the UC model, and a UC commitment scheme, all of them based on SIS and LWE assumptions.

This is a joint work with Céline Chevalier, Léo Ducas and Jiaxin Pan.

We explain how condition numbers of problems can be used to assess the quality
of a computed solution. We illustrate our approach by considering the example of
overdetermined linear least squares (linear systems being a special case of the latter).
Our method is based on deriving exact values or estimates for the condition number
of these problems. We describe algorithms and software to compute these quantities
using standard parallel libraries. We present numerical experiments in a physical
application and we propose performance results using new routines on top of the
multicore-GPU library MAGMA.

Since the breakthrough of Gentry presenting the first plausible candidate
construction, the past few years have seen an intensive work on new
constructions achieving fully homomorphic encryption. However, all these
primitives have a major downside: they are order of magnitude slower than
usual public-key primitives.

In this talk, we will tackle the practicality of (fully) homomorphic
encryption, its potential and limitation. We will also discuss an inherent
problem about the noise growth in the ciphertexts, the intricate parameter
derivation process (using BKZ-2.0) and some promising recent results and
improvements.

We present a new discrete logarithm algorithm, in the same vein as in recent works by Joux, using an asymptotically more
efficient descent approach. The main result gives a quasi-polynomial heuristic complexity for the discrete logarithm problem
in finite field of small characteristic. By quasi-polynomial, we mean a complexity of type n^{O(log n)} where n is the
bit-size of the cardinality of the finite field. Such a complexity is smaller than any L(ε) for ε>0.
It remains super-polynomial in the size of the input, but offers a major asymptotic improvement compared to L(1/4+o(1)).

Joint work with Jean-Charles Faugère, Pierrick Gaudry and Guénaël Renault.

Polynomial system solving is a classical problem in mathematics with a
wide range of applications. Therefore, its complexity is a central
object of study in theoretical computer science. Depending
on the context, solving has different meanings. To handle the
most general case, we consider a representation of the solutions
that allows us to easily recover the exact solutions
and/or a certified approximation.

Under some genericity assumptions, such a representation is given by the
lexicographical Gröbner basis of the system and consists of a set of
univariate polynomials. The best known algorithm for computing the
lexicographical Gröbner basis requires O(nD³) arithmetic
operations, where n is the number of variables and D is the number of
solutions of the system. We improve this bound to
Õ(D^ω), where 2 ≤ ω < 2.3727 is the
exponent in the complexity of multiplying two dense matrices and the
Õ notation means that we neglect logarithmic factors. To
achieve this result we propose new algorithms that rely on fast
linear algebra. When the degree of the equations is bounded we
propose a deterministic algorithm. In the unbounded case we present a
Las Vegas algorithm.

Wiretap codes are families of codes that promise
both reliability between the legitimate users Alice and Bob, and
confidentiality in the
presence of an eavesdropper Eve. We survey an error probability point
of view to the design of wiretap codes for several continuous
channels, and discuss the resulting code design criteria. They give
rise to a serie of interesting problems,
such as the understanding of a new lattice invariant, or the search
for number fields with particular discriminant and regulator.

Lattices have become an important tool to construct
codes for communication systems impaired by Gaussian noise. We first
propose to review the construction of Euclidean codes for the Gaussian
channel, based on Lattices. After that, we present lattices endowed
with a multiplicative structure that have become very important in the
case of wireless fading channels and wireless Multiple-Antenna
channels. These lattices are in fact ideal lattices coming from either
the canonical embedding of a number field or from the matrix
representation of a central division algebra.

Other communications problems involving lattice codes will be very
briefly presented to show the importance of that tool.

In this talk we will present a compensated
algorithm for the evaluation of the k-th derivative  of a polynomial
in power basis. The proposed algorithm makes it possible the direct
evaluation without obtaining the k-th derivative expression of the
polynomial itself, with a very accurate result to all but the most
ill-conditioned evaluation. Forward error  analysis and running error
analysis are performed by an approach based on the data  dependency
graph. Numerical experiments illustrate the accuracy and efficiency of
the  algorithm. We will use this algorithm to improve the accuracy of
Newton’s method for simple roots that are ill-conditioned.

The adoption of FPGAs as mainstream accelerators
requires the existence of efficient high-level design tools (DSP
Builder Advanced, Altera OpenCL SDK), efficient arithmetic libraries
and an easy/automatic integration (handled automatically by OpenCL
SDK) with the host operating system. Building the mathematical library
for OpenCL (as specified by the Khronos Group) requires the
implementation approximately 70 floating-point functions. In this talk
I will discuss the way we have implemented some of these functions,
focusing on division, tangent and arctangent functions. I will also
cover macro operators, presenting an FPGA-specific implementation of a
fused floating-point polynomial evaluator. Last, I will present a
low-cost implementation of a multiplicative-based FPU targeting
industrial applications.

Nous présentons des calculs de distribution de
motifs dans de longues séquences générées par des sources
markoviennes.

Notre approche tient compte de l’aspect compact du motif considéré par
rapport à la taille de la séquence. Nous présenterons notamment une
approche par expansion de Taylor rapide d’une reconstruction
rationnelle bivariée de la distribution.

L’intérêt de notre approche sera illustré sur deux applications
biologiques : les facteurs de transcription du chromosome humain n°5
et la signature PROSITE de motifs fonctionnels de protéines.Travail en commun avec Grégory Nuel, CNRS-MAP5.

GPUs represent nowadays an important development
hardware platform for many scientific computing applications that
demand massive parallel computations, but currently GPU-tuned multiple
precision arithmetic libraries are scarce. We develop a
multiple-precision floating-point arithmetic library using the CUDA
programming language for the NVidia GPU platform.  In our case, we are
currently using this library for locating invariant sets for chaotic
dynamical systems. I will detail the numerical study, GPU
implementation and a posteriori validation of existence of stable
periodic orbits (sinks) for the Henon map for parameter values close
to the canonical ones. This is a joint work with V. Popescu and W.
Tucker.

Lattice based cryptography has many attributes
compared to Elliptic Curves or Factorization based constructions. On
the theoretical side, hardness of underlying problem is better
understood, it is still resistant to quantum algorithms, and some new
constructionx were unlocked, for example with the breakthrough of
Fully Homomorphic Encryption. On the practical side, it seems well
adapted to small and parallel architectures, most operation being
linear algebra with a very small modulus.However, early schemes schemes such as NTRUSign were broken by
statistical attack, the reason being that Babaï’s algorithms behavior
reflect the geometry of the secret keys. In 2008, Gentry et al. shows
that it is possible to prevent such statistical leakage by using
Discrete Gaussian distribution. However, Sampling such distribution is
quite slow in practice; in particular it requires computations with
real numbers at high precision.

This presentation will focus on the algorithmic and implementation
aspects of Discrete Gaussian, and cryptographic applications. Our
first topic will be the analysis of existing algorithms, and
improvements using laziness techniques, shrinking the overall
complexity from quadratic to quasi-linear. Then we will focus on a
less general case of Gaussian Sampling, for which we can tailor
bit-level algorithms that requires no floating point arithmetic at
all. Those last algorithms are part of a new signature scheme, BLISS,
that outperforms RSA signatures by a speed factor more than 10.

Je ferai un petit tour des différentes techniques
arithmétiques que nous utilisons actuellement pour la protection
contre des attaques par mesure de la consommation d’énergie, du
rayonnement électromagnétique et/ou du temps de calcul.

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.

Un schéma de signatures « préservant la structure »
(SPS) est un schéma de signature numérique à clef publique dans lequel
la clef publique, les messages et les signatures sont tous des
n-uplets d’éléments de groupe bilinéaire, et la vérification de
signature s’obtient en évaluant des produits de couplages. Cette
primitive a de nombreuses applications à la construction de protocoles
cryptographiques. Sur les groupes bilinéaires asymétriques (couplages
de type III), on connaît des schémas de SPS optimaux : on sait montrer
qu’un nombre minimal d’équations de vérification et une taille
minimale de signature sont nécessaires pour qu’un tel schéma soit
(prouvé) sûr, et l’on dispose par ailleurs de constructions atteignant
cette borne inférieure. En revanche, les constructions de SPS sur les
groupes bilinéaires symétriques (couplages de type I) sont beaucoup
moins bien comprises. Dans cet exposé, nous présentons la première
borne inférieure pour les SPS sur un groupe bilinéaire symétrique, en
établissant qu’un tel schéma avec une seule équation de vérification
ne peut pas être sûr. Pour cela, nous ramenons le problème d’obtenir
une attaque par message connu sur un tel schéma à la recherche d’une
courbe rationnelle dans l’intersection d’une famille explicite de
quadriques en dimension 10, que nous effectuons par un calcul de base
de Gröbner. La même méthode permet en outre d’établir une borne
inférieure analogue pour les signatures « one-time » préservant la
structure, ce qui fournit un résultat de séparation entre groupes
bilinéaires symétriques et asymétriques. Travail commun avec Masayuki
Abe (NTT, Japon) et Miyako Ohkubo (NICT, Japon).

A fast multipole method (FMM) for asymptotically
smooth kernel functions (1/r, 1/r4, Gauss and Stokes kernels, radial
basis functions, etc.) based on a Chebyshev interpolation scheme has
been introduced in [1]. The method has been extended to oscillatory
kernels (e.g., Helmholtz kernel) in [2]. We present optimizations of
the multipole-to-local (M2L) operator (the costliest FMM operator) for
these formulations and address both potential uses of the FMM: (1) a
single matrix-vector product requires a quick precomputation, and (2)
many matrix-vector products (iterative solution of a system of linear
equations ) require a quick application of the M2L oper- ator. First,
we propose an improvement of the optimizations introduced in [1, 2]:
an individual recompression of the M2L operators leads to a provably
smallest computational cost among the class of dense M2L operators.
The second bottleneck of the existing optimizations is their
precomputation time. We introduce a new set of optimizations that
exploit all symmetries in the arrangement of the far-field
interactions. This allows us to express all M2L operators as per-
mutations of a small subset of operators only. Besides drastically
reducing precomputation time and memory requirement, this approach
also paves the road for various algorithmic improve- ments, such as a
more efficient use of processor memory cache through the use of
matrix-matrix products instead of matrix-vector products. We conclude
the talk with numerical benchmarks of the optimizations of the M2L
operator and an in depth analysis of the outperforming variants.

References

[1] W. Fong and E. Darve. The black-box fast multipole method. J. of
Comput. Phys., 228(23):8712–8725, 2009.

[2] M. Messner, M. Schanz, and E. Darve. Fast directional multilevel
summation for oscillatory kernels based on chebyshev interpolation. J.
of Comput. Phys., 231(4):1175 – 1196, 2012.

 Both the direct computation and the inversion of
the cumulative $\chi^2$ distributions (also called gamma
distributions) are used in many problems in statistics, applied
probability and  engineering. Algorithms for the numerical evaluation
and inversion of the incomplete gamma function ratios  (central
$\chi^2$ distributions) $P(a,x)=\gamma(a,x)/\Gamma(a)$ and
$Q(a,x)=\Gamma(a,x)/\Gamma(a)$  are described for positive values of
$a$ and $x$. The method for the computation of the ratios $P(a,x)$ and
$Q(a,x)$ use different approximations (Taylor series, continued
fraction and uniform asymptotic expansions) in different regions of
the parameters and it is similar to Gautschi’s method but with the
addition of uniform asymptotic expansions for large values of $a$ and
$x$. Non-central gamma distribution functions (also called Marcum
functions) are functions of three variables $P_{\mu}(x,y)$,
$Q_{\mu}(x,y)$ which reduce to  central gamma distributions when
$x=0$. We describe algorithms for the computation and inversion of the
non-central cumulative distributions based on series expansions,
integral representations,   asymptotic expansions and the use of
three-term homogeneous recurrence relations.

Les intégrales multiples de fractions rationnelles
dépendant de paramètres satisfont des équations différentielles. Je
détaillerai quelques applications de ces équations en arithmétique et
en combinatoire. La question qui se pose est alors de calculer ces
équations. Je présenterai un algorithme récent que nous avons
développé avec Alin Bostan et Bruno Salvy à partir d’une méthode due à
Griffiths et Dwork. D’un point de vue concret, les calculs se ramènent
à de la manipulation de matrices à coefficients polynomiaux. D’un
point de vue plus théorique en calcul formel, nous obtenons de
nouvelles bornes sur la taille de ces équations différentielles, ainsi
qu’une complexité améliorant de manière importante ce qui était connu.
Un des facteurs de cette amélioration est que cet algorithme, pour la
première fois, évite le calcul d’un certificat, qui permet a
posteriori la vérification du calcul mais dont la taille peut être
bien plus importante que celle de l’équation désirée.

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.

A secure multiparty computation protocol allows a
set of parties, each holding a private input, to jointly compute a
function of these private inputs, while preserving the secrecy of the
private inputs. Such protocols have numerous applications in settings
where mutually distrusting parties need to collaborate in a
computation (e.g. auctions). The classical approach to constructing
such protocols for general functions (in the computationally
unbounded, passive attack model), reduces the task to a computation
over a finite field.In this talk, we introduce the topic of secure multiparty computation,
and then present an alternative to the classical approach to
constructing secure multiparty protocols for general functions, that
reduces the task to a computation over a non-Abelian group. We then
show how to implement such protocols over black-box groups via a

reduction to a graph colouring problem, and present some constructions
for such colourings.

This talk is based on joint works with (subsets of) Yvo Desmedt, Josef
Pieprzyk, Xiaoming Sun, Christophe Tartary, Huaxiong Wang and Andrew
Chi-Chih Yao.

The talk is about computing efficiently p-adic
lifting by relaxed algorithms. In a first part, we introduce relaxed
algorithms and their application to the computation of recursive
p-adics. To use this framework for the p-adic lifting of various
systems of equations, one has to transform the given implicit
equations to recursive ones. We detail the process of equations
transformation for linear equations, possibly differential, and also
for the lifting of resolutions of polynomial systems. In all cases
cases, these new relaxed algorithms are compared to existing
algorithms, both in theory and practice. This talk sums up different
works in collaboration with J. Berthomieu, A. Bostan, M. Chowdhurry,
B. Salvy and É. Schost.

Data analysis in High Energy Physics, from
acquisition to publication, is computational intensive. We will
describe the process that transforms raw data in physics results at
LHC with focus on computational challanges in terms of data volume,
speed, and numerical accuracy. This process involves many different
types of software appllications, ranging from simple signal processing
to multivariate data analysis, with very different requirements on the
precision and accuracy of numerical computations. In particular the
need of both high precision numerical libraries as well as of faster
algorithm with tunable precision will be underlined.

Résumé : la sélection polynomiale pour factoriser
un entier N via le crible algébrique (Number Field Sieve ou NFS en
anglais) consiste à trouver deux polynômes f(x) et g(x) à coefficients
entiers ayant une racine commune m modulo N. Autrement dit, on veut
Res(f(x),g(x)) = k*N, avec k un entier aussi petit que possible (k=1
ou k=-1 sont optimaux). Les meilleurs algorithmes connus utilisent un
polynôme g(x) linéaire (de la forme p*x-q). Par exemple pour la
factorisation de RSA768 on a utilisé f(x) de degré 6 et g(x) de degré
1. Or des expériences montrent que si on savait trouver des paires
optimales de polynômes non-linéaires (par exemple de degrés 5 et 2) on
pourrait accélérer la phase de crible, qui est la plus coûteuse (1500
années CPU pour RSA768). L’exposé décrira l’état de l’art en ce qui
concerne la sélection polynomiale non linéaire, et donnera quelques
pistes possibles pour trouver des polynômes optimaux.

More than ten years ago, S. Rump proposed to use
midrad representation when multiplying interval matrices. With this
representation, interval matrix products can be performed through
successive calls to point matrix product functions of an optimized
BLAS library. In 2011, H.D. Nguyen and Rump improved the original
algorithm from the points of view of both efficency and accuracy. This
talk will deal with the implementation issues of these algorithms,
especially issues of parallelization targeted on multicores. The
differences in accurracy will also be presented through the
theoretical error analysis and numerical experiments.

Un code correcteur d’erreurs de distance minimale d
peut corriger sans ambiguïté, en théorie, jusqu’à (d – 1) / 2 erreurs.
Cette borne naturelle n’est quasiment jamais atteinte en temps
polynomial. Il existe néanmoins une famille de codes dont on connait
un algorithme polynomial permettant de corriger plus de (d – 1) / 2
erreurs. Or il n’existe pas d’implantation dédiée à cet algorithme. Je
commencerai par faire quelques rappels rapides sur les codes
correcteurs d’erreurs et leurs algorithmes de décodage. Ensuite je
vais présenter brièvement le système Mathemagix et certains de ses
paquets, pertinents pour les problèmes de corrections d’erreurs. Je
donnerai quelques détails sur le mécanisme des variantes qui utilise
fortement les templates de C++. J’exposerai les conséquences de ce
mécanisme qui permet en particulier d’écrire des algorithms de manière
générique. Enfin j’expliquerai pourquoi j’ai commencé l’écriture d’une
librairie dédiée aux algorithmes de décodage en C et non en C++. Je
donnerai quelques détails d’implantation pour expliquer les choix que
j’ai fait pour avoir une certaine généricité au niveau de l’alphabet
des codes correcteurs.

Dans un premier temps, je présenterai succinctement
les principales problématiques et contributions de mes travaux de
thèse sur certaines familles de systèmes polynomiaux structurées
(systèmes déterminantiels, systèmes multi-homogènes, systèmes points
critiques). Leur lien avec différents domaines applicatifs
(cryptologie, géométrie réelle, problèmes de minimisation) sera
également évoqué.Je parlerai ensuite plus précisément des systèmes quadratiques
booléens, qui apparaissent fréquemment en cryptologie. Nous donnons un
algorithme probabiliste (de type Las Vegas) qui combine recherche
exhaustive et algèbre linéaire creuse sur les matrices de Macaulay
afin d’en trouver les solutions avec une complexité bornée par
O(2^0.792n) sous des hypothèses algébriques précises. Une variante
déterministe (de complexité O(2^0.841n) est également proposée. Des
expériences sur des systèmes aléatoires montrent que ces hypothèses
sont vérifiées avec une probabilité proche de 1. Travail commun avec
Magali Bardet, Jean-Charles Faugère et Bruno Salvy.

Commitment schemes are a cryptographic primitive
that can be seen as the digital equivalent of a safe or a sealed
envelope. Namely, the content remains secret until the envelope is
opened. At  the same time, everyone is convinced that the sender has
defined a unique message and cannot change his mind about it before
the opening phase.

In 2003, Micali, Rabin and Kilian (MRK) defined a primitive, called
zero-knowledge sets (ZKS), which allows a prover to commit to a secret
set S – or even an elementary database – so as to be able to prove
statements of the form « element x belongs to S » or « element x does
not belong to S » without revealing anything else, not even the size
of S.

Chase et al. (Eurocrypt 2005) showed that ZKS protocols are underlain
by a cryptographic primitive called mercurial commitment. A mercurial
commitment scheme has two commitment procedures. At committing time,
the sender can choose not to commit to a specific message and rather
generate a dummy value which it will be able to softly open to any
message without being able to completely open it. Hard commitments, on
the other hand, can be hardly or softly opened to only one message. At
Eurocrypt 2008, Catalano, Fiore and Messina (CFM) introduced an
extension called trapdoor q-mercurial commitment (qTMC), which allows
committing to a vector of q messages. These qTMC schemes are
interesting since their openings w.r.t. specific vector positions can
be short (ideally, the opening length should not depend on q), which
provides zero-knowledge sets with much shorter proofs when such a
commitment is combined with a Merkle tree of arity q. The CFM
construction notably features short proofs of non-membership as it
makes use of a qTMC scheme with short soft openings. However, hard
openings still have size O(q), which prevents proofs of membership
from being as compact as those of non-membership. In this talk, we
present a solution to this problem and describe a qTMC scheme where
hard and soft position-wise openings, both, have constant size. For
suitable parameters, our system allows compressing the proofs of the
MRK solution to 13% of their initial length. We also show that our
scheme is amenable to constructing independent ZKS schemes, which
prevent cheating provers from correlating their set to the sets of
honest provers.

The aim of this talk is to give an idea of how to
formally certify Taylor models in the Coq proof assistant. The concept
of Taylor model for a real function is an instance of a more general
concept, a rigorous polynomial approximation (RPA) for that function.
A RPA is defined as a pair formed of a polynomial and of an interval
which contains the approximation error between the polynomial and the
function. In the case of Taylor models for elementary functions the
polynomial is the Taylor polynomial and the error interval is given by
the Lagrange remainder. For composite functions we introduce an
arithmetic on Taylor models.We implemented an abstract interface for RPAs in Coq. We then provide
an abstract interface for Taylor models as a special kind of RPAs. We
prove the correctness of our Taylor models at the abstract interface
level, therefore every instance of this interface will benefit from
the proofs. The difficulty in doing the proofs at this level is to
find the minimal assumptions on the abstract structures that are
needed to ensure correctness and that are verified by the concrete
structures.

In our implementation we use a uniform approach to compute the Taylor
models of elementary functions: we use recurrence relations to compute
the Taylor polynomial as well as the remainder. All functions we are
interested in satisfy recurrence relations of order 1 or of order 2.
For each kind of these recurrences we provide one generic proof that
can be then specialized to the desired function. We also provide
proofs of correctness for Taylor models of composite functions.

Besides the specific proofs for Taylor models, we will discuss some
general techniques that are used in the formal certification of
computation inside proof assistants.

At Eurocrypt 2010, Howgrave-Graham and Joux
described an algorithm for solving hard knapsacks of n elements and
density close to 1 using a new technique that we call representation
technique. This improved a 30-year old algorithm by Shamir and
Schroeppel. In this talk we will present the following: Using the
simple observation that the solution to the knapsack problem, a binary
vector, can be represented by two overlapping vectors with
coefficients in {-1,0,1}, we can improve on the above result.
Furthermore, the technique can be applied to improve information set
decoding attacking linear codes such as used in McEliece public key
encryption. We can improve recent results on half-distance decoding
such as Ball-collision decoding and May-Meurer-Thomae–ISD of
asymptotic time complexity. Previous attempts split the solution
vector in disjoint

parts. We search the solution as decomposition of two overlapping
vectors which permits to reduce the running time in the asymptotic
case.

The talk is based on the publications:

http://eprint.iacr.org/2011/474

http://eprint.iacr.org/2012/026

a joined work with Jean-Sébastien Coron, Antoine Joux, Alexander
Meurer and Alexander May.

Résumé à venir

The implementation of signal processing algorithms
(or control algorithms) in embedded digital devices is a difficult,
error-prone and time-consuming task, essentially due to the finite
precision problems. The fixed-point arithmetic used in that context
implies a deterioration in performance and characteristics of the
filters/controllers, due to the quantization of the embedded
coefficients and the roundoff errors occurring in the computations.

We propose in this presentation to detail the “optimal implementation
problem” and to list the various possible actions required to deal
with the tradeoff  precision/performance/implementation cost.  A
global method to transform real filters/controllers to fixed-point
implementations will be presented, and compared to the floating-point
function evaluation problem.

Determinants of 2 by 2 matrices are basic numerical
kernels used for example for implementing complex arithmetic or
geometric predicates, and whose naive evaluation in floating point can
suffer severe cancellations and eventually produce inaccurate answers
(0 instead of 1). When a fused multiply-add operation is available,
Kahan gave an algorithm that is known to reduce the effect of such
cancellations. In this talk we will see that Kahan’s algorithm is in
fact *always* highly accurate. Specifically, we shall present a
complete rounding error analysis of this algorithm and establish, for
radix r and unit roundoff u, that its absolute error is at most
(r+1)/2 ulps of the exact result, that its relative error is at most
2*u, and that these bounds are essentially optimal.This is joint work with Nicolas Louvet and Jean-Michel Muller.

Les systèmes de calcul formel et de preuves
formelles sont deux familles de logiciels qui ont vocation à utiliser
un ordinateur pour faire des mathématiques. Si le calcul formel
s’intéresse principalement à l’algorithmique

et à l’efficacité des calculs, la preuve formelle s’attache à obtenir
une très haute garantie de la correction des énoncés formalisés. Une
des spécificités du système Coq est la place que la notion de calcul
occupe dans le formalisme logique sous-jacent à cet assistant à la
preuve. Une conséquence en est que l’on dispose dans ce système d’un
véritable langage de programmation fonctionnel, qui peut être utilisé
pour modéliser mais aussi pour exécuter (relativement efficacement)
des programmes, garantissant ainsi la correction des valeurs
calculées. Cette utilisation du calcul, combinée avec le développement
récent d’un nombre substantiel de bibliothèques de mathématiques
formalisées, est particulièrement propice à l’implémentation et à la
certification en Coq d’algorithmes issus du calcul formel. Dans ce
exposé, nous montrerons quelques expériences autour du mariage entre
calcul formel et preuves formelles, qui s’efforcent d’exploiter au
mieux les avantages respectifs de ces deux modes de programmation en
les faisant coopérer.

LinBox is a C++ software library for high
performance exact linear algebra (dense, sparse, and structured
matrices over integers, finite fields).  It is developed now within
the HPAC project. I will briefly review the history and central ideas
of LinBox then discuss several current opportunities.  The central
ideas include blackbox algorithms (iterative methods in surprising
places), efficient dense matrix operations (use of numeric BLAS for
exact results), and generic design for effective combination of
general and specialized algorithms.  As I am a visitor to LIP until
July, I will then emphasize several areas where collaborations might
be possible either to advance LinBox capabilities or exploit current
ones.  Current opportunities include several in the area of
symbolic/numeric hybrid computation and blackbox/dense combinations.

Il est bien connu que l’addition dans un système de
numération standard a une complexité linéaire, ce qui est trop lent
pour faire un processeur arithmétique efficace. En 1961, Avizienis a
donné un algorithme parallèle d’addition en base 10 avec les chiffres
{-6, -5, …, 5, 6} où la retenue ne se propage pas. On obtient ainsi
une complexité (en parallèle) constante. Dans le langage de la
dynamique symbolique, une telle addition est une fonction locale
(sliding block code). Cette technique est utilisée pour accélérer les
algorithmes de multiplication et de division.Dans ce travail nous nous intéressons à des systèmes de numération où
la base est un nombre algébrique beta, |beta|>1. Quand tous les
conjugués algébriques de beta ont un module différent de 1, on peut
trouver un alphabet symétrique de chiffres signés entiers sur lequel
faire l’addition en parallèle. Cet algorithme est une généralisation
de celui d’Avizienis.

L’algorithme d’addition est simple, mais l’alphabet obtenu est en
général plus grand que nécessaire. Nous donnons des bornes inférieures
sur la cardinalité minimale d’un alphabet permettant de faire
l’addition en parallèle. Nous présentons ensuite une série de cas où
la borne est atteinte.

Travail en collaboration avec Edita Pelantová et Milena Svobodová
(CTU, Prague)

Monte-Carlo simulations have slow convergence and
so require ridiculous numbers of random trials in order to provide an
accurate answer, but for many high-dimensional problems they are the
only numerical tool available. Fortunately Monte-Carlo simulations are
also embarassingly parallel, so there is huge scope for acceleration
using devices such as GPUs and FPGAs, particularly if one is willing
to take advantage of low-precision number formats. However, this
becomes dangerous: how can one guarantee (or even define) quality and
accuracy for a massively parallel simulation utilising many trillions
of independent low-precision random trials?This talk will explore two specific areas of concern when using
hardware-accelerated Monte-Carlo: are the sources of uniform random
bits “random” enough, and do the process which shape them into
non-uniform random samples actually produce the correct distribution?
The first part will examine the use of GF2-based linear recurrences
for generating random bits, and question whether traditional software
notions of lattice-based randomness make sense for hardware. The
second part will consider the role of accuracy and ULP-ness in
statistical code, showing that (sometimes) a cheap low-precision table
lookup is more accurate than a traditional high-precision
function-approximation with rounding guarantees.

De nombreux problèmes applicatifs se modélisent par
des systèmes polynomiaux. Dans de nombreuses situations, des
informations sur les solutions réelles de ces systèmes sont attendues.
Dans cet exposé, on se concentrera sur 3 spécifications importantes :
le test d’existence de solutions et le calcul de certificats
algébriques de positivité, l’élimination d’un bloc de quantificateurs
et les tests de connexité.L’enjeu est d’obtenir des algorithmes efficaces tant en pratique qu’en
théorie permettant de traiter ces problèmes. On survolera les récentes
avancées sur ces 3 sujets, en mettant l’accent sur les idées le plus
souvent intuitives et géométriques qui ont permis d’aboutir. Une
attention particulière sera aussi apportée aux interactions entre
calcul formel et numérique dans ce contexte.

Cet exposé est construit sur la base de travaux communs avec B. Bank,
S. Basu, J.-C. Faugère, M. Giusti, A. Greuet, J. Heintz, M.-F. Roy, E.
Schost et L. Zhi.

In this talk I describe a new deterministic
algorithm for the computation of a minimal nullspace basis of an
$m\times n$ input matrix of univariate polynomials over a field
$\mathbb{K}$ with $m\le n$. This algorithm computes a minimal
nullspace basis of a degree $d$ input matrix with a cost of
$O^{\sim}\left(n^{\omega}\left\lceil md/n\right\rceil \right)$ field
operations in $\mathbb{K}$. The same algorithm also works in the more
general situation on computing a shifted minimal nullspace basis, with
a given degree shift $\vec{s}\in\mathbb{Z}^{n}$ whose entries bound
the corresponding column degrees of the input matrix. In this case a
$\vec{s}$-minimal right nullspace basis can be computed with a cost of
$O^{\sim}(n^{\omega}\rho/m)$ field operations where $\rho$ is the sum
of the $m$ largest entries of $\vec{s}$.This is joint work with Wei Zhou and Arne Storjohann of Waterloo.

One  of the  most common  and practical  ways of
representing  a real function on  machines is by  using a polynomial
approximation.   It is then  important to  properly handle  the error
introduced by  such an approximation.    A  typical  way   to
provide   rigorous  polynomial approximations relies  on the concept
of Taylor  model, which consists of a pair combining a Taylor
approximation polynomial with an interval remainder that bounds the
approximation errors.Our goal  is to provide  an efficient implementation of  Taylor models
with formally  guaranteed error bounds.   A key requirement was  to be
able to perform all the  computations at stake inside the formal proof
checker.  After  a brief introduction  to the Coq proof  assistant, we
will thus  present how we  carry out this  work in Coq with  a special
focus on  genericity and efficiency  for our implementation.   On some
examples  inspired  by  the   TaMaDi  project,  we  will  compare  the
performances of  our implementation  in Coq with  those of  the Sollya
tool, which contains an implementation of Taylor models written in C.

The  talk is  based on  a joint  work with  N. Brisebarre,  M. Joldes,
M. Mayero, J.-M. Muller, I. Pasca, L. Rideau and L. Théry that will be
presented at NASA Formal Methods 2012.

Key-Words: Coq proof assistant, rigorous polynomial approximation,
guaranteed error bounds, Taylor models, interval arithmetic.

 Dans cet exposé, nous nous intéressons au problème
du rang bilinéaire : étant donnée une application bilinéaire (par
exemple, le calcul d’un produit de polynômes, d’éléments d’un corps
fini, ou encore de matrices), quel est le nombre minimal de
multiplications sur le corps de base nécessaires pour évaluer cette
application ?

Ainsi, par exemple, la méthode de Karatsuba permet de calculer le
produit de deux polynômes linéaires en seulement trois multiplications
au lieu de quatre. Nous donnons dans cet exposé une formalisation du problème du rang
bilinéaire, connu pour être NP-dur, et proposons un algorithme général
permettant de calculer efficacement des solutions exactes, qui nous
permettent ainsi de prouver l’optimalité de, voire même d’améliorer
certaines bornes de la littérature.

En algorithmique, on manipule très souvent des mots,
notamment dans l’algorithmique du texte ; plus souvent encore, on
manipule ce qu’on appelle communément des clés, notamment dans les
algorithmes de tri ou de recherche, ou dans les bases de données. Dans
une perspective plus réaliste, il faut vraiment considérer une clé
comme une suite finie de symboles, c’est-à-dire comme un mot. On
remplace alors le coût unitaire d’une comparaison entre deux clés par
le coût de la comparaison entre deux mots, égal au nombre de symboles
comparés. L’algorithmique générale devient alors de l’algorithmique du
texte, et le processus qui produit les mots, appelé source, acquiert
alors une grande importance.

Notre programme, décrit dans l’exposé, est donc le suivant

(a) Donner un sens à ce qu’on appelle une ≪ source générale ≫, opérer
une classification des sources, en exhibant des sous-classes
intéressantes, reliées notamment à des systèmes dynamiques.

(b) Définir une série génératrice (de type Dirichlet) reliée
canoniquement à la source et relier la classification des sources à la
classification (analytique) de leurs séries de Dirichlet.

(c) Exhiber une propriété importante de la source, appelée la ≪
discipline ≫, et, dans le cas des sources dynamiques, donner des
conditions suffisantes qui entraînent la discipline.