Comment on Two schemes for Secure Outsourcing of Linear Programming
This work exposes fundamental errors in existing secure outsourcing methods for linear programming, which is incremental as it critiques rather than proposes new solutions.
The authors identified a critical flaw in two prior schemes for secure outsourcing of linear programming, showing that the proposed form is unsolvable and meaningless because it misinterprets essential constraints, leading to failure of both schemes.
Recently, Wang et al. [IEEE INFOCOM 2011, 820-828], and Nie et al. [IEEE AINA 2014, 591-596] have proposed two schemes for secure outsourcing of large-scale linear programming (LP). They did not consider the standard form: minimize c^{T}x, subject to Ax=b, x>0. Instead, they studied a peculiar form: minimize c^{T}x, subject to Ax = b, Bx>0, where B is a non-singular matrix. In this note, we stress that the proposed peculiar form is unsolvable and meaningless. The two schemes have confused the functional inequality constraints Bx>0 with the nonnegativity constraints x>0 in the linear programming model. But the condition x>0 is indispensable to the simplex method. Therefore, both two schemes failed.