Academic literature on the topic 'Fonctions de corrélation pseudo-aléatoires'

International audience In this article, we investigate the asymptotic occurrence rates of specific subwords in any infinite binary word. We prove that the asymptotic occurrence rate for the subwords is upper- and lower-bounded in the same way for every infinite binary word, in terms of the asymptotic occurrence rate of the zeros. We also show that both of the bounds are best-possible by constructing, for each bound, a concrete infinite binary word such that the bound is reached. Moreover, we apply the result to analyses of recently-proposed pseudorandom number generators that are based on integer-valued variants of logistic maps. Dans cet article, nous étudions les fréquences asymptotiques d’occurrence de suites spécifiques dans tout mot binaire infini. Nous prouvons que la fréquence asymptotique d’occurrence pour ces suites est borné supérieurement et inférieurement de la même façon pour chaque mot binaire infini, en termes des fréquences asymptotiques d’occurrence de zéros. Nous montrons aussi que les deux limites sont les meilleures possibles en construisant concrètement, pour chaque limite, un mot binaire infini tel que la borne est atteinte à la limite. De plus, nous appliquons ce résultat à des analyses de générateurs de nombres pseudo-aléatoires proposés récemment qui sont basés sur des variantes des fonctions logistiques à valeurs entières.

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<br>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)<br>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<br>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<br>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<br>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<br>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&gt;O, où m désigne le nombre de messages choisis<br>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&gt;O, where m is the number of chosen messages