Portail HAL des publications du LIRMM
Not a member yet
13279 research outputs found
Sort by
Polyadic Relational Concept Analysis
No full textInternational audienceFormal concept analysis is a mathematical framework based on lattice theory that aims at representing the information contained in binary object-attribute datasets (called formal contexts) in the form of a lattice of so-called formal concepts. Since its introduction, it has been extended to more complex types of data. In this paper, we are interested in two of those extensions: relational concept analysis and polyadic concept analysis that allow to process, respectively, relational data and n-ary relations. We present a framework for polyadic relational concept analysis that extends relational concept analysis to relational datasets that are made of n-ary relations. We show its basic properties and that it is a valid extension of relational concept analysis
Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
No full textInternational audienceWe investigate the existence in geometric graph classes of subexponential parameterized algorithms for cycle-hitting problems like \textsc{Triangle Hitting} (TH), \textsc{Feedback Vertex Set} (FVS) or \textsc{Odd Cycle Transversal} (OCT). These problems respectively ask for the existence in a graph of a set of at most vertices such that is triangle-free, acyclic, or bipartite. It is know that subexponential FPT algorithms of the form exist in planar and even -minor free graphs from bidimensionality theory [Demaine et al. 2005], and there is a recent line of work lifting these results to geometric graph classes consisting of intersection of similarly sized ``fat'' objects ([Fomin et al. 2012]\nocite{Fomin12}, [Grigoriev et al. 2014], or disk graphs [Lokshtanov et al. 2022], [An et al. 2023]). In this paper we first identify sufficient conditions, for any graph class included in string graphs, to admit subexponential FPT algorithms for any problem in , a family of bidimensional problems where one has to find a set of size at most hitting a fixed family of graphs, containing in particular \FVS. Informally, these conditions boil down to the fact that for any , the \emph{local radius of } (a new parameter introduced in [Lokshtanov et al. 2023]) is polynomial in the clique number of and in the maximum matching in the neighborhood of a vertex.To demonstrate the applicability of this generic result, we bound the local radius for two special classes: intersection graphs of axis-parallel squares and of contact graphs of segments in the plane. This implies that any problem (in particular, \FVS) can be solved in:\begin{itemize} \item -time in contact segment graphs, \item in intersection graphs of axis-parallel squares\end{itemize}On the positive side, we also provide positive results for Triangle Hitting by solving it in: \begin{itemize} \item -time in contact segment graphs, \item -time in -free \dDIR graphs (intersection of segments with at most possible slopes) \end{itemize}On the negative side, assuming the ETH we rule out the existence of algorithms solving:\begin{itemize} \item Triangle Hitting and Odd Cycle Transversal in time in 2-DIR graphs and more generally in time in 2-DIR graphs with maximum degree , and \item Triangle Hitting, Feedback Vrtex Set, and Odd Cycle Transversal in time in -free contact-2-DIR graphs of maximum degree~6.\end{itemize}Observe that together, these results show that the absence of large is a necessary and sufficient condition for the existence of subexponential FPT algorithms for Triangle Hitting in 2-DIR
Étude des gadgets masqués dans Kyber
No full textWith the advent of the quantum computer threat, the NIST (National Institute of Standards and Technology) initiated a post-quantum standardization process in 2017 to select new algorithms for asymmetric cryptography. Several of these algorithms are based on lattice-based cryptography. One of the major challenges in implementing these algorithms is protecting them against side-channel attacks. A widely used defense technique is masking, which involves splitting sensitive values into a predefined number of random shares, such that an attacker with access to only a subset of these shares learns nothing about the secret. Operations that are adapted to masked inputs are referred to as gadgets. Securing post-quantum algorithms based on lattice cryptography is particularly challenging because they combine arithmetic operations on fields/rings with Boolean functions that operate on bits or bit vectors. This characteristic requires the use of mechanisms that enable conversion between different types of masking, which are known to be costly. In recent years, the literature on masking post-quantum schemes has been very active. With the emergence of new gadgets, it has become evident that comparing different gadgets masking the same operation is difficult. Neither asymptotic cost nor execution time in clock cycles on a given architecture provides a fully satisfactory solution. In this thesis, we introduce InspectorGadget, an Open Source Python-based software tool for evaluating and comparing the complexity of masking gadgets. By providing a limited set of characteristics of a hardware platform, our tool allows estimating the cost of a masking gadget in terms of clock cycles equivalent and memory footprint. InspectorGadget is highly flexible. It allows users to define their own estimation functions, as well as extend the predefined sets of gadgets and microcontrollers. As a case study, we propose a fair comparison of several masked versions of the Kyber compression function from the litera- ture, as well as new alternatives automatically generated by our tool. In the following, we focus exclusively on Kyber and the masking of its 1-bit compression function. We present the first fully arithmetic-masked 1-bit compression gadget, in contrast to the compression gadgets in the literature, which all require the use of a masking conversion. Our gadget simplifies Kyber masking by reducing the number of masking conversions used in this scheme. Although our results show that this conversion is less efficient than those from the literature, it is a first step towards a fully arithmetic-masked Kyber scheme.Avec l’arrivée de la menace de l’ordinateur quantique, le NIST (National Institute of Standards and Technology) a lancé en 2017 un processus de standardisation post-quantique, afin de sélectionner de nouveaux algorithmes en cryptographie asymétrique. Plusieurs algorithmes sont basés sur les réseaux euclidiens. L’un des défis majeurs dans la mise en œuvre de ces algorithmes est de les protéger contre les attaques par canaux auxiliaires. Une technique de défense largement utilisée est le masquage, qui consiste à partager des valeurs sensibles en un nombre prédéfini de parts aléatoires, de sorte qu’un attaquant n’ayant accès qu’à un sous-ensemble de ces parts ne puisse rien apprendre sur le secret. Les opérations adaptées à des entrées masquées sont appelées des gadgets. Sécuriser les algorithmes post-quantiques basés sur les réseaux euclidiens est particulièrement difficile, car ils combinent des opérations arithmétiques sur des corps/anneaux et des fonctions booléennes opérant sur des bits ou des vecteurs de bits. Cette particularité impose de considérer des mécanismes permettant la conversion entre différents types de masquage, qui sont connus pour être coûteux. La littérature sur le masquage de schémas post-quantiques a été très active ces dernières années. Avec l’apparition de nouveaux gadgets, il est apparu que la comparaison de différents gadgets masquant la même opération est difficile. Ni le coût asymptotique, ni le temps d’exécution en nombre de cycles sur une architecture donnée n’apporte de solution satisfaisante. Au cours de cette thèse, nous présenterons InspectorGadget, un logiciel Open Source basé sur Python pour évaluer et comparer la complexité de gadgets de masquage. En fournissant un ensemble limité de caractéristiques d’une plateforme matérielle, notre outil permet d’estimer le coût d’un gadget de masquage en termes d’équivalent en cycles d’horloge et d’empreinte mémoire. InspectorGadget est extrêmement flexible. Il permet à l’utilisateur de définir ses propres fonctions d’estimation, ainsi que d’étendre l’ensemble des gadgets et des microcontrôleurs prédéfinis. En tant qu’étude de cas, nous proposons une comparaison équitable de plusieurs versions masquées de la fonction de compression de Kyber, issues de la littérature, ainsi que des alternatives nouvelles générées automatiquement par notre outil. Dans la suite, nous nous concentrerons exclusivement sur Kyber et sur le masquage de sa fonction de compression à 1-bit. Nous présenterons le premier gadget de compression à 1-bit entièrement masqué en arithmétique, en opposition aux gadgets de compression de la littérature qui nécessitent tous l’utilisation d’une conversion de masquage. Notre gadget permet de simplifier le masquage de Kyber en réduisant le nombre de conversions de masque utilisées dans ce schéma. Bien que nos résultats montrent que cette conver- sion reste moins efficace que celles de la littérature, elle est une première étape vers un masquage de Kyber totalement arithmétique
Une étude de cas sur les vulnérabilités de la blockchain à l'aide de l'apprentissage par renforcement multi-agents.
No full textBlockchain technology has gained substantial traction in recent years, revolutionizing industries through its decentralized and trustless nature. However, the security of blockchain systems and, specifically, their underlying incentive mechanisms remains a critical concern, potentially leading to catastrophic losses if those economic incentives shaping the behavior of rational participants are not aligned with the expected behavior. This thesis addresses this challenge by proposing a comprehensive framework that ultimately leverages MARL to enhance the security of blockchain incentives while not being strictly limited to it. We propose a generic blockchain model that encapsulates the core components of blockchain systems, making it flexible and easily adaptable to diverse blockchain designs. This model serves as a foundational framework for enhancing blockchain security. Based on this model, we define a taxonomy of incentive vulnerabilities in blockchain systems. This classification categorizes, ranks and prioritizes vulnerabilities based on their feasibility and network impact. The taxonomy aids in identifying critical areas of interest where automatic and potentially exploratory work might be required to assess the resilience of the system. To complete the framework, we introduce a blockchain simulator that is, by construction, as close as possible to the generic blockchain model but, it is also ex-act with respect to specific protocols, and, compatible with reinforcement learning, allowing us to replicate real-world scenarios using honest or byzantine agents with arbitrary objectives. The same simulator can then be used to assess the effectiveness of a given countermeasure. Finally, we show a concrete study of protocol vulnerability of Ethereum 2.0 using all of the above contributions, serving as a practical example of the usage of MARL in the context of the proposed framework. By integrating these contributions, this thesis contributes to the evolving field of blockchain security and provides the means for developers and researchers to analyze, identify and address incentive vulnerabilities in a standardized and systematic manner. Using MARL as a security enhancement tool offers promising results, paving the way for more robust and secure blockchain systems in the future.La technologie blockchain a connu un essor considérable ces dernières années, révolutionnant les industries grâce à sa nature décentralisée et sans confiance. Cependant, la sécurité des systèmes de blockchain et, en particulier, de leurs mécanismes d'incitation sous-jacents reste une préoccupation majeure, pouvant conduire à des pertes financières catastrophiques si les incitations économiques qui façonnent le comportement des participants rationnels ne sont pas alignées sur le comportement attendu. Cette thèse aborde cette thématique en proposant un cadre complet qui tire parti du MARL pour renforcer la sécurité des incitations de la blockchain sans s'y limiter strictement. Nous proposons un modèle générique de blockchain qui encapsule les composants essentiels de ces systèmes, ce qui le rend flexible et facilement adaptable à diverses conceptions de blockchain. Ce modèle sert de cadre fondamental pour améliorer la sécurité de la blockchain. Sur la base de ce modèle, nous définissons une taxonomie des vulnérabilités d'incitation dans les systèmes de blockchain. Cette classification catégorise, classe et hiérarchise les vulnérabilités en fonction de leur faisabilité et de leur impact sur le réseau. La taxonomie aide à identifier les domaines d'intérêt critiques où un travail automatique et potentiellement exploratoire pourrait être nécessaire pour évaluer la résilience du système. Pour compléter ce cadre, nous introduisons un simulateur de blockchain qui est, par construction, aussi proche que possible du modèle générique de blockchain, mais qui est également exact en ce qui concerne les protocoles spécifiques, et qui est compatible avec l'apprentissage par renforcement, ce qui nous permet de reproduire des scénarios du monde réel en utilisant des agents honnêtes ou byzantins avec des objectifs arbitraires. Le même simulateur peut alors être utilisé pour évaluer l'efficacité d'une contre-mesure donnée. Enfin, nous montrons une étude concrète de la vulnérabilité du protocole d'Ethereum 2.0 en utilisant toutes les contributions ci-dessus, servant d'exemple pratique de l'utilisation du MARL. En intégrant ces contributions, cette thèse contribue à l'évolution du domaine de la sécurité des blockchains et fournit aux développeurs et aux chercheurs les moyens d'analyser, d'identifier et de traiter les vulnérabilités d'incitation d'une manière standardisée et systématique. L'utilisation du MARL comme outil d'amélioration de la sécurité offre des résultats prometteurs, ouvrant la voie à des systèmes de blockchain plus robustes et plus sûrs à l'avenir
IMGT/RobustpMHC: robust training for class-I MHC peptide binding prediction
No full textInternational audienceThe accurate prediction of peptide-major histocompatibility complex (MHC) class I binding probabilities is a critical endeavor in immunoinformatics, with broad implications for vaccine development and immunotherapies. While recent deep neural network based approaches have showcased promise in peptide-MHC (pMHC) prediction, they have two shortcomings: (i) they rely on hand-crafted pseudo-sequence extraction, (ii) they do not generalize well to different datasets, which limits the practicality of these approaches. While existing methods rely on a 34 amino acid pseudo-sequence, our findings uncover the involvement of 147 positions in direct interactions between MHC and peptide. We further show that neural architectures can learn the intricacies of pMHC binding using even full sequences. To this end, we present PerceiverpMHC that is able to learn accurate representations on full-sequences by leveraging efficient transformer based architectures. Additionally, we propose IMGT/RobustpMHC that harnesses the potential of unlabeled data in improving the robustness of pMHC binding predictions through a self-supervised learning strategy. We extensively evaluate RobustpMHC on eight different datasets and showcase an overall improvement of over 6% in binding prediction accuracy compared to state-of-the-art approaches. We compile CrystalIMGT, a crystallography-verified dataset presenting a challenge to existing approaches due to significantly different pMHC distributions. Finally, to mitigate this distribution gap, we further develop a transfer learning pipeline
Introduction to the Special Issue on Security and Privacy of Avatar in Metaverse
No full textThe Metaverse is a 3D interactive virtual community that has gained significant attention in academia, business, and industry as a potential future internet paradigm. In this space, avatars serve as key elements, acting as the primary means of human interaction. Avatars are expected to be created using real data, tailored to users' preferences, and controlled in real-time through signals from wearable devices.Avatars allow users to feel as though they are extensions of their own bodies, creating an immersive experience that blurs the line between virtual and real compared to other virtual communities. On the other hand, the avatar faces serious security and privacy problems, especially when people and the law/regulation are increasingly less tolerant of security and privacy, such as copyright, false identity detection, dataset security, authentication, and content tampering. This special issue collects 15 papers reporting the recent developments of security and privacy of avatar in metaverse.For the Avatar Copyright Protection. "A Self-Defense Copyright Protection Scheme for NFT Image Art Based on Information Embedding" addresses copyright issues related to avatars produced in the Metaverse and proposes a copyright protection scheme that not only enables tracking and verification of avatar content transactions but also validates the legality of the source and ownership of the avatar content."Invisible Adversarial Watermarking: A Novel Security Mechanism for Enhancing Copyright Protection" addresses the potential for unauthorized access and use of image datasets used to generate avatars and proposes an image protection method that combines adversarial perturbations with invisible watermarks. This approach not only prevents illegal use of the image datasets but also enables effective tracking of data copyright.In "FaceDefend: Copyright Protection to Prevent Face Embezzle, " the authors propose a solution to the misuse problem arising from the theft of real facial image data used in avatar generation, based on defensive strategies. This approach effectively ensures copyright protection for real facial data.For the False Identity Detection for Avatars.The authors of "Audio-Visual Contrastive Pre-train for Face Forgery Detection" address the issue of potential facial privacy breaches due to the realism of avatars in virtual worlds, which can lead
Shortest Disjoint Paths on a Grid
No full textInternational audienceThe well-known k-disjoint paths problem involves finding pairwise vertex-disjoint paths between k specified pairs of vertices within a given graph if they exist. In the shortest k-disjoint paths problem one looks for such paths of minimum total length. Despite nearly 50 years of active research on the k-disjoint paths problem, many open problems and complexity gaps still persist. A particularly well-defined scenario, inspired by VLSI design, focuses on infinite rectangular grids where the terminals are placed at arbitrary grid points. While the decision problem in this context remains NP-hard, no prior research has provided any positive results for the optimization version. The main result of this paper is a fixed-parameter tractable (FPT) algorithm for this scenario. It is important to stress that this is the first result achieving the FPT complexity of the shortest disjoint paths problem in any, even very restricted classes of graphs where we do not put any restriction on the placements of the terminals
Multiomics analysis reveals B. MO1 as a distinct Babesia species and provides insights into its evolution and virulence
No full textAll datasets generated for the current study are accessible in the NCBI/SRA repository under Bioproject PRJNA1032622 (reviewer link). Specifically, the datasets include PacBio HiFi reads (SRA accession number SRR26661633), B. MO1 genome, RNA-Seq (SRA accession number SRR26661632), Hi-C reads (SRA accession number SRR26661630, SRR26661631), ChIP-Seq reads (SRA accession number SRR26661627, SRR26661629, SRR26661626, SRR26661628, SRR26661625).Babesiosis, caused by protozoan parasites of the genus Babesia , is an emerging tick-borne disease of significance for both human and animal health. Babesia parasites infect erythrocytes of vertebrate hosts where they develop and multiply rapidly to cause the pathological symptoms associated with the disease. The identification of various Babesia species underscores the ongoing risk of new zoonotic pathogens capable of infecting humans, a concern amplified by anthropogenic activities and environmental shifts impacting the distribution and transmission dynamics of parasites, their vectors, and reservoir hosts. One such species, Babesia MO1, previously implicated in severe cases of human babesiosis in the midwestern United States, was initially considered closely related to B. divergens , the predominant agent of human babesiosis in Europe. Yet, uncertainties persist regarding whether these pathogens represent distinct variants of the same species or are entirely separate species. We show that although both B. MO1 and B. divergens share similar genome sizes, comprising three nuclear chromosomes, one linear mitochondrial chromosome, and one circular apicoplast chromosome, major differences exist in terms of genomic sequence divergence, gene functions, transcription profiles, replication rates and susceptibility to antiparasitic drugs. Furthermore, both pathogens have evolved distinct classes of multigene families, crucial for their pathogenicity and adaptation to specific mammalian hosts. Leveraging genomic information for B. MO1, B. divergens , and other members of the Babesiidae family within Apicomplexa provides valuable insights into the evolution, diversity, and virulence of these parasites. This knowledge serves as a critical tool in preemptively addressing the emergence and rapid transmission of more virulent strains
Detecting and Visualizing Implementation Feature Interactions in Extracted Core Assets of Software Product Line
No full textInternational audienceRecently, software products have played a vital role in our daily lives, having a significant impact on industries and the economy. Software product line engineering is an engineering strategy that allows for the systematic reuse and development of a set of software products simultaneously, rather than just one software product at a time. This strategy mainly relies on features composition to generate multiple new software products. Unwanted feature interactions, where the integration of multiple feature implementations hinders each other, are challenging in this strategy. This leads to performance degradation, and unexpected behaviors may happen. In this article, we propose an approach to detect and visualize all feature interactions early. Our approach depends on an unsupervised clustering technique called formal concept analysis to achieve the goal. The effectiveness of the proposed approach is evaluated by applying it to a large and benchmark case study in this domain. The results indicate that the proposed approach effectively detects and visualizes all interacted features. Also, it saves developer efforts for detecting interacted features in a range between 67% and 93%
Pilot study protocol evaluating the impact of telerobotics interactions with autistic children during a Denver intervention on communication skills using single-case experimental design
No full textInternational audienceIntroduction For several years, studies have been conducted on the contribution of social robots as an intervention tool for children with autism spectrum disorder (ASD). One of the early intervention models recommended by the French National Authority for Health is the Early Start Denver Model, an individualised, intensive programme based on play activities chosen by the child. While studies published in recent years suggest that robots provide benefits for autistic children in learning social interactions within a clinical setting, there is no scientific consensus on the widespread contribution and maintenance of their effects over time. On the other hand, a robotic solution controlled directly by a practitioner (ie, on-site telepresence system) enables greater adaptability to children’s responses and choices during interventions. We believe that such a solution would enable better assessment of progress in the fundamental skills of expressive communication and imitation as well as greater engagement during interventions. Methods and analysis This is a prospective, monocentric, descriptive and evaluative pilot study based on single-case experimental design (SCED) methodology. The study will recruit eight children diagnosed with ASD aged between 2 and 5 years. The intervention will take place 15 min after the usual weekly care. The SCED methodology is constructed in three stages: (A) 4 weekly sessions at baseline without the robot, (B) 9 weekly sessions with intervention modification using a social robot as cotherapist and (C) 4 weekly sessions without the robot for follow-up. Ethics and dissemination Ethical approval was obtained from the South East IV Ethics Committee (CPP Sud-Est IV) (number: 2023-A00895-40) in France. Explicit consent is required from all legal representatives (parents) of children participating in this study. We aim to disseminate the results of this study through national and international conferences, international peer-reviewed journals and social media. Trial registration number NCT05991791