Dynamic Programming is an optimization technique used in computer science and mathematics. Introduced in the 1950s, it has been applied to many classic combinatorial optimization problems, such as the Shortest Path Problem, the Knapsack Problem, and the Traveling Salesman Problem, with varying degrees of practical success. In this thesis, we present two applications of dynamic programming to optimization problems. The first application is as a method to compute the Branch-Cut-and-Price (BCP) family of lower bounds for the Traveling Salesman Problem (TSP), and several vehicle routing problems that generalize it. We then prove that the BCP family provides a set of lower bounds that is at least as strong as the Approximate Linear Program (ALP) family of lower bounds for the TSP. The second application is a novel dynamic programming model used to determine the placement of cuts for a particular form of skull surgery called Cranial Vault Remodeling.

In this thesis, we provide a summary of fully homomorphic encryption, and in particular, look at the BGV encryption scheme by Brakerski, Gentry, and Vaikuntanathan; as well the DGHV encryption scheme by van Dijk, Gentry, Halevi, and Vaikuntanathan. We explain the mechanisms developed by Gentry in his breakthrough work, and show examples of how they are used. While looking at the BGV encryption scheme, we make improvements to the underlying lemmas dealing with modulus switching and noise management, and show that the lemmas as currently stated are false. We then examine a lower bound on the hardness of the Learning With Errors lattice problem, and use this to develop specific parameters for the BGV encryption scheme at a variety of security levels. We then study the DGHV encryption scheme, and show how the somewhat homomorphic encryption scheme can be implemented as both a fully homomorphic encryption scheme with bootstrapping, as well as a leveled fully homomorphic encryption scheme using the techniques from the BGV encryption scheme. We then extend the parameters from the optimized version of this scheme to higher security levels, and describe a more straightforward way of arriving at these parameters.

We introduce methods for dealing with linear programming (LP) problems with uncertain data, using the notion of weighted analytic centers. Our methods are based on high interaction with the decision maker (DM) and try to find solutions which satisfy most of his/her important criteria/goals. Starting with the drawbacks of different methods for dealing with uncertainty in LP, we explain how our methods improve most of them. We prove that, besides many practical advantages, our approach is theoretically as strong as robust optimization. Interactive cutting-plane algorithms are developed for concave and quasi-concave utility functions. We present some probabilistic bounds for feasibility and evaluate our approach by means of computational experiments.

The k-core of a graph is its maximal subgraph with minimum degree at least k. The study of k-cores in random graphs was initiated by Bollobás in 1984 in connection to k-connected subgraphs of random graphs. Subsequently, k-cores and their properties have been extensively investigated in random graphs and hypergraphs, with the determination of the threshold for the emergence of a giant k-core, due to Pittel, Spencer and Wormald, as one of the most prominent results. In this thesis, we obtain an asymptotic formula for the number of 2-connected graphs, as well as 2-edge-connected graphs, with given number of vertices and edges in the sparse range by exploiting properties of random 2-cores. Our results essentially cover the whole range for which asymptotic formulae were not described before. This is joint work with G. Kemkes and N. Wormald. By defining and analysing a core-type structure for uniform hypergraphs, we obtain an asymptotic formula for the number of connected 3-uniform hypergraphs with given number of vertices and edges in a sparse range. This is joint work with N. Wormald. We also examine robustness aspects of k-cores of random graphs. More specifically, we investigate the effect that the deletion of a random edge has in the k-core as follows: we delete a random edge from the k-core, obtain the k-core of the resulting graph, and compare its order with the original k-core. For this investigation we obtain results for the giant k-core for Erdős-Rényi random graphs as well as for random graphs with minimum degree at least k and given number of vertices and edges.

This thesis investigates three areas of the theory of graph homomorphisms: cores of graphs, the homomorphism order, and quantum homomorphisms. A core of a graph X is a vertex minimal subgraph to which X admits a homomorphism. Hahn and Tardif have shown that, for vertex transitive graphs, the size of the core must divide the size of the graph. This motivates the following question: when can the vertex set of a vertex transitive graph be partitioned into sets which each induce a copy of its core? We show that normal Cayley graphs and vertex transitive graphs with cores half their size always admit such partitions. We also show that the vertex sets of vertex transitive graphs with cores less than half their size do not, in general, have such partitions. Next we examine the restriction of the homomorphism order of graphs to line graphs. Our main focus is in comparing this restriction to the whole order. The primary tool we use in our investigation is that, as a consequence of Vizing's theorem, this partial order can be partitioned into intervals which can then be studied independently. We denote the line graph of X by L(X). We show that for all n ≥ 2, for any line graph Y strictly greater than the complete graph Kₙ, there exists a line graph X sitting strictly between Kₙ and Y. In contrast, we prove that there does not exist any connected line graph which sits strictly between L(Kₙ) and Kₙ, for n odd. We refer to this property as being ``n-maximal", and we show that any such line graph must be a core and the line graph of a regular graph of degree n. Finally, we introduce quantum homomorphisms as a generalization of, and framework for, quantum colorings. Using quantum homomorphisms, we are able to define several other quantum parameters in addition to the previously defined quantum chromatic number. We also define two other parameters, projective rank and projective packing number, which satisfy a reciprocal relationship similar to that of fractional chromatic number and independence number, and are closely related to quantum homomorphisms. Using the projective packing number, we show that there exists a quantum homomorphism from X to Y if and only if the quantum independence number of a certain product graph achieves |V(X)|. This parallels a well known classical result, and allows us to construct examples of graphs whose independence and quantum independence numbers differ. Most importantly, we show that if there exists a quantum homomorphism from a graph X to a graph Y, then ϑ̄(X) ≤ ϑ̄(Y), where ϑ̄ denotes the Lovász theta function of the complement. We prove similar monotonicity results for projective rank and the projective packing number of the complement, as well as for two variants of ϑ̄. These immediately imply that all of these parameters lie between the quantum clique and quantum chromatic numbers, in particular yielding a quantum analog of the well known ``sandwich theorem". We also briefly investigate the quantum homomorphism order of graphs.

Bilinear pairings on elliptic curves have many cryptographic applications such as identity based encryption, one-round three-party key agreement protocols, and short signature schemes. The elliptic curves which are suitable for pairing-based cryptography are called pairing friendly curves. The prime-order pairing friendly curves with embedding degrees k=3,4 and 6 were characterized by Miyaji, Nakabayashi and Takano. We study this characterization of MNT curves in details. We present explicit algorithms to obtain suitable curve parameters and to construct the corresponding elliptic curves. We also give a heuristic lower bound for the expected number of isogeny classes of MNT curves. Moreover, the related theoretical findings are compared with our experimental results.

In this thesis we consider some network design games that arise from common network design problems. A network design game involves multiple players who control nodes in a network, each of which has a personal interest in seeing their nodes connected in some manner. To this end, the players will submit bids to a mechanism whose task will be to select which of the players to connect, how to connect their nodes, and how much to charge each player for the connection. We rely on many fundamental results from mechanism design (from [8], [9] & [5]) in this thesis and focus our efforts on designing and analyzing cost-sharing methods. That is, for a given set of players and their connection requirements, our algorithms compute a solution that satisfies all the players’ requirements and calculates ’fair’ prices to charge each of them for the connection. Our cost-sharing methods use a primal-dual framework developed by Agrawal, Klein and Ravi in [1] and generalized by Goemans &Williamson in [3]. We modify the algorithms by using the concept of death-time introduced by K¨onemann, Leonardi & Sch¨afer in [6]. Our main result is a 2-budget balanced and cross-monotonic cost sharing method for the downwards monotone set cover game, which arises naturally from any downwards monotone 0, 1-function. We have also designed a 2-budget balanced and cross-monotonic cost sharing method for two versions of the edge cover game arising from the edge cover problem. These games are special cases of the downwards monotone set cover game. By a result by Immorlica, Mahdian & Mirrokni in [4] our result is best possible for the edge cover game. We also designed a cross-monotonic cost sharing method for a network design game we call the Even Parity Connection game arising from the T-Join problem that generalizes proper cut requirement functions. We can show our algorithm returns cost shares that recover at least half the cost of the solution. We conjecture that our cost sharing method for the even parity connection game is competitive and thus 2-budget balance.

Key establishment is the process whereby two or more parties derive a shared secret, typically used for subsequent confidential communication. However, identifying the exact security requirements for key establishment protocols is a non-trivial task. This thesis compares, extends and merges existing security definitions and models for key establishment protocols. The primary focus is on two-party key agreement schemes in the public-key setting. On one hand new protocols are proposed and analyzed in the existing Canetti-Krawzcyk model. On the other hand the thesis develops a security model and novel definition that capture the essential security attributes of the standardized Unified Model key agreement protocol. These analyses lead to the development of a new security model and related definitions that combine and extend the Canetti-Krawzcyk pre- and post- specified peer models in terms of provided security assurances. The thesis also provides a complete analysis of a one-pass key establishment scheme. There are security goals that no one-pass key establishment scheme can achieve, and hence the two-pass security models and definitions need to be adapted for one-pass protocols. The analysis provided here includes the description of the required modification to the underlying security model. Finally, a complete security argument meeting these altered conditions is presented as evidence supporting the security of the one-pass scheme. Lastly, validation and reusing short lived key pairs are related to efficiency, which is a major objective in practice. The thesis considers the formal implication of omitting validation steps and reusing short lived key pairs. The conclusions reached support the generally accepted cryptographic conventions that incoming messages should not be blindly trusted and extra care should be taken when key pairs are reused.

We propose a formal model for non-interactive message authentication protocols (NIMAPs) using two channels and analyze all the attacks that can occur in this model. Further, we introduce the notion of hybrid-collision resistant (HCR) hash functions. This leads to a new proposal for a NIMAP based on HCR hash functions. This protocol is as efficient as the best previous NIMAP while having a very simple structure and not requiring any long strings to be authenticated ahead of time. We investigate interactive message authentication protocols (IMAPs) and propose a new IMAP, based on the existence of interactive-collision resistant (ICR) hash functions, a new notion of hash function security. The efficient and easy-to-use structure of our IMAP makes it very practical in real world ad hoc network scenarios. We also look at message recognition protocols (MRPs) and prove that there is a one-to-one correspondence between non-interactive MRPs and digital signature schemes with message recovery. Further, we look at an existing recognition protocol and point out its inability to recover in case of a specific adversarial disruption. We improve this protocol by suggesting a variant which is equipped with a resynchronization process. Moreover, another variant of the protocol is proposed which self-recovers in case of an intrusion. Finally, we propose a new design for message recognition in ad hoc networks which does not make use of hash chains. This new design uses random passwords that are being refreshed in each session, as opposed to precomputed elements of a hash chain.

The main goal of cryptography is to enable secure communication over a public channel; often a secret shared among the communicating parties is used to achieve this. The process by which these parties agree on such a shared secret is called key agreement. In this thesis, we focus on two-party key agreement protocols in the public-key setting and study the various methods used to establish and validate public keys. We pay particular attention to certificateless key agreement schemes and attempt to formalize a relevant notion of security. To that end, we give a possible extension of the existing extended Canetti-Krawzcyk security model applicable to the certificateless setting. We observe that none of the certificateless protocols we have seen in the literature are secure in this model; it is an open question whether such schemes exist. We analyze several published certificateless key agreement protocols, demonstrating the existence of key compromise impersonation attacks and even a man-in-the-middle attack in one case, contrary to the claims of the authors. We also briefly describe weaknesses exhibited by these protocols in the context of our suggested security model.