No description available.

<p>In this thesis, we address two applications of threshold cryptography — designing information escrows and key-distribution in cryptocurrency systems. We design escrow mechanisms in two-party and multi-party scenarios such that any unauthorized revelation of<br> data results in the loss of cryptocurrency by the dishonest party. Later, we discuss user mental models in adopting cryptocurrency wallets and propose a protocol to efficiently provide cryptographic keys to the users in large-user systems. An information escrow refers to users storing their data at a custodian such that it can be revealed later. In the case of unauthorized leakage of this data by the custodian (receiver of data), taking legal actions is expensive, time consuming and also difficult owing to difficulty in establishing the responsibility. We address this by automatically penalizing the custodian through the loss of cryptocurrency in case of leakage. Initially, we consider a two party scenario where a sender forwards multimedia data to a receiver; we propose the Pepal protocol<br> where any total or partial leakage of data penalizes the receiver. To avoid single point of failure at the receiver in a two-party system, we extend the protocol to a multi-party system where a group of agents offer the escrow as a service. However, this introduces a collusion scenario among the rational agents leading to premature and undetectable unlocking of the data. Addressing this, we propose a collusion-deterrent escrow (CDE) protocol where any collusion among the agents is penalized. We show that the provably secure protocol deters collusion in game-theoretic terms by dis-incentivising it among the rational agents. In the second part of this work, we investigate the mental models of cryptocurrency wallet users in choosing single-device or multi-device wallets along with their preferences. We investigate the user-preferred default (threshold) settings for the key distribution in the wallets. We then propose the D-KODE protocol, an efficient key-generation mechanism for<br> cryptocurrency systems where either the payee or payer may not have the cryptographic setup but wish to transact. The protocol utilizes a practical black-box secret sharing scheme along with a distributed almost key-homomorphic PRF to achieve the threshold key distribution.</p>

As Machine Learning (ML) algorithms are deployed to solve a wide variety of tasks in today’s world, data poisoning attack poses a significant threat to ML applications. Although numerous defence algorithms against data poisoning attack have been proposed and shown to be effective, most defence algorithms are analyzed under the assumption of fixed attack strategies, without accounting for the strategic interactions between the attacker and the defender. In this work, we perform game theoretic analysis of defence algorithms against data poisoning attacks on Machine Learning. We study the defence strategy as a competitive game between the defender and the adversary and analyze the game characteristics for several defence algorithms. We propose a game model for the poisoning attack scenario, and prove the characteristics of the Nash Equilibrium (NE) defence strategy for all distance-based defence algorithms. Based on the NE characteristics, we develop an efficient algorithm to approximate for the NE defence strategy. Using fixed attack strategies as the benchmark, we then experimentally evaluate the impact of strategic interactions in the game model. Our approach does not only provide insights about the effectiveness of the analyzed algorithms under optimal poisoning attacks, but also serves as a method for the modellers to determine capable defence algorithms and optimal strategies to employ on their ML models. / Thesis / Master of Science (MSc) / As Machine Learning (ML) algorithms are deployed to solve a wide variety of tasks in today’s world, data poisoning attack poses a significant threat to ML applications. In this work, we study the defence against poisoning attack scenario as a competitive game between the defender and the adversary and analyze the game characteristics for several defence algorithms. Our goal is to identify the optimal defence strategy against poisoning attacks, even when the adversary responds optimally to the defence strategy. We propose a game model for the poisoning attack scenario, and develop an efficient algorithm to approximate for the Nash Equilibrium defence strategy. Our approach does not only provide insights about the effectiveness of the analyzed algorithms under optimal poisoning attacks, but also serves as a method for the modellers to determine capable defence algorithms and optimal strategies to employ on their ML models.

No description available.

Opportunistic spectrum access has become a high priority research area in the past few years. The motivation behind this actively researched area is the fact that the limited spectrum available is currently being utilized in an inefficient way. The complete wireless spectrum is assigned and reserved, but not necessarily being used. At the same time, the demand for innovation in wireless technology is growing. Since there is no room in the wireless spectrum to allocate significant frequency bands for future wireless technologies, the only recourse is to increase utilization of the spectrum. To achieve this, we must find a way to share the spectrum. Spectrum sharing techniques will require coordination between all the layers of the protocol stack. The network and the wireless medium are inextricably linked and, thus, both must be considered when optimizing wireless network performance. Unfortunately, interactions in the wireless medium can lead to non-convex problems which have been shown to be NP-hard. Techniques must be developed to tackle the optimization problems that arise from wireless network analysis. In this document we focus on analyzing the spectrum sharing problem from two perspectives: cooperative game theory and non-convex optimization. We develop a cooperative game theory model to analyze a scenario where nodes in a multi-hop wireless network need to agree on a fair allocation of spectrum. We show that in high interference environments, the utility space of the game is non-convex, which may make some optimal allocations unachievable with pure strategies. However, we show that as the number of channels available increases, the utility space becomes close to convex and thus optimal allocations become achievable with pure strategies. We propose the use of the NBS and show that it achieves a good compromise between fairness and efficiency, using a small number of channels. We also propose a distributed algorithm for spectrum sharing and show that it achieves allocations reasonably close to the NBS. In our game theory analysis, we studied the possible outcomes of the spectrum sharing problem and propose the NBS as a desirable outcome and propose an algorithm to achieve the NBS spectrum allocation. However, the expression used to compute the NBS is a non-convex optimization problem. We propose an optimization model to solve a class of problems that incorporate the non-convex dynamics of the wireless medium that occur when the objective is a function of SINR. We present two case studies to show the application of the model to discrete and continuous optimization problems. We propose a branch and bound heuristic, based on the RLT, for approximating the solution of continuous optimization problems. Finally, we present results for the continuous case study. We show simulation results for the heuristic compared to a time constrained mixed integer linear program (MILP) as well as a nonlinear optimization using random starting points. We show that for small networks the MILP achieves the optimal in reasonable time and the heuristic achieves a value close to the optimal. We also show that for large networks the heuristic outperforms the MILP as well as the nonlinear search. / Ph. D.

Dynamic spectrum sharing (DSS) is a new paradigm for spectrum allocation that is expected to lead to more efficient spectrum usage and alleviate the spectrum-scarcity that has been perceived in recent years. DSS refers to the opportunistic, dynamic, and uncoordinated use of the spectrum by multiple, possibly non-cooperating, systems. It allows bands which may be underutilized by incumbent or legacy systems to be shared by agile or cognitive radios on a ``do no harm" basis. An ideal DSS technique is one which efficiently uses the allocated spectrum and maximizes the performance of the DSS network while causing no interference to the legacy radio system with which it coexists. We address this issue in our work by investigating desirable features for DSS with respect to the impact on a legacy radio system as well as the performance of a DSS network. It is found that ``ideal" DSS techniques with respect to both objectives are characterized by the removal of the strongest interferers in the system and averaging of the remaining interference. This motivates the use of an interference avoidance (IA) based underlay technique for DSS. The performance benefit provided by this technique, over an IA-based overlay technique, is shown to increase with the transmission bandwidth available to the DSS system. It is also shown that this technique is more robust to inaccuracies in the system knowledge required for implementing IA. An example of an IA-based underlay technique is a spreading-sequence-based transmission scheme that employs sequence adaptation to avoid interference. We use game-theoretic tools to design such schemes for distributed or ad hoc networks. The designed schemes can also be used to avoid interfering with other agile or static radios. We then extend this work to Ultra Wideband systems which can maximally exploit the gains from the proposed scheme due to the large transmission bandwidths. / Ph. D.

In this dissertation, I study two topics in the context of revenue management. The First topic involves building a mathematical model to analyze the competition between many retailers who can change the price of their respective products in real time. I develop a game-theoretic model for the dynamic price competition where each retailer's objective is to maximize its own expected total revenue. I use the Nash equilibrium to predict market equilibrium and provide managerial insights into how each retailer should take into account its competitors' behavior when setting the price. The second topic involves working with Amtrak, the national railroad passenger corporation, to develop a revenue management model. The revenue management department of Amtrak provides the sales data of Auto Train, a service of Amtrak that allows passengers to bring their vehicles on the train. I analyze the demand structure from sales data and build a mathematical model to describe the sales process for Auto Train. I further develop an algorithm to calculate the optimal pricing strategy that yields the maximum revenue. Because of the distinctive service provided by Auto Train, my findings make important contribution to the revenue management literature. / Ph. D.

This dissertation consists of five chapters on the informational contents of strategies and the role of the perfect recall condition for information partitions in extensive games. The first, introductory, chapter gives basic definitions of extensive games and some results known in the game theory literature. The questions that will be investigated in the remaining chapters and their significance in the literature are also described. In the second chapter it is shown that strategies defined as contingent plans may contain some information that is additional to what the information partition describes. Two types of additional information that strategies may contain when perfect recall is violated are considered. Both behavior and mixed strategies contain the first type of information, but only mixed strategies contain the second type. Addition of either type of information, however, leads to a refinement of the information partition that satisfies perfect recall. The perfect recall condition is found to be significant in demarcating the roles of strategies and information partitions in extensive games. In the third chapter the full informational contents of mixed strategy spaces is explored. The informational content of mixed strategy spaces is found to be invariant over a range of information partitions. A weakening of the perfect recall condition called A-loss is obtained and found to be necessary and sufficient for the information contained in mixed strategies to be equivalent to that of a game with perfect recall. An implication of this result is that a player whose information partition satisfies A-loss can play "as-if" he has perfect recall and a player without A-loss can't. In other words, if an information partition satisfies A-loss, every mixed strategy makes up for any lack of perfect recall described by the information partition. For behavior strategies, we never obtain informational equivalence between distinct information partitions. A-loss turns out to also be a necessary condition for a game without chance moves to have a Nash equilibrium in pure strategies for all payoff assignments. In the fourth chapter the role of the perfect recall condition in preserving some information in the transformation from an extensive game to its agent normal form is discussed. If we interpret a player as a team of agents (one at each information set) then the essential difference between an extensive game and the associated agent normal form game is that in the former the agents act cooperatively while in the latter they act independently. The perfect recall condition is shown to be necessary and sufficient for the perfect equilibria of an extensive game to coincide with those of the associated agent normal form game for all payoff assignments. The contribution of this result is necessity; sufficiency is already known. Since this is proved using pure strategies for the player with imperfect recall in question, one subtle implication is obtained: a perfect equilibrium of the agent normal form game where each agent effectively knows the actions taken and information acquired by his preceding agents, may not be a perfect equilibrium in the original extensive game. This means that perfect recall implies more than just effective knowledge of what happened previously. Chapter 5 concludes. / Ph. D.

Many real word networks exhibit cascading phenomena, e.g., disease outbreaks in social contact networks, malware propagation in computer networks, failures in cyber-physical systems such as power grids. As they grow in size and complexity, their security becomes increasingly important. In this thesis, we address the problems of controlling cascading failures in various network settings. We address the cascading phenomena which are either natural (e.g., disease outbreaks) or malicious (e.g., cyber attacks). We consider the nodes of a network as being individually or collectively controlled by self-interested autonomous agents and study their strategic decisions in the presence of these failure cascades. There are many models of cascading failures which specify how a node would fail when some neighbors have failed, such as: (i) epidemic spread models in which the cascading can be viewed as a natural and stochastic process and (ii) cyber attack models where the cascade is driven by malicious intents. We present our analyses and algorithms for these models in two parts. Part I focuses on problems of controlling epidemic spread. Epidemic outbreaks are generally modeled as stochastic diffusion processes. In particular, we consider the SIS model on networks. There exist heuristic centralized approaches in the literature for containing epidemic spread in SIS/SIR models; however no rigorous performance bounds are known for these approaches. We develop algorithms with provable approximation guarantees that involve either protective intervention (e.g., vaccination) or link removal (e.g., unfriending). Our approach relies on the characterization of the SIS model in terms of the spectral radius of the network. The centralized approaches, however, are sometimes not feasible in practice. For example, targeted vaccination is often not feasible because of limited compliance to directives. This issue has been addressed in the literature by formulating game theoretic models for the containment of epidemic spread. However they generally assume simplistic propagation models or homogeneous network structures. We develop novel game formulations which rely on the spectral characterization of the SIS model. In these formulations, the failures start from a random set of nodes and propagate through the network links. Each node acts as a self-interested agent and makes strategic intervention decisions (e.g., taking vaccination). Each agent decides its strategy to optimize its payoff (modeled by some payoff function). We analyze the complexity of finding Nash equilibria (NE) and study the structure of NE for different networks in these game settings. Part II focuses on malware spread in networks. In cybersecurity literature malware spreads are often studied in the framework of ``attack graph" models. In these models, a node represents either a physical computing unit or a network configuration and an edge represents a physical or logical vulnerability dependency. A node gets compromised if a certain set of its neighbors are compromised. Attack graphs describe explicit scenarios in which a single vulnerability exploitation cascades further into the network exploiting inherent dependencies among the network components. Attack graphs are used for studying cascading effects in many cybersecurity applications, e.g., component failure in enterprise networks, botnet spreads, advanced persistent attacks. One distinct feature of cyber attack cascades is the stealthy nature of the attack moves. Also, cyber attacks are generally repeated. How to control stealthy and repeated attack cascades is an interesting problem. Dijk et. al.~cite{van2013flipit} first proposed a game framework called ``FlipIt" for reasoning about the stealthy interaction between a defender and an attacker over the control of a system resource. However, in cybersecurity applications, systems generally consists of multiple resources connected by a network. Therefore it is imperative to study the stealthy attack and defense in networked systems. We develop a generalized framework called ``FlipNet" which extends the work of Dijk et. al.~cite{van2013flipit} for network. We present analyses and algorithms for different problems in this framework. On the other hand, if the security of a system is limited to the vulnerabilities and exploitations that are known to the security community, often the objective of the system owner is to take cost-effective steps to minimize potential damage in the network. This problem has been formulated in the cybersecurity literature as hardening attack graphs. Several heuristic approaches have been shown in the litrature so far but no algorithmic analysis have been shown. We analyze the inherent vulnerability of the network and present approximation hardening algorithms. / Ph. D.

Increasing dynamics in power systems on account of renewable integration, electric vehicle penetration and rising demands have resulted in the exploration of energy storage for potential solutions. Recent technology- and industry-driven developments have led to a drastic decrease in costs of these storages, further advocating their usage. This thesis compiles the author's research on optimal integration of energy storage. Unpredictability is modelled using random variables favouring the need of stochastic optimization algorithms such as Lyapunov optimization and stochastic approximation. Moreover, consumer interactions in a competitive environment implore the need of topics from game theory. The concept of Nash equilibrium is introduced and methods to identify such equilibrium points are laid down. Utilizing these notions, two research contributions are made. Firstly, a strategy for controlling heterogeneous energy storage units operating at different timescales is put forth. They strategy is consequently employed optimally for arbitrage in an electricity market consisting of day-ahead and real-time pricing. Secondly, energy storages owned by consumers connected to different nodes of a power distribution grid are coordinated in a competitive market. A generalized Nash equilibrium problem is formulated for their participation in arbitrage and energy balancing, which is then solved using a novel emph{weighted} Lyapunov approach. In both cases, we design real-time algorithms with provable suboptimality guarantees in terms of the original centralized and equilibrium problems. The algorithms are tested on realistic scenarios comprising of actual data from electricity markets corroborating the analytical findings. / Master of Science