Electrical & Computer Engineering Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2765
Browse
18 results
Search Results
Item SYMMETRIC-KEY CRYPTOGRAPHY AND QUERY COMPLEXITY IN THE QUANTUM WORLD(2024) Bai, Chen; Katz, Jonathan; Alagic, Gorjan; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Quantum computers are likely to have a significant impact on cryptography. Many commonly used cryptosystems will be completely broken once large quantum computers are available. Since quantum computers can solve the factoring problem in polynomial time, the security of RSA would not hold against quantum computers. For symmetric-key cryptosystems, the primary quantum attack is key recovery via Grover search, which provides a quadratic speedup. One way to address this is to double the key length. However, recent results have shown that doubling the key length may not be sufficient in all cases. Therefore, it is crucial to understand the security of various symmetric-key constructions against quantum attackers. In this thesis, we give the first proof of post-quantum security for certain symmetric primitives. We begin with a fundamental block cipher, the Even-Mansour cipher, and the tweakable Even-Mansour construction. Our research shows that both are secure in a realistic quantum attack model. For example, we prove that 2^{n/3} quantum queries are necessary to break the Even-Mansour cipher. We also consider the practical applications that our work implies. Using our framework, we derive post-quantum security proofs for three concrete symmetric-key schemes: Elephant (an Authenticated Encryption (AE) finalist of NIST’s lightweight cryptography standardization effort), Chaskey (an ISO-standardized Message Authentication Code), and Minalpher (an AE second-round candidate of the CAESAR competition). In addition, we consider the two-sided permutation inversion problem in the quantum query model. In this problem, given an image y and quantum oracle access to a permutation P (and its inverse oracle), the goal is to find its pre-image x such that P(x)=y. We prove an optimal lower bound \Omega(\sqrt{2^n}) for this problem against an adaptive quantum adversary. Moreover, we apply our lower bound above to show that a natural encryption scheme constructed from random permutations is secure against quantum attacks.Item NEW APPROACHES FOR ANALYZING SYSTEMS WITH HISTORY-DEPENDENT EFFICIENCY(2020) Lin, Michael; La, Richard J; Martins, Nuno C; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In my dissertational work, I propose two novel models for analyzing systems in which the operational efficiency depends on the past history, e.g., systems with human-in-the-loop and energy harvesting sensors. First, I investigate a queuing system with a single server that serves multiple queues with different types of tasks. The server has a state that is affected by the current and past actions. The task completion probability of each kind of task is a function of the server state. A task scheduling policy is specified by a function that determines the probability of assigning a task to the server. The main results with multiple types of tasks include: (i) necessary and sufficient conditions for the existence of a randomized stationary policy that stabilizes the queues; and (ii) the existence of threshold type policies that can stabilize any stabilizable system. For a single type system, I also identify task scheduling policies under which the utilization rate is arbitrarily close to that of an optimal policy that minimizes the utilization rate. Here, the utilization rate is defined to be the long-term fraction of time the server is required to work. Second, I study a remote estimation problem over an activity packet drop link. The link undergoes packet drops and has an (activity) state that is influenced by past transmission requests. The packet-drop probability is governed by a given function of the link's state. A scheduler determines the probability of a transmission request regarding the link's state. The main results include: (i) necessary and sufficient conditions for the existence of a randomized stationary policy that stabilizes the estimation error in the second-moment sense; and (ii) the existence of deterministic policies that can stabilize any stabilizable system. The second result implies that it suffices to search for deterministic strategies for stabilizing the estimation error. The search can be further narrowed to threshold policies when the function for the packet-drop probability is non-decreasing.Item Efficient Solutions to High-Dimensional and Nonlinear Neural Inverse Problems(2019) Miran, Sayyed Sina; Babadi, Behtash; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Development of various data acquisition techniques has enabled researchers to study the brain as a complex system and gain insight into the high-level functions performed by different regions of the brain. These data are typically high-dimensional as they pertain to hundreds of sensors and span hours of recording. In many experiments involving sensory or cognitive tasks, the underlying cortical activity admits sparse and structured representations in the temporal, spatial, or spectral domains, or combinations thereof. However, current neural data analysis approaches do not take account of sparsity in order to harness the high-dimensionality. Also, many existing approaches suffer from high bias due to the heavy usage of linear models and estimation techniques, given that cortical activity is known to exhibit various degrees of non-linearity. Finally, the majority of current methods in computational neuroscience are tailored for static estimation in batch-mode and offline settings, and with the advancement of brain-computer interface technologies, these methods need to be extended to capture neural dynamics in a real-time fashion. The objective of this dissertation is to devise novel algorithms for real-time estimation settings and to incorporate the sparsity and non-linear properties of brain activity for providing efficient solutions to neural inverse problems involving high-dimensional data. Along the same line, our goal is to provide efficient representations of these high-dimensional data that are easy to interpret and assess statistically. First, we consider the problem of spectral estimation from binary neuronal spiking data. Due to the non-linearities involved in spiking dynamics, classical spectral representation methods fail to capture the spectral properties of these data. To address this challenge, we integrate point process theory, sparse estimation, and non-linear signal processing methods to propose a spectral representation modeling and estimation framework for spiking data. Our model takes into account the sparse spectral structure of spiking data, which is crucial in the analysis of electrophysiology data in conditions such as sleep and anesthesia. We validate the performance of our spectral estimation framework using simulated spiking data as well as multi-unit spike recordings from human subjects under general anesthesia. Next, we tackle the problem of real-time auditory attention decoding from electroencephalography (EEG) or magnetoencephalography (MEG) data in a competing-speaker environment. Most existing algorithms for this purpose operate offline and require access to multiple trials for a reliable performance; hence, they are not suitable for real-time applications. To address these shortcomings, we integrate techniques from state-space modeling, Bayesian filtering, and sparse estimation to propose a real-time algorithm for attention decoding that provides robust, statistically interpretable, and dynamic measures of the attentional state of the listener. We validate the performance of our proposed algorithm using simulated and experimentally-recorded M/EEG data. Our analysis reveals that our algorithms perform comparable to the state-of-the-art offline attention decoding techniques, while providing significant computational savings. Finally, we study the problem of dynamic estimation of Temporal Response Functions (TRFs) for analyzing neural response to auditory stimuli. A TRF can be viewed as the impulse response of the brain in a linear stimulus-response model. Over the past few years, TRF analysis has provided researchers with great insight into auditory processing, specially under competing speaker environments. However, most existing results correspond to static TRF estimates and do not examine TRF dynamics, especially in multi-speaker environments with attentional modulation. Using state-space models, we provide a framework for a robust and comprehensive dynamic analysis of TRFs using single trial data. TRF components at specific lags may exhibit peaks which arise, persist, and disappear over time according to the attentional state of the listener. To account for this specific behavior in our model, we consider a state-space model with a Gaussian mixture process noise, and devise an algorithm to efficiently estimate the process noise parameters from the recorded M/EEG data. Application to simulated and recorded MEG data shows that the {proposed state-space modeling and inference framework can reliably capture the dynamic changes in the TRF, which can in turn improve our access to the attentional state in competing-speaker environments.Item Machine Learning of Facial Attributes Using Explainable, Secure and Generative Adversarial Networks(2018) Samangouei, Pouya; Chellappa, Rama; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)"Attributes" are referred to abstractions that humans use to group entities and phenomena that have a common characteristic. In machine learning (ML), attributes are fundamental because they bridge the semantic gap between humans and ML systems. Thus, researchers have been using this concept to transform complicated ML systems into interactive ones. However, training the attribute detectors which are central to attribute-based ML systems can still be challenging. It might be infeasible to gather attribute labels for rare combinations to cover all the corner cases, which can result in weak detectors. Also, it is not clear how to fill in the semantic gap with attribute detectors themselves. Finally, it is not obvious how to interpret the detectors' outputs in the presence of adversarial noise. First, we investigate the effectiveness of attributes for bridging the semantic gap in complicated ML systems. We turn a system that does continuous authentication of human faces on mobile phones into an interactive attribute-based one. We employ deep multi-task learning in conjunction with multi-view classification using facial parts to tackle this problem. We show how the proposed system decomposition enables efficient deployment of deep networks for authentication on mobile phones with limited resources. Next, we seek to improve the attribute detectors by using conditional image synthesis. We take a generative modeling approach for manipulating the semantics of a given image to provide novel examples. Previous works condition the generation process on binary attribute existence values. We take this type of approaches one step further by modeling each attribute as a distributed representation in a vector space. These representations allow us to not only toggle the presence of attributes but to transfer an attribute style from one image to the other. Furthermore, we show diverse image generation from the same set of conditions, which was not possible using existing methods with a single dimension per attribute. We then investigate filling in the semantic gap between humans and attribute classifiers by proposing a new way to explain the pre-trained attribute detectors. We use adversarial training in conjunction with an encoder-decoder model to learn the behavior of binary attribute classifiers. We show that after our proposed model is trained, one can see which areas of the image contribute to the presence/absence of the target attribute, and also how to change image pixels in those areas so that the attribute classifier decision changes in a consistent way with human perception. Finally, we focus on protecting the attribute models from un-interpretable behaviors provoked by adversarial perturbations. These behaviors create an inexplainable semantic gap since they are visually unnoticeable. We propose a method based on generative adversarial networks to alleviate this issue. We learn the training data distribution that is used to train the core classifier and use it to detect and denoise test samples. We show that the method is effective for defending facial attribute detectors.Item OPTIMIZATION ALGORITHMS USING PRIORS IN COMPUTER VISION(2018) Shah, Sohil Atul; Goldstein, Tom; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Over the years, many computer vision models, some inspired by human behavior, have been developed for various applications. However, only handful of them are popular and widely used. Why? There are two major factors: 1) most of these models do not have any efficient numerical algorithm and hence they are computationally very expensive; 2) many models, being too generic, cannot capitalize on problem specific prior information and thus demand rigorous hyper-parameter tuning. In this dissertation, we design fast and efficient algorithms to leverage application specific priors to solve unsupervised and weakly-supervised problems. Specifically, we focus on developing algorithms to impose structured priors, model priors and label priors during the inference and/or learning of vision models. In many application, it is known a priori that a signal is smooth and continuous in space. The first part of this work is focussed on improving unsupervised learning mechanisms by explicitly imposing these structured priors in an optimization framework using different regularization schemes. This led to the development of fast algorithms for robust recovery of signals from compressed measurements, image denoising and data clustering. Moreover, by employing re-descending robust penalty on the structured regularization terms and applying duality, we reduce our clustering formulation to an optimization of a single continuous objective. This enabled integration of clustering processes in an end-to-end feature learning pipeline. In the second part of our work, we exploit inherent properties of established models to develop efficient solvers for SDP, GAN, and semantic segmentation. We consider models for several different problem classes. a) Certain non-convex models in computer vision (e.g., BQP) are popularly solved using convex SDPs after lifting to a high-dimensional space. However, this computationally expensive approach limits these methods to small matrices. A fast and approximate algorithm is developed that directly solves the original non-convex formulation using biconvex relaxations and known rank information. b) Widely popular adversarial networks are difficult to train as they suffer from instability issues. This is because optimizing adversarial networks corresponds to finding a saddle-point of a loss function. We propose a simple prediction method that enables faster training of various adversarial networks using larger learning rates without any instability problems. c) Semantic segmentation models must learn long-distance contextual information while retaining high spatial resolution at the output. Existing models achieves this at the cost of computationally expensive and memory exhaustive training/inference. We designed stacked u-nets model which can repeatedly process top-down and bottom-up features. Our smallest model exceeds Resnet-101 performance on PASCAL VOC 2012 by 4.5% IoU with ∼ 7× fewer parameters. Next, we address the problem of learning heterogeneous concepts from internet videos using mined label tags. Given a large number of videos each with multiple concepts and labels, the idea is to teach machines to automatically learn these concepts by leveraging weak labels. We formulate this into a co-clustering problem and developed a novel bayesian non-parametric weakly supervised Indian buffet process model which additionally enforces the paired label prior between concepts. In the final part of this work we consider an inverse approach: learning data priors from a given model. Specifically, we develop numerically efficient algorithm for estimating the log likelihood of data samples from GANs. The approximate log-likelihood function is used for outlier detection and data augmentation for training classifiers.Item Compressed Sensing Beyond the IID and Static Domains: Theory, Algorithms and Applications(2017) Kazemipour, Abbas; Wu, Min; Babadi, Behtash; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Sparsity is a ubiquitous feature of many real world signals such as natural images and neural spiking activities. Conventional compressed sensing utilizes sparsity to recover low dimensional signal structures in high ambient dimensions using few measurements, where i.i.d measurements are at disposal. However real world scenarios typically exhibit non i.i.d and dynamic structures and are confined by physical constraints, preventing applicability of the theoretical guarantees of compressed sensing and limiting its applications. In this thesis we develop new theory, algorithms and applications for non i.i.d and dynamic compressed sensing by considering such constraints. In the first part of this thesis we derive new optimal sampling-complexity tradeoffs for two commonly used processes used to model dependent temporal structures: the autoregressive processes and self-exciting generalized linear models. Our theoretical results successfully recovered the temporal dependencies in neural activities, financial data and traffic data. Next, we develop a new framework for studying temporal dynamics by introducing compressible state-space models, which simultaneously utilize spatial and temporal sparsity. We develop a fast algorithm for optimal inference on such models and prove its optimal recovery guarantees. Our algorithm shows significant improvement in detecting sparse events in biological applications such as spindle detection and calcium deconvolution. Finally, we develop a sparse Poisson image reconstruction technique and the first compressive two-photon microscope which uses lines of excitation across the sample at multiple angles. We recovered diffraction-limited images from relatively few incoherently multiplexed measurements, at a rate of 1.5 billion voxels per second.Item POSITIVE FILTERED P_N METHOD FOR LINEAR TRANSPORT EQUATIONS AND THE ASSOCIATED OPTIMIZATION ALGORITHM(2016) Laiu, Ming Tse Paul; Tits, André; Hauck, Cory; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)We propose a positive, accurate moment closure for linear kinetic transport equations based on a filtered spherical harmonic (FP_N) expansion in the angular variable. The FP_N moment equations are accurate approximations to linear kinetic equations, but they are known to suffer from the occurrence of unphysical, negative particle concentrations. The new positive filtered P_N (FP_N+) closure is developed to address this issue. The FP_N+ closure approximates the kinetic distribution by a spherical harmonic expansion that is non-negative on a finite, predetermined set of quadrature points. With an appropriate numerical PDE solver, the FP_N+ closure generates particle concentrations that are guaranteed to be non-negative. Under an additional, mild regularity assumption, we prove that as the moment order tends to infinity, the FP_N+ approximation converges, in the L2 sense, at the same rate as the FP_N approximation; numerical tests suggest that this assumption may not be necessary. By numerical experiments on the challenging line source benchmark problem, we confirm that the FP_N+ method indeed produces accurate and non-negative solutions. To apply the FP_N+ closure on problems at large temporal-spatial scales, we develop a positive asymptotic preserving (AP) numerical PDE solver. We prove that the propose AP scheme maintains stability and accuracy with standard mesh sizes at large temporal-spatial scales, while, for generic numerical schemes, excessive refinements on temporal-spatial meshes are required. We also show that the proposed scheme preserves positivity of the particle concentration, under some time step restriction. Numerical results confirm that the proposed AP scheme is capable for solving linear transport equations at large temporal-spatial scales, for which a generic scheme could fail. Constrained optimization problems are involved in the formulation of the FP_N+ closure to enforce non-negativity of the FP_N+ approximation on the set of quadrature points. These optimization problems can be written as strictly convex quadratic programs (CQPs) with a large number of inequality constraints. To efficiently solve the CQPs, we propose a constraint-reduced variant of a Mehrotra-predictor-corrector algorithm, with a novel constraint selection rule. We prove that, under appropriate assumptions, the proposed optimization algorithm converges globally to the solution at a locally q-quadratic rate. We test the algorithm on randomly generated problems, and the numerical results indicate that the combination of the proposed algorithm and the constraint selection rule outperforms other compared constraint-reduced algorithms, especially for problems with many more inequality constraints than variables.Item A comprehensive study of multiplicative attribute graph model(2016) Qu, Sikai; Makowski, Armand; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Graphs are powerful tools to describe social, technological and biological networks, with nodes representing agents (people, websites, gene, etc.) and edges (or links) representing relations (or interactions) between agents. Examples of real-world networks include social networks, the World Wide Web, collaboration networks, protein networks, etc. Researchers often model these networks as random graphs. In this dissertation, we study a recently introduced social network model, named the Multiplicative Attribute Graph model (MAG), which takes into account the randomness of nodal attributes in the process of link formation (i.e., the probability of a link existing between two nodes depends on their attributes). Kim and Lesckovec, who defined the model, have claimed that this model exhibit some of the properties a real world social network is expected to have. Focusing on a homogeneous version of this model, we investigate the existence of zero-one laws for graph properties, e.g., the absence of isolated nodes, graph connectivity and the emergence of triangles. We obtain conditions on the parameters of the model, so that these properties occur with high or vanishingly probability as the number of nodes becomes unboundedly large. In that regime, we also investigate the property of triadic closure and the nodal degree distribution.Item Model Based Optimization and Design of Secure Systems(2013) Malik, Waseem Ansar; Martins, Nuno C; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)ABSTRACT Title of dissertation: MODEL BASED OPTIMIZATION AND DESIGN OF SECURE SYSTEMS Waseem Ansar Malik, Doctor of Philosophy, 2013 Dissertation directed by: Prof. Nuno C. Martins Department of Electrical and Computer Engineering University of Maryland, College Park Dr. Ananthram Swami Computational and Information Sciences Directorate Army Research Laboratory Control systems are widely used in modern industry and find wide applications in power systems, nuclear and chemical plants, the aerospace industry, robotics, communication devices, and embedded systems. All these systems typically rely on an underlying computing and networking infrastructure which has considerable security vulnerabilities. The biggest threat, in this age and time, to modern systems are cyber attacks from adversaries. Recent cyber attacks have practically shut down government websites affecting government operation, undermined financial institutions, and have even infringed on public privacy. Thus it is extremely important to conduct studies on the design and analysis of secure systems. This work is an effort in this research direction and is mainly focused on incorporating security in the design of modern control systems. In the first part of this dissertation, we present a linear quadratic optimal control problem subjected to security constraints. We consider an adversary which can make partial noisy measurements of the state. The task of the controller is to generate control sequences such that the adversary is unable to estimate the terminal state. This is done by minimizing a quadratic cost while satisfying security constraints. The resulting optimization problems are shown to be convex and the optimal solution is computed using Lagrangian based techniques. For the case when the terminal state has a discrete distribution the optimal solution is shown to be nonlinear in the terminal state. This is followed by considering the case when the terminal state has a continuous distribution. The resulting infinite dimensional optimization problems are shown to be convex and the optimal solution is proven to be affine in the terminal state. In the next part of this dissertation, we analyze several team decision problems subjected to security constraints. Specifically, we consider problem formulations where there are two decision makers each controlling a different dynamical system. Each decision maker receives information regarding the respective terminal states that it is required to reach and applies a control sequence accordingly. An adversary makes partial noisy measurements of the states and tries to estimate the respective terminal states. It is shown that the optimal solution is affine in the terminal state when it is identical for both systems. We also consider the general case where the terminal states are correlated. The resulting infinite dimensional optimization problems are shown to convex programs and we prove that the optimal solution is affine in the information available to the decision makers. Next, a stochastic receding horizon control problem is considered and analyzed. Specifically, we consider a system with bounded disturbances and hard bounds on the control inputs. Utilizing a suboptimal disturbance feedback scheme, the optimization problem is shown to be convex. The problem of minimizing the empirical mean of the cost function is analyzed. We provide bounds on the disturbance sample size to compute the empirical minimum of the problem. Further, we consider the problem where there are hard computational constraints and complex on-line optimization is not feasible. This is addressed by randomly generating both the control inputs and the additive disturbances. Bounds on sample sizes are provided which guarantee a notion of a probable near minimum. Model uncertainty is also incorporated into the framework and relevant bounds are provided which guarantee a probable near minimax value. This work finds many applications in miniature devices and miniature robotics. In the final part of this dissertation, we consider a centralized intrusion detection problem with jointly optimal sensor placement. A team of sensors make measurements regarding the presence of an intruder and report their observations to a decision maker. The decision maker solves a jointly optimal detection and sensor placement problem. For the case when the number of sensors is equal to the number of placement points, we prove that uniform placement of sensors is not strictly optimal. We introduce and utilize a majorization based partial order for the placement of sensors. For the case when the number of sensors is less than or equal to six, we show that for a fixed local probability of detection (probability of false alarm) increasing the probability of false alarm (probability of detection) results in optimal placements that are higher on a majorization based partial order.Item The Effects of Coupling Delay and Amplitude / Phase Interaction on Large Coupled Oscillator Networks(2012) Lee, Wai Shing; Ott, Edward; Antonsen, Thomas M.; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The interaction of many coupled dynamical units is a theme across many scientific disciplines. A useful framework for beginning to understanding such phenomena is the coupled oscillator network description. In this dissertation, we study a few problems related to this. The first part of the dissertation studies generic effects of heterogeneous interaction delays on the dynamics of large systems of coupled oscillators. Here, we modify the Kuramoto model (phase oscillator model) to incorporate a distribution of interaction delays. Corresponding to the continuum limit, we focus on the reduced dynamics on an invariant manifold of the original system, and derive governing equations for the system, which we use to study stability of the incoherent state and the dynamical transitional behavior from stable incoherent states to stable coherent states. We find that spread in the distribution function of delays can greatly alter the system dynamics. The second part of this dissertation is a sequel to the first part. Here, we consider systems of many spatially distributed phase oscillators that interact with their neighbors, and each oscillator can have a different natural frequency, and a different response time to the signals it receives from other oscillators in its neighborhood. By first reducing the microscopic dynamics to a macroscopic partial-differential-equation description, we then numerically find that finite oscillator response time leads to many interesting spatio-temporal dynamical behaviors, and we study interactions and evolutionary behaviors of these spatio-temporal patterns. The last part of this dissertation addresses the behavior of large systems of heterogeneous, globally coupled oscillators each of which is described by the generic Landau-Stuart equation, which incorporates both phase and amplitude dynamics. Our first goal is to investigate the effect of a spread in the amplitude growth parameter of the oscillators and that of a homogeneous nonlinear frequency shift. Both of these effects are of potential relevance to recently reported experiments. Our second goal is to gain further understanding of the observation that, at large coupling strength, a simple constant-amplitude sinusoidal oscillation is always a solution for the dynamics of the global order parameter when the system has constant nonlinear characteristics.