No description available.

No description available.

No description available.

Providing a security proof is always an important issue in the process of designing a cryptographic scheme or protocol. We often show the security of a cryptosystem via ¡§problem reduction.¡¨ In this thesis, lots of emphasis was put on the review of techniques for proving the security of cryptosystems. These techniques consist of Random Oracle Model and Forking Lemma. We also introduced some well-known cryptographic schemes which can be proved secure using these techniques. Then we offered a security proof of a blind signature scheme based on the one proposed by Fan. In the end, we made a comparison between our proof and the proof of another blind signature scheme provided by David Pointcheval and Jacques Stern. Some arguments and discussions about using the Random Oracle Model to prove the security of a cryptosystem were also included.

No description available.

Dans le cadre des théories stables, il a été prouvé qu'une courbe pseudolinéaire était toujours, spécifiquement, linéaire (ce qui correspond dans ce cadre également à localement modulaire): on peut alors caractériser la géométrie de l'ensemble associé, qui est soit projective (avec le type associé à la courbe non-trivial et modulaire), soit affine (quand le type est non-modulaire) sur un corps gauche; lorsque le type associé est trivial, la géométrie est dégénérée. Cela nous permet donc de déduire de la simple pseudolinéarité d'un type la structure de l'ensemble sous-jacent: cette thèse étend ce résultat au cadre des théories simples, ce qui nous permettra à nouveau de détermé de la théorie), mais en se restreignant au cas où k < 4 / In the context of stable theories, it has been proven that a plane curve which is pseudolinear must be linear; it is then possible to deduce the geometry of the associated set, which is either projective (when the type associated to the plane curve is non-trivial and modular), or affine (when the type is non-modular) on a division ring; if the associated type is trivial, the geometry is degenerate. This means we can infer, from a type's pseudolinearity, the structure of the underlying set; this thesis extends this result to the context of simple theories, allowing us to determine the set's geometry (with several differences to account for the fact that the theory is simple and not stable) if we restrict ourselves to k < 4

Software forking---creating a variant product by copying and modifying an existing project---is often considered an ad hoc, low cost alternative to principled product line development. To maintain forked projects, developers need to manually port existing features or bug-fixes from one project to another. Such manual porting is not only tedious but also error-prone. When the contexts of the ported code vary, developers often have to adapt the ported code to fit its surroundings. Faulty adaptations or inconsistent updates of the ported code could potentially introduce subtle inconsistencies in the codebase. To build a deeper understanding to cross-system porting and porting related errors, this dissertation investigates: (1) How can we identify ported code from software version histories? (2) What is the overhead of cross-system porting required to maintain forked projects? (3) What is the extent and characteristics of porting errors that occur in practice? and (4) How can we detect and characterize potential porting errors? As a first step towards assessing the overhead of cross-system porting, we implement REPERTOIRE, a tool to analyze repeated work of cross-system porting across peer projects. REPERTOIRE can detect ported edits between program patches with high accuracy of 94% precision and 84% recall. Using REPERTOIRE, we study the temporal, spatial, and developer dimensions of cross-system porting using 18 years of parallel evolution history of the BSD product family. Our study finds that cross-system porting happens periodically and the porting rate does not necessarily decrease over time. The upkeep work of porting changes from peer projects is significant and currently, porting practice seems to heavily depend on developers doing their porting job on time. Analyzing version histories of Linux and FreeBSD, we derive five categories of porting errors, including incorrect control- and data-flow, code redundancy, and inconsistent identifier and token renamings. Leveraging this categorization, we design a static control- and data-dependence analysis technique, SPA, to detect and characterize porting inconsistencies. SPA detects porting inconsistencies with 65% to 73% precision and 90% recall, and identify inconsistency types with 58% to 63% precision and 92% recall on average. In a comparison with two existing error detection tools, SPA outperforms them with 14% to 17% better precision. / text

In 2004, Christakis and colleagues published findings that he and others used to argue for a link between early childhood television exposure and later attention problems, a claim that continues to be frequently promoted by the popular media. Using the same National Longitudinal Survey of Youth 1979 data set (N = 2,108), we conducted two multiverse analyses to examine whether the finding reported by Christakis and colleagues was robust to different analytic choices. We evaluated 848 models, including logistic regression models, linear regression models, and two forms of propensity-score analysis. If the claim were true, we would expect most of the justifiable analyses to produce significant results in the predicted direction. However, only 166 models (19.6%) yielded a statistically significant relationship, and most of these employed questionable analytic choices. We concluded that these data do not provide compelling evidence of a harmful effect of TV exposure on attention.

Cette thèse est consacrée à l’étude d’expansions de certaines structures algébriques et leur place dans la classification modèle-théorique des structures, initiée par Shelah. La première partie aborde de manière abstraite l’expansion d’une théorie par un prédicat aléatoire –ou générique– pour une sous-structure modèle d’un réduit de la théorie. Nous éla- borons un critère pour l’existence d’une telle expansion, qui est vérifié pour certaines théories de structures algébriques. En particulier, nous montrons l’existence de sous-groupes additifs génériques pour certaines théories de corps, ainsi que de sous-groupes multiplicatifs génériques pour les corps algébriquement clos en toute caractéristique. Nous étudions aussi la conservation de diverses notions de néostabilité, en particulier nous montrons que cette expansion préserve la propriété NSOP 1 , mais en général ne préserve pas la simplicité. Nous produisons par cette construction de nouveaux exemples de structures NSOP 1 non simples, et faisons une étude toute particulière de l’une d’entre elles : l’expansion d’un corps algébriquement clos de caractéristique positive par un sous-groupe additif générique. La deuxième partie étudie les expansions du groupe des entiers par des valuations p-adiques. Nous montrons l’élimination des quantificateurs dans un langage naturel et calculons le dp-rang d’une telle expansion : il est égal au nombre de valuations considérées. L’expansion du groupe des entiers par une seule valuation p-adique est donc une nouvelle expansion dp-minimale du groupe des entiers. Enfin, nous montrons que cette dernière n’admet pas de structures intermédiaires : tout ensemble définissable dans l’expansion est soit définissable dans le groupe des entiers, soit capable de “reconstruire” la valuation en utilisant seulement la structure additive / This thesis is concerned with the expansions of some algebraic structures and their fit in Shelah’s classification landscape. The first part deals with the expansion of a theory by a random –or generic– predicate for a substructure model of a reduct of the theory. We describe a setup allowing such an expansion to exist, which is suitable for several algebraic structures. In particular, we obtain the existence of additive generic subgroups of some theories of fields and multiplicative generic subgroups of algebraically closed fields in all characteristic. We also study the preservation of certain neostability notions, for instance, the NSOP 1 property is preserved but the simplicity is not in general. Thus, this construction produces new examples of NSOP 1 not simple theories, and we study in depth a particular example: the expansion of an algebraically closed field of positive characteristic by a generic additive subgroup. The second part studies expansions of the groups of integers by p-adic valuations. We prove quantifier elimination in a natural language and compute the dp-rank of these expansions: it equals the number of distinct p-adic valuations considered. Thus, the expansion of the integers by one p-adic valuation is a new dp-minimal expansion of the group of integers. Finally, we prove that the latter expansion does not admit intermediate structures: any definable set in the expansion is either definable in the group structure or is able to "reconstruct" the valuation using only the group operation

Aquesta tesi té tres objectius. En primer lloc, estudiem generalitzacions de la jerarquia no ample relatives a una família de tipus parcials. Aquestes jerarquies en permeten classificar la complexitat del “forking” respecte a una família de tipus parcials. Si considerem la família de tipus algebraics, aquestes generalitzacions corresponen a la jerarquia ordinària, on el primer i el segon nivell corresponen a one-basedness i a CM-trivialitat, respectivament. Fixada la família de tipus regulars “no one-based”, el primer nivell d'una d'aquestes possibles jerarquies no ample ens diu que el tipus de la base canònica sobre una realització és analitzable en la família. Demostrem que tota teoria simple amb suficients tipus regulars pertany al primer nivell de la jerarquia dèbil relativa a la família de tipus regulars no one-based. Aquest resultat generalitza una versió dèbil de la “Canonical Base Property” estudiada per Chatzidakis i Pillay. En segon lloc, discutim problemes d'eliminació de hiperimaginaris assumint que la teoria és CM-trivial, en tal cas la independència del “forking” té un bon comportament. Més concretament, demostrem que tota teoria simple CM-trivial elimina els hiperimaginaris si elimina els hiperimaginaris finitaris. En particular, tota teoria petita simple CM-trivial elimina els hiperimaginaris. Cal remarcar que totes les teories omega-categòriques simples que es coneixen són CM-trivials; en particular, aquelles teories obtingudes mitjançant una construcció de Hrushovski. Finalment, tractem problemes de classificació en les teories simples. Estudiem la classe de les teories simples baixes; classe que inclou les teories estables i les teories supersimples de D-rang finit. Demostrem que les teories simples amb pes finit acotat també pertanyen a aquesta classe. A més, provem que tota teoria omega-categòrica simple CM-trivial és baixa. Aquest darrer fet resol parcialment una pregunta formulada per Casanovas i Wagner. / The development of first-order stable theories required two crucial abstract notions: forking independence, and the related notion of canonical base. Forking independence generalizes the linear independence in vector spaces and the algebraic independence in algebraically closed fields. On the other hand, the concept of canonical base generalizes the field of definition of an algebraic variety. The general theory of independence adapted to simple theories, a class of first-order theories which includes all stable theories and other interesting examples such as algebraically closed fields with an automorphism and the random graph. Nevertheless, in order to obtain canonical bases for simple theories, the model-theoretic development of hyperimaginaries --equivalence classes of arbitrary tuple modulo a type-definable (without parameters) equivalence relation-- was required. In the present thesis we deal with topics around the geometry of forking in simple theories. Our first goal is to study generalizations of the non ample hierarchy which will code the complexity of forking with respect to a family of partial types. We introduce two hierarchies: the non (weak) ample hierarchy with respect to a fixed family of partial types. If we work with respect to the family of bounded types, these generalizations correspond to the ordinary non ample hierarchy. Recall that in the ordinary non ample hierarchy the first and the second level correspond to one-basedness and CM-triviality, respectively. The first level of the non weak ample hierarchy with respect to some fixed family of partial types states that the type of the canonical base over a realization is analysable in the family. Considering the family of regular non one-based types, the first level of the non weak ample hierarchy corresponds to the weak version of the Canonical Base Property studied by Chatzidakis and Pillay. We generalize Chatzidakis' result showing that in any simple theory with enough regular types, the canonical base of a type over a realization is analysable in the family of regular non one-based types. We hope that this result can be useful for the applications; for instance, the Canonical Base Property plays an essential role in the proof of Mordell-Lang for function fields in characteristic zero and Manin-Mumford due to Hrushovski. Our second aim is to use combinatorial properties of forking independence to solve elimination of hyperimaginaries problems. For this we assume the theory to be simple and CM-trivial. This implies that the forking independence is well-behaved. Our goal is to prove that any simple CM-trivial theory which eliminates finitary hyperimaginaries --hyperimaginaries which are definable over a finite tuple-- eliminates all hyperimaginaries. Using a result due to Kim, small simple CM-trivial theories eliminate hyperimaginaries. It is worth mentioning that all currently known omega-categorical simple theories are CM-trivial, even those obtained by an ab initio Hrushovski construction. To conclude, we study a classification problem inside simple theories. We study the class of simple low theories, which includes all stable theories and supersimple theories of finite D-rank. In addition, we prove that it also includes the class of simple theories of bounded finite weight. Moreover, we partially solve a question posed by Casanovas and Wagner: Are all omega-categorical simple theories low? We solve affirmatively this question under the assumption of CM-triviality. In fact, our proof exemplifies that the geometry of forking independence in a possible counterexample cannot come from finite sets.