February 2010

Enforcing Honesty in Privacy-Preserving Computation

It's been some time since my recent post. The topic this time is honesty in privacy-preserving computation. Homomorphic encryption or secure multi-party computation allows a number of parties to compute a function on their joint input without revealing anything but the result. This can be very useful to implement mechanisms that would not be implementable without privacy. A typical is supply chain management where companies can combine their planning without revealing sensitive information, such as production costs or capacities. A fundamental problem is that there is no technique to force anyone to provide the honest input. No one can check the data, since it is encrypted and any revelation would contradict the idea of encrypting it in the first place. This can be detrimental, since if that participant can gain an advantage by lying, he might be inclined to lie destroying the mechanism. The ideal way to circumvent this to make the mechanism truth-inducing or provide fair benefits, but apparently this cannot always be done. So here my second priority idea: We implement the honesty check as another secure computation. Each party provides bounds on the other parties input, e.g. the production cost of my supplier may not be higher than the price I am paying and not lower than the prices its suppliers are charging him. Both pieces of information are known to parties other than the one inputting the cost. We can also use statistics. E.g. the distribution of production costs should correspond to the distribution of the average time the goods spend at that organization. Two questions remain: Does this lead to a truth inducing mechanism or at least limit the spectrum of the equilibrium ? Does this change the security requirements for the secure computation ? No one wants to implement the malicious security model.