In this chapter we study transformation-based approaches for outsourcing some particular tasks, based on publishing and solving a transformed version of the problem instance. First, we demonstrate a number of attacks against existing transformations for privacy-preserving linear programming. Our attacks show the deficiencies of existing security definitions; we propose a stronger, indistinguishability-based definition of security of problem transformations that is very similar to IND-CPA security of encryption systems. We study the realizability of this definition for linear programming and find that barring radically new ideas, there cannot be transformations that are information-theoretically or even computationally secure. Finally, we study the possibility of achieving IND-CPA security in privately outsourcing linear equation systems over real numbers, and see that it is not as easy as for linear equations over finite fields for which it is known that efficient information-theoretically secure transformations do exist.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com