Search

info:eu-repo/semantics/inPress

An important open problem in supersingular isogeny-based cryptography is to produce, without a trusted authority, concrete examples of ‘hard supersingular curves’ that is equations for supersingular curves for which computing the endomorphism ring is as difficult as it is for random supersingular curves. A related open problem is to produce a hash function to the vertices of the supersingular $ell $-isogeny graph, which does not reveal the endomorphism ring, or a path to a curve of known endomorphism ring. Such a hash function would open up interesting cryptographic applications. In this paper, we document a number of (thus far) failed attempts to solve this problem, in the hope that we may spur further research, and shed light on the challenges and obstacles to this endeavour. The mathematical approaches contained in this article include: (i) iterative root-finding for the supersingular polynomial; (ii) gcd’s of specialized modular polynomials; (iii) using division polynomials to create small systems of equations; (iv) taking random walks in the isogeny graph of abelian surfaces, and applying Kummer surfaces and (v) using quantum random walks., info:eu-repo/semantics/published

Zero-knowledge proofs for NP statements are an essential tool for building various cryptographic primitives and have been extensively studied in recent years. In a seminal result from Goldreich, Micali and Wigderson [17], zero-knowledge proofs for NP statements can be built from any one-way function, but this construction leads very inefficient proofs. To yield practical constructions, one often uses the additional structure provided by homomorphic commitments. In this paper, we introduce a relaxed notion of homomorphic commitments, called malleable commitments, which requires less structure to be instantiated. We provide a malleable commitment construction from the ElGamal-type isogeny-based group action from Eurocrypt’22 [5]. We show how malleable commitments with a group structure in the malleability can be used to build zero-knowledge proofs for NP statements, improving on the naive construction from one-way functions. We compare three different approaches, namely from arithmetic circuits, rank-1 constraint systems and branching programs., SCOPUS: cp.k, info:eu-repo/semantics/published

In a context where technological advancements have enabled increased availability of genetic data through high-throughput sequencing technologies, the complexity of genetic diseases has become increasingly apparent. Oligogenic diseases, characterised by a combination of genetic variants in two or more genes, have emerged as a crucial research area, challenging the traditional model of "one genotype, one phenotype". Thus, understanding the underlying mechanisms and genetic interactions of oligogenic diseases has become a major priority in biomedical research. This context underlines the importance of developing dedicated tools to study these complex diseases.Our first major contribution, OLIDA, is an innovative database designed to collect data on variant combinations responsible for these diseases, filling significant gaps in the current knowledge, focused up until now on the digenic diseases. This resource, accessible via a web platform, adheres to FAIR principles and represents a significant advancement over its predecessor, DIDA, in terms of data curation and quality assessment.Furthermore, to support the biocuration of oligogenic diseases, we used active learning to construct DUVEL, a biomedical corpus focused on digenic variant combinations. To achieve this, we first investigated how to optimise these methods across numerous biomedical relation extraction datasets and developed a web-based platform, ALAMBIC, for text annotation using active learning. Our results and the quality of the corpus obtained demonstrate the effectiveness of active learning methods in biomedical relation annotation tasks.By establishing a curation pipeline for oligogenic diseases, as well as a standards for integrating active learning methods into biocuration, our work represents a significant advancement in the field of biomedical natural language processing and the understanding of oligogenic diseases., Option Informatique du Doctorat en Sciences, info:eu-repo/semantics/nonPublished

Customer churn is an important concern for large companies, especially in the telecommunications sector. Customer retention campaigns are often used to mitigate churn, but targeting the right customers based on their historical profiles presents an important challenge. Companies usually have recourse to two data-driven approaches: churn prediction and uplift modeling. In churn prediction, customers are selected on the basis of their propensity to churn in the near future. In uplift modeling, only customers who react positively to the campaign are considered. Uplift modeling is used in various other domains, such as marketing, healthcare, and finance. Despite the theoretical appeal of uplift modeling, its added value with respect to conventional machine learning approaches has rarely been quantified in the literature.This doctoral thesis is the result of a collaborative research project between the Machine Learning Group (ULB) and Orange Belgium, funded by Innoviris. This collaboration offers a unique research opportunity to assess the added value of causal-oriented strategies to address customer churn in the telecommunication sector. Following the introduction, we give the necessary background in probability theory, causality theory, and machine learning, and we describe the state of the art in uplift modeling and counterfactual identification. Then, we present the contributions of this thesis: - An empirical comparison of various predictive and causal models for selecting customers in churn prevention campaigns. We perform several benchmarks of different state-of-the-art approaches on real-world datasets and in live campaigns with our industrial partner, we propose a new approach that exploits domain knowledge to improve predictions, and we make available the first public churn dataset for uplift modeling, whose unique characteristics make it more challenging than the few other public uplift datasets. - Counterfactual identification allows one to classify the diffe, L'attrition de la clientèle est une préoccupation importante pour de nombreuses entreprises, notamment dans le secteur des télécommunications. Des campagnes de fidélisation sont souvent utilisées pour réduire le taux de désabonnement, mais cibler les bons clients en fonction de leur profil représente un défi majeur. Les entreprises ont généralement recours à l'une de deux approches :la prédiction de churn (attrition) et la modélisation de l'uplift. Dans la prédiction de churn, les clients sont sélectionnés sur la base de leur propension estimée à se désabonner dans un avenir proche. Dans la modélisation de l'uplift, seuls les clients qui réagissent positivement à la campagne sont pris en compte. Les prédictions de ces deux approches sont basées sur les caractéristiques des clients. La modélisation de l'uplift est aussi utilisée dans d'autres domaines tels que le marketing, la médecine et la finance. Malgré son attrait théorique, la valeur ajoutée de la modélisation de l'uplift par rapport à l'approche plus conventionnelle de prédiction de churn a rarement été quantifiée dans la littérature.Cette thèse doctorale est le résultat d'un projet de recherche collaborative entre le Machine Learning Group (ULB) et Orange Belgique, financé par Innoviris. Cette collaboration offre une opportunité unique pour évaluer la valeur ajoutée de stratégies causales pour prévenir l'attrition de la clientèle dans le secteur des télécommunications. Après l'introduction, nous présentons les base théoriques nécessaires en théorie des probabilités, théorie de la causalité et apprentissage automatique, et nous décrivons l'état de l'art en matière de modélisation de l'uplift et d'identification contrefactuelle. Nous présentons ensuite les contributions de cette thèse :- Une comparaison empirique de divers modèles prédictifs et causaux pour la sélection des clients dans les campagnes de prévention du désabonnement. Nous comparons différentes approches de pointe sur des jeux de données réels et, Doctorat en Sciences, info:eu-repo/semantics/nonPublished

info:eu-repo/semantics/nonPublished

One of the reasons human groups struggle to make the best decisions is that they are inherently biased in their beliefs. In essence, our perception of what is true is often distorted by individual and social biases, including stereotypes. When individuals deliberate about a decision, they tend to transmit these beliefs to others, thereby steering the entire group away from the best decision. For example, a senior doctor could spread a misinterpretation of symptoms to junior doctors, resulting in inappropriate treatments. The primary objective of this thesis is to mitigate the impact of such biases on group decision-making in domains such as medical diagnostics, policy-making, and crowdsourced fact-checking. We propose to achieve this by having humans interact through a collective decision-making platform in charge of handling the aggregation of group knowledge. The key hypothesis here is that by carefully managing the collectivization of knowledge through this platform, it will be substantially harder for humans to impose their biases on the final decision. The core of our work involves the development and analysis of algorithms for decision-making systems. These algorithms are designed to effectively aggregate diverse expertise while addressing biases. We thus focus on aggregation methods that use online learning to foster collective intelligence more effectively. In doing so, we take into account the nuances of individual expertise and the impact of biases, aiming to filter out noise and enhance the reliability of collective decisions. Our theoretical analysis of the proposed algorithms is complemented by rigorous testing in both simulated and online experimental environments to validate the system’s effectiveness. Our results demonstrate a significant improvement in performance and reduction in bias influence. These findings not only highlight the potential of technology-assisted decision-making but also underscore the value of addressing human biases in collabor, Doctorat en Sciences, info:eu-repo/semantics/nonPublished

Background and Objectives: The extensive collection of electrocardiogram (ECG) recordings stored in paper format has provided opportunities for numerous digitization studies. However, the traditional 10 s 12-lead ECG printout typically splits the ECG signals into four asynchronous sections of 3 leads and 2.5 s each. Since each lead corresponds to different time instants, developing a synchronization method becomes necessary for applications such as vectorcardiogram (VCG) reconstruction. Methods: A beat-level synchronization method has been developed and validated using a dataset of 21,674 signals. This method effectively addresses synchronization distortions caused by RR interval variations and preserves the time lags between R peaks across different leads for each beat. Results: The results demonstrate that the proposed method successfully synchronizes the ECG, allowing a VCG reconstruction with an average Pearson Correlation Coefficient of 0.9815±0.0426. The Normalized Root Mean Squared Error (NRMSE) and Mean Absolute Error (MAE) values for the reconstructed VCG are 0.0248±0.0214 mV and 0.0133±0.0123 mV, respectively. These metrics indicate the reliability of the VCG reconstruction achieved by means of the proposed synchronization method. Conclusions: The synchronization method has demonstrated its robustness and high performance compared to existing techniques in the field. Its effectiveness has been observed across a wide variety of signals, showcasing its applicability in real clinical environments. Moreover, its ability to handle a large number of signals makes it suitable for various applications, including retrospective studies and the development of machine learning methods., SCOPUS: ar.j, info:eu-repo/semantics/published

While biomedical relation extraction (bioRE) datasets have been instrumental in the development of methods to support biocuration of single variants from texts, no datasets are currently available for the extraction of digenic or even oligogenic variant relations, despite the reports in literature that epistatic effects between combinations of variants in different loci (or genes) are important to understand disease etiologies. This work presents the creation of a unique dataset of oligogenic variant combinations, geared to train tools to help in the curation of scientific literature. To overcome the hurdles associated with the number of unlabelled instances and the cost of expertise, active learning (AL) was used to optimize the annotation, thus getting assistance in finding the most informative subset of samples to label. By pre-annotating 85 full-text articles containing the relevant relations from the Oligogenic Diseases Database (OLIDA) with PubTator, text fragments featuring potential digenic variant combinations, i.e. gene–variant–gene–variant, were extracted. The resulting fragments of texts were annotated with ALAMBIC, an AL-based annotation platform. The resulting dataset, called DUVEL, is used to fine-tune four state-of-the-art biomedical language models: BiomedBERT, BiomedBERT-large, BioLinkBERT and BioM-BERT. More than 500 000 text fragments were considered for annotation, finally resulting in a dataset with 8442 fragments, 794 of them being positive instances, covering 95% of the original annotated articles. When applied to gene–variant pair detection, BiomedBERT-large achieves the highest F1 score (0.84) after fine-tuning, demonstrating significant improvement compared to the non-fine-tuned model, underlining the relevance of the DUVEL dataset. This study shows how AL may play an important role in the creation of bioRE dataset relevant for biomedical curation applications. DUVEL provides a unique biomedical corpus focusing on 4-ary relations, SCOPUS: ar.j, info:eu-repo/semantics/published

Consider the problem of efficiently evaluating isogenies of elliptic curves over a finite field, where the kernel is a cyclic group of odd (prime) order: given, and a point (or several points) P on, we want to compute. 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élu’s formulæ give an efficient solution when the kernel generator G is defined over, but for general isogenies is only defined over some extension, even though as a whole (and thus) is defined over the base field ;and the performance of Vélu-style algorithms degrades rapidly as k grows. In this article we revisit isogeny evaluation with a special focus on the case where. We improve Vélu-style evaluation for many cases where using special addition chains, and combine this with the action of Galois to give greater improvements when., SCOPUS: cp.k, info:eu-repo/semantics/published

The Isogeny to Endomorphism Ring Problem (IsERP) asks to compute the endomorphism ring of the codomain of an isogeny between supersingular curves in characteristic p given only a representation for this isogeny, i.e. some data and an algorithm to evaluate this isogeny on any torsion point. This problem plays a central role in isogeny-based cryptography; it underlies the security of pSIDH protocol (ASIACRYPT 2022) and it is at the heart of the recent attacks that broke the SIDH key exchange. Prior to this work, no efficient algorithm was known to solve IsERP for a generic isogeny degree, the hardest case seemingly when the degree is prime. In this paper, we introduce a new quantum polynomial-time algorithm to solve IsERP for isogenies whose degrees are odd and have O(log log p) many prime factors. As main technical tools, our algorithm uses a quantum algorithm for computing hidden Borel subgroups, a group action on supersingular isogenies from EUROCRYPT 2021, various algorithms for the Deuring correspondence and a new algorithm to lift arbitrary quaternion order elements modulo an odd integer N with O(log log p) many prime factors to powersmooth elements. As a main consequence for cryptography, we obtain a quantum polynomial-time key recovery attack on pSIDH. The technical tools we use may also be of independent interest., SCOPUS: cp.k, info:eu-repo/semantics/published

We consider the design of adaptive data structures for searching elements of a tree-structured space. We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings. The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path. We describe an online O (log log n )-competitive search tree data structure in this model, where n is the number of vertices. This matches the best-known competitive ratio of binary search trees. Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one that we call Steiner-closed search trees, which may be of independent interest. Moreover, our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees and, second, from these trees into paths., SCOPUS: ar.j, info:eu-repo/semantics/published

info:eu-repo/semantics/published

Automatic biomedical relation extraction (bioRE) is an essential task in biomedical research in order to generate high-quality labelled data that can be used for the development of innovative predictive methods. However, building such fully labelled, high quality bioRE data sets of adequate size for the training of state-of-the-art relation extraction models is hindered by an annotation bottleneck due to limitations on time and expertise of researchers and curators. We show here how Active Learning (AL) plays an important role in resolving this issue and positively improve bioRE tasks, effectively overcoming the labelling limits inherent to a data set. Six different AL strategies are benchmarked on seven bioRE data sets, using PubMedBERT as the base model, evaluating their area under the learning curve (AULC) as well as intermediate results measurements. The results demonstrate that uncertainty-based strategies, such as Least-Confident or Margin Sampling, are statistically performing better in terms of F1-score, accuracy and precision, than other types of AL strategies. However, in terms of recall, a diversity-based strategy, called Core-set, outperforms all strategies. AL strategies are shown to reduce the annotation need (in order to reach a performance at par with training on all data), from 6% to 38%, depending on the data set; with Margin Sampling and Least-Confident Sampling strategies moreover obtaining the best AULCs compared to the Random Sampling baseline. We show through the experiments the importance of using AL methods to reduce the amount of labelling needed to construct high-quality data sets leading to optimal performance of deep learning models. The code and data sets to reproduce all the results presented in the article are available at https://github.com/oligogenic/Deep_active_learning_bioRE ., SCOPUS: ar.j, info:eu-repo/semantics/published

This thesis presents my research on fast neural architecture search (NAS) algorithms, and specifically on algorithms for dynamically growing and pruning artificial neural networks (NN) while they are trained. NAS, as a problem and as a research field, has emerged out of researchers' concern for developing accurate and efficient neural architectures for target tasks, while also avoiding undesirable and even harmful characteristics in these architectures, such as a very high parameter count or a superfluous time and energy cost for using them. The NAS problem is in fact bilevel: in order to optimize a NN, one must optimize both its architecture and its learnable parameters (weights, biases and the like)-and the relative importance of these two levels is still the subject of much debate. For this reason, the most "extreme" fast NAS approaches can be classified into two paradigms, "train one net" or "train zero nets", which respectively address the two optimization levels of NAS simultaneously or sequentially. This thesis provides an extensive survey of the state of the art for these two paradigms, but its main research work is only concerned with the first paradigm: "train one net". The thesis' main contribution is DensEMANN, an algorithm for quickly growing and training minimal yet optimal DenseNet architectures for target tasks. Inspired on a 1990's method for growing early NNs (EMANN), the algorithm is based on a "selfstructuring" or "in-supervised" approach that, through an introspection of the network's learned weights, determines when to add and/or remove components in it. As a result, it can generate architectures that, while small in size, are competitive at their target task: within half a GPU day, its latest version can generate NNs with less than 0.5 million learnable parameters, and 93% to 95% accuracy on image classification benchmarks such as CIFAR-10, SVHN and Fashion-MNIST. The thesis is built as a succession of research works and publications, highligh, Doctorat en Sciences de l'ingénieur et technologie, In reference to IEEE copyrighted material which is used with permission in this thesis, the IEEE does not endorse any of the Université libre de Bruxelles’ products or services. Internal or personal use of this material is permitted. If interested in reprinting/republishing IEEE copyrighted material for advertising or promotional purposes or for creating new collective works for resale or redistribution, please go to http://www.ieee.org/publications_standards/publications/rights/rights_link.html to learn how to obtain a License from RightsLink. If applicable, University Microfilms and/or ProQuest Library, or the Archives of Canada may supply single copies of the dissertation., info:eu-repo/semantics/nonPublished

info:eu-repo/semantics/published

Selectivity estimation refers to the ability of the SQL query optimizer to estimate the size of the results of a predicate in the query. It is the main calculation based on which the optimizer can select the least expensive plan to execute. While the problem has been known since the mid-1970s, we were surprised that there are no solutions in the literature for the selectivity estimation of inequality joins. By testing four common database systems: Oracle, SQL-Server, PostgreSQL, and MySQL, we found that the open-source systems PostgreSQL and MySQL lack this estimation. Oracle and SQL-Server make fairly accurate estimations, yet their algorithms are secret. This paper, thus, proposes an algorithm for inequality join selectivity estimation. The proposed algorithm was implemented in PostgreSQL and sent as a patch to be included in the next releases. We compared this implementation with the above DBMS for three different data distributions (uniform, normal, and Zipfian) and showed that our algorithm provides extremely accurate estimations (below 0.1% average error), outperforming the other systems by an order of magnitude., SCOPUS: ar.j, info:eu-repo/semantics/published

Experts advising decision-makers are likely to display expertise which varies as a function of the problem instance. In practice, this may lead to sub-optimal or discriminatory decisions against minority cases. In this work, we model such changes in depth and breadth of knowledge as a partitioning of the problem space into regions of differing expertise. We provide here new algorithms that explicitly consider and adapt to the relationship between problem instances and experts' knowledge. We first propose and highlight the drawbacks of a naive approach based on nearest neighbor queries. To address these drawbacks we then introduce a novel algorithm — expertise trees — that constructs decision trees enabling the learner to select appropriate models. We provide theoretical insights and empirically validate the improved performance of our novel approach on a range of problems for which existing methods proved to be inadequate., info:eu-repo/semantics/published

info:eu-repo/semantics/nonPublished

info:eu-repo/semantics/nonPublished

Background: The prediction of potentially pathogenic variant combinations in patients remains a key task in the field of medical genetics for the understanding and detection of oligogenic/multilocus diseases. Models tailored towards such cases can help shorten the gap of missing diagnoses and can aid researchers in dealing with the high complexity of the derived data. The predictor VarCoPP (Variant Combinations Pathogenicity Predictor) that was published in 2019 and identified potentially pathogenic variant combinations in gene pairs (bilocus variant combinations), was the first important step in this direction. Despite its usefulness and applicability, several issues still remained that hindered a better performance, such as its False Positive (FP) rate, the quality of its training set and its complex architecture. Results: We present VarCoPP2.0: the successor of VarCoPP that is a simplified, faster and more accurate predictive model identifying potentially pathogenic bilocus variant combinations. Results from cross-validation and on independent data sets reveal that VarCoPP2.0 has improved in terms of both sensitivity (95% in cross-validation and 98% during testing) and specificity (5% FP rate). At the same time, its running time shows a significant 150-fold decrease due to the selection of a simpler Balanced Random Forest model. Its positive training set now consists of variant combinations that are more confidently linked with evidence of pathogenicity, based on the confidence scores present in OLIDA, the Oligogenic Diseases Database ( https://olida.ibsquare.be ). The improvement of its performance is also attributed to a more careful selection of up-to-date features identified via an original wrapper method. We show that the combination of different variant and gene pair features together is important for predictions, highlighting the usefulness of integrating biological information at different levels. Conclusions: Through its improved performance and faster e, SCOPUS: ar.j, info:eu-repo/semantics/published

Background: Understanding the impact of gene interactions on disease phenotypes is increasingly recognised as a crucial aspect of genetic disease research. This trend is reflected by the growing amount of clinical research on oligogenic diseases, where disease manifestations are influenced by combinations of variants on a few specific genes. Although statistical machine-learning methods have been developed to identify relevant genetic variant or gene combinations associated with oligogenic diseases, they rely on abstract features and black-box models, posing challenges to interpretability for medical experts and impeding their ability to comprehend and validate predictions. In this work, we present a novel, interpretable predictive approach based on a knowledge graph that not only provides accurate predictions of disease-causing gene interactions but also offers explanations for these results. Results: We introduce BOCK, a knowledge graph constructed to explore disease-causing genetic interactions, integrating curated information on oligogenic diseases from clinical cases with relevant biomedical networks and ontologies. Using this graph, we developed a novel predictive framework based on heterogenous paths connecting gene pairs. This method trains an interpretable decision set model that not only accurately predicts pathogenic gene interactions, but also unveils the patterns associated with these diseases. A unique aspect of our approach is its ability to offer, along with each positive prediction, explanations in the form of subgraphs, revealing the specific entities and relationships that led to each pathogenic prediction. Conclusion: Our method, built with interpretability in mind, leverages heterogenous path information in knowledge graphs to predict pathogenic gene interactions and generate meaningful explanations. This not only broadens our understanding of the molecular mechanisms underlying oligogenic diseases, but also presents a novel application of knowl, SCOPUS: ar.j, info:eu-repo/semantics/published

Nowadays, numerous applications incorporate machine learning algorithms due to their prominent achievements. However, many studies in the field of computer vision have shown that machine learning can be fooled by intentionally crafted instances, called adversarial examples. These adversarial examples take advantage of the intrinsic vulnerability of machine learning models. This vulnerability raises many concerns in the cybersecurity field since an increasing number of security systems are powered by machine-learning algorithms. In this thesis, we explored the effects of adversarial machine learning on cybersecurity systems driven by machine learning models, focusing on intrusion detection systems. To do so, we implement and evaluate evasion attacks in both black-box and white-box settings to generate adversarial network traffic able to fool the intrusion detection system. We also design and test novel evasion attacks and adversarial defenses to improve the robustness of intrusion detection systems. The experimental results demonstrated that machine learning-based intrusion detection systems are vulnerable to adversarial attacks generated by adding minor specially crafted perturbations to malicious network traffic, allowing the attacker to evade detection and thus successfully perform his initial attacks. Adversarial detection, on the other hand, provides an efficient way to mitigate the effect of adversarial attacks at the expense of increasing model complexity by adding a second line of defense., Doctorat en Sciences de l'ingénieur et technologie, info:eu-repo/semantics/nonPublished

info:eu-repo/semantics/published, 4

info:eu-repo/semantics/inPress

The aim of this dissertation is to investigate the role of optimization in the automatic modular design of control software for robot swarms. One of the main challenges in swarm robotics is to design the behavior of the individual robots so that a desired collective mission can be performed. Optimization-based design methods utilize an optimization algorithm to search for well-performing instances of control software. In optimization-based design, past research has mainly focused on proving the feasibility of optimization-based design methods for given missions. With this approach, researchers could tackle a wide range of missions. However, only a few works compare the role of the components of any chosen optimization-based design method. In particular, very little attention has been devoted to the optimization algorithm, arguably the central element in optimization-based design. In the context of my research, I focused on automatic modular design, an optimization-based design approach that combines modules into higher-level control architectures. Automatic modular design has shown to produce control software that not onlyperforms well in simulation but that also transfers well into reality.In this dissertation, I present a study of different types of optimization algorithms: local-search, model-free racing, and model-based. I defined three automatic modular design methods and compared them against state-of-the-art methods from the literature. I assessed and compared these design methods in experiments for several missions, both in simulation and on real robots. In particular, I showed that, while the choice of the optimization algorithm has an impact on the performance of the generated control software, it appears to not compromise the ability to cross the reality gap satisfactorily.The work presented in this dissertation represents a first step towards systematically investigating the role of optimization in optimization-based design. More work is still needed to, Doctorat en Sciences de l'ingénieur et technologie, info:eu-repo/semantics/nonPublished

SCOPUS: ed.j, SCOPUS: ed.j, info:eu-repo/semantics/published

The SIDH protocol is an isogeny-based key exchange protocol using supersingular isogenies, designed by Jao and De Feo in 2011. The protocol underlies the SIKE algorithm which advanced to the fourth round of NIST’s post-quantum standardization project in May 2022. The algorithm was considered very promising: indeed the most significant attacks against SIDH were meet-in-the-middle variants with exponential complexity, and torsion point attacks which only applied to unbalanced parameters (and in particular, not to SIKE). This security picture dramatically changed in August 2022 with new attacks by Castryck-Decru, Maino-Martindale and Robert. Like prior attacks on unbalanced versions, these new attacks exploit torsion point information provided in the SIDH protocol. Crucially however, the new attacks embed the isogeny problem into a similar isogeny problem in a higher dimension to also affect the balanced parameters. As a result of these works, the SIKE algorithm is now fully broken both in theory and in practice. Given the considerable interest attracted by SIKE and related protocols in recent years, it is natural to seek countermeasures to the new attacks. In this paper, we introduce two such countermeasures based on partially hiding the isogeny degrees and torsion point information in the SIDH protocol. We present a preliminary analysis of the resulting schemes including non-trivial generalizations of prior attacks. Based on this analysis we suggest parameters for our M-SIDH variant with public key sizes of 4434, 7037 and 9750 bytes respectively for NIST security levels 1, 3, 5., SCOPUS: cp.k, SCOPUS: cp.k, info:eu-repo/semantics/published

When partitioning gate-level netlists using graphs, it is beneficial to cluster gates to reduce the order of the graph and preserve some characteristics of the circuit that the partitioning might degrade. Gate clustering is even more important for netlist partitioning targeting 3D system integration. In this paper, we make the argument that the choice of clustering method for 3D-ICs partitioning is not trivial and deserves careful consideration. To support our claim, we implemented three clustering methods that were used prior to partitioning two synthetic designs representing two extremes of the circuits medium/long interconnect diversity spectrum. Automatically partitioned netlists are then placed and routed in 3D to compare the impact of clustering methods on several metrics. From our experiments, we see that the clustering method indeed has a different impact depending on the design considered and that a circuit-blind, universal partitioning method is not the way to go, with wire-length savings of up to 31%, total power of up to 22%, and effective frequency of up to 15% compared to other methods. Furthermore, we highlight that 3D-ICs open new opportunities to design systems with a denser interconnect, drastically reducing the design utilization of circuits that would not be considered viable in 2D., SCOPUS: ar.j, info:eu-repo/semantics/published

Several methods have already been proposed to automatically design control software for robot swarms by assembling predefined modules. Yet, so far, the modules on which these methods operate have always been defined manually in a process that is time consuming, requires domain knowledge, and must be performed by an expert. Motivated by the goal of automatizing the definition of these modules, we propose an approach in which repertoires of modules, in the form of neural networks, are automatically generated via a quality-diversity evolutionary algorithm. To illustrate the proposal, we introduce Nata, a novel approach belonging to the AutoMoDe family. Nata automatically generates probabilistic finite-state machines in which states are selected from a repertoire of neural networks, and transition conditions are selected from a set of rules based on the sensory capabilities of the robotic platform considered. Both the repertoire of neural networks and the set of transition rules are automatically generated a priori, once and for all, in a mission-agnostic way. We study Nata on three missions, both in simulation and with real robots. Nata is the first modular automatic design method that assembles modules that were themselves generated automatically., SCOPUS: ar.j, info:eu-repo/semantics/published

In this paper, we present ALAMBIC, an open-source dockerized web-based platform for annotating text data through active learning for classification task. Active learning is known to reduce the need of labelling, a time-consuming task, by selecting the most informative instances among the unlabelled instances, reaching an optimal accuracy faster than by just randomly labelling data. ALAMBIC integrates all the steps from data import to customization of the (active) learning process and annotation of the data, with indications of the progress of the trained model that can be downloaded and used in downstream tasks. Its architecture also allows the easy integration of other types of model, features and active learning strategies.The code is available on https://github.com/Trusted-AI-Labs/ALAMBIC and a video demonstration is available on https://youtu.be/4oh8UADfEmY., info:eu-repo/semantics/published

This article was motivated by the question whether gamification represents a substantial innovation in internal party democracy, by contributing to change the dynamics of power within parties. To answer this question, we examine the only known case of gamification in the field of internal party voting, launched by the Italian Movimento 5 Stelle. We expected that gamified internal votes would reduce the incumbent advantage and promote party activists. Our data, however, suggest that these decision-making processes follow the same logic as the traditional ones. We thus conclude that digital innovations often end up working as “business as usual”., SCOPUS: ar.j, info:eu-repo/semantics/published

Let us consider some class of (Petri) nets. The corresponding Synthesis problem consists in deciding whether a given labeled transition system (TS) A can be implemented by a net N of that class. In case of a negative decision, it may be possible to convert A into an implementable TS B by applying various modification techniques, like relabeling edges that previously had the same label, suppressing edges/states/events, etc. It may however be useful to limit the number of such modifications to stay close to the original problem, or optimize the technique. In this paper, we show that most of the corresponding problems are NP-complete if the considered class corresponds to so-called flip-flop nets or some flip-flop net derivatives., SCOPUS: cp.j, info:eu-repo/semantics/published

The paper examines how to decide if a given (initially marked) Petri net is reversible, i.e. may always return to the initial situation. In particular, it concentrates on a very specific subclass of weighted circuits where the total number of tokens is constant, for which the worst case complexity is not known. Various ways to tackle the problem are considered, and some subcases are derived for which the problem is more or less easy., SCOPUS: cp.k, info:eu-repo/semantics/published

Document stores have gained popularity among NoSQL systems mainly due to the semi-structured data storage structure and the enhanced query capabilities. The database design in document stores expands beyond the first normal form by encouraging de-normalization through nesting. This hinders the process, as the number of alternatives grows exponentially with multiple choices in nesting (including different levels) and referencing (including the direction of the reference). Due to this complexity, document store data design is mostly carried out in trial-and-error or ad-hoc rule-based approaches. However, the choices affect multiple, often conflicting, aspects such as query performance, storage space, and complexity of the documents. To overcome these issues, in this paper, we apply multicriteria optimization. Our approach is driven by a query workload and a set of optimization objectives. First, we formalize a canonical model to represent alternative designs and introduce an algebra of transformations that can systematically modify a design. Then, using these transformations, we implement a local search algorithm driven by a loss function that can propose near-optimal designs with high probability. Finally, we compare our prototype against an existing document store data design solution purely driven by query cost, where our proposed designs have better performance and are more compact with less redundancy., SCOPUS: ar.j, info:eu-repo/semantics/published

info:eu-repo/semantics/published

SCOPUS: ed.j, info:eu-repo/semantics/published

info:eu-repo/semantics/published

In Petri net synthesis we ask whether a given transition system A can be implemented by a Petri net N. Depending on the level of accuracy, there are three ways how N can implement A: an embedding, the least accurate implementation, preserves only the diversity of states of A; a language simulation already preserves exactly the language of A; a realization, the most accurate implementation, realizes the behavior of A exactly. However, whatever the sought implementation, a corresponding net does not always exist. In this case, it was suggested to modify the input behavior - of course as little as possible. Since transition systems consist of states, events and edges, these components appear as a natural choice for modifications. In this paper we show that the task of converting an unimplementable transition system into an implementable one by removing as few states or events or edges as possible is NP-complete -regardless of what type of implementation we are aiming for; we also show that the corresponding parameterized problems are W[2]-hard, where the number of removed components is considered as the parameter; finally, we show there is no c-approximation algorithm (with a polynomial running time) for neither of these problems, for every constant c ≥ 1., SCOPUS: ar.j, info:eu-repo/semantics/published

NoSQL is an umbrella term used to classify alternate storage systems to the traditional Relational Database Management Systems (RDBMSs). At the moment of writing, there are more than 200 NoSQL systems available that can be classified into four main categories on the data storage model: key-value stores, document stores, column family stores, and graph stores. Document stores have gained popularity mainly due to the semi-structured data storage model and the rich query capabilities compared to the other NoSQL systems making them an ideal candidate for rapid prototyping. Document stores encourage users to use a data-first approach as opposed to a design-first one. Database design on document stores is mainly carried out in a trial-and-error or ad-hoc rule-based manner instead of a formal process such as normalization in an RDBMS. However, these approaches could easily lead to a non-optimal database design leading to additional costs in query processing, data storage, and redesigning.This PhD thesis aims to provide a novel multi-criteria-based approach to database design in document stores. Most of the existing approaches of database design are based on optimizing query performance. However, other factors include storage requirement and complexity of the stored documents specific to each use case. Moreover, there is a large solution space of alternative designs due to the different combinations of referencing and nesting of data. Hence, we believe multi-criteria optimization is ideal with a proven track record of solving such problems in various domains. However, to achieve this, we need to address several issues that will enable us to apply multi-criteria optimization for the data design problem.First, we evaluate the impact of alternate storage representations of semi-structured data. There are multiple and equivalent ways to physically represent semi-structured data, but there is a lack of evidence about the potential impact on space and query performance. Thus, we, Doctorat en Sciences de l'ingénieur et technologie, info:eu-repo/semantics/nonPublished

SCOPUS: ed.j, DecretOANoAutActif, info:eu-repo/semantics/published

This paper presents a few experiments that we carried out using DensEMANN (an algorithm that we are developing for automatically generating small and efficient DenseNet neural networks) and various algorithms for pruning or sparsifying neural networks at different granularity levels. The pruning algorithms that we used are based on the Lottery Ticket algorithm by Frankle and Carbin (2019), and on the Dense-Sparse-Dense (DSD) training algorithm by Han et al. (2017). Our experiments show that the pruning method based on DSD training is very efficient for reducing the parameter count of both human-designed and DensEMANN-generated neural networks while making them recover their original accuracy, and that this is especially true when sparsification is performed at the granularity level of individual convolution weights (by means of a mask that zeroes them out). Further research is nevertheless necessary to find out if (and how) this method can become an alternative to DensEMANN, or work in tandem with it, for actually shrinking already small and efficient neural networks., SCOPUS: cp.k, info:eu-repo/semantics/published

info:eu-repo/semantics/published

Self-organized aggregation is a well studied behavior in swarm robotics as it is the pre-condition for the development of more advanced group-level responses. In this paper, we investigate the design of decentralized algorithms for a swarm of heterogeneous robots that self-aggregate over distinct target sites. A previous study has shown that including as part of the swarm a number of informed robots can steer the dynamic of the aggregation process to a desirable distribution of the swarm between the available aggregation sites. We have replicated the results of the previous study using a simplified approach: we removed constraints related to the communication protocol of the robots and simplified the control mechanisms regulating the transitions between states of the probabilistic controller. The results show that the performances obtained with the previous, more complex, controller can be replicated with our simplified approach which offers clear advantages in terms of portability to the physical robots and in terms of flexibility. That is, our simplified approach can generate self-organized aggregation responses in a larger set of operating conditions than what can be achieved with the complex controller., SCOPUS: cp.k, SCOPUS: cp.k, info:eu-repo/semantics/published

In reduced-order modeling, complex systems that exhibit high state-space dimensionality are described and evolved using a small number of parameters. These parameters can be obtained in a data-driven way, where a high-dimensional dataset is projected onto a lower-dimensional basis. A complex system is then restricted to states on a low-dimensional manifold where it can be efficiently modeled. While this approach brings computational benefits, obtaining a good quality of the manifold topology becomes a crucial aspect when models, such as nonlinear regression, are built on top of the manifold. Here, we present a quantitative metric for characterizing manifold topologies. Our metric pays attention to non-uniqueness and spatial gradients in physical quantities of interest, and can be applied to manifolds of arbitrary dimensionality. Using the metric as a cost function in optimization algorithms, we show that optimized low-dimensional projections can be found. We delineate a few applications of the cost function to datasets representing argon plasma, reacting flows and atmospheric pollutant dispersion. We demonstrate how the cost function can assess various dimensionality reduction and manifold learning techniques as well as data preprocessing strategies in their capacity to yield quality low-dimensional projections. We show that improved manifold topologies can facilitate building nonlinear regression models., SCOPUS: ar.j, info:eu-repo/semantics/published

The SIDH key exchange is the main building block of SIKE, the only isogeny based scheme involved in the NIST standardization process. In 2016, Galbraith et al. presented an adaptive attack on SIDH. In this attack, a malicious party manipulates the torsion points in his public key in order to recover an honest party’s static secret key, when having access to a key exchange oracle. In 2017, Petit designed a passive attack (which was improved by de Quehen et al. in 2020) that exploits the torsion point information available in SIDH public key to recover the secret isogeny when the endomorphism ring of the starting curve is known. In this paper, firstly, we generalize the torsion point attacks by de Quehen et al. Secondly, we introduce a new adaptive attack vector on SIDH-type schemes. Our attack uses the access to a key exchange oracle to recover the action of the secret isogeny on larger subgroups. This leads to an unbalanced SIDH instance for which the secret isogeny can be recovered in polynomial time using the generalized torsion point attacks. Our attack is different from the GPST adaptive attack and constitutes a new cryptanalytic tool for isogeny based cryptography. This result proves that the torsion point attacks are relevant to SIDH (Disclaimer: this result is applicable to SIDH-type schemes only, not to SIKE.) parameters in an adaptive attack setting. We suggest attack parameters for some SIDH primes and discuss some countermeasures., SCOPUS: cp.k, info:eu-repo/semantics/published

info:eu-repo/semantics/published

In this paper, we examine the synthesis problem from a finite labeled transition system when the target is the class of weighted nets with (possibly) inhibitor and/or reset links, or some subclasses of them. We also discuss the intrinsic complexity of some cases; in particular we show that although some subclasses have a polynomial synthesis, most of the time it is NP-complete., SCOPUS: cp.k, info:eu-repo/semantics/published

Two major approaches in synthesis consist in specifying either the worst case behaviour or specifying the stochastic behaviour of a system. This thesis aims at studying the interplays of sure and stochastic conditions by considering algorithms to decide the existence of strategies in Markov decision processes for combinations of objectives. These objectives are omega-regular properties expressed as parity conditions, that need to be enforced either surely, almost surely, or with some threshold probability. In this setting, relevant strategies are randomized infinite memory strategies: both infinite memory and randomization may be needed to play optimally. We provide algorithms and complexity bounds for three main problems. First, we study multiple sure objectives, and multiple almost-sure objectives. Second, we consider Boolean combinations of sure objectives and multiple almost-sure objectives. Third, we consider one sure objective, and stochastic objectives that have to hold with a given probability threshold., Doctorat en Sciences, info:eu-repo/semantics/nonPublished

info:eu-repo/semantics/published