Analysis of Privacy Measures for Multi-Agent and Networked Systems

Privacy Preserving Computation is an important area of research. Quantifying privacy (or loss of) is a crucial part of such research. In this thesis we have provided various techniques for quantifying loss of privacy in networked and multi-agent systems. In the first part of the thesis we investigated approximate privacy model. We identified a protocol that provides constant average privacy approximation ratio for tiling functions. We also provided calculations of average and worst case privacy approxixation ratio of bisection protocols for non-tiling functions. In the second part of the thesis, we formalized problems concerning a privacy measure, (k,l)-anonymity, for quantifying privacy in large networks. We provide non-trivial computational complexity results for effective computation of this measure.