Search

International audience; Digital data plays a central role in sciences, journalism, environment, digital humanities, etc. Open Data sharing initiatives lead to many large, interesting datasets being shared online. Some of these are RDF graphs, but other formats like CSV, relational, property graphs, JSON or XML documents are also frequent.Practitioners need to understand a dataset to decide whether it is suited to their needs. Datasets may come with a schema and/or may be summarized, however the first is not always provided and the latter is often too technical for non-IT users. To overcome these limitations, we present an end-to-end dataset abstraction approach, which (i) applies on any (semi)structured data model; (ii) computes a description meant for human users, in the form of an Entity- Relationship diagram; (ii) integrates Information Extraction and data profiling to classify dataset entities among a large set of intelligible categories. We implemented our approach in a system called Abstra, and detail its performance on various datasets.

International audience; Graphs, and notably RDF graphs, are a prominent way of sharing data. As data usage democratizes, users need help figuring out the useful content of a graph dataset. In particular, journalists with whom we collaborate are interested in identifying, in a graph, the connections between entities, e.g., people, organizations, emails, etc.We present a novel, interactive method for exploring data graphs through their data paths connecting Named Entities (NEs, in short); each data path leads to a tabular-looking set of results. NEs are extracted from the data through dedicated Information Extraction modules. Our method builds upon the pre-existing ConnectionLens platform and follow-up work on dataset abstraction. The contribution of the present work is in the interactive and efficient approach to enumerate and compute NE paths, based on an algorithm which automatically recommends subpaths to materialize, and rewrites the path queries using these subpaths. Our experiments demonstrate the interest of NE paths and the efficiency of our method for computing them.

International audience

International audience; In this paper we introduce modified versions of CMA-ES with the objective to help to prove convergence of CMA-ES. In order to ensure that the modifications do not alter the performances of the algorithm too much, we benchmark variants of the algorithm derived from them on problems of the bbob test suite. We observe that the main performances losses are observed on ill-conditioned problems, which is probably due to the absence of cumulation in the adaptation of the covariance matrix. However, the versions of CMA-ES presented in this paper have globally similar performances to the original CMA-ES.

International audience; We present a surrogate-assisted multiobjective optimization algorithm. The aggregation of the objectives relies on the Uncrowded Hypervolume Improvement (UHVI) which is partly replaced by a linear-quadratic surrogate that is integrated into the CMA-ES algorithm. Surrogating the UHVI poses two challenges. First, the UHVI is a dynamic function, changing with the empirical Pareto set. Second, it is a composite function, defined differently for dominated and nondominated points. The presented algorithm is thought to be used with expensive functions of moderate dimension (up to about 50) with a quadratic surrogate which is updated based on its ranking ability. We report numerical experiments which include tests on the COCO benchmark. The algorithm shows in particular linear convergence on the double sphere function with a convergence rate that is 6-20 times faster than without surrogate assistance.

International audience; Bilinear pairings have been used in different cryptographic applications and demonstrated to be a key building block for a plethora of constructions. In particular, some Succinct Non-interactive ARguments of Knowledge (SNARKs) have very short proofs and very fast verification thanks to a multi-pairing computation. This succinctness makes pairing-based SNARKs suitable for proof recursion, that is proofs verifying other proofs. In this scenario one requires to express efficiently a multi-pairing computation as a SNARK arithmetic circuit. Other compelling applications such as verifying Boneh-Lynn-Shacham (BLS) signatures or Kate-Zaverucha-Goldberg (KZG) polynomial commitment opening in a SNARK fall into the same requirement. The implementation of pairings is challenging but the literature has very detailed approaches on how to reach practical and optimized implementations in different contexts and for different target environments. However, to the best of our knowledge, no previous publication has addressed the question of efficiently implementing a pairing as a SNARK arithmetic circuit. In this work, we consider efficiently implementing pairings in Rank-1 Constraint Systems (R1CS), a widely used model to express SNARK statements. We implement our techniques in the gnark open-source ecosystem and show that the arithmetic circuit depth can be almost halved compared to the previously best known pairing implementation on a Barreto-Lynn-Scott (BLS) curve of embedding degree 12, resulting in a significantly faster proving time. We also investigate and implement the case of BLS curves of embedding degree 24.

Persistent homology (PH) provides topological descriptors for geometric data, such as weighted graphs, which are interpretable, stable to perturbations, and invariant under, e.g., relabeling. Most applications of PH focus on the one-parameter case -- where the descriptors summarize the changes in topology of data as it is filtered by a single quantity of interest -- and there is now a wide array of methods enabling the use of one-parameter PH descriptors in data science, which rely on the stable vectorization of these descriptors as elements of a Hilbert space. Although the multiparameter PH (MPH) of data that is filtered by several quantities of interest encodes much richer information than its one-parameter counterpart, the scarceness of stability results for MPH descriptors has so far limited the available options for the stable vectorization of MPH. In this paper, we aim to bring together the best of both worlds by showing how the interpretation of signed barcodes -- a recent family of MPH descriptors -- as signed measures leads to natural extensions of vectorization strategies from one parameter to multiple parameters. The resulting feature vectors are easy to define and to compute, and provably stable. While, as a proof of concept, we focus on simple choices of signed barcodes and vectorizations, we already see notable performance improvements when comparing our feature vectors to state-of-the-art topology-based methods on various types of data., 23 pages, 3 figures, 8 tables

Consider the problem of efficiently evaluating isogenies $\phi: E \to E/H$ of elliptic curves over a finite field $\mathbb{F}_q$, where the kernel $H = \langle G\rangle$ is a cyclic group of odd (prime) order: given $E$, $G$, and a point (or several points) $P$ on $E$, we want to compute $\phi(P)$. This problem is at the heart of efficient implementations of group-action- and isogeny-based post-quantum cryptosystems such as CSIDH. Algorithms based on V{\'e}lu's formulae give an efficient solution to this problem when the kernel generator $G$ is defined over $\mathbb{F}_q$. However, for general isogenies, $G$ is only defined over some extension $\mathbb{F}_{q^k}$, even though $\langle G\rangle$ as a whole (and thus $\phi$) is defined over the base field $\mathbb{F}_q$; and the performance of V{\'e}lu-style algorithms degrades rapidly as $k$ grows. In this article we revisit the isogeny-evaluation problem with a special focus on the case where $1 \le k \le 12$. We improve V{\'e}lu-style isogeny evaluation for many cases where $k = 1$ using special addition chains, and combine this with the action of Galois to give greater improvements when $k > 1$.

International audience; Graphs, and notably RDF graphs, are a prominent way of sharing data. As data usage democratizes, users need help figuring out the useful content of a graph dataset. In particular, journalists with whom we collaborate [3] are interested in identifying, in a graph, the connections between entities, e.g., people, organizations, emails, etc. We propose PathWays, an interactive tool for exploring data graphs through their data paths connecting Named Entities (NEs, in short); each data path leads to a tabular-looking set of results. NEs are extracted from the data through dedicated Information Extraction modules. PathWays leverages the ConnectionLens platform [4,6] and follow-up work on dataset abstraction [5]. Its novelty lies in its interactive and efficient approach to enumerate, compute, and analyze NE paths.

International audience; Exploring Knowledge Graphs (KGs, in short) to discover facts and links is tedious even for experts with knowledge of SPARQL due to their unfamiliarity with the structure and labels of entities, classes and relations. Some KG applications require finding the connections between groups of nodes, even if users ignore the shape of these connections. However, SPARQL only allows checking if paths exist, not returning them. A recent property graph query language, GPML, allows also returning connecting paths, but not connections between three or more nodes. We propose to demonstrate RelSearch, a system supporting extended SPARQL queries, featuring standard Basic Graph Patterns (BGPs) as well as novel Connecting Tree Patterns (CTPs); each CTP requests the connections (paths, or trees) between nodes bound to variables. RelSearch evaluates such extended queries using novel algorithms which, unlike prior keyword search methods, return connections regardless of the edge directions and are independent of how we measure the quality (score) of each connection. We will demonstrate RelSearch's expressivity and efficiency using a variety of RDF graphs, user-selected score functions, and search exploration orders.

International audience; Several targeted advertising platforms offer transparency mechanisms, but researchers and civil societies repeatedly showed that those have major limitations. In this paper, we propose a collaborative ad transparency method to infer, without the cooperation of ad platforms, the targeting parameters used by advertisers to target their ads. Our idea is to ask users to donate data about their attributes and the ads they receive and to use this data to infer the targeting attributes of an ad campaign. We propose a Maximum Likelihood Estimator based on a simplified Bernoulli ad delivery model. We first test our inference method through controlled ad experiments on Facebook. Then, to further investigate the potential and limitations of collaborative ad transparency, we propose a simulation framework that allows varying key parameters. We validate that our framework gives accuracies consistent with real-world observations such that the insights from our simulations are transferable to the real world. We then perform an extensive simulation study for ad campaigns that target a combination of two attributes. Our results show that we can obtain good accuracy whenever at least ten monitored users receive an ad. This usually requires a few thousand monitored users, regardless of population size. Our simulation framework is based on a new method to generate a synthetic population with statistical properties resembling the actual population, which may be of independent interest.

Delta lenses are functors equipped with a suitable choice of lifts, and are used to model bidirectional transformations between systems. In this paper, we construct an algebraic weak factorisation system whose R-algebras are delta lenses. Our approach extends a semi-monad for delta lenses previously introduced by Johnson and Rosebrugh, and generalises to any suitable category equipped with an orthogonal factorisation system and an idempotent comonad. We demonstrate how the framework of an algebraic weak factorisation system provides a natural setting for understanding the lifting operation of a delta lens, and also present an explicit description of the free delta lens on a functor., 14 pages + 2 page appendix, submitted to ACT 2023

International audience; Open Information Extraction (OIE) is the task of extracting tuples of the form (subject, predicate, object), without any knowledge of the type and lexical form of the predicate, the subject, or the object. In this work, we focus on improving OIE quality by exploiting domain knowledge about the subject and object. More precisely, knowing that the subjects and objects in sentences are often named entities, we explore how to inject constraints in the extraction through constrained inference and constraint-aware training. Our work leverages the state-of-the-art OpenIE6 platform, which we adapt to our setting. Through a carefully constructed training dataset and constrained training, we obtain a 29.17% F1-score improvement in the CaRB metric and a 24.37% F1-score improvement in the WIRe57 metric. Our technique has important applications-one of them is investigative journalism, where automatically extracting conflict-of-interest between scientists and funding organizations helps understand the type of relations companies engage with the scientists. Our code and data are available at https: //github.com/prajnaupadhyay/ openie-with-entities

We introduce SQISignHD, a new post-quantum digital signature scheme inspired by SQISign. SQISignHD exploits the recent algorithmic breakthrough underlying the attack on SIDH, which allows to efficiently represent isogenies of arbitrary degrees as components of a higher dimensional isogeny. SQISignHD overcomes the main drawbacks of SQISign. First, it scales well to high security levels, since the public parameters for SQISignHD are easy to generate: the characteristic of the underlying field needs only be of the form 2 f 3 f ′ − 1. Second, the signing procedure is simpler and more efficient. Third, the scheme is easier to analyse, allowing for a much more compelling security reduction. Finally, the signature sizes are even more compact than (the already record-breaking) SQISign, with compressed signatures as small as 105 bytes for the post-quantum NIST-1 level of security. These advantages may come at the expense of the verification, which now requires the computation of an isogeny in dimension 4, a task whose optimised cost is still uncertain, as it has been the focus of very little attention.

This paper implements a method for sampling from the d-dimensional Von Mises Fisher distribution using NumPy, focusing on speed and readability. The complexity of the algorithm is O(nd) for n samples, which is theoretically optimal taking into account that nd is the output size.

The SEA algorithm for computing the cardinality of elliptic curves over finite fields in many characteristic uses modular polynomials. These polynomials come into different flavors, and methods to compute them flourished. Once equipped with some modular polynomials for prime $\ell$, algebraic formulas are used to compute a curve $\mathcal{E}^*/\mathbb{F}_q$ that is $\ell$-isogenous to the curve of interest $\mathcal{E}$. These formulas involve derivatives of the modular polynomial that may sometime vanish. One way to overcome this problem is to use alternative trivariate polynomials $U_\ell$, $V_\ell$, and $W_\ell$ introduced by Charlap, Coley and Robbins to overcome some difficulties in the first versions of Elkies's approach. We give properties of these polynomials, as well as formulas to compute the isogenous curve that were sketched by Atkin. Also we investigate another suggestion of Atkin using modular polynomials associated to a power product of Dedekind's $\eta$ function.

This paper implements a method for sampling from the d-dimensional Von Mises Fisher distribution using NumPy, focusing on speed and readability. The complexity of the algorithm is O(nd) for n samples, which is theoretically optimal taking into account that nd is the output size.

International audience; We use the focused proof system LJF as a framework for describing term structures and substitution. Since the proof theory of LJF does not pick a canonical polarization for primitive types, two different approaches to term representation arise. When primitive types are given the negative polarity, LJF proofs encode terms as tree-like structures in a familiar fashion. In this situation, cut elimination also yields the familiar notion of substitution. On the other hand, when primitive types are given the positive polarity, LJF proofs yield a structure in which explicit sharing of term structures is possible. Such a representation of terms provides an explicit method for sharing term structures. In this setting, cut elimination yields a different notion of substitution. We illustrate these two approaches to term representation by applying them to the encoding of untyped λ-terms. We also exploit concurrency theory techniques-namely traces and simulation-to compare untyped λ-terms using such different structuring disciplines.

International audience; Internal resistance is a critical parameter of the thermal behavior of Li-ion battery cells. This paper proposes an innovative way to deal with the uncertainties related to this physical parameter using experimental data and numerical simulation. First, a CFD model is validated against an experimental configuration representing the behavior of heated Li-ion battery cells under constant discharging current conditions. Secondly, an Uncertainty Quantification based methodology is proposed to represent the internal resistance and its inherent uncertainties. Thanks to an accurate and fast to compute surrogate model, the impact of those uncertainties on the temperature evolution of Li-ion cells is quantified. Finally, Bayesian inference of the internal resistance model parameters using experimental measurements is performed, reducing the prediction uncertainty by almost 95% for some temperatures of interest. Finally, an enhanced internal model is constructed by considering the state of charge and temperature dependency on internal resistance. This model is implemented in the CFD code and used to model a full discharge of the Li-ion batteries. The resulting temperature evolution computed with the two different resistance models is compared for the low state of charge situations.

National audience; François Pottier's unionFind library is parameterized over an underlying store of mutable references, and provides the usual references, transactional reference stores (for rolling back some changes in case of higher-level errors), and persistent reference stores. We extend this library with a new implementation of backtracking reference stores, to get a Union-Find implementation that efficiently supports arbitrary backtracking and also subsumes the transactional interface. Our backtracking reference stores are not specific to unionFind, they can be used to build arbitrary backtracking data structures. The natural implementation, using a journal to record all writes, provides amortized-constant-time operations with a space overhead linear in the number of store updates. A refined implementation reduces the memory overhead to be linear in the number of store cells updated, and gives performance that match non-backtracking references in practice.

Missing values are unavoidable when working with data. Their occurrence is exacerbated as more data from different sources become available. However, most statistical models and visualization methods require complete data, and improper handling of missing data results in information loss or biased analyses. Since the seminal work of Rubin (1976), a burgeoning literature on missing values has arisen, with heterogeneous aims and motivations. This led to the development of various methods, formalizations, and tools. For practitioners, it remains nevertheless challenging to decide which method is most suited for their problem, partially due to a lack of systematic covering of this topic in statistics or data science curricula. To help address this challenge, we have launched the "R-miss-tastic" platform, which aims to provide an overview of standard missing values problems, methods, and relevant implementations of methodologies. Beyond gathering and organizing a large majority of the material on missing data (bibliography, courses, tutorials, implementations), "R-miss-tastic" covers the development of standardized analysis workflows. Indeed, we have developed several pipelines in R and Python to allow for hands-on illustration of and recommendations on missing values handling in various statistical tasks such as matrix completion, estimation and prediction, while ensuring reproducibility of the analyses. Finally, the platform is dedicated to users who analyze incomplete data, researchers who want to compare their methods and search for an up-to-date bibliography, and also teachers who are looking for didactic materials (notebooks, video, slides)., Comment: 36 pages, 9 figures

National audience; Graph data management and querying has many practical applications. When graphs are very heterogeneous and/or users are unfamiliar with their structure, they may need to find how two or more groups of nodes are connected in a graph, even when users are not able to describe the connections. This is only partially supported by existing query languages, which allow searching for paths, but not for trees connecting three or more node groups. The latter is related to the NP-hard Group Steiner Tree problem, and has been previously considered for keyword search in databases. In this work, we formally show how to integrate connecting tree patterns (CTPs, in short) within a graph query language such as SPARQL or Cypher, leading to an Extended Query Language (or EQL, in short). We then study a set of algorithms for evaluating CTPs; we generalize prior keyword search work, most importantly by (i) considering bidirectional edge traversal and (ii) allowing users to select any score function for ranking CTP results. To cope with very large search spaces, we propose an efficient pruning technique and formally establish a large set of cases where our algorithm, MOLESP, is complete even with pruning. Our experiments validate the performance of our CTP and EQL evaluation algorithms on a large set of synthetic and real-world workloads.

ISSN 2184-4356; International audience; Federated learning (FL) is a type of collaborative machine learning where participating peers/clients process their data locally, sharing only updates to the collaborative model. This enables to build privacy-aware distributed machine learning models, among others. The goal is the optimization of a statistical model's parameters by minimizing a cost function of a collection of datasets which are stored locally by a set of clients. This process exposes the clients to two issues: leakage of private information and lack of personalization of the model. On the other hand, with the recent advancements in various techniques to analyze data, there is a surge of concern for the privacy violation of the participating clients. To mitigate this, differential privacy and its variants serve as a standard for providing formal privacy guarantees. Often the clients represent very heterogeneous communities and hold data which are very diverse. Therefore, aligned with the recent focus of the FL community to build a framework of personalized models for the users representing their diversity, it is also of utmost importance to protect the clients' sensitive and personal information against potential threats. To address this goal we consider $d$-privacy, also known as metric privacy, which is a variant of local differential privacy, using a a metric-based obfuscation technique that preserves the topological distribution of the original data. To cope with the issue of protecting the privacy of the clients and allowing for personalized model training to enhance the fairness and utility of the system, we propose a method to provide group privacy guarantees exploiting some key properties of $d$-privacy which enables personalized models under the framework of FL. We provide theoretical justifications to the applicability and experimental validation on real datasets to illustrate the working of our method.

The symmetrized tropical semiring is an extension of the tropical semifield, initially introduced to solve tropical linear systems using Cramer's rule. It is equivalent to the real tropical hyperfield, which has been used in the study of tropicalizations of semialgebraic sets. Polynomials over the symmetrized tropical semiring, and their factorizations, were considered by Quadrat. Recently, Baker and Lorscheid introduced a notion of multiplicity for the roots of univariate polynomials over hyperfields. In the special case of the hyperfield of signs, they related multiplicities with Descarte's rule of sign for real polynomials. We investigate here the factorizations of univariate polynomial functions over symmetrized tropical semirings, and relate them with the multiplicities of roots over these semirings. We deduce a Descartes' rule for ``signs and valuations'', which applies to polynomials over a real closed field with a convex valuation and an arbitrary (divisible) value group. We show in particular that the inequality of the Descartes' rule is tight when the value group is non-trivial. This extends to arbitrary value groups a characterization of Gunn in the rank one case, answering also to the tightness question. Our results are obtained using the framework of semiring systems introduced by Rowen, together with model theory of valued fields.

International audience; Denoising is a common, yet critical operation in geometry processing aiming at recovering high-fidelity models of piecewisesmooth objects from noise-corrupted pointsets. Despite a sizable literature on the topic, there is a dearth of approaches capable of processing very noisy and outlier-ridden input pointsets for which no normal estimates and no assumptions on the underlying geometric features or noise type are provided. In this paper, we propose a new robust-statistics approach to denoising pointsets based on line processes to offer robustness to noise and outliers while preserving sharp features possibly present in the data. While the use of robust statistics in denoising is hardly new, most approaches rely on prescribed filtering using data-independent blending expressions based on the spatial and normal closeness of samples. Instead, our approach deduces a geometric denoising strategy through robust and regularized tangent plane fitting of the initial pointset, obtained numerically via alternating minimizations for efficiency and reliability. Key to our variational approach is the use of line processes to identify inliers vs. outliers, as well as the presence of sharp features. We demonstrate that our method can denoise sampled piecewise-smooth surfaces for levels of noise and outliers at which previous works fall short. CCS Concepts • Computing methodologies → Point-based models

Machine learning algorithms can produce biased outcome/prediction, typically, against minorities and under-represented sub-populations. Therefore, fairness is emerging as an important requirement for the large scale application of machine learning based technologies. The most commonly used fairness notions (e.g. statistical parity, equalized odds, predictive parity, etc.) are observational and rely on mere correlation between variables. These notions fail to identify bias in case of statistical anomalies such as Simpson's or Berkson's paradoxes. Causality-based fairness notions (e.g. counterfactual fairness, no-proxy discrimination, etc.) are immune to such anomalies and hence more reliable to assess fairness. The problem of causality-based fairness notions, however, is that they are defined in terms of quantities (e.g. causal, counterfactual, and path-specific effects) that are not always measurable. This is known as the identifiability problem and is the topic of a large body of work in the causal inference literature. This paper is a compilation of the major identifiability results which are of particular relevance for machine learning fairness. The results are illustrated using a large number of examples and causal graphs. The paper would be of particular interest to fairness researchers, practitioners, and policy makers who are considering the use of causality-based fairness notions as it summarizes and illustrates the major identifiability results, Comment: arXiv admin note: text overlap with arXiv:2010.09553

This paper presents a general strategy to recover a block cipher secret key in the cold boot attack setting. More precisely, we propose a key-recovery method that combines key enumeration algorithms and Grover’s quantum algorithm to recover a block cipher secret key after an attacker has procured a noisy version of it via a cold boot attack. We also show how to implement the quantum component of our algorithm for several block ciphers such as AES, PRESENT and GIFT, and LowMC. Additionally, since evaluating the third-round post-quantum candidates of the National Institute of Standards and Technology (NIST) post-quantum standardization process against different attack vectors is of great importance for their overall assessment, we show the feasibility of performing our hybrid attack on Picnic, a post-quantum signature algorithm being an alternate candidate in the NIST post-quantum standardization competition. According to our results, our method may recover the Picnic private key for all Picnic parameter sets, tolerating up to 40% of noise for some of the parameter sets. Furthermore, we provide a detailed analysis of our method by giving the cost of its resources, its running time, and its success rate for various enumerations.

Using order structures in a proof assistant naturally raises the problem of working with multiple instances of a same structure over a common type of elements. This goes against the main design pattern of hierarchies used for instance in Coq's MathComp or Lean's mathlib libraries, where types are canonically associated to at most one instance and instances share a common overloaded syntax.We present new design patterns to leverage these issues, and apply them to the formalization of order structures in the MathComp library. A common idea in these patterns is underloading, i.e., a disambiguation of operators on a common type. In addition, our design patterns include a way to deal with duality in order structures in a convenient way. We hence formalize a large hierarchy which includes partial orders, semilattices, lattices as well as many variants.We finally pay a special attention to order substructures. We introduce a new kind of structure called prelattice. They are abstractions of semilattices, and allow us to deal with finite lattices and their sublattices within a common signature. As an application, we report on significant simplifications of the formalization of the face lattices of polyhedra in the Coq-Polyhedra library.

We investigate a new class of fault-injection attacks against the CSIDH family of cryptographic group actions. Our disorientation attacks effectively flip the direction of some isogeny steps. We achieve this by faulting a specific subroutine, connected to the Legendre symbol or Elligator computations performed during the evaluation of the group action. These subroutines are present in almost all known CSIDH implementations. Post-processing a set of faulty samples allows us to infer constraints on the secret key. The details are implementation specific, but we show that in many cases, it is possible to recover the full secret key with only a modest number of successful fault injections and modest computational resources. We provide full details for attacking the original CSIDH proof-of-concept software as well as the CTIDH constant-time implementation. Finally, we present a set of lightweight countermeasures against the attack and discuss their security.

International audience; We report on a spectral splitting effect of the cavity-less lasing emission of nitrogen ions at 391.4 nm pumped by 800-nm femtosecond laser pulses. It was found that with the increase of the nitrogen gas pressure and pump pulse energy, both R and P branches experience spectral splitting. With an external injected seeding pulse, a similar split spectral line is observed for the amplified emission. In contrast, for the fluorescence radiation, no such spectral splitting phenomenon is observed with much more abundant R branch structures. Our theoretical model considers gas ionization by the pump pulse, the competition of excitation of all relevant electronic and vibrational states, and an amplification of the seeding pulse in the plasma with a population inversion. Our simulation reproduces this spectral splitting effect, which is attributed to the gain saturation resulting in the oscillation of the amplitude of the amplified signal.

International audience; Post-Compromise Security (PCS) is a property of secure channel establishment schemes, which limits the security breach of an adversary that has compromised one of the end point to a certain number of messages, after which the channel heals. An attractive property, especially in view of Snowden's revelation of mass-surveillance, PCS was pioneered by the Signal messaging protocol, and is present in OTR. In this paper, we introduce a framework for quantifying and comparing PCS security, with respect to a broad taxonomy of adversaries. The generality and flexibility of our approach allows us to model the healing speed of a broad class of protocols, including Signal, but also an identity-based messaging protocol named SAID, and even a composition of 5G handover protocols.

International audience; In this paper, we focus on extensions of methods for interpolating rational functions from their evaluations, in the context of erroneous evaluations. This problem can be seen both from a computer algebra and a coding theory point of view. In computer algebra, this is a generalization of Simultaneous Rational Function Reconstruction with errors and multiprecision evaluations. From an error correcting codes point of view, this problem is related to the decoding of some algebraic codes such as Reed-Solomon, Derivatives or Multiplicity codes. We give conditions on the inputs of the problem which guarantee the uniqueness of the interpolant.Since we deal with rational functions, some evaluation points may be poles: a first contribution of this work is to correct any error in a scenario with poles and multiplicities that extends (Kaltofen et al., 2020). Our second contribution is to adapt rational function reconstruction for random errors, and provide better conditions for uniqueness using interleaving techniques as in (Guerrini et al., 2021).

International audience; The application motivating this work is related to the identification of deposits inside nuclear power plant steam generators using eddy-current probes. We consider a realistic experimental process that relies on the scan of a domain by sweeping along a tube axis a probe made out of coils, playing the role of the sources/receivers. Solving the inverse shape problem associated with these measurements using a least squares method requires solutions to the eddy-current and the adjoint problems for a large number of right-hand sides at each gradient-descent iteration. Additional cost in the forward solver comes from the use of a potential formulation of the problem that has the advantage of being independent from the topology of the conductive media (that may vary during iterations). We use a level-set approach to avoid remeshing and handle unknown topologies. The crucial ingredient in our algorithm is an optimized way of handling high numbers of right-hand sides for iterative solvers of large-scale problems. We first benchmark various block Krylov methods, block GMRES and block BGCRODR, to test their effectiveness compared to their standard counterpart, i.e., GMRES and GCRODR. Then, we propose for BGCRODR a new implementation for recycling information from previously generated Krylov bases that scales better than traditional approaches. This part is independent from the practical inverse problem at hand. The efficiency of the overall inversion procedure is finally demonstrated on realistic synthetic 3D examples.

An attacker can gain information of a user by analyzing its network traffic. The size of transferred data leaks information about the file being transferred or the service being used, and this is particularly revealing when the attacker has background knowledge about the files or services available for transfer. To prevent this, servers may pad their files using a padding scheme, changing the file sizes and preventing anyone from guessing their identity uniquely. This work focuses on finding optimal padding schemes that keep a balance between privacy and the costs of bandwidth increase. We consider R\'enyi-min leakage as our main measure for privacy, since it is directly related with the success of a simple attacker, and compare our algorithms with an existing solution that minimizes Shannon leakage. We provide improvements to our algorithms in order to optimize average total padding and Shannon leakage while minimizing R\'enyi-min leakage. Moreover, our algorithms are designed to handle a more general and important scenario in which multiple servers wish to compute padding schemes in a way that protects the servers' identity in addition to the identity of the files.

This thesis proposes several contributions to the problem of optimizing a nonlinear function of several variables in a continuous search space in the presence of constraints. The approach is called black box in that the considered algorithms have only access to the objective and constraint functions for the search of an optimal solution.The first contribution is the establishment of a suite of test problems for continuous constrained optimization. The method used to construct these test problems is based on optimality conditions that are general enough to allow defining non-convex problems where the optimum is known. The construction has other practical interests, such as the possibility to vary the number of variables or the number of constraints. We also propose a method for monitoring the performance of an optimization algorithm that can be applied to any such problem.The second contribution is a thorough study and improvement of a stochastic algorithm for the optimization of a multivariate function. This algorithm combines the principles of an evolution strategy with covariance matrix adaptation (CMA-ES) for non-convex optimization with the augmented Lagrangian (AL) technique to handle constraints. Based on recent work, our experiments reveal that other values of the hyperparameters, and even alternative mechanisms for adapting the penalty parameters, are competitive in a black-box context. We also propose a heuristic for the initialization of the adaptive parameters, and a preliminary study of the use of linear models to replace the constraints. The previously introduced suite of test problems is used as a tool to develop and validate the performance of these algorithmic alternatives.The third contribution is the generation of extensive experimental data with many popular algorithms for nonlinear optimization operating on our test problem suite. These data highlight concrete use cases where one algorithm is more suitable than the other competitors.Finally, we illustrate the diversity of optimization problems encountered in practice in the case of Radar signal processing. We address two classical Radar antenna design problems as numerical optimization problems. The first problem is the optimal configuration of a sensor array for the estimation of the direction of arrival of a detected signal. The second one is the phase modulation of an antenna array in order to obtain a radiation pattern with minimum unwanted emission losses. These 2 problems differ in many aspects (regularity of the objective function, dimension, number of constraints) and lead to the selection of different algorithms as the most suitable for each problem.In addition, some aspects of computer programming for handling and solving optimization problems will be discussed, as well as some avenues for future work in the quest for the best optimization algorithm to solve a given problem.; La thèse propose plusieurs contributions à l’optimisation d’une fonction non linéaire de plusieurs variables dans un espace de recherche continu en présence de contraintes. L’approche est dite boîte noire en cela` que les algorithmes considérés ont seulement accès aux fonctions objectif et contraintes pour la recherche d’une solution optimale. La première contribution est l’établissement d’une suite de problèmes tests pour l’optimisation continue sous contraintes. La méthode utilisée pour construire ces problèmes test se base sur des conditions d’optimalité suffisamment générales pour permettre la construction de problèmes non convexes ou` l’optimum est connu, et présente d’autres intérêts pratiques, comme la possibilité de faire varier le nombre de variables ou le nombre de contraintes. Nous proposons également une méthode de suivi (monitoring) des performances d’un algorithme d’optimisation qui s’applique à n’importe quel problème ou` l’optimum est connu. La seconde contribution est une étude approfondie et l’amélioration d’un algorithme stochastique pour l’optimisation d’une fonction de plusieurs variables. Cet algorithme combine les principes d’une stratégie d’évolution avec adaptation de la matrice de covariance (CMA-ES) pour l’optimisation non convexe avec la technique du Lagrangien augmenté (AL) pour la gestion des contraintes. Sur la base de travaux récents, nos expériences révèlent que d’autres valeurs des hyperparamètres, et même des mécanismes alternatifs d’adaptation des paramètres de pénalités, sont compétitifs dans un contexte boîte-noire. On propose par ailleurs une heuristique pour l’initialisation des paramètres adaptatifs, et une étude préliminaire à l’utilisation de modèles linéaires pour remplacer les contraintes. La suite de problème tests précédemment introduite sert d’outil de développement et de validation des performances de ces alternatives algorithmiques. La troisième contribution est la génération de nombreuses données expérimentales avec de nombreux algorithmes populaires pour l’optimisation non linéaire opérant sur notre suite de problèmes tests. Ces données mettent en lumière des cas d’usages concrets ou` un algorithme est plus adapté que les autres compétiteurs. Enfin, nous illustrons la diversité des problèmes d’optimisation rencontrés en pratique dans le cas du traitement du signal Radar. Nous proposons de traiter deux problèmes classiques de conception d’antenne Radar sous la forme de problèmes d’optimisation numérique. Le premier problème est la configuration optimale d’un réseau de capteurs pour l’estimation de la direction d’arrivée d’un signal détecté. Le second est la modulation en phase d’une antenne réseau afin d’obtenir un diagramme de rayonnement avec le minimum de pertes d’émissions indésirables. Ces 2 problèmes diffèrent par de nombreux aspects (régularité de la fonction objectif, dimension, nombre de contraintes) et donnent lieu a` la sélection d’algorithmes différents comme le plus adapté a` chaque problème. On discutera aussi quelques aspects de programmation informatique pour la manipulation et la résolution de problèmes d’optimisation, ainsi que quelques pistes de travaux futurs dans la quête du meilleur algorithme d’optimisation pour résoudre un problème donné.

Non-homogeneous groups like the special Euclidean group SE(3) (of the translations and rotations in R 3) or the Poincaré group of Minkowski space-time R 4 also contain translations, which seems to preclude the possibility of building a representation based on Clifford algebra for them because representations are purely based on matrix multiplication. Summing of group elements is a priori not defined, only products are. However, with the use of homogeneous coordinates, SE(3) can be obtained as the group generated by an even number of reflections with respect to hyperplanes of R 4. Similarly the Poincaré group is a group that can be generated by an even number of reflections with respect to hyperplanes of R 5. However, this leads to some normalization problems and in order to avoid these, null vectors must be introduced. We work this out for the group SE(3) and for the Poincaré group. It leads to groups noted as SO(3,1,0) for SE(3) and SO(3,1,1) or SO(1,1,3) for the Poincaré group.

We consider the decoding of rank metric codes assuming the error matrix is symmetric. We prove two results. First, for rates $1/2$, we propose a decoder for Gabidulin codes correcting symmetric errors of rank up to $n-k$. The two mentioned decoders are deterministic and worst case.

International audience; Oblivious Transfer (OT) is a major primitive for secure multiparty computation. Indeed, combined with symmetric primitives along with garbled circuits, it allows any secure function evaluation between two parties. In this paper, we propose a new approach to build OT protocols. Interestingly, our new paradigm features a security analysis in the Universal Composability (UC) framework and may be instantiated from post-quantum primitives. In order to do so, we define a new primitive named Smooth Projective Hash Function with Grey Zone (SPHFwGZ) which can be seen as a relaxation of the classical Smooth Projective Hash Functions, with a subset of the words for which one cannot claim correctness nor smoothness: the grey zone. As a concrete application, we provide two instantiations of SPHFwGZ respectively based on the Diffie-Hellman and the Learning With Errors (LWE) problems. Hence, we propose a quantum-resistant OT protocol with UC-security in the random oracle model.

Hybrid lead halide perovskites (ABX3) are an intriguing class of semiconductors with excellent optoelectronic properties and promising for photovoltaic applications. A fundamental understanding of the ultrafast dynamics in these materials is required. This work deals with two main topics: (1) The study of electron relaxation in the conduction band using time-resolved photoemission (2PPE) and angle-resolved photoemission (tr-ARPES). Here, the influence of the orientation of A-site cations and crystallographic structure on charge screening have been studied, explaining the high tolerance to electron trapping on the surface in MAPbI3 crystals. (2) Understanding the dynamic role of phonons and their influence on electrons using the THz-induced Kerr effect. We obtained coherent control over a Raman-active Pb-Br sublattice mode, which was found to dominate the ultrafast lattice polarizability in both single and complex A-site cation perovskites. This finding highlights the potential of the inorganic lattice for dynamic carrier screening and the related mechanism of charge carrier protection., Les pérovskites hybrides aux halogénures de plomb (ABX3) sont une classe de semi-conducteurs présentant d’excellentes propriétés optoélectroniques et particulièrement prometteuses pour les applications photovoltaïques. Une compréhension fondamentale des dynamiques ultrarapides de ces matériaux est nécessaire. Ces travaux traitent deux thématiques principales : (1) L’étude de la relaxation des électrons dans la bande de conduction à l’aide de la photoémission résolue en temps et en angle. Cette technique a permis d’étudier l’influence de l’orientation des cations A et de la structure cristallographique sur l’écrantage des charges et ainsi d’expliquer la grande tolérance au piégeage des électrons sur la surface des cristaux de MAPbI3. (2) Comprendre le rôle des phonons et leur influence sur les électrons à l’aide de l’effet Kerr excité au THz. Le mode de phonon Raman le plus polarisable lié au sous-réseau Pb-Br a été dévoilé dans les pérovskites à cation A unique et complexe. Cette découverte met en évidence le rôle du réseau inorganique le mécanisme d’écrantage des porteurs de charges.

International audience; In the first edition of this book, we discussed methods for determining the support of an inhomogeneous media from measured far field data as well as an extensive study of the central role played by the transmission eigenvalue problem in the mathematical development of these methods. In particular, we introduced the generalized linear sampling method (GLSM) and showed that this method provides a mathematical explanation of why it is permissible to use Tikhonov regularization to obtain an approximate solution of the far field equation associated with the linear sampling method.In the five years since the first edition of our book appeared, there has been considerable progress in both the development of GLSM as well as the theory of transmission eigenvalues. In this second edition, in addition to correcting typos in the first edition, we have added several highlights taken from these new developments. In particular, we have included new chapters on 1) the use of modified background media in the nondestructive testing of materials and in particular methods for determining the modified transmission eigenvalues that arise in such applications from measured far field data, 2) a study of a subset of transmission eigenvalues, called non-scattering wave numbers, through the use of techniques taken from the theory of free boundary value problems for elliptic partial differential equations and 3) the duality between scattering poles and transmission eigenvalues which, in addition to their intrinsic mathematical interest, leads to new methods for the numerical computation of scattering poles.

International audience; We consider a control problem for a heterogeneous population composed of customers able to switch at any time between different contracts, depending not only on the tariff conditions but also on the characteristics of each individual. A provider aims to maximize an average gain per time unit, supposing that the population is of infinite size. This leads to an ergodic control problem for a "mean-field" MDP in which the state space is a product of simplices, and the population evolves according to a controlled linear dynamics. By exploiting contraction properties of the dynamics in Hilbert's projective metric, we show that the ergodic eigenproblem admits a solution. This allows us to obtain optimal strategies, and to quantify the gap between steady-state strategies and optimal ones. We illustrate this approach on examples from electricity pricing, and show in particular that the optimal policies may be cyclic-alternating between discount and profit taking stages.

International audience; This paper focuses on isogeny representations, defined as ways to evaluate isogenies and verify membership to the language of isogenous supersingular curves (the set of triples D, E1, E2 with a cyclic isogeny of degree D between E1 and E2). The tasks of evaluating and verifying isogenies are fundamental for isogeny-based cryptography. Our main contribution is the design of the suborder representation, a new isogeny representation targetted at the case of (big) prime degree. The core of our new method is the revelation of endomorphisms of smooth norm inside a well-chosen suborder of the codomain's endomorphism ring. This new representation appears to be opening interesting prospects for isogeny-based cryptography under the hardness of a new computational problem: the SubOrder to Ideal Problem (SOIP). As an application, we introduce pSIDH, a new NIKE based on the suborder representation. Studying new assumption appears to be particularly crucial in the light of the recent attacks against isogeny-based cryptography. In order to manipulate efficiently the suborder representation, we develop several heuristic algorithmic tools to solve norm equations inside a new family of quaternion orders. These new algorithms may be of independent interest.

Resistance of cements against sulfate attacks is a very important issue since the beginning of the history of cements. Sulfates are responsible of the swelling and breaking of concrete. Their presence in many environments, such as sea water and gypsum-rich soil, is a problem for the durability of Portland cement. Portland cement is composed of two calcium silicates, and two calcium aluminates, tricalcium aluminate and calcium ferrite. Studies have shown the important role of tricalcium aluminate in the lowering of cement resistance in sulfated environments, however, the role of ferrite is not well known and appears now to be important.That is why we worked on the reactivity in sulfated medium of synthetic and industrial ferrite.However, the complexity of cement renders the study of industrial material very difficult. We have developed a double extraction method in order to extract the industrial ferrite. Ferrite was systematically studied by powder X-ray diffraction, electron microprobe, X-ray fluorescence spectroscopy and 57Fe Mössbauer spectroscopy. Results show a strong dependence of ferrite reactivity either on the Al/Fe ratio and the environment. Several threshold values can be found depending on the solution. Dissolution speeds in very diluted solutions made it possible to predict the reactivity of ferrite and to distinguish very close Al/Fe ratios. It appears through this work that ferrite can no longer be ignored for its role in the sulfated attack.; La résistance des ciments aux sulfates est restée un problème important depuis le début de leur histoire. Les sulfates sont à l’origine de gonflements qui provoquent la fissuration du matériau. Leur présence dans les environnements marins ou sols gypseux pose donc des problèmes vis-à-vis de la durabilité du ciment Portland. Le ciment Portland, contient essentiellement deux silicates de calcium, et deux aluminates de calcium, l’aluminate tricalcique et le ferrite. Le rôle de l’aluminate tricalcique dans la baisse de résistance aux sulfates est connu, cependant celui du ferrite qui n’a pas été étudié semble déterminant.C’est pourquoi nous avons travaillé sur la réactivité en milieu sulfatique du ferrite de synthèse et industriel.Néanmoins, la complexité du ciment ne permet pas de travailler directement sur ce dernier. Nous sommes parvenus à mettre au point une méthode de double extraction pour l’étudier.Le ferrite fut étudié par diffraction des rayons X, spectroscopie Mössbauer, spectroscopie de fluorescence X et microsonde de Castaing. La réactivité du ferrite fut aussi étudiée dans différents milieux réactionnels par spectroscopie d’émission atomique et conductimétrie. Les résultats montrent que la réactivité du ferrite dépend très fortement du rapport molaire Al/Fe mais aussi du milieu réactionnel. Différentes valeurs pivots ont pu être trouvées en fonction du milieu. On arrive à mesurer très finement la réactivité, même pour des ferrites très proches chimiquement.Il s’avère à travers ce travail que le ferrite ne peut plus être négligé pour les études de durabilité.

International audience; It is crucial to consider the social and ethical consequences of AI and ML based decisions for the safe and acceptable use of these emerging technologies. Fairness, in particular, guarantees that the ML decisions do not result in discrimination against individuals or minorities. Identifying and measuring reliably fairness/discrimination is better achieved using causality which considers the causal relation, beyond mere association, between the sensitive attribute (e.g. gender, race, religion, etc.) and the decision (e.g. job hiring, loan granting, etc.). The big impediment to the use of causality to address fairness, however, is the unavailability of the causal model (typically represented as a causal graph). Existing causal approaches to fairness in the literature do not address this problem and assume that the causal model is available. In this paper, we do not make such assumption and we review the major algorithms to discover causal relations from observable data. This study focuses on causal discovery and its impact on fairness. In particular, we show how different causal discovery approaches may result in different causal models and, most importantly, how even slight differences between causal models can have significant impact on fairness/discrimination conclusions. These results are consolidated by empirical analysis using synthetic and standard fairness benchmark datasets. The main goal of this study is to highlight the importance of the causal discovery step to appropriately address fairness using causality.

The success of Density Functional Theory (DFT) is partly due to that of simple approximations, such as the Local Density Approximation (LDA), which uses results of a model, the homogeneous electron gas, to simulate exchange-correlation effects in real materials. We turn this intuitive approximation into a general and in principle exact theory by introducing the concept of a connector: a prescription how to use results of a model system in order to simulate a given quantity in a real system. In this framework, the LDA can be understood as one particular approximation for a connector that is designed to link the exchange-correlation potentials in the real material to that of the model. Formulating the in principle exact connector equations allows us to go beyond the LDA in a systematic way. Moreover, connector theory is not bound to DFT, and it suggests approximations also for other functionals and other observables. We explain why this very general approach is indeed a convenient starting point for approximations. We illustrate our purposes with simple but pertinent examples.

Detection of Zn(II) in oil-polluted seawater via square-wave anodic stripping voltammetry (SW-ASV) utilizing thin gold electrodes sputtered onto nanoporous poly(acrylic acid)-grafted-poly(vinylidene difluoride) (PAA-g-PVDF) membrane is herein reported. Prior to SW-ASV, PAA grafted nanopores demonstrated to efficiently trap Zn(II) ions at open circuit. This passive adsorption followed a Langmuir law. An affinity constant of 1.41 L $$\upmu $$ μ mol$$^{-1}$$ - 1 and a maximum Zn(II) adsorbed mass q$$_{max}$$ max of 1.21 $$\upmu $$ μ mol g$$^{-1}$$ - 1 were found. Applied SW-ASV protocol implied an accumulation step (− 1.2 V for 120 s) followed by a stripping step (− 1.2 to 1 V; 25 Hz; step: 4 mV; amplitude: 25 mV; acetate buffer (pH 5.5)). It revealed a Zn redox potential at − 0.8 V (Ag/AgCl pseudo-reference). Multiple measurements in synthetic waters close to the composition of production waters exhibited a decreasing precision with the number of readings R (1.65$$\%$$ % (R = 2) and 6.56$$\%$$ % (R = 3)). These membrane-electrodes should be used as disposable. The intra-batch mean precision was 14$$\%$$ % (n = 3) while inter-batches precision was 20$$\%$$ % (n = 15). Linear and linear-log calibrations allow exploitation of Zn(II) concentrations ranging from 10 to 500 $$\upmu $$ μ g L$$^{-1}$$ - 1 and 100 to 1000 $$\upmu $$ μ g L$$^{-1}$$ - 1 respectively. The LOD was 4.2 $$\upmu $$ μ g L$$^{-1}$$ - 1 (3S/N). Thanks to obtained calibration, a detected Zn(II) content of 1 ppm in a raw production water from North Sea oil platform was determined.

We introduce a family of cardinality's lower bounds, defined as ratios of norms. We prove that the tightest bound of the family is obtained as a limit case, and involves a Shannon entropy. We then use this entropic lower bound in sparse optimization problems to approximate cardinality requirements. This provides a nonlinear nonconvex relaxed problem, which can be efficiently solved by off-the-shelf nonlinear solvers. In the numerical study, we focus on the case where the optimization is performed on the simplex, and where the classical l1 penalization does not yield sparse solution. The Finance Index Tracking problem is taken as an example and illustrates the efficiency of the proposed approach.

In this work, we present a novel non-rigid shape matching framework based on multi-resolution functional maps with spectral attention. Existing functional map learning methods all rely on the critical choice of the spectral resolution hyperparameter, which can severely affect the overall accuracy or lead to overfitting, if not chosen carefully. In this paper, we show that spectral resolution tuning can be alleviated by introducing spectral attention. Our framework is applicable in both supervised and unsupervised settings, and we show that it is possible to train the network so that it can adapt the spectral resolution, depending on the given shape input. More specifically, we propose to compute multi-resolution functional maps that characterize correspondence across a range of spectral resolutions, and introduce a spectral attention network that helps to combine this representation into a single coherent final correspondence. Our approach is not only accurate with near-isometric input, for which a high spectral resolution is typically preferred, but also robust and able to produce reasonable matching even in the presence of significant non-isometric distortion, which poses great challenges to existing methods. We demonstrate the superior performance of our approach through experiments on a suite of challenging near-isometric and non-isometric shape matching benchmarks., NeurIPS 2022. Code and data: https://github.com/craigleili/AttentiveFMaps

We study a tight Bennett-type concentration inequality for sums of heterogeneous and independent variables, defined as a one-dimensional minimization. We show that this refinement, which outperforms the standard known bounds, remains computationally tractable: we develop a polynomial-time algorithm to compute confidence bounds, proved to terminate with an epsilon-solution. From the proposed inequality, we deduce tight distributionally robust bounds to Chance-Constrained Programming problems. To illustrate the efficiency of our approach, we consider two use cases. First, we study the chance-constrained binary knapsack problem and highlight the efficiency of our cutting-plane approach by obtaining stronger solution than classical inequalities (such as Chebyshev-Cantelli or Hoeffding). Second, we deal with the Support Vector Machine problem, where the convex conservative approximation we obtain improves the robustness of the separation hyperplane, while staying computationally tractable.