Alumni Dissertations and Theses

 
 

Alumni Dissertations and Theses

Filter Dissertations and Theses By:

 
 
  • Theory and Applications of Outsider Anonymity in Broadcast Encryption

    Author:
    Irippuge Perera
    Year of Dissertation:
    2015
    Program:
    Computer Science
    Advisor:
    Nelly Fazio
    Abstract:

    Broadcast Encryption (BE) allows efficient one-to-many secret communication of data over a broadcast channel. In the standard setting of BE, information about receivers is transmitted in the clear together with ciphertexts. This could be a serious violation of recipient privacy since the identities of the users authorized to access the secret content in certain broadcast scenarios are as sensitive as the content itself. Anonymous Broadcast Encryption (AnoBe) prevents this leakage of recipient identities from ciphertexts but at a cost of a linear lower bound (in the number of receivers) on the length of ciphertexts. A linear ciphertext length is a highly undesirable bottleneck in any large-scale broadcast application. In this thesis, we propose a less stringent yet very meaningful notion of anonymity for anonymous broadcast encryption called Outsider-Anonymous Broadcast Encryption (oABE) that allows the creation of ciphertexts that are sublinear in the number of receivers. We construct several oABE schemes with varying security guarantees and levels of efficiency. We also present two very interesting cryptographic applications afforded by the efficiency of our oABE schemes. The first is Broadcast Steganography (BS), the extension of the state of the art setting of point-to-point steganography to the multi-recipient setting. The second is Oblivious Group Storage (OGS), the introduction of fine-grained data access control policies to the setting of multi-client oblivious cloud storage protocols.

  • Secure Critical Care Resource Optimization based on Heterogeneous Vital Signs

    Author:
    Mohamed Saad
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    Bilal Khan
    Abstract:

    Preventable, in-hospital errors account for a substantial number of deaths and injuries in the United States. Various studies estimate that such deaths number between 100,000 and 200,000 each year. One of the key challenges in critical care is a legacy of existing largely wired medical networks, which due to the complexity of their constituent heterogeneous medical devices, limit the ability to optimize the allocation of medical resources such as caregivers. The absence of reliable solutions which address the interoperability of different systems inside critical care units, is principally due to market concerns, since competing vendors do not embrace data sharing standards. In this work, we present a solution that integrates heterogeneous wired legacy systems within a backward compatible wireless interconnect system, providing mobility to caregivers, and the ability to coordinate and optimize their assignment to patients. The design and architecture is able to scale as needed in terms of system load and size. We demonstrate, through simulation, that the system is able to, through the optimization of caregiver assignment, significantly reduce total patient risk within health-care institutions. A prototype implementation of the system, demonstrates that the system has great promise in real-world field deployments, and can be instrumented to be compliant with site security requirements and the HIPAA privacy act.

  • Geometric Graph Theory and Wireless Sensor Networks

    Author:
    Deniz Sarioz
    Year of Dissertation:
    2012
    Program:
    Computer Science
    Advisor:
    Janos Pach
    Abstract:

    In this work, we apply geometric and combinatorial methods to explore a variety of problems motivated by wireless sensor networks. Imagine sensors capable of communicating along straight lines except through obstacles like buildings or barriers, such that the communication network topology of the sensors is their visibility graph. Using a standard distributed algorithm, the sensors can build common knowledge of their network topology. We first study the following inverse visibility problem: What positions of sensors and obstacles define the computed visibility graph, with fewest obstacles? This is the problem of finding a minimum obstacle representation of a graph. This minimum number is the obstacle number of the graph. Using tools from extremal graph theory and discrete geometry, we obtain for every constant $h$ that the number of $n$-vertex graphs that admit representations with $h$ obstacles is $2^{o(n^2)}$. We improve this bound to show that graphs requiring $\Omega(n / \log^{2} n)$ obstacles exist. We also study restrictions to convex obstacles, and to obstacles that are line segments. For example, we show that every outerplanar graph admits a representation with five convex obstacles, and that allowing obstacles to intersect sometimes decreases their required number. Finally, we study the corresponding problem for sensors equipped with GPS. Positional information allows sensors to establish common knowledge of their communication network geometry, hence we wish to compute a minimum obstacle representation of a given straight-line graph drawing. We prove that this problem is NP-complete, and provide a $O(\log OPT)$-approximation algorithm by bounding the Vapnik-Chervonenkis dimension for the corresponding hypergraph family.

  • Information Transmission in Communication Games: Signaling with an Audience

    Author:
    Farishta Satari
    Year of Dissertation:
    2013
    Program:
    Computer Science
    Advisor:
    Rohit Parikh
    Abstract:

    Communication is a goal-oriented activity where interlocutors use language as a means to achieve an end while taking into account the goals and plans of others. Game theory, being the scientific study of strategically interactive decision-making, provides the mathematical tools for modeling language use among rational decision makers. When we speak of language use, it is obvious that questions arise about what someone knows and what someone believes. Such a treatment of statements as moves in a language game has roots in the philosophy of language and in economics. In the first, the idea is prominent with the work of Strawson, later Wittgenstein, Austin, Grice, and Lewis. In the second, the work of Crawford, Sobel, Rabin, and Farrell. We supplement the traditional model of signaling games with the following innovations: We consider the effect of the relationship whether close or distant among players. We consider the role that ethical considerations may play in communication. And finally, in our most significant innovation, we introduce an audience whose presence affects the sender's signal and/or the receiver's response. In our model, we no longer assume that the entire structure of the game is common knowledge as some of the priorities of the players and relationships among some of them might not be known to the other players.

  • Optimization Problems in Sensor Network Data Collection

    Author:
    Simon Shamoun
    Year of Dissertation:
    2011
    Program:
    Computer Science
    Advisor:
    Amotz Bar-Noy
    Abstract:

    Data collection is one of the most important tasks of many sensor networks. The data collected by sensors is used to monitor and analyze various systems, such as volcanoes, forests, and bridges. Large scale wireless sensor networks can provide timely access to a wealth of data, but obtaining this data is challenged by various resource constraints. This thesis proposes and analyzes solutions to three optimization problems that arise from the conflict between data collection and resource constraints: (1) maximize coverage by a set of sensors when the coverage they provide varies with location; (2) select a subset of the sensors, within some budget constraint, that best predict the data streams produced by all the sensors in the network; and (3) minimize the cost needed to find the top ranking sensor readings according to some criteria. The analyses of these problems use three different views of a sensor network: a coverage-centric view, in which each sensor is valued for its coverage ability; a data-centric view, in which each sensor is valued for the data it provides; and an agent-centric view, in which each sensor is viewed as an independent agent with information of value to the application. By choosing an appropriate view of the network, it is possible to separate the analysis from implementation details and apply well-established techniques from other domains to the problem solution. In this case, methodologies from stochastic and computational geometry, graph theory, and search theory are applied to the respective problems. This thesis presents optimal solutions to the coverage and search problems, approximation bounds on the best possible solution to the selection problem, and quantitative comparisons to alternative solutions to each problem in synthetic environments.

  • ON THE PROBLEM OF PACKING STEINER TREES OF A GRAPH

    Author:
    MOHAMMAD TALAFHA
    Year of Dissertation:
    2010
    Program:
    Computer Science
    Advisor:
    LOUIS PETINGI
    Abstract:

    On The Problem of Packing Steiner Trees of a Graph Let G = (V, E) be an undirected graph with vertex-set V, edge-set E, and a subset of distinguished terminal vertices K of V, where |K| ≥ 2 (the vertices in V - K are called the non-terminal vertices). The degree of a vertex v of G is the number of edges incident at v in G. A K-Steiner tree T of G is a tree containing the terminal vertex-set K, and any vertex of degree one in T must belong to K. The K-edge-connectivity, denoted as λK(G), of a connected graph G with terminal vertex-set K, is the minimum number of edges whose removal from G disconnects at least two vertices of K. The Steiner Tree Packing problem (STPP for short) is the problem of finding the maximum number of edge-disjoint K-Steiner trees, tK(G), contained in G. Specifically, in this thesis, we are interested in finding a lower bound on tK(G) with respect to the K-edge-connectivity, λK(G). The Steiner Tree Packing problem has attracted considerable attention from many researchers in different areas because of its wide applicability. It has applications in routing problems arising in VLSI circuit design, where an effective way of sharing different signals among cells in a circuit can be achieved by the use of edge-disjoint Steiner trees. It also has a variety of computer network applications such as multicasting, video-conferencing, and network information flow where simultaneous communications can be facilitated by using edge-disjoint Steiner trees. In 2003, Kriesell conjectured that any graph G = (V, E) with terminal vertex-set with subset of terminal vertices K of V has at least λK(G) / 2 edge-disjoint K-Steiner trees. In this thesis we give a background on this problem and we present most of the major results obtained so far. Moreover, we show that Kriesell's conjecture can be answered affirmatively if the edges of G can be partitioned into K-Steiner trees. This result yields bounds for the problem of packing K-Steiner trees with certain intersection properties in a graph. In addition we show that for any graph G with terminal vertex-set K, ; tK(G) ≥ λK(G) -­ |V - K| / 2 - 1. Moreover, we study a vulnerability index called the edge-toughness, which connects the connectivity of a network with the problem of packing Steiner trees of a graph.

  • SEMIPARAMETRIC TEMPORAL CLUSTERING

    Author:
    Suzanne Tamang
    Year of Dissertation:
    2013
    Program:
    Computer Science
    Advisor:
    Simon Parsons
    Abstract:

    Although temporal data provides critical context for many real-world reasoning tasks, incorporating the temporal dimension into an analysis can present methodological challenges. Traditional methods from statistics are limited in their ability to process noisy, large-scale secondary data sources. Data mining approaches are better suited for these types of problems, but have primarily focused on static data sets. However, few real-world data sets are static, or measure stationary phenomena; rather, they are dynamic. To facilitate the meaningful use of abundant, unlabeled temporal data, I develop a new temporal clustering method that can assist in the preprocessing, exploration, and discovery of new knowledge from secondary data sources that are subject to arbitrary sampling schemes, and contain observation sequences of different durations. My approach builds on the semiparametric time series clustering framework, which has demonstrated clear benefits over fully parametric, or fully non-parametric methods. The framework combines beneficial parametric assumptions, such as the Markov or hidden-state assumption, to model temporal systems, with a more agnostic, nonparametric approach for clustering the embedded models. Using digital health data as a case study, I broaden the range of scenarios for which semiparametric clustering can be successfully applied. Specifically, I develop a method to use a state-of-the-art continuous-time Bayesian network to more naturally represent temporal information, addressing limitations of discrete- time methods. Also, as an alternative to spectral methods I pair model-based abstraction with a nonparametric Bayesian clustering technique that allows k to be expressed as a function of the size and complexity of the patient population, avoiding the requirement to prespecify the number of clusters using a heuristic. To demonstrate the ability of this approach to produce meaningful results, clusters are evaluated using intrinsic and extrinsic validation. In addition, I compare cluster assignments with that of temporal clustering systems reported in the research literature, showing a 20% relative improvement over the best system's performance and recognizable differences among the patient clusters that are detected.

  • A Symbolic Exploration of the Joint State Space and the Underlying Argumentation-based Reasoning Processes for Multiagent Planning

    Author:
    Yuqing Tang
    Year of Dissertation:
    2012
    Program:
    Computer Science
    Advisor:
    Simon Parsons
    Abstract:

    Coming up with coherent behaviors for a team of agents in a non-deterministic environment is a complex process. The problem is further complicated by information regarding the environment being defeasible --- new information will disqualify the old information --- while at the same time this information is distributed, uncertain and possibly inconsistent. In this dissertation, I propose an approach based on symbolic model checking techniques to implicitly explore the state space of a system of agents to form a coherent set of joint behaviors for the agents with uncertainty captured as non-deterministism in the state space. The exploration process is based on individual agents' defeasible factored information about the dynamic of the state space towards a set of possibly inconsistent goals. This process can be interpreted using an argumentation-based approach. The exploration of the state space and the argumentation-based reasoning processes are carried out by a sequence of logical operations in the logic of Quantified Boolean Formulae (QBFs) and its model representation --- Binary Decision Diagrams (BDDs). All the algorithms to carry out these processes can be computed with a polynomial number of QBF operations in terms of the number of inputs and the number of boolean variables in the domain. Although general symbolic solving QBFs and BDDs is PSPACE complete, the practices of QBF solvers and BDD implementations allow us to employ various techniques and application-specific heuristics to solve a number of applications. In summary, the approaches proposed in this dissertation provide a formal system and implementation techniques to integrate non-monotonic reasoning and non-deterministic planning into defeasible multiagent decentralized planning so that coherent behaviors can be formed for a system of agents in a very demanding setting where the information regarding the environment and goals regarding what to do are distributed, incomplete, possibly inconsistent and uncertain.

  • 3D SCENE MODELING AND UNDERSTANDING FROM IMAGE SEQUENCES

    Author:
    Hao Tang
    Year of Dissertation:
    2013
    Program:
    Computer Science
    Advisor:
    Zhigang Zhu
    Abstract:

    A new method for 3D modeling is proposed, which generates a content-based 3D mosaic (CB3M) representation for long video sequences of 3D, dynamic urban scenes captured by a camera on a mobile platform. In the first phase, a set of parallel-perspective (pushbroom) mosaics with varying viewing directions is generated to capture both the 3D and dynamic aspects of the scene under the camera coverage. In the second phase, a unified patch-based stereo matching algorithm is applied to extract parametric representations of the color, structure and motion of the dynamic and/or 3D objects in urban scenes, where a lot of planar surfaces exist. Multiple pairs of stereo mosaics are used for facilitating reliable stereo matching, occlusion handling, accurate 3D reconstruction and robust moving target detection. The outcome of this phase is a CB3M representation, which is a highly compressed visual representation for a dynamic 3D scene, and has object contents of both 3D and motion information. In the third phase, a multi-layer based scene understanding algorithm is proposed, resulting in a planar surface model for higher-level object representations. Experimental results are given for both simulated and several different real video sequences of large-scale 3D scenes to show the accuracy and effectiveness of the representation. We also show the patch-based stereo matching algorithm and the CB3M representation can be generalized to 3D modeling with perspective views using either a single camera or a stereovision head on a ground mobile platform or a pedestrian. Applications of the proposed method include airborne or ground video surveillance, 3D urban scene modeling, traffic survey, transportation planning and the visual aid for perception and navigation of blind people.

  • Efficient Communication Through Structured Node Labeling in Peer-to-Peer Networks

    Author:
    Andi Toce
    Year of Dissertation:
    2013
    Program:
    Computer Science
    Advisor:
    Abbe Mowshowitz
    Abstract:

    Peer to Peer (P2P) networks have become increasingly popular in recent years as administrators are choosing to move away from monolithic centralized networks. These networks, while offering significant advantages in a variety of applications, are presented with a new set of challenges, from communication efficiency to network vulnerability and security. Numerous researchers have proposed a variety of solutions to improve the quality of service in P2P networks. A critical factor in maintaining an acceptable level of service quality is the efficiency and reliability of communication among nodes. One way of improving communication is to assign identifiers (labels) to each node and then use these labels to facilitate and improve message routing. This proposed work introduces two labeling schemata for P2P networks. Each participating node is assigned a label set. Labels are then used to determine node positions within an engineered logical overlay and identify routing paths during communication. We prove that the assignment of labels reduces the overall cost of communication thus saving valuable network resources. These theoretical findings are confirmed by experimental results with randomly selected P2P networks of various sizes. Detailed statistics on the performance of each protocol are provided which show clearly the practical utility of the labeling approach.