| In this dissertation, I study privacy, integrity, and incentive compatibility in computations with untrusted parties. The study of privacy and integrity belongs to the research area of secure multi-party computation , while incentive compatibility is a natural extension of the research on secure multi-party computation.; First, I present a mix network tailored for election systems, with a substantial speedup over previous work. Second, I design and analyze efficient algorithms for distributed mining of association rules. Third, to protect data integrity in an untrusted storage service, I study the possibility of entangling multiple users' data together in such a way that loss of one user's data implies loss of all others'. Fourth, I introduce VDOT, a new cryptographic primitive, which can be viewed as an extension of oblivious transfer with malicious servers. I also apply VDOT to the problem of mobile-agent security to implement the key components of an architecture for mobile agents.; Finally, I propose a way to add incentive considerations to the study of secure multi-party computation, by stimulating cooperation among selfish mobile nodes in an ad hoc network. I propose Sprite, a simple, cheat-proof, credit-based system for accomplishing this task. The system suppresses cheating behavior and provides incentives for mobile nodes to cooperate and report actions honestly. Simulations and analysis show that mobile nodes can cooperate and forward each other's messages, unless the resources of each node are extremely depleted. |
