Дисертації з теми "Fonctions de corrélation pseudo-aléatoires"

Les fonctions pseudo-aléatoires (Pseudorandom Functions, alias PRFs) ont été introduites en 1986, par Goldreich, Goldwasser et Micali, comme moyen efficace de générer de l’aléa et servent depuis d’outils essentiels en cryptographie. Ces fonctions utilisent une clé secrète principale pour faire correspondre différentes entrées à des sorties pseudo-aléatoires. Les fonctions pseudo-aléatoires contraintes (Constrained Pseudorandom Functions, alias CPRFs), introduites en 2013, étendent les PRFs enautorisant la délégation des clés contraintes qui permettent l’évaluation de la fonction uniquement sur des sous-ensembles spécifiques d’entrées. Notamment, même avec cette évaluation partielle, la sortie d’une CPRF devrait rester pseudo-aléatoire sur les entrées en dehors de ces sous-ensembles. Dans cette thèse, nous établissons des liens entre les CPRFs et deux autres outils cryptographiques qui ont été introduits dans le contexte du calcul sécurisé : 1. Nous montrons comment les CPRFs peuvent être construites à partir de protocoles de partage de secrets homomorphes (Homomorphic Secret Sharing, alias HSS). Les protocoles de partage de secrets homomorphes permettent des calculs distribués sur des parties d’un secret. Nous commençons par identier deux nouvelles versions des protocoles HSS et montrons comment elles peuvent être transformées en CPRFs générant des clés contraintes pour des sous-ensembles d’entrées qui peuvent être exprimés via des prédicats de produit scalaire ou de NC1. Ensuite, nous observons que les constructions de protocoles HSS qui existent déjà dans la littérature peuvent être adaptées à ces nouvelles extensions. Cela conduit à la découverte de cinq nouvelles constructions CPRF basées sur diverses hypothèses de sécurité standardes. 2. Nous montrons comment les CPRFs peuvent être utilisées pour construire des fonctions de corrélation pseudo-aléatoires (Pseudorandom Correlation Functions, alias PCFs) pour les corrélations de transfert inconscient (Oblivious Transfer, alias OT). Les PCFs pour les corrélations OT permettent à deux parties de générer des paires corrélées OT qui peuvent être utilisées dans des protocoles de calcul sécurisés rapides. Ensuite, nous détaillons l’instanciation de notre transformation en appliquant une légère modification à la construction PRF bien connue de Naor et Reingold. Enfin, nous présentons une méthode de génération non-interactive de clés d’évaluation pour cette dernière instanciation, qui permet d’obtenir une PCF à clé publique efficace pour les corrélations OT à partir d’hypothèses standardes
Pseudorandom functions (PRFs) were introduced in 1986 by Goldreich, Goldwasser, and Micali as efficient means of generating randomness and serve as essential tools in cryptography. These functions use a master secret key to map different inputs to pseudorandom outputs. Constrained pseudorandom functions (CPRFs), introduced in 2013, extend PRFs by additionally allowing the delegation of constrained keys that enable the evaluation of the function only on specific subsets of inputs. Notably, given a constrained key that evaluates the function on a subset of inputs, the output of a CPRF should remain pseudorandom on inputs outside of this subset. In this thesis, we establish links between CPRFs and two other cryptographic tools which were introduced in the context of secure computation: 1. We show how CPRFs can be constructed from homomorphic secret sharing (HSS) protocols. Homomorphic secret sharing protocols allow distributed computations over shares of a secret. We start by identifying two extensions of HSS protocols and show how they can be transformed into CPRFs generating constrained keys for subset of inputs that can be expressed via inner-product and NC1 predicates. Next, we observe that HSS protocols that already exist in the literature can be adapted to these new extensions. This leads to the discovery of five new CPRF constructions based on various standard hardness assumptions. 2.We show how CPRFs can be used to construct pseudorandom correlation functions (PCFs) for oblivious transfer (OT) correlations. PCFs for OT correlations enable two parties to generate OT-correlated pairs that can be used in fast secure computation protocols. Next, we instantiate our transformation by applying a slight modification to the well-known PRF construction of Naor and Reingold. We finally present a method for the non-interactive generation of evaluation keys for the latter instantiation which results in an efficient public-key PCF for OT correlations from standard assumptions

L’objectif de ce travail est de concevoir un système de communication et de localisation destiné à des métros automatiques guidés afin d’améliorer leur exploitation et d’accroître la sécurité. La principale application du RADAR est de réduire le temps de perte d’exploitation causé par un métro en panne, en permettant au train suivant de connaître en temps réel la distance le séparant de celui qui est immobilisé. Le capteur est du type radar coopératif constitué de deux couples d’interrogateurs–répondeurs équipant l’avant et l’arrière de chaque train et formant ainsi une boucle complète. Le choix du capteur s’est orienté vers le radar à corrélation, car il maximise le rapport signal à bruit en sortie. Des techniques de multiplexage originales à étalement de spectre ont été développées afin de combiner la fonction de localisation et l’établissement d’une communication avec le même capteur. Une des caractéristiques de ce système est qu’il est amené à fonctionner en tunnel et en espace libre. D’où le choix des têtes hyperfréquences proposées. La chaîne de transmission/réception a ensuite été simulée dans son intégralité et dans son environnement de fonctionnement afin de valider les choix techniques opérées. Finalement, nous avons présenté des solutions d’implémentation des algorithmes de traitement sur une plateforme de développement de type FPGA. Un prototype a été réalisé et les premiers tests ont été menés en espace libre. Les résultats obtenus montrent qu’une portée de l’ordre de 700 m peut être atteinte. Les techniques de multiplexage que nous avons proposées permettent d’établir une communication avec des débits variables suivant la technique de multiplexage. Ils peuvent prendre les valeurs (97kb/s,1,6Mb/S, 5,4Mb/s et 11,27Mb/s)
The aim of this work is to design a localization and communication system dedicated to guided automatic trains in order to enhance their exploitation and to increase their reliability. The principal function of this radar is to reduce the lost exploitation time caused by a broken-down train to allow the following train to estimate in real time the distance between them. The sensor is a cooperative radar composed by two couples of interrogators– transponders which equip the front and the rear of each train following a complete loop. The choice of the sensor type is directed towards the correlation radar, because it maximizes the output signal to noise ratio. Some original multiplexing techniques based on spreading spectrum have been developed to combine the localization and the communication functions inside the same device. This system must be able to work on open area and also in tunnel. The choice of Hyperfrequency front-ends has been done following this important characteristic. The whole system (Transmitter/Receiver) have been simulated in real conditions in order to validate the selected technical choices. Finally, we present some solutions to implement the computing algorithms on a FPGA devices. A mock-up has been realized and the first tests have been carried out on open area. The obtained results show that a range of about 700m could be reached. The proposed multiplexing techniques allow the system to establish a communication with different data rates among (97kb/s, 1. 6Mb/S, 5. 4Mb/s and 11. 27Mb/s)

Les principes de telecommunications actuels reposent sur des transmissions numériques dans lesquelles une source (binaire ou q-aire) délivré des messages a des destinataires. La qualité de la transmission repose sur la corrélation des signaux et se trouve conditionnée par le choix d'une famille de séquences ayant de bonnes propriétés d'autocorrelation (problème de type synchronisation) et d'intercorrelation (accès a un même canal par plusieurs utilisateurs). Les recherches exhaustives (ou semi-exhaustives) étant exclues pour les grandes longueurs, de nombreux travaux ont été réalises pour rechercher de bonnes familles. Les séquences connues ne présentent hélas que des possibilités restreintes en ce qui concerne leurs périodes. L’objet de cette étude est donc d'élargir le choix des périodes utilisables. La première partie de cet ouvrage est consacrée à l'élaboration de nouvelles suites par la mise en présence de la trace et de caractères multiplicatifs. L’association d'objets multiplicatifs et additifs conduit à des propriétés intéressantes et innovantes par rapport aux travaux antérieurs. La deuxième partie est dédiée à l'étude de l'intercorrelation des suites précédentes. Nous donnons des éléments de réponse et concluons par une étude numérique, sélectionnant des familles par un algorithme de recherche de cliques maximales. La dernière partie de ce travail consiste à modifier ou arranger des suites ou familles existantes. Les deux constructions proposées sont l'entrelacement et la multiplication par des caractères additifs
Nowadays, communication systems are based on numerical transmissions, in wich a source delivers messages to recipients. The merits of the transmission depend on correlation of signals and on the choice of a family of sequences with good autocorrelation properties (to allow synchronization) and good crosscorrelation properties no allow several users a simultaneous access to a common channel). Exhaustive studies are impossible for high lengths, so a lot of theoretical studies have been performed to find good families. Unfortunately, there are a lot of lengths for which no known sequences exist. The goal of this work is rims to enlarge the choice of lengths which can be used. The first part of this document is dedicated to new design of sequences by associating trace and multiplicative characters. Tins leads to interesting properties, new in regard to prior research. The second part is devoted to the study of the crosscorrelation of the former sequences. We give some elements of a complete answer and conclude by a numerical study, selecting families by a maximal clique problem algorithm. In the last part of this work- we modify some existing sequences or families. Two constructions are proposed ; interleaving and multiplication by an additive character

Cette thèse s’inscrit dans le cadre des projets eBOSS et DESI. Ces projets utilisent, entreautres, l’absorption Lyman-α (Lyα) afin de sonder la répartition de matière dans l’univers et ainsi mesurer l’échelle des oscillations acoustiques de baryon (BAO). La mesure du rapport de la taille de l’échelle BAO et de la taille de l’horizon acoustique lors du découplage des baryons et des photons permet de contraindre l’expansion de l’univers, et donc les paramètres de l’équation d’état de l’énergie noire. Cette thèse présente le développement de simulations (ou pseudo-données, ou mocks) à partir de champs aléatoires gaussiens (GRF) utilisées afin de tester les analyses BAO des groupes Lyα de eBOSS et DESI. Les GRF permettent de générer un champ de densité δ. A partir de ce champ de densité, les positions des quasars (QSO) sont tirées, puis à partir de chaque quasar, les lignes de visées sont constituées. Le champ de densité δ est interpolé le long de ces lignes de visées. Enfin, à l’aide de l’approximation FGPA (Fluctuating Gunn Peterson Approximation), la densité interpolée est transformée en profondeur optique τ , puis en absorption Lyα. Grâce à un programme développé par la communauté de DESI, un continuum est ajouté aux forêts Lyα afin de créer des spectres de quasars synthétiques. Les mocks présentées dans ce manuscrit fournissent donc un relevé de quasars dont les forêts Lyα présentes dans les spectres possèdent les bonnes fonctions d’auto-corrélation Lyα×Lyα, de corrélation croisée Lyα×QSO, ainsi que d’auto-corrélationQSO×QSO et HCD×HCD (High Column Density systems).L’étude de ces mocks permet de montrer quel’analyse BAO menée sur l’ensemble des données Lyα du relevé eBOSS produit une mesure non biaisée des paramètres BAO αk et α⊥. Par ailleurs, une étude approfondie du modèle utilisé pour ajuster les fonctions de corrélation montre que la forme de la fonction d’auto-corrélation Lyα×Lyα, c’est à dire les mesures du biais bLyα et du paramètre RSD (Redshift Space Distorsions) βLyα, est comprise à environ 20 % près. Les systématiques qui affectent les mesures des paramètres Lyα (bLyα et βLyα) sont issues de deux effets. Le premier effet provient de la matrice de distorsion qui ne capture pas l’intégralité des distorsions produites par l’ajustement du continuum des quasars. Le second effet est lié à la modélisation des HCD. La modélisation de ces absorbeurs denses n’est pas parfaite et affecte la mesure des paramètres Lyα, en particulier le paramètre RSD βLyα. L’analyse de ces mocks permet donc de valider un bon contrôle des systématiques pour les analyses BAO avec le Lyα. Cependant, une meilleure compréhension des mesures des paramètres Lyα est nécessaire afin d’envisager une analyse RSD à l’aide de la combinaison de l’auto-corrélation Lyα×Lyα et de la corrélation croisée Lyα×QSO
This PhD thesis is part of eBOSS and DESI projects. These projects, among other tracers, use the Lyman-α (Lyα) absorption to probe the matter distribution in the universe and measure thebaryon acoustic oscillations (BAO) scale. The measurement of the BAO scale to the sound horizon ratio allows to constrain the universe expansion and so the ΛCDM model, the standard model of cosmology. This thesis presents the development of mock data sets used in order to check the BAO analyses carried out by the Lyα group within the eBOSS and DESI collaborations. These mocks make use of gaussian random fields (GRF). GRF allow to generate a density field δ. From this density field, quasar (QSO) positions are drawn. From each quasar, a line of sight is constructed. Then, the density field δ is interpolated along each line of sight. Finally, the fluctuating Gunn Peterson approximation (FGPA) is used to convert the interpolated density into the optical depth τ , and then into the Lyα absorption. Thanks to a program developed by the DESI community, a continuum is added to each Lyα forest in order to produce quasar synthetic spectra. The mocks presented in the manuscript provide a survey of quasars whose Lyα forests in the quasar spectra have the correct Lyα×Lyα auto-correlation, Lyα×QSO cross-correlation, as well as the correct QSO×QSO and HCD×HCD (High Column Density systems) auto-correlation functions. The study of these mocks shows that the BAO analysis run on the whole Lyα eBOSS data set produces a non-biaised measurement of the BAO parameters αk et α⊥. In addition, the analysis of the model used to fit the correlation functions shows that the shape of the Lyα×Lyα auto-correlation, which is linked to the bias bLyα and redshift space distorsions (RSD) parameter βLyα, are understood up to 80 %. The systematics affecting the measurement of the Lyα parameters (bLyα et βLyα) come from two different effects. The first one originates from thedistortion matrix which does not capture all the distortions produced by the quasar continuum fittingprocedure. The second one is linked to the HCD modelling. The modelling of these strong absorbers is not perfect and affects the measurement of the Lyα parameters, especially the RSD parameter βLyα. Thus, the analysis of these mocks allows to validate the systematic control of the BAO analyses done with the Lyα. However, a better understanding of the measurement of the Lyα parameters is required in order to consider using the Lyα, which means combining the Lyα×Lyα autocorrelation and Lyα×QSO cross-correlation, to do a RSD analysis

Cette thèse porte sur la construction de certaines suites pseudo-aléatoires inspirées par les questions naturelles en théorie des nombres. Nous utilisons les deux principales mesures introduites par A. Sárközy et C. Mauduit, à savoir la mesure de bonne distribution et la mesure de corrélation de l'ordre k pour étudier quelques aspects des tests a priori de ces suites. Grâce à des résultats dus à A. Weil, certains caractères de Dirichlet fournissent une large famille d'exemples de constructions intéressantes. En revanche, l'étude de la distribution des plus grands facteurs ne nous donne pas une estimation suffisamment exploitable. Cependant, on constate numériquement qu'il y a un biais sur certaines classes de facteurs premiers. On discute aussi quelques aspects probabilistes de ces mesures. On présente également une brève histoire sur le thème du hasard. Certains sujets relatifs à la cryptologie sont aussi rappelés dans une annexe
This thesis presents some constructions of pseudo-random sequences inspired by natural questions in number theory. We use two measures introduced by A. Sárközy et C. Mauduit to discuss some aspects of a priori testing of these sequences. They are the well-distribution measure and correlation measure of order k. On the one hand, thanks to a work of A. Weil, some Dirichlet characters give a large family of interesting examples of constructions. On the other hand, our study on a construction based on the distribution of the greatest prime factors do not supply any sufficiently exploitable estimate. However, we observe the bias on some congruence classes of prime factors. We also discuss some probability aspects of both measures. A brief history on the randomness is presented to help better comprehension, as well as some subjects in cryptology which are given in an appendix

En échographie ultrasonore classique, l'extraction de signatures à partir d'échos est basée sur des traitements de déconvolution temporelle ou fréquentielle. La détection basée sur la corrélation nécessite l'utilisation de signaux codés, continus ou discrets. Les signaux discrets fournissent une bonne dynamique et limitent les artéfacts. La résolution est simultanément améliorée dans la cas des séquences pseudo-aléatoires binaires. L'étude des corrélateurs à un bit et multibits est présentée, pour des cibles isolées ou multiples. Les influences du moyennage, du sur-échantillonnage, de la précision de quantification numérique, et de la bande passante du système sont mises en évidence. Une architecture basée sur une approche logicielle et le stockage des signaux donne accès à des techniques de post-traitement numérique. Plusieurs expériences sont présentées, qui mettent en évidence les performances et avantages de la détection par corrélation
In classical ultrasonic echography, the extraction of signatures from echoes is performed using deconvolution processes in time and frequency domains. The detection based on correlation resorts to continuous or coded signals. Discrete signals give good dynamic and limit ghosts. The resolution is jointly improved using pseudorandom binary sequences. The study of one bit and multibits correlators is given for isolated or multiple targets. The influences of averaging, oversampling, quantization and system response bandwith are evidenced. An architecture based on software approach and storage of signals give access to digital post-processing techniques. Several experiments are reported which highlight the performances and advantages of correlation detection

Cette thèse est constituée de deux sections. Dans la première section, nous nous intéressons à un cas particulier de calcul multi-parties : le Problème de La Demande en Mariage, ou calcul équitable du ET logique. Nous proposons un protocole efficace en modifiant la solution du Problème des Millionnaires Socialistes (égalité ou non de deux entiers) apportée par Boudot, Schoenmakers et Traoré. Nous étendons ensuite ce protocole au cas de n joueurs ainsi qu'à d'autre fonctions booléennes. Dans la seconde section, nous revisitons le schéma de Benes (composition de deux schémas nommés "Papillons ") qui permet de construire, à partir de fonctions aléatoires de n bits vers n bits, une fonction pseudo¬aléatoire de Zn bits vers Zn bits. On constate que la preuve de sécurité donnée dans l'article initial de Aiello et Venkatesan n'est pas valide pour toute les attaques à clairs choisis. Nous fournissons une preuve détaillée de la sécurité face aux attaques à clairs choisis adaptatives quand m«Z-(n(l-e», pour tout e>O, où m désigne le nombre de messages choisis
This thesis consists of two sections. Ln the first section, we study a particular case of a multiparty computation: the Marriage ProposaI' s Problem, or more formally the fair computation of the logical AND. We give an efficient protocol b modifying the solution of the Socialist Millionaires' Problem (equality between two integers) from Boudot, Schoenmaker and Traoré. We ex tend our protocol to the case of n players and to other Boolean functions. Ln the second section, we ar interested with the Benes scheme (composition of two schemes called "Butterfly") which gives, from random functions 0 n bits to n bits, a pseudo-random function of Zn bits to Zn bits. We have noticed that the proof of security given in th initial paper of Aiello and Venkatesan is not valid for aIl chosen plaintext attacks. We provide a detailed proof of security against adaptive chosen plaintext attacks when m«Z-(n(l-e», for aIl e>O, where m is the number of chosen messages

Dans cette thèse, nous considérons les générateurs de nombres aléatoires en cryptographie. D'une part, nous avons étudié des générateurs, comme HAVEGE, qui produisent leurs données en se basant sur des événements imprévisibles. D'autre part, nous avons examiné les chiffrements à flots, qui peuvent être vus comme des générateurs de nombre pseudo-aléatoires qui produisent une suite chiffrante à partir d'une courte séquence initiale dépendant de la clé, et du vecteur d'initialisation, l'IV. Nous avons étudié plus particulièrement le chiffrement Dragon, ainsi qu'un modèle utilisant des fonctions aléatoires qui nous a été inspiré par une attaque sur le chiffrement MICKEY. Enfin, nous avons étudié plusieurs aspects des registres à décalages avec retenue (ou FCSR pour "feedback with carry shift register" en anglais) utilisés dans le chiffrement F-FCSR.

Nous étudions mécanismes généraux qui sont à l'origine de vieillissement de dynamiques en environnements aléatoires, connu sous. Le vieillissement s'observe dans le comportement de certaines fonctions de corrélation, qui ne deviennent jamais indépendantes de l'âge du système. Une approche universelle à ce problème fut développée durant les dernières décennies: le comportement des fonctions de corrélation peut être lié à celui du processus d'horloge, qui est le temps total écoulé le long d'une trajectoire de la dynamique.Une approche élégante fut proposée par Gayrard (2010, 2012) pour étudier le processus d'horloge. Celui-ci est vu comme un processus de sommes partielles à incréments corrélés auquel des critères de convergence, dûs à Durett et Resnick (1978) sont appliqués. Cette méthode fut poussée plus avant par Bovier et Gayrard (2013).Nous étendons les méthodes développées par Gayrard (2012) et Bovier et Gayrard (2013), et étudions vieillissement dans divers modèles. Dans la première partie, nous établissons des critères de convergence vers des processus extrémaux pour des graphes finis et improuver résulats obtenus par Ben Arous et Gun (2012) sur le vieillissement extrémal. La deuxième partie traite de dynamiques sur des graphes infinis. Nous donnons des conditions suffisantes sous lesquelles le processus d'horloge sous-jacent converge vers un subordinateur, et établir l'existence de vieillissement normal dans le modèle assymétrique de pièges de Bouchaud sur $Z^d$ pour $dgeq 2$. La troisième partie concerne le modèle de Bouchaud assymétrique lorsque $dgeq 3$ et sa version symétrique lorsque $d=2$. Nous prouvons l'existence d'un régime de sur-vieillissement
We study general mechanisms that lead to aging behavior of dynamics in random environments. Aging is observed in the behavior of correlation functions that never become independent of the age of the system. A universal approach to this problem was developed over the past decades: the behavior correlation functions can be linked to the long-time behavior of the clock process, which is the total time elapsed along the trajectory of the random motion. An elegant approach to studying clock processes was proposed by Gayrard (2010,2012). Here, the clock process is viewed as a partial sum process whose increments are dependent random variables and then convergence criteria, due to Durrett and Resnick (1978), are employed. This method was further developed by Bovier and Gayrard (2013).We extend the methods of Gayrard (2012) and Bovier and Gayrard (2013) and use our methods to study the aging behavior of various models. In the first part we establish criteria for the convergence of clock processes on sequences of finite graphs to extremal processes and improve results on extremal aging obtained by Ben Arous and Gun (2012). The second part deals with dynamics that are defined on infinite graphs. We introduce sufficient conditions for the clock process to converge to a subordinator and establish the existence of a normal aging regime in Bouchaud's asymmetric trap model on $Z^d$, for $dgeq 2$. In the third part of this thesis we consider Bouchaud's asymmetric trap model for $dgeq 3$, and its symmetric version for $d=2$. We prove the existence of an super-aging regime

L’aléatoire est un ingrédient clé en cryptographie. Par exemple, les nombres aléatoires sont utilisés pour générer des clés, pour le chiffrement et pour produire des nonces. Ces nombres sont générés par des générateurs pseudo-aléatoires et des fonctions pseudo-aléatoires dont les constructions sont basées sur des problèmes qui sont supposés difficiles. Dans cette thèse, nous étudions certaines mesures de complexité des fonctions pseudo-aléatoires de Naor-Reingold et Dodis-Yampolskiy et étudions la sécurité de certains générateurs pseudo-aléatoires (le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques) et de certaines signatures à base de couplage basées sur le paradigme d’inversion. Nous montrons que la fonction pseudo-aléatoire de Dodis-Yampolskiy est uniformément distribué et qu’un polynôme multivarié de petit dégré ou de petit poids ne peut pas interpoler les fonctions pseudo-aléatoires de Naor-Reingold et de Dodis-Yampolskiy définies sur un corps fini ou une courbe elliptique. Le contraire serait désastreux car un tel polynôme casserait la sécurité de ces fonctions et des problèmes sur lesquels elles sont basées. Nous montrons aussi que le générateur linéaire congruentiel et le générateur puissance basés sur les courbes elliptiques sont prédictibles si trop de bits sont sortis à chaque itération. Les implémentations pratiques de cryptosystèmes souffrent souvent de fuites critiques d’informations à travers des attaques par canaux cachés. Ceci peut être le cas lors du calcul de l’exponentiation afin de calculer la sortie de la fonction pseudo-aléatoire de Dodis-Yampolskiy et plus généralement le calcul des signatures dans certains schémas de signatures bien connus à base de couplage (signatures de Sakai-Kasahara, Boneh-Boyen et Gentry) basées sur le paradigme d’inversion. Nous présentons des algorithmes (heuristiques) en temps polynomial à base des réseaux qui retrouvent le secret de celui qui signe le message dans ces trois schémas de signatures lorsque plusieurs messages sont signés sous l’hypothèse que des blocs consécutifs de bits des exposants sont connus de l’adversaire
Randomness is a key ingredient in cryptography. For instance, random numbers are used to generate keys, for encryption and to produce nonces. They are generated by pseudo-random generators and pseudorandom functions whose constructions are based on problems which are assumed to be difficult. In this thesis, we study some complexity measures of the Naor-Reingold and Dodis-Yampolskiy pseudorandom functions and study the security of some pseudo-random generators (the linear congruential generator and the power generator on elliptic curves) and some pairing-based signatures based on exponentinversion framework. We show that the Dodis-Yampolskiy pseudo-random functions is uniformly distributed and that a lowdegree or low-weight multivariate polynomial cannot interpolate the Naor-Reingold and Dodis-Yampolskiy pseudo-random functions over finite fields and over elliptic curves. The contrary would be disastrous since it would break the security of these functions and of problems on which they are based. We also show that the linear congruential generator and the power generator on elliptic curves are insecure if too many bits are output at each iteration. Practical implementations of cryptosystems often suffer from critical information leakage through sidechannels. This can be the case when computing the exponentiation in order to compute the output of the Dodis-Yampolskiy pseudo-random function and more generally in well-known pairing-based signatures (Sakai-Kasahara signatures, Boneh-Boyen signatures and Gentry signatures) based on the exponent-inversion framework. We present lattice based polynomial-time (heuristic) algorithms that recover the signer’s secret in the pairing-based signatures when used to sign several messages under the assumption that blocks of consecutive bits of the exponents are known by the attacker

La surveillance de phénomènes physiques à l’aide d’un réseau de capteurs (autonomes mais communicants) est fortement contrainte en consommation énergétique, principalement pour la transmission de données. Dans ce cadre, cette thèse propose des méthodes de traitement du signal permettant de réduire les communications sans compromettre la précision des calculs ultérieurs. La complexité de ces méthodes est réduite, de façon à ne consommer que peu d’énergie supplémentaire. Deux éléments servent à leur synthèse : la compression dès l’acquisition (Acquisition compressive) et la quantification grossière (sur 1 bit). D’abord, on étudie le corrélateur compressé, un estimateur qui permet d’évaluer les fonctions de corrélation, temps de retard et densités spectrales en exploitant directement des signaux compressés. Ses performances sont comparées au corrélateur usuel. Si le signal à traiter possède un support spectral étroit, l’estimateur proposé s’avère sensiblement meilleur que l’usuel. Ensuite, inspirés par les corrélateurs à forte quantification des années 50 et 60, deux nouveaux corrélateurs sont étudiés : le compressé sur 1 bit et le compressé hybride, qui peuvent également surpasser les performances de leurs contreparties non-compressées. Finalement, on montre la pertinence de ces méthodes pour les applications envisagées à travers l’exploitation de données réelles
Monitoring physical phenomena by using a network of sensors (autonomous but interconnected) is highly constrained in energy consumption, mainly for data transmission. In this context, this thesis proposes signal processing tools to reduce communications without compromising computational accuracy in subsequent calculations. The complexity of these methods is reduced, so as to consume only little additional energy. Our two building blocks are compression during signal acquisition (Compressive Sensing) and CoarseQuantization (1 bit). We first study the Compressed Correlator, an estimator which allows for evaluating correlation functions, time-delay, and spectral densities directly from compressed signals. Its performance is compared with the usual correlator. As we show, if the signal of interest has limited frequency content, the proposed estimator significantly outperforms theconventional correlator. Then, inspired by the coarse quantization correlators from the 50s and 60s, two new correlators are studied: The 1-bit Compressed and the Hybrid Compressed, which can also outperform their uncompressed counterparts. Finally, we show the applicability of these methods in the context of interest through the exploitation of real data

Dans cette thèse, nous étudions les propriétés de concentration des fonctions propres du laplacien discret sur des graphes réguliers de degré fixé dont le nombre de sommets tend vers l'infini. Cette étude s'inspire de la théorie de l'ergodicité quantique sur les variétés. Par analogie avec cette dernière, nous développons un calcul pseudo-différentiel sur les arbres réguliers : nous définissons des classes de symboles et des opérateurs associés, et nous prouvons un certain nombre de propriétés de ces classes de symboles et opérateurs. Nous montrons notamment que les opérateurs sont bornés dans L², et nous donnons des formules de l'adjoint et du produit. Nous nous servons ensuite de cette théorie pour montrer un théorème d'ergodicité quantique pour des suites de graphes réguliers dont le nombre de sommets tend vers l'infini. Il s'agit d'un résultat de délocalisation de la plupart des fonctions propres dans la limite des grands graphes réguliers. Les graphes vérifient une hypothèse d'expansion et ne comportent pas trop de cycles courts, deux hypothèses vérifiées presque sûrement par des suites de graphes réguliers aléatoires.

Dans cette thèse, nous étudions la sécurité des primitives cryptographiques avancées contre des adversaires qui se comportent plus près de scénarios réels. Plus précisément, ils peuvent mettre à jour de manière adaptative leur stratégie pendant l'attaque, en fonction des informations précédemment obtenues, à partir de sources externes comme des utilisateurs corrompus. Nous construisons des fonctions pseudo-aléatoires distribuées produisant des valeurs qui paraissent aléatoires, même si l'adversaire peut corrompre de manière adaptative certains serveurs. Un tel système suppose que la clé secrète est partagée entre plusieurs serveurs qui doivent combiner leurs évaluations partielles afin d'obtenir une valeur pseudo-aléatoire. Nous prouvons également la sécurité contre les corruptions adaptatives, dans le modèle de sécurité renforcé basé sur la simulation, pour le chiffrement fonctionnel des produits scalaires. Un tel schéma à clé publique chiffre les vecteurs x et peut émettre plusieurs clés secrètes associées aux vecteurs clés y. Le décrypteur apprend les informations partielles mais rien d'autre. Cette primitive peut calculer des statistiques (par exemple, des sommes pondérées ou des moyennes) sur une base de données, tout en gardant chaque entrée individuelle confidentielle. Nous construisons également une variante étiquetée, dans laquelle chaque entrée de la base de donnée est chiffrée par un client différent, appelé chiffrement fonctionnel multi-client. Enfin, nous fournissons une nouvelle construction de preuve non interactive à divulgation nulle de connaissance, qui convainc un vérificateur de l'appartenance d'un certain élément à un langage NP sans rien divulguer d'autre. De plus, un adversaire qui obtient de nombreuses preuves simulées pour d'éventuelles fausses affirmations ne peut pas produire lui-même une preuve valide d'une fausse affirmation. Cette primitive est utilisée comme élément de base pour les schémas de chiffrement à clé publique avec des propriétés de sécurité avancées
In this thesis, we study the security of advanced cryptographic primitives against adversaries that behave closer to real-life scenarios. Namely, they can adaptively update their strategy during the attack, based on previously obtained information, possible from external sources like corrupted users. We construct Distributed Pseudorandom Functions that still output random-looking values, even when the adversary can adaptively corrupt some servers. Such a system assumes that the secret key is shared among multiple servers that have to combine their partial evaluations in order to obtain a pseudorandom value. We also prove security against adaptive corruptions, in the stronger simulation-based security model, for Inner Product Functional Encryption. Such a public-key scheme encrypts vectors x and can issue multiple secret keys associated to key vectors y. The decryptor learns the partial information but nothing else. This primitive can compute statistics (e.g., weighted sums or means) on a database, while keeping each individual input private. We also construct a labeled variant, wherein each database entry is encrypted by a different client, called Multi-Client Functional Encryption.We finally provide a new construction of Non-Interactive Zero-Knowledge proof, which convinces a verifier of the validity of some NP statement without leaking anything else. In addition, an adversary obtaining many simulated proofs for possibly false statements cannot produce a valid proof of its own for a false statement. This primitive is used as a building-block for public-key encryption schemes with advanced security properties

Dans cette thèse, nous étudions la structure algébrique sous-jacente aux fonctions pseudo-aléatoires basées sur la théorie des nombres. Précisément, nous montrons que le caractère pseudo-aléatoire de fonctions d’une forme particulière est équivalent au fait que ces fonctions vérifient une propriété algébrique simple. Cette caractérisation algébrique s’applique à la plupart des constructions connues et s’étend naturellement aux généralisations des fonctions pseudo-aléatoires, par exemple aux fonctions pseudo-aléatoires sûres contre les attaques par clés liées, multilinéaires ou supportant l’agrégation. Cette caractérisation repose sur une famille d’hypothèses MDDH, qui contient en particulier différentes hypothèses classiques, comme DDH, DLin, ou k-Lin. Ainsi, en choisissant les paramètres des constructions selon, ce résultat permet de construire des fonctions pseudo-aléatoires (ou leurs généralisations) prouvées sûres sous ces différentes hypothèses. Enfin, nous étudions également plus précisément le cas de la sécurité contre les attaques par clés liées. D’une part, nous corrigeons et étendons la transformation proposée par Bellare et Cash pour ensuite construire de nouvelles fonctions pseudo-aléatoires sûres contre des attaques par clés liées plus puissantes. D’autre part, nous construisons la première fonction pseudo-aléatoire prouvée sûre contre des attaques par XOR. Cette construction repose sur l’existence d’une forme faible d’applications multilinéaires
In this thesis, we study the algebraic structure underlying number-theoretic pseudorandom functions. Specifically, we define an algebraic framework that translates the pseudorandomness of a particular form of functions into a simple algebraic property. The resulting generic framework encompasses most of existing constructions and naturally extends to related primitives, such as related-key secure, aggregate, and multilinear pseudorandom functions. This framework holds under a family of MDDH assumptions, that contains especially different classical assumptions, such as DDH, DLin, or k-Lin. Therefore, setting accordingly the parameters in the constructions, our framework can be used to construct secure pseudorandom functions (or related primitives) whose security holds under these assumptions. Finally, we also study more specifically the case of related-key security. On the one hand, we propose a fix and some extensions to the Bellare-Cash framework and then build pseudorandom functions secure against larger classes of attacks. On the other hand, we construct the first pseudorandom function provably secure against XOR attacks. The latter construction relies on the existence of a weak form of multilinear maps

Cette thèse se situe à l'intersection des mathématiques et de l'informatique théorique. Une suite pseudo-aléatoire, bien qu'engendrée par un algorithme déterministe, possède un comportement proche de celui d'une suite aléatoire. Nous nous intéressons à différentes mesures de complexité pour les suites pseudo-aléatoires. D'un autre côté, les suites automatiques sont des suites non aléatoires. Cependant, certaines sous-suites des suites automatiques, comme les sous-suites polynomiales, sont bien plus aléatoires. Dans la première partie de cette thèse, nous établissons une borne inférieure de la complexité d'ordre maximal de la suite de Thue-Morse et des suites de motifs le long de tout polynôme unitaire, ce qui répond à une question de Sun et Winterhof (2019). Nous étudions ensuite le système de numération de Zeckendorf. Sa fonction somme des chiffres est une suite morphique non-automatique. Nous établissons une borne inférieure de la complexité d'ordre maximal de la suite de Fibonacci-Thue-Morse le long de tout polynôme unitaire. Nous calculons la complexité d'ordre maximal à l'aide du Graphe Acyclique Orienté de Mot (DAWG). Dans la deuxième partie de cette thèse, nous nous intéressons à la somme des chiffres binaire des carrés parfaits. Nous reprenons les travaux de Hare, Laishram et Stoll (2011) qui étudient le problème de déterminer les entiers impairs dont le poids de Hamming est égal à celui de son carré. Nous résolvons ce problème pour la majorité des cas restants et introduisons de nouveaux outils potentiellement utiles à la résolution complète du problème. Nos méthodes combinent la théorie des nombres, la combinatoire des mots et l'informatique. La dernière partie de cette thèse porte sur les corrélations de la suite de Rudin-Shapiro. La corrélation d'ordre 2 est historiquement très étudiée pour cette suite car elle possède un comportement aléatoire bien que la suite soit déterministe. Cependant, des corrélations d'ordre supérieur de cette suite ne possèdent plus ce comportement aléatoire. Dans la lignée des travaux de Aloui, Mauduit et Mkaouar (2021) sur les corrélations de la suite de Thue-Morse le long des nombres premiers, nous établissons un résultat sur les corrélations de la suite de Rudin-Shapiro le long des nombres premiers
The topic of this thesis lies at the interface between mathematics and computer science. A pseudorandom sequence is a sequence generated by a deterministic algorithm that has properties similar to those of a random sequence. We are interested in various complexity measures for these pseudorandom sequences. Automatic and morphic sequences are not random or pseudorandom, but certain subsequences of these sequences, such as polynomial subsequences for instance, are more random than the original sequences. In the first part of the thesis, we establish a lower bound on the maximal order complexity of the Thue-Morse sequence and related sequences along polynomial subsequences. This answers a question of Sun and Winterhof (2019). We then study the problem in the Zeckendorf numeration system. Its sum of digits function is a morphic non-automatic sequence. We establish a lower bound on the maximal order complexity of the Fibonacci-Thue-Morse sequence along unitary polynomials. We calculate the complexity with the help of the Directed Acyclic Word Graph (DAWG). In the second part, we are interested in the binary sum of digits of squares. We take up the work of Hare, Laishram and Stoll (2011) who studied the problem to determine the odd integers whose Hamming weight is the same as the one of their square. We solve the problem in the majority of the remaining cases, and introduce new tools that might be helpful to completely solve the problem. Our methods range from number theory, combinatorics on words to implementations in the area of computer science. In the third part of the thesis, we study the correlations of the Rudin-Shapiro sequence. The correlations of order 2 are well understood for this sequence, the behavior of this sequence is rather random whereas the original sequence is completely deterministic. The correlation of higher orders of this sequence do not show this random behavior. Aloui, Mauduit and Mkaouar (2021) studied the correlation of the Thue-Morse sequence along prime numbers. We provide a result on the correlation of the Rudin-Shapiro sequence along prime numbers

Cette thèse étudie les propriétés de l'opérateur de propagation des ondes ultrasonores en milieu aléatoire. Le dispositif expérimental consiste en un réseau multi-éléments placé en vis-à-vis d'un milieu désordonné. L'opérateur de propagation est donné par la matrice des réponses inter-éléments mesurées entre chaque couple de transducteurs. En s'appuyant sur la théorie des matrices aléatoires, le comportement statistique de cet opérateur a été étudié en régime de diffusion simple et multiple. Une cohérence déterministe des signaux est ainsi mise en évidence en régime de diffusion simple, cohérence qui disparaît dès que la diffusion multiple prédomine. Cette différence de comportement a permis la mise au point d'un radar intelligent séparant les échos simplement et multiplement diffusés. On peut ainsi extraire l'écho direct d'une cible échogène enfouie dans un milieu hautement diffusant, bien que ce dernier soit source de diffusion multiple et d'aberration. Une deuxième approche consiste, au contraire, à extraire une contribution de diffusion multiple noyée dans une contribution de diffusion simple largement prédominante. L'étude de l'intensité multiplement diffusée permet de mesurer des paramètres de transport (p.ex. la constante de diffusion D) caractérisant la propagation de l'onde multiplement diffusée. Un passage en champ lointain (ondes planes) permet d'obtenir une mesure fiable de D en étudiant le cône de rétrodiffusion cohérente. Un passage en champ proche, via l'utilisation de faisceaux gaussiens, permet d'effectuer des mesures locales de D en étudiant la croissance du halo diffusif. Cette approche a été appliquée au cas de l'os trabéculaire humain autour de 3 MHz.