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

Abstract

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
Pages591-596
Number of pages6
ISBN (Print)9781479936298
DOIs
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

Conference

ConferenceInternational Conference on Advanced Information Networking and Applications 2014
Abbreviated titleAINA 2014
CountryCanada
CityVictoria
Period13/05/1416/05/14

Cite this

Nie, H., Chen, X., Li, J., Liu, J., & Lou, W. (2014). Efficient and verifiable algorithm for secure outsourcing of large-scale linear programming. In L. Barolli, K. Fun Li, T. Enokido, F. Xhafa, & M. Takizawa (Eds.), Proceedings - 2014 IEEE/AINA 28th International Conference on Advanced Information Networking and Applications, AINA 2014: 13-16 May 2014, University of Victoria, Victoria, Canada (pp. 591-596). Piscataway NJ USA: IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/AINA.2014.147
Nie, Haixin ; Chen, Xiaofeng ; Li, Jin ; Liu, Joseph ; Lou, Wenjing. / Efficient and verifiable algorithm for secure outsourcing of large-scale linear programming. Proceedings - 2014 IEEE/AINA 28th International Conference on Advanced Information Networking and Applications, AINA 2014: 13-16 May 2014, University of Victoria, Victoria, Canada. editor / Leonard Barolli ; Kin Fun Li ; Tomoya Enokido ; Fatos Xhafa ; Makoto Takizawa. Piscataway NJ USA : IEEE, Institute of Electrical and Electronics Engineers, 2014. pp. 591-596
@inproceedings{007504ee7a204076be6202ad098c3f78,
title = "Efficient and verifiable algorithm for secure outsourcing of large-scale linear programming",
abstract = "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).",
author = "Haixin Nie and Xiaofeng Chen and Jin Li and Joseph Liu and Wenjing Lou",
year = "2014",
doi = "10.1109/AINA.2014.147",
language = "English",
isbn = "9781479936298",
pages = "591--596",
editor = "Barolli, {Leonard } and {Fun Li}, {Kin } and Enokido, {Tomoya } and Xhafa, {Fatos } and Takizawa, {Makoto }",
booktitle = "Proceedings - 2014 IEEE/AINA 28th International Conference on Advanced Information Networking and Applications, AINA 2014",
publisher = "IEEE, Institute of Electrical and Electronics Engineers",
address = "United States of America",

}

Nie, H, Chen, X, Li, J, Liu, J & Lou, W 2014, Efficient and verifiable algorithm for secure outsourcing of large-scale linear programming. in L Barolli, K Fun Li, T Enokido, F Xhafa & M Takizawa (eds), Proceedings - 2014 IEEE/AINA 28th International Conference on Advanced Information Networking and Applications, AINA 2014: 13-16 May 2014, University of Victoria, Victoria, Canada. IEEE, Institute of Electrical and Electronics Engineers, Piscataway NJ USA, pp. 591-596, International Conference on Advanced Information Networking and Applications 2014, Victoria, Canada, 13/05/14. https://doi.org/10.1109/AINA.2014.147

Efficient and verifiable algorithm for secure outsourcing of large-scale linear programming. / Nie, Haixin; Chen, Xiaofeng; Li, Jin; Liu, Joseph; Lou, Wenjing.

Proceedings - 2014 IEEE/AINA 28th International Conference on Advanced Information Networking and Applications, AINA 2014: 13-16 May 2014, University of Victoria, Victoria, Canada. ed. / Leonard Barolli; Kin Fun Li; Tomoya Enokido; Fatos Xhafa; Makoto Takizawa. Piscataway NJ USA : IEEE, Institute of Electrical and Electronics Engineers, 2014. p. 591-596.

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

TY - GEN

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

AU - Nie, Haixin

AU - Chen, Xiaofeng

AU - Li, Jin

AU - Liu, Joseph

AU - Lou, Wenjing

PY - 2014

Y1 - 2014

N2 - 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).

AB - 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).

U2 - 10.1109/AINA.2014.147

DO - 10.1109/AINA.2014.147

M3 - Conference Paper

SN - 9781479936298

SP - 591

EP - 596

BT - Proceedings - 2014 IEEE/AINA 28th International Conference on Advanced Information Networking and Applications, AINA 2014

A2 - Barolli, Leonard

A2 - Fun Li, Kin

A2 - Enokido, Tomoya

A2 - Xhafa, Fatos

A2 - Takizawa, Makoto

PB - IEEE, Institute of Electrical and Electronics Engineers

CY - Piscataway NJ USA

ER -

Nie H, Chen X, Li J, Liu J, Lou W. Efficient and verifiable algorithm for secure outsourcing of large-scale linear programming. In Barolli L, Fun Li K, Enokido T, Xhafa F, Takizawa M, editors, Proceedings - 2014 IEEE/AINA 28th International Conference on Advanced Information Networking and Applications, AINA 2014: 13-16 May 2014, University of Victoria, Victoria, Canada. Piscataway NJ USA: IEEE, Institute of Electrical and Electronics Engineers. 2014. p. 591-596 https://doi.org/10.1109/AINA.2014.147