Privacy preserving and incentive compatible protocols for cooperation in distributed computations

In today's society, advanced cyber-infrastructure are connecting a huge number of mutually unfamiliar people, and forming a computing environment with untrusted parties. The human factors of untrusted parties, especially the considerations of privacy, security and incentives, bring new challenges in designing our systems, services and software with distributed computations. This thesis addresses the incentive and privacy issues in distributed computing with untrusted parties.;Wireless networks with recent technical advances have become one of the most popular platforms for computing with untrusted parties. However, in civilian wireless networks, nodes often belong to different users and those users may be selfish. Existing protocols that were designed without considering user incentives often require nodes to spend their own resources for others. Hence selfish users may deviate from these protocols, in order to maximize their benefits. It causes serious problems to performance and even functioning of wireless networks. So, it is of great importance to provide incentives to those selfish users in wireless networks. First part of this thesis focuses on designing incentive-compatible packet forwarding protocols for three different types of wireless networks, i.e., ad hoc wireless networks, wireless networks using network coding and vehicular ad hoc networks. First, for traditional ad hoc wireless networks, the first reputation system that has rigorous analysis and guaranteed incentive compatibility in a practical model is proposed, to enhance the cooperation among nodes in forwarding packets for others. Second, for newly emerging wireless networks using network coding, the first-ever enforceable incentive scheme to stimulate packet forwarding is proposed that uses a combination of game theoretic and cryptographic techniques. Third, the problem on how to stimulate message forwarding in vehicular ad hoc networks that have no end-to-end connections is solved, and an incentive scheme with rigorous analysis based on coalitional game theory is proposed.;In the distributed computing environments with untrusted parties, besides incentive issues, privacy concerns from the participants also impede the process of obtaining better computation results. To address the privacy concerns, the second part of this thesis focuses on designing privacy preserving distributed data mining protocols, when the input data comes from different parties. In particular, the first privacy preserving back-propagation learning algorithms for multi-layer neural networks with vertically partitioned data, using cryptographic tools, with provable security is proposed. Furthermore, a privacy preserving algorithm for growing neural gas with input data from two parties is also presented. This algorithm allows two parties to jointly conduct grow neural gas algorithm without revealing any party's data.