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

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

doi:10.1109/AINA.2014.147

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 proceeding › Conference Paper › Research › peer-review

19 Citations (Scopus)

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 language	English
Title of host publication	Proceedings - 2014 IEEE/AINA 28th International Conference on Advanced Information Networking and Applications, AINA 2014
Subtitle of host publication	13-16 May 2014, University of Victoria, Victoria, Canada
Editors	Leonard Barolli, Kin Fun Li, Tomoya Enokido, Fatos Xhafa, Makoto Takizawa
Place of Publication	Piscataway NJ USA
Publisher	IEEE, Institute of Electrical and Electronics Engineers
Pages	591-596
Number of pages	6
ISBN (Print)	9781479936298
DOIs	https://doi.org/10.1109/AINA.2014.147
Publication status	Published - 2014
Externally published	Yes
Event	International Conference on Advanced Information Networking and Applications 2014 - Victoria, Canada Duration: 13 May 2014 → 16 May 2014 Conference number: 28th https://ieeexplore.ieee.org/xpl/conhome/6835111/proceeding (Proceedings)

Conference

Conference	International Conference on Advanced Information Networking and Applications 2014
Abbreviated title	AINA 2014
Country/Territory	Canada
City	Victoria
Period	13/05/14 → 16/05/14
Internet address	https://ieeexplore.ieee.org/xpl/conhome/6835111/proceeding (Proceedings)

Access to Document

10.1109/AINA.2014.147

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). IEEE, Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/AINA.2014.147

Nie, Haixin ; Chen, Xiaofeng ; Li, Jin et al. / 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",

note = "International Conference on Advanced Information Networking and Applications 2014, AINA 2014 ; Conference date: 13-05-2014 Through 16-05-2014",

url = "https://ieeexplore.ieee.org/xpl/conhome/6835111/proceeding",

}

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, British Columbia, 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 et al.

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 proceeding › Conference Paper › Research › peer-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

N1 - Conference code: 28th

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

T2 - International Conference on Advanced Information Networking and Applications 2014

Y2 - 13 May 2014 through 16 May 2014

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