Document Type



Doctor of Philosophy


Electrical and Computer Engineering

First Adviser

Venkitasubramaniam, Parv


Tradeoffs between privacy and utilities, and privacy preserving control mechanisms in dynamical systems and networks are studied in this dissertation. Despite security mechanisms and data encryption, these systems are still vulnerable to timing analysis, wherein an eavesdropper can use these observations to interpret the identity of individuals. Motivated by this vulnerability, the first three topics of this dissertation investigates privacy preserving mechanisms in dynamical systems and network. The last chapter studies the effect of privacy awareness of consumers on retail competition.The first topic of this dissertation studies the tradeoff between delay and packet source anonymity in a network of mixes. The achievable anonymity is characterized analytically for a general multipath model, and it is shown that under light traffic conditions, there exists a unique single route strategy which achieves the optimal delay anonymity tradeoff. A low complexity algorithm is presented that derives the optimal routes to achieve a desired tradeoff. In the heavy traffic regime, it is shown that optimal anonymity is achieved for any allocation of rates across the different routes. Simulations on example networks are presented where it is shown that the optimal routes derived under light traffic performs quite well in general traffic regime.Next, an analytical framework is presented to integrate and control the degree of link padding mechanisms in the functioning of anonymous relays such that a desired degree of source-destination pair anonymity is achieved from timing analysis without adding significant latency. In particular, the optimal choices of relays and the degree of link padding are investigated to characterize the best tradeoff between anonymity from timing analysis, as measured by Shannon entropy of source destination pairs, and the average latency. The optimization required for the best tradeoff is shown to require exponential complexity, and a sub optimal algorithm is presented that is shown numerically to perform close to the optimal, but only requires linear complexity. In addition, an incremental optimization is presented for a new user to be added optimally to an existing system without altering the prevalent routing scheme.The third part of this dissertation studies the reward optimal decision making in Markov Decision Processes (MDPs) while protecting against inference of type of MDP. Against an adversary attempting to classify between two MDPs with identical state-action spaces but differing reward functions and transition probabilities, a joint policy design is studied for the pair of MDPs that maximize a weighted sum of infinite horizon discounted rewards. Specifically, the adversary observes the sequence of states with the goal of identifying which of the two MDPs are in operation, while the controllers are designed such that an $\epsilon$-differential privacy isguaranteed for the observed state transitions. It is demonstrated that a unique optimal weighted discounted reward exists fora fixed privacy parameter and the weighting factor. A value iteration method is proposed to determine the optimal reward and obtain the differentially private policies for the two MDPs. Convergence of the method is proved and the rate of convergence is characterized. A special application of this framework in routing where nodes serve as states is also studied in this section. Using differential privacy as a metric to quantify the privacy of the intended destination in networked data collections, optimal probabilistic routing schemes are investigated under unicast and multicast paradigms. It is shown that the optimal private unicast routing can be implemented in decentralized manner. Under a multicast paradigm, the optimal solution when overhead is weighted equal to the intended cost, the optimal solution is shown to be a variant of the Steiner tree problem. In general, it is proved that multicast private routing is an np-complete problem. Simulations and numerical results for both private unicast and multicast routing on random graphs are presented.In the last section, the problem of coupon targeting competition between two retailers who sell the same product in a privacy sensitive market is considered. In particular, consumers purchasing decisions are influenced by product prices as well as prior privacy violations by retailers. A Hoteling line model is utilized to investigate the coupon targeting competitionbetween the retailers. Within this framework, privacy sensitivity is modeled using a Markov chain, wherein consumers switch back and forth probabilistically between a privacy alerted state and privacy non-alerted state depending on whether or not they receive targeted coupons from a retailer. The competition between these two retailers at each segment of Hoteling line is modeled by a stochastic nonzero-sum game. In every segment of the Hoteling line, stationary equilibrium strategies of retailers that provide optimal discounted return over an infinite horizon is derived. It is demonstrated that segments in a privacy sensitive market are divided to three categories: 1) Segments not affected by privacy constraints. 2) Segments fully affected by privacy constraints. 3) Segments partially affected by privacy constraints. It is illustrated that in contrast to a price sensitive market, when privacy is a factor, consumers with weak brand loyalty can be driven away from the popular retailer because of a targeted coupon from that retailer. It is also proved that the popular retailer will be more conservative distributing targeted coupon to consumers with weak preference for him whilst the rival retailer will be more offensive on these consumers.