The calendar of these seminars can be subscribed to by clicking here.

# Next seminars

Carlos Beltrán (Universidad de Cantabria, Spain)

December, 7 2023 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Do we have a sound theory of stability for floating point algorithms?

# 2023-2024

Rémi Prébet (LIP6, Sorbonne Université)

November, 23 2023 at 10h15, online seminar and salle du conseil du LIP (3rd floor, Monod)

Connectivity in real algebraic sets: algorithms and applications

I will first show how classical subroutines of this field, such as computing one point in each connected component or deciding connectivity queries, can be used to solve challenging problems in robotics, such as cuspidality decisions. Then, I will present new algorithmic improvements to the problem of answering connectivity queries in real algebraic sets by using the notion of roadmaps, which allows to reduce such problems to the case of connectivity queries over real algebraic curves. Throughout the talk, we will pay close attention to the complexity of the algorithms under consideration.

This talk gathers joint works with D. Chablat, N. Islam, A. Poteaux, M. Safey El Din, D. Salunkhe, É. Schost and P. Wenger.

# 2022-2023

Michael Overton (Courant Institute, New York University)

June, 28 2023 at 16h15, Amphi B (3rd floor, Monod)

Crouzeix’s Conjecture

*A*, \(\|p(A)\| \le 2 \max\{|p(z)|: z \in W(A)\}\), where the norm is the 2-norm and \( W(A) \) is the field of values (numerical range) of \(A\), that is the set of points attained by \( v^*Av \) for some vector \(v\) of unit length. Crouzeix proved in 2007 that the inequality above holds if \(2\) is replaced by \(11.08\), and in 2016 this was greatly improved by Palencia, replacing \( 2 \) by \( 1+\sqrt{2} \). Furthermore, it is known that the conjecture holds in a number of special cases. We use nonsmooth optimization to investigate the conjecture numerically by locally minimizing the “Crouzeix ratio”, defined as the quotient with numerator the right-hand side and denominator the left-hand side of the conjectured inequality. We use Chebfun to compute the boundary of the fields of values and BFGS for the optimization, computing the Crouzeix ratio at billions of data points. We also present local nonsmooth variational analysis of the Crouzeix ratio at conjectured global minimizers. All our results strongly support the truth of Crouzeix’s conjecture.

Gilles Villard (LIP, ENS Lyon)

June, 22 2023 at 10h15, online seminar and salle du conseil du LIP (3rd floor, Monod)

Elimination ideal (and bivariate resultant) in quasi-linear time over finite fields

Our approach is to use the reduction of the problem to a problem of minimal polynomial in the quotient algebra \(\mathbb F_q[x,y]/\langle a,b \rangle\). By proposing a new method based on structured polynomial matrix division for computing with the elements in the quotient, we manage to improve the best known complexity bounds.

We present the main lines of the algorithm, and more particularly the underlying computations modulo the ideal generated by \(a\) and \(b\).

Marc Mezzarobba (CNRS, LIX, MAX)

June, 15 2023 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Asymptotic Expansions with Error Bounds for Solutions of Linear Recurrences

This is based on joint work with Ruiwen Dong and Stephen Melczer.

Jérémy Berthomieu (PolSys, LIP6, Sorbonne Université)

May, 11 2023 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Guessing linear recurrence relations for polynomial system solving

First, we shall present msolve, a new open source C library, for solving polynomial systems using Gröbner bases. Second, we describe new algorithms and complexity estimates for computing Gröbner bases either for a total degree order or the lexicographic one. Then, we present linear algebras-based and polynomial-division-based algorithms for guessing linear recurrences with constant or polynomial coefficients, in generic and structured situations.

This is based on joint works with Alin Bostan, Christian Eder, Jean-Charles Faugère, Andrew Ferguson, Vincent Neiger and Mohab Safey El Din

Fredrik Johansson (LFANT, INRIA Bordeaux)

March, 16 2023 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Faster computation of elementary functions

Alexandre Goyer (MATHEXP, Inria Saclay)

January, 26 2023 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Seminumeric Approach to Dealing with Differential Operators

First I will explain how we revisited the seminumeric factorization algorithm [4]. Secondly, if time allows, I will show some preliminary observations that should lead to seminumeric algorithms for deciding the algebraicity of the solutions. The second part will be illustrated by some worksheets using my code for the factorization of differential operators. Based on joint work and discussions with Moulay Barkatou, Frédéric Chyzak, Thomas Cluzeau, Marc Mezzarobba, Sergey Yurkevich and Jacques-Arthur Weil.

References:

[1] Introduction to the Galois Theory of Linear Differential Equations, M. F. Singer, 2007

[2] Computing the Galois Group of a Linear Differential Equation, E. Hrushovski, 2002

[3] Around the Numeric-Symbolic Computation of Differential Galois Groups, J. van der Hoeven, 2007

[4] Symbolic-Numeric Factorization of Linear Differential Operators, F. Chyzak, A. Goyer, M. Mezzarobba, 2022

Alhussein Fawzi (Google DeepMind, London, UK)

January, 19 2023 at 10h15, online seminar

Discovering faster matrix multiplication algorithms with deep reinforcement learning

Armelle Perret du Cray (ECO, LIRMM, Université de Montpellier)

December, 8 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Interpolation de polynômes creux sur les entiers

Ceci provient de travaux effectués avec Pascal Giorgi, Bruno Grenet et Daniel S. Roche.

Damien Stehlé (AriC, LIP, ENS Lyon)

November, 24 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Fiat-Shamir lattice signatures: Dilithium and perspectives

In this talk, I will give an overview of Fiat-Shamir lattice signatures and their security, focusing on Dilithium. If time permits, I will also describe ongoing works towards improving the efficiency.

Warwick Tucker (AriC, LIP, ENS Lyon and Monash Univ., Australia)

October, 27 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Lower bounds on the Hausdorff dimensions of Julia sets

Thomas Espitau (NTT Secure Platform Laboratories, Tokyo)

October, 14 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

On hash-and-sign lattice based signatures scheme: GPV, Falcon and beyond.

Christoph Koutschan (Radon Institute for Computational and Applied Mathematics, Austrian Academy of Sciences, Austria)

October, 13 2022 at 10h15, online seminar

Guessing with Little Data

Klara Nosan (IRIF, Université Paris Cité)

September, 22 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

The Membership Problem for Hypergeometric Sequences with Rational Parameters

This work is in collaboration with Amaury Pouly, Mahsa Shirmohammadi and James Worrell. The full version of the paper is available at https://arxiv.org/abs/2202.07416.

# 2021-2022

Julien Devevey (AriC, LIP, ENS Lyon)

June, 23 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

On Rejection Sampling in Lyubashevsky’s Signature Scheme

This is joint work with Omar Fawzi, Alain Passelègue and Damien Stehlé.

Alain Passelègue (INRIA, AriC, LIP, ENS Lyon)

May, 19 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

New Constructions of Statistical NIZKs: Dual-Mode DV-NIZKs and More

In this work, we develop new techniques for constructing statistical NIZK arguments. First, we construct statistical DV-NIZK arguments from the k-Lin assumption in pairing-free groups, the QR assumption, and the DCR assumption. These are the first constructions in pairing-free groups and from QR that satisfy statistical zero-knowledge. All of our constructions are secure even if the verification key is chosen maliciously (i.e., they are “malicious-designated-verifier” NIZKs), and moreover, they satisfy a “dual-mode” property where the CRS can be sampled from two computationally indistinguishable distributions: one distribution yields statistical DV-NIZK arguments while the other yields computational DV-NIZK proofs. We then show how to adapt our k-Lin construction in a pairing group to obtain new publicly-verifiable statistical NIZK arguments from pairings with a qualitatively weaker assumption than existing constructions of pairing-based statistical NIZKs.

Our constructions follow the classic paradigm of Feige, Lapidot, and Shamir (FLS). While the FLS framework has traditionally been used to construct computational (DV)-NIZK proofs, we show that the same framework can be leveraged to construct dual-mode (DV)-NIZKs.

Joint work with Benoît Libert, Hoeteck Wee, and David J. Wu.

Hippolyte Signargout (LIP, ENS Lyon and LJK, Université Grenoble Alpes)

May, 12 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Computing the resultant of bivariate polynomials with structured high-order lifting

This is joint work with Clément Pernet (LJK) and Gilles Villard (LIP).

Le Quoc Tung (Ockham, LIP, ENS Lyon)

May, 5 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Sparse Matrix Factorization with Fixed Support

This is joint work with Elisa Riccietti and Rémi Gribonval.

Balthazar Bauer (IRIF, Paris)

April, 7 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Transferable E-cash: An analysis in the algebraic group model

Our main goal was to revisit security models concerning the anonymity of payments, and then to propose a theoretically deployable payment system also based on the paradigm of proven security. During the presentation, I will talk about security models guaranteeing anonymity, as well as more fundamental questions concerning a family of cryptographic assumptions commonly used in provable security.

Théo Mary (CNRS LIP6, Sorbonne Université)

March, 24 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Blocked summation, GPU tensor cores, probabilistic analysis, and how it all ties together with multiword arithmetic

Clément Pernet (LJK, Université Grenoble Alpes)

March, 10 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Deterministic computation of the characteristic polynomial in the time of matrix multiplication

Philippe Dumas (SpecFun, INRIA Saclay)

February, 10 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Hypergeometric solutions for linear Mahler equations

These equations are a tool for the proof of transcendence of certain formal power series appearing as ordinary generating functions of sequences related to the divide-and-conquer strategy or produced by automata.

We are looking for solutions of these equations that are analogues of hypergeometric sequences in the context of recurrences in the shift. In other words, we look for solutions of a given equation which are themselves solutions of equations of order 1, \(y(x) = u(x) y(x^b)\) with \(u(x)\) a ramified rational function a priori unknown. For this purpose we develop two approaches. The first one mimics the Gosper-Petkovšek method for finding hypergeometric solutions of a linear recurrence. The second one uses Hermite-Padé approximants and experimentally provides a more efficient way than the first approach.

Magali Bardet (LITIS, Université de Rouen)

February, 3 2022 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

Algebraic decoding of Fqm-linear codes in rank metric

In this talk, I will present the three problems and their relations to cryptographic schemes, their algebraic modeling and the recent improvements in the understanding of the complexity of solving those systems using algebraic techniques like Gröbner bases computations.

This gathers joint works with P. Briaud, M. Bros, D. Cabarcas, P. Gaborit, V. Neiger, R. Perlner, O. Ruatta, D. Smith-Tone, J.-P. Tillich.

Éric Goubault (LIX, École Polytechnique)

January, 27 2022 at 10h15, online seminar

Verification of ReLU neural networks with tropical polyhedra

This is joint work with Sylvie Putot.

Stef Graillat (PEQUAN, LIP6, Sorbonne Université)

December, 16 2021 at 10h15, online seminar

On a compensated Ehrlich-Aberth method for the accurate computation of all polynomial roots

Huu Phuoc Le (PolSys, LIP6, Sorbonne Université)

December, 9 2021 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

One block quantifier elimination over the reals: algorithms, complexity and applications

In this task, I will describe a new efficient algorithm for one block quantifier elimination under some mild assumptions. This computes semi-algebraic formulas which describe a dense subset of the interior of the projection of a given real algebraic set on a subset of coordinates. Interestingly, the output formula is encoded through a determinantal representation which make them easy to evaluate.

Under some genericity assumptions, we use the theory of Groebner bases to prove that our algorithm runs in time \(O(8^tD^{4nt})\) where \(D\) bounds the degree of the input variables, \(n\) is the number of quantified variables and \(t\) the number of parameters. Note that, by contrast with the classical Cylindrical Algebraic Decomposition algorithm (which is doubly exponential in \(n\) and \(t\)), our algorithm runs in time singly exponential.

We report on practical experiments and show that our implementation outperforms the state-of-the-art software.

Our algorithm relies on properties of Groebner bases, specialization properties of Hermite quadratic forms (a tool for real root counting) and new algorithms for solving zero-dimensional parametric systems.

Next, we show how to apply our contributions to compute the totally real hyperplane sections coming from the theory of real algebraic curves.

This talk gathers joint works with Dimitri Manevich, Daniel Plaumann and Mohab Safey El Din.

Jan Verschelde (Dpt of Mathematics, Statistics and Computer, University of Illinois at Chicago, U.S.A.)

November, 18 2021 at 15h00, online seminar

Least Squares on GPUs in Multiple Double Precision

Pierre Briaud (Inria Paris/Sorbonne Université)

October, 14 2021 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

A polynomial time key-recovery attack on the Sidon cryptosystem

This is joint work with Jean-Pierre Tillich and Javier Verbel.

Michael Plum (Fakultät für Mathematik, Karlsruher Institut für Technologie, Karlsruhe, Deutschland)

October, 7 2021 at 10h15, online seminar

Computer-assisted existence and multiplicity proofs for semilinear elliptic boundary value problems

Alice Pellet–Mary (CNRS, LFANT, Institut de mathématiques de Bordeaux, Université de Bordeaux)

September, 9 2021 at 10h15, online seminar and room M7-315 (3rd floor, Monod)

On the hardness of the NTRU problem

In this talk, we will describe different variants of the NTRU problem, and study how they compare to each other (and to other more classical lattice problems) in terms of reductions.

More precisely, we will show that a search variant of the NTRU problem is at least as hard as the shortest vector problem (SVP) in ideal lattices; and that the decisional variant of NTRU is at least as hard as another search variant of NTRU. Unfortunately, the two search variants of NTRU that are considered in these reductions do not match, meaning that we cannot combine the reductions in order to obtain a reduction from the ideal shortest vector problem to the decisional NTRU problem.

This is a joint work with Damien Stehlé.

# 2020-2021

Richard Peng (Georgia Institute of Technology)

July 8, 2021 at 14h00, online seminar

Solving Sparse Linear Systems Faster than Matrix Multiplication

We present an algorithm that solves linear systems in sparse matrices asymptotically faster than matrix multiplication for any \(\omega>2\). This speedup holds for any input matrix A with \(o(n^{\omega -1}/\log(\kappa(A)))\) non-zeros, where \(\kappa(A)\) is the condition number of \(A\). For poly(\(n\))-conditioned matrices with \(O(n)\) nonzeros, and the current value of \omega, the bit complexity of our algorithm to solve to within any \(1/\textrm{poly}(n)\) error is \(O\left(n^{2.331645}\right)\).

Our algorithm can be viewed as an efficient randomized implementation of the block Krylov method via recursive low displacement rank factorizations. It is inspired by the algorithm of [Eberly-Giesbrecht-Giorgi-Storjohann-Villard ISSAC `06 `07] for inverting matrices over finite fields. In our analysis of numerical stability, we develop matrix anti-concentration techniques to bound the smallest eigenvalue and the smallest gap in eigenvalues of semi-random matrices.

Joint work with Santosh Vempala, manuscript at https://arxiv.org/abs/2007.10254.

Sheehan Olver (Department of Mathematics, Imperial College London, United Kingdom)

July 1, 2021 at 10h15, online seminar

Infinite Linear Algebra + Interval Arithmetic

Shweta Agrawal (C.S.E. department, I.I.T. Madras, India)

June 24, 2021 at 10h15, online seminar

Deniable Fully Homomorphic Encryption from LWE

Our constructions achieve compactness independently of the level of deniability- both the size of the public key and the size of the ciphertexts are bounded by a fixed polynomial, independent of the faking probability achieved by the scheme. This is in contrast to all previous constructions of deniable encryption schemes (even without requiring homomorphisms) which are based on polynomial hardness assumptions, originating with the seminal work of Canetti, Dwork, Naor and Ostrovsky (CRYPTO 1997) in which the ciphertext size grows with the inverse of the faking probability. Canetti et al. argued that this dependence “seems inherent”, but our constructions illustrate this is not the case. The running time of our encryption algorithm depends on the inverse of the faking probability, thus the scheme falls short of achieving simultaneously compactness, negligible deniability and polynomial encryption time. Yet, we believe that achieving compactness is a fundamental step on the way to achieving all properties simultaneously as has been the historical journey for other primitives such as functional encryption.

Interestingly, we note that our constructions support large message spaces, whereas previous constructions were bit by bit, and can be run in online-offline model of encryption, where the bulk of computation is independent of the message and may be performed in an offline pre-processing phase. The running time of the online phase, is independent of the faking probability, whereas the offline encryption run-time grows with the inverse of the faking probability. At the heart of our constructions is a new way to use bootstrapping to obliviously generate FHE ciphertexts so that it supports faking under coercion.

Joint work with Saleet Mossel and Shafi Goldwasser

Guillaume Melquiond (Toccata, INRIA Paris Saclay)

June 17, 2021 at 10h15, online seminar

Plotting in a formally verified way

Joel Dahne (Uppsala University, Sweden)

May 20, 2021 at 10h15, online seminar

A computer assisted counterexample to Payne’s nodal line conjecture with few holes

It’s joint work with both Javier Gómez-Serrano and Kimberly Hou.

Martin Albrecht (Information Security Group at Royal Holloway, University of London)

May 6, 2021 at 10h15, online seminar

On Bounded Distance Decoding with Predicate: Breaking the “Lattice Barrier” for the Hidden Number Problem

I will then discuss how we can formalise lattice problems augmented with a predicate distinguishing a target vector and give algorithms for solving instances of these problems. I will also describe the application of our techniques to lattice-based approaches for solving the Hidden Number Problem, a popular technique for recovering secret DSA or ECDSA keys in side-channel attacks, and discuss how our algorithms succeed in recovering the signing key for instances that were previously believed to be unsolvable using lattice approaches.

This talk is based on joint work with Nadia Heninger available at https://github.com/malb/bdd-predicate.

Benjamin Wesolowski (CNRS, LFANT, Institut de mathématiques de Bordeaux, Université de Bordeaux)

March 11, 2021 at 10h15, online seminar

SQISign: Compact Post-Quantum Signature from Quaternions and Isogenies

Xavier Caruso (CNRS, LFANT, Institut de mathématiques de Bordeaux, Université de Bordeaux)

February 25, 2021 at 10h15, online seminar

Points de vue sur la p-courbure

Marc Mezzarobba (CNRS, Péquan, LIP6)

January 21, 2021 at 10h15, online seminar

Analyse d’erreur de récurrences linéaires à l’aide de séries génératrices

Les combinatoriciens confrontés à ce genre de difficultés savent bien que coder une suite par sa série génératrice rend souvent les calculs plus digestes, tout en donnant accès à de puissants outils analytiques. Dans cet exposé, je montrerai à travers quelques exemples comment ce même langage des séries génératrices permet de mener à bien l’analyse d’erreur d’algorithmes numériques fondés sur divers types de récurrences linéaires.

Mohab Safey El Din (LIP6, Sorbonne Université)

January 14, 2021 at 10h15, online seminar

Polynomial system solving, kinematic singularities and eight connected components

This is joint work with Jose Capco and Josef Schicho.

Stephen Melczer (Department of Combinatorics and Optimization, University of Waterloo, Canada)

December 17, 2020 at 14h30, online seminar

Analytic Combinatorics, Rigorous Numerics, and Uniqueness of Biomembranes

This is joint work with Marc Mezzarobba.

Alin Bostan (SpecFun, INRIA Saclay Île-de-France)

December 10, 2020 at 10h15, online seminar

A Simple and Fast Algorithm for Computing the N-th Term of a Linearly Recurrent Sequence

Léo Ducas (CWI, Amsterdam, Netherlands)

November 26, 2020 at 10h15, online seminar

An Algorithmic Reduction Theory for Binary Codes: LLL and more

There are many analogies to be drawn between Euclidean lattices and linear codes over finite fields. In this work, we propose to extend the range of these analogies by considering the task of reducing the basis of a binary code. In fact, all it takes is to choose the adequate notion mimicking Euclidean orthogonality (namely orthopodality), after which, all the required notions, arguments, and algorithms unfold before us, in quasi-perfect analogy with lattices.

This is joint work with Thomas Debris-Alazard and Wessel van Woerden.

Jean-Michel Muller (AriC, LIP, ENS Lyon)

November 12, 2020 at 10h15, online seminar

Quick and dirty: immediately obtaining a rough approximation to \( \sin(x), \log(x), \arctan(y/x), \sqrt{x}\)…

Gleb Pogudin (MAX, LIX, École Polytechnique)

November 6, 2020 at 10h15, online seminar

Global parameter identifiability of ODE models

I will present several recent algorithms for analyzing parameter identifiability based on computational algebra.

# 2019-2020

Pierre Lairez (SpecFun, INRIA Saclay – Île-de-France)

June 25, 2020 at 10h15, online seminar

Calcul symbolique-numérique d’intégrales de volumes

La première, due à Henrion, Lasserre et Sarvognan, dans une variante due à Jasour, Hofmann et Williams, utilise une formulation en termes de moments pour ramener le calcul du volume à une suite de problèmes d’optimisation convexe.

La seconde, introduite par Mezzarobba, Safey El Din et moi-même, utilise l’intégration symbolique pour ramener le calcul du volume à la résolution numérique d’une équation différentielle linéaire.

Enfin, la troisième, encore en cours d’élaboration, par Berthomieu, Mezzarobba, Safey El Din et moi-même, combine les deux précédentes.

Tristan Vaccon (XLIM, Université de Limoges)

June 4 , 2020 at 10h15, online seminar

\( p \)-adic precision, examples and applications

With X. Caruso and D. Roe, we have provided a method to handle precision over \(p\)-adics that relies on differentials and first-order approximation. It provides results that are (essentially) optimal and do not depend on the choice of algorithm.

We will present various illustrations of this technique: computation of determinants, characteristic polynomials, \(p\)-adic differential equations,etc…

We will also present a Sagemath implementation to compute automatically the optimal precision on a given computation.

Pascal Koiran (MC2, LIP) and Bruno Salvy (AriC, LIP)

March 12, 2020 at 10h15, Amphi B (3rd floor, Monod)

Bruno Salvy: Absolute root separation

This is joint work with Yann Bugeaud, Andrej Dujella, Wenjie Fang and Tomislav Pejkovic.

Pascal Koiran: Root separation for trinomials

As an algorithmic application, we show that the number of real roots of a trinomial \(f\) can be computed in time polynomial in the size of the sparse encoding of \(f\). The same problem is open for 4-nomials.

Robin Larrieu (LMV, Université de Versailles)

February 13, 2020 at 10h15, room M7-315 (3rd floor, Monod)

Fast polynomial reduction for generic bivariate ideals

We will consider two situations where these new ideas apply, leading to different algorithms:

- First, there is a class called “vanilla Gröbner bases” for which there is a so-called terse representation that, once precomputed, allows to reduce any polynomial \( P \) in time \( O(n^2)\). In this setting, assuming suitable precomputation, multiplication and change of basis can therefore be done in time \( O(n^2)\) in the quotient algebra \(K[X,Y] / ⟨A,B⟩\).
- Then, we assume that \( A \) and \( B \) are given in total degree and we consider the usual degree lexicographic order. Although the bases are not vanilla in this case, they admit a so-called concise representation with similar properties. Actually, the precomputation can also be done efficiently in this particular setting: from the input \(A, B\), one can compute a Gröbner basis in concise representation in time \( O(n^2)\). As a consequence, multiplication in \( K[X,Y] / ⟨A,B⟩\) can be done in time \( O(n^2) \) including the cost of precomputation.

Laurence Rideau (STAMP, INRIA Sophia Antipolis – Méditerranée)

January 30, 2020 at 10h15, room M7-315 (3rd floor, Monod)

Formalisation in Coq of the correctness of double-word arithmetic algorithms and their errors bounds

We show how this formalisation made it possible to highlight some errors and some inaccuracies in the proofs of the paper.

I will focus in particular on the dangers of the “wlog”, which is used extensively in this type of proofs.

We will also discuss the advantages and disadvantages of such formalization, and how this work has improved confidence in the results of the article, despite the errors detected, and has also improved the Flocq library (intensively used for it).

Miruna Rosca (AriC, LIP)

December 5, 2019 at 10h15, room M7-315 (3rd floor, Monod)

MPSign: A Signature from Small-Secret Middle-Product Learning with Errors

This is joint work with Shi Bai, Dipayan Das, Ryo Hiromasa, Amin Sakzad, Damien Stehlé, Ron Steinfeld and Zhenfei Zhang

Vincent Lefèvre (AriC, LIP)

November 21, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Accurate Complex Multiplication in Floating-Point Arithmetic

This is a joint work with Jean-Michel Muller.

Fabien Laguillaumie (AriC, LIP)

November 14, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Threshold variant of the digital signature algorithm standard

In this talk, I will give some recent results to improve Lindell’s solution in terms of security and efficiency, and discuss some possible extension to a full threshold variant.

This is joint works with Guilhem Castagnos, Dario Catalano, Federico Savasta and Ida Tucker.

Mioara Joldes (CNRS LAAS, Toulouse)

November 7, 2019 at 10h15, room M7-315 (3rd floor, Monod)

An optimization viewpoint for machine-efficient polynomial approximations

Geoffroy Couteau (CNRS and Paris 7)

October 24, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Efficient Pseudorandom Correlation Generators: Silent OT Extension and More

A PCG allows two or more parties to securely generate long sources of useful correlated randomness via a local expansion of correlated short seeds and no interaction. PCGs enable MPC with silent preprocessing, where a small amount of interaction used for securely sampling the seeds is followed by silent local generation of correlated pseudorandomness.

A concretely efficient PCG for Vector-OLE correlations was recently obtained by Boyle et al. (CCS 2018) based on variants of the learning parity with noise (LPN) assumption over large fields. In this work, we initiate a systematic study of PCGs and present concretely efficient constructions for several types of useful MPC correlations. We obtain the following main contributions:

– PCG foundations. We give a general security definition for PCGs. Our definition suffices for any MPC protocol satisfying a stronger security requirement that is met by existing protocols. We prove that a stronger security requirement is indeed necessary, and justify our PCG definition by ruling out a stronger and more natural definition.

– Silent OT extension. We present the first concretely efficient PCG for oblivious transfer correlations. Its security is based on a variant of the binary LPN assumption and any correlation-robust hash function. We expect it to provide a faster alternative to the IKNP OT extension protocol (Crypto ’03) when communication is the bottleneck. We present several applications, including protocols for non-interactive zero-knowledge with bounded-reusable preprocessing from binary LPN, and concretely efficient related-key oblivious pseudorandom functions.

– PCGs for simple 2-party correlations. We obtain PCGs for several other types of useful 2-party correlations, including (authenticated) one-time truth-tables and Beaver triples. While the latter PCGs are slower than our PCG for OT, they are still practically feasible. These PCGs are based on a host of assumptions and techniques, including specialized homomorphic secret sharing schemes and pseudorandom generators tailored to their structure.

– Multiparty correlations. We obtain PCGs for multiparty correlations that can be used to make the circuit-dependent communication of MPC protocols scale linearly (instead of quadratically) with the number of parties.

Benjamin Wesolowski (CWI Amsterdam)

October 10, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Discrete logarithms in quasi-polynomial time in finite fields of small characteristic

Théo Mary (University of Manchester, U.K.)

October 3, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Sharper and smaller error bounds for low precision scientific computing

# 2018-2019

Miruna Rosca (AriC)

July 4, 2019 at 10h15, room M7-315 (3rd floor, Monod)

On the Middle-Product Learning With Errors Problem and its applications in cryptography

This is joint work with A. Sakzad, D. Stehlé and R. Steinfeld.

François Morain (LIX, École polytechnique)

June 13, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Fractions continues avec des algorithmes rapides

Vincent Neiger (XLIM, Université de Limoges)

May 2, 2019 at 10h15, room M7-315 (3rd floor, Monod)

On the complexity of modular composition of generic polynomials

Contains joint work with Seung Gyu Hyun, Bruno Salvy, Eric Schost, Gilles Villard.

Bruno Grenet (ECO, LIRMM)

April 11, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Multiplications polynomiales sans mémoire

Plus récemment, certains de ces algorithmes ont été étudiés du point de vue de leur complexité en espace, et modifiés pour n’utiliser aucun espace supplémentaire autre que les entrées et sorties, tout en gardant la même complexité en temps asymptotiquement.

Dans ce travail, nous étendons ces résultats de deux façons. D’une part, nous nous demandons si tout algorithme de multiplication polynomiale admet une variante « en place », c’est-à-dire n’utilisant aucun espace supplémentaire, de manière générique. D’autre part, nous considérons deux variantes importantes de ce problème qui ne produisent qu’une partie du résultat, les produits dits court et médian, et nous nous demandons si ces opérations peuvent également être effectuées en place.

Pour répondre de manière (essentiellement) affirmative à ces deux questions, nous proposons une série de réductions ayant comme point de départ n’importe quel algorithme de multiplication de complexité en espace linéaire. Pour le produit complet et le produit court, ces réductions fournissent des variantes en place des algorithmes avec la même complexité en temps asymptotiquement. Pour le produit médian, la réduction implique un facteur logarithmique supplémentaire dans la complexité en temps, quand celle-ci est quasi-linéaire.

Travail en commun avec Pascal Giorgi et Daniel Roche

Damien Stehlé (AriC)

April 4, 2019 at 10h15, room M7-315 (3rd floor, Monod)

A survey on security foundations of fast lattice-based cryptography

To address this issue, algebraic variants of LWE have been introduced, such as Polynomial-LWE, Ring-LWE, Module-LWE and MiddleProduct-LWE, whose definitions involve polynomial rings and number fields.

In this talk, I will survey the state of the art on these problems.

Jean-Michel Muller (AriC)

March 7, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Error analysis of some operations involved in the Fast Fourier Transform

This is a joint work with N. Brisebarre, M. Joldes, A.-M. Nanes and J. Picot.

Assia Mahboubi (Gallinette, INRIA Rennes – Bretagne Atlantique, LS2N)

February 14, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Formally Verified Approximations of Definite Integrals

This is a joint work with Guillaume Melquiond and Thomas Sibut-Pinote.

Ida Tucker (AriC)

February 7, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Practical fully secure unrestricted inner product functional encryption modulo a prime p

However constructions for general FE are far from practical, or rely on non-standard and ill-understood cryptographic assumptions.

In this talk I will focus on the construction of efficient FE schemes for linear functions (i.e. the inner product functionality), and the framework in which our constructions hold. Such schemes yield many practical applications, and our constructions are the first FE schemes for inner products modulo a prime that are both efficient and recover the result whatever its size. I will also describe an instantiation of the framework in using class groups of imaginary quadratic fields.

This is a joint work with Guilhem Castagnos and Fabien Laguillaumie.

Éric Goubault (LIX, École Polytechnique)

January 24, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Finding Positive Invariants of Polynomial Dynamical Systems – some experiments

Alain Passelègue (AriC)

January 17, 2019 at 10h15, room M7-315 (3rd floor, Monod)

New candidate pseudorandom functions and their applications

The advantage of our approach is twofold. On the theoretical side, the simplicity of our candidates enables us to draw many natural connections between their hardness and questions in complexity theory or learning theory. On the applied side, the piecewise-linear structure of our candidates lends itself nicely to applications in secure multiparty computation (MPC). In particular, we construct protocols for distributed PRF evaluation that achieve better round complexity and/or communication complexity compared to protocols obtained by combining standard MPC protocols with practical PRFs (included MPC-friendly ones).

Finally, we introduce a new primitive we call an encoded-input PRF, which can be viewed as an interpolation between weak PRFs and standard (strong) PRFs. As we demonstrate, an encoded-input PRF can often be used as a drop-in replacement for a strong PRF, combining the efficiency benefits of weak PRFs and the security benefits of strong PRFs. We give a candidate EI-PRF based on our main weak PRF candidate.

Joint work with Dan Boneh, Yuval Ishai, Amit Sahai, and David J. Wu, published at TCC 2018

Chee Yap (New-York University)

January 9, 2019 at 10h15, room M7-315 (3rd floor, Monod)

Subdivision Path Planning in Robotics: Theory and Practice

(1) The notion of “resolution-exact” planners. Conceptually, it avoids the zero problem of exact computation.

(2) The use of “soft predicates” for achieving such algorithms in the subdivision approach.

(3) The “feature-based technique” for constructing such soft predicates.

We formulate an algorithmic framework called “Soft Subdivision Search” (SSS) that incorporates these ideas. There are many parallels between our framework and the well-known Sampling or Probabilistic Roadmap framework. Both frameworks lead to algorithms that are

* practical

* easy to implement

* flexible and extensible

* with adaptive and local complexity

In contrast to sampling and previous resolution approaches, SSS confers strong theoretical guarantees, including halting.

In a series of papers we demonstrated the power of these ideas, by producing planners for planar robots with 2, 3 and 4 degrees of freedom (DOF) that outperform or matches state-of-art sampling-based planners. Most recently, we produced a planner for two spatial robots (rod and ring) with 5 DOFs. Non-heuristic planners for such robots has been considered a challenge for the subdivision approach. We outline a general axiomatic theory underlying these results, including subdivision in non-Euclidean configuration spaces,

Joint work with Y.J. Chiang, C.H. Hsu, C. Wang, Z. Luo, B. Zhou, J.P. Ryan.

Elena Kirshanova (AriC)

December 13, 2018 at 10h15, room M7-315 (3rd floor, Monod)

Practical sieving algorithms for the Shortest Vector Problem

Nicolas Brunie (Kalray)

December 6, 2018 at 10h15, room M7-315 (3rd floor, Monod)

Overview of arithmetic at Kalray: metalibm and the rest

Sylvie Putot (LIX, École Polytechnique)

November 29, 2018 at 10h15, room M7-315 (3rd floor, Monod)

Forward Inner-Approximated Reachability of Non-Linear Continuous Systems

Radu Titiu (AriC and BitDefender)

November 22, 2018 at 10h15, room M7-315 (3rd floor, Monod)

Adaptively secure PRFs from LWE

This is joint work with Benoit Libert and Damien Stehlé.

Martin Kumm (Uni. Kassel, Germany)

November 8, 2018 at 10h15, room M7-315 (3rd floor, Monod)

Exact Computation of Monotonic Functions with Large Input Word Sizes using Look-Up Tables

Silviu Filip (CAIRN, Inria Rennes Bretagne Atlantique)

October 25, 2018 at 10h15, room M7-315 (3rd floor, Monod)

A High Throughput Polynomial and Rational Function Approximations Evaluator

Florent Bréhard (AriC)

October 18, 2018 at 10h15, room M7-315 (3rd floor, Monod)

Rigorous Numerics for Function Space Problems and Applications to Aerospace

A relevant practical example occurs in the spacecraft rendezvous problem, which consists in determining the optimal command law for a spacecraft equipped with thrusters to be transferred from its original orbit to a target orbit within a given time interval. Computing rigorous trajectories is of high interest to guarantee a posteriori the correctness of the numerical command law returned by the optimization algorithm used to solve this problem.

In this talk we discuss a rigorous framework called Chebyshev models to provide validated enclosures of real-valued functions defined over a compact interval. After having presented the basic arithmetic operations on them, we focus on an algorithm that computes validated solutions of linear ordinary differential equations, specifically, approximate truncated Chebyshev series together with a rigorous uniform error bound. The method relies on an a posteriori validation based on a Newton-like fixed-point operator, which also exploits the almost-banded structure of the problem in an efficient way. We provide an open-source C implementation (https://gforge.inria.fr/projects/tchebyapprox/).

Finally, certified enclosures of spacecraft trajectories arising in the rendezvous problem will be computed using the tools introduced during the talk.

# Archives of the seminar

For seminars in previous years, see former AriC seminars.