Efficient and verifiable algorithm for secure outsourcing of large-scale linear programming

Haixin Nie, Xiaofeng Chen, Jin Li, Joseph Liu, Wenjing Lou

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

21 Citations (Scopus)


Linear programming (LP) has been well studied in the scientific community for various engineering applications such as network flow problems, packet routing, portfolio optimization, and financial data management, etc. In this paper, we first utilize the sparse matrix to investigate secure outsourcing for large-scale LP systems, which is considered as a prohibitively expensive computation for the clients with resource-constraint devices. Besides, we propose a secure and practical scheme which is suitable for any LP problem (feasible, infeasible or unbounded) even in the fully malicious model. Compared with the state-of-the-art algorithm [30], our proposed algorithm only requires O(n(2)) computational overhead instead of O(n(rho)) for 2 < rho <= 3. Furthermore, the client C can detect the misbehavior of cloud server S with the (optimal) probability 1 under the computational complexity of O(n).
Original languageEnglish
Title of host publicationProceedings - 2014 IEEE/AINA 28th International Conference on Advanced Information Networking and Applications, AINA 2014
Subtitle of host publication13-16 May 2014, University of Victoria, Victoria, Canada
EditorsLeonard Barolli, Kin Fun Li, Tomoya Enokido, Fatos Xhafa, Makoto Takizawa
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages6
ISBN (Print)9781479936298
Publication statusPublished - 2014
Externally publishedYes
EventInternational Conference on Advanced Information Networking and Applications 2014 - Victoria, Canada
Duration: 13 May 201416 May 2014
Conference number: 28th
https://ieeexplore.ieee.org/xpl/conhome/6835111/proceeding (Proceedings)


ConferenceInternational Conference on Advanced Information Networking and Applications 2014
Abbreviated titleAINA 2014
Internet address

Cite this