Second Priority Ideas Blog

Another Approach for Enforcing Honesty

Long time, no post, but I have been enjoying some very nice vacations and also I hate to sacrifice quality. In a previous post I already presented an approach for enforcing honesty in privacy-preserving computation. The idea was to verify the input against some public information. Now someone has proven that this idea can be incentive-compatible in a special setting. In "Incentive Compatible Distributed Data Mining" Kantarcioglu and Nix propose to share some input data with a trusted provider. This provider then uses this data to check errors (deviations) in the computed result and accordingly charges the participants. The paper actually received the best paper award at IEEE PASSAT 2010 and it deserved to do so.

Let's recap: every party shares some fraction of his input with a trustworthy party. This party checks the securely computed result against the collected data and detects deviations. Now, my follow-up question would be: How much data do I have to share? The paper does not yet answer this question. And, I fear that there is an evil trade-off. Assume I share very little information, then I can only barely detect deviations and cheaters may escape. Assume I share most of the information, then I can reliably detect information, but then what's the point of the secure computation? I now have a trusted third party that simply could compute the result for me - no more secure computation.

Let x be the maximum error the shared data may tolerate, what is the error y if I compute solely on the shared data. It would be interesting to draw a graph for x and y. This could be solved analytically or empirically. The result could be very surprising, because it could either strongly support the idea or completely destroy it. Again, it's a question of time for me - or better against me - and I hope that someone will pick up the idea. In the mean time I am happy that my proposal for enforcing honesty does not rely on such a trade-off and can be solely computed as part of the secure protocol.