Usable and Efficient Secure Multiparty Computation

We have considered Linear Programming (LP), a versatile tool for solving various polynomial-time optimization problems. For privacy-preserving LP, there have been two approaches so far. One of them is to implement an LP solution algorithm directly, using privacy-preserving primitive operations. The other one is based on problem transformation: scramble the initial problem, make the scrambled LP public, solve it, and descramble the solution. The first approach has stronger and cleaner privacy properties, while the second approach is much more efficient.

We have investigated the second approach, trying to come of with methods that combine the good aspects of both approaches. We have concluded that finding such a scrambling method is impossible, at least when restricting oneselves to affine transformations, which also all previous proposals have done. Moreover, we have found serious weaknesses in previous proposals that have been overlooked so far.

Currently, the viability of the entire approach is questionable. Our suggestion is to look for LP solution algorithms that are as efficient as possible when implemented using privacy-preserving primitive operations.