The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Secure and practical outsourcing of linear programming in cloud computing
Abstract
Cloud computing enables customers with limited computational resources to outsource large-scale computational tasks to the cloud, where massive computational power can be easily utilized in a pay-per-use manner. However, security is the major concern that prevents the wide adoption of computation outsourcing in the cloud, especially when end-user's confidential data are processed and produced during the computation. Thus, secure outsourcing mechanisms are in great need to not only protect sensitive information by enabling computations with encrypted data, but also protect customers from malicious behaviors by validating the computation result. Such a mechanism of general secure computation outsourcing was recently shown to be feasible in theory, but to design mechanisms that are practically efficient remains a very challenging problem. Focusing on engineering computing and optimization tasks, this paper investigates secure outsourcing of widely applicable linear programming (LP) computations. In order to achieve practical efficiency, our mechanism design explicitly decomposes the LP computation outsourcing into public LP solvers running on the cloud and private LP parameters owned by the customer. The resulting flexibility allows us to explore appropriate security/efficiency tradeoff via higher-level abstraction of LP computations than the general circuit representation. In particular, by formulating private data owned by the customer for LP problem as a set of matrices and vectors, we are able to develop a set of efficient privacy-preserving problem transformation techniques, which allow customers to transform original LP problem into some random one while protecting sensitive input/output information. To validate the computation result, we further explore the fundamental duality theorem of LP computation and derive the necessary and sufficient conditions that correct result must satisfy. Such result verification mechanism is extremely efficient and incurs close-to-zero additional cost on both cloud server and customers. Extensive security analysis and experiment results show the immediate practicability of our mechanism design.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
Shamir, A. (1979) · Communications of the ACM · doi:10.1145/359168.359176 · Cited by 13,756
Grossman, P. (2009) · Discrete Mathematics for Computing · doi:10.1007/978-0-230-37405-8_1 · Cited by 8,834
Public-Key Cryptosystems Based on Composite Degree Residuosity Classes
Paillier, P. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_16 · Cited by 7,250
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806
Linear and nonlinear programming.
(1986) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(86)90092-3 · Cited by 4,805
Linear and Nonlinear Programming
Luenberger, D. G., & Ye, Y. (2008) · International Series in Operations Research & Management Science · doi:10.1007/978-0-387-74503-9 · Cited by 2,804
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509
Matrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1990) · Journal of Symbolic Computation · doi:10.1016/s0747-7171(08)80013-2 · Cited by 2,248
Introduction to algorithms [2nd ed.]
Cormen, T. H. (2001) · Cited by 1,911
Achieving Secure, Scalable, and Fine-grained Data Access Control in Cloud Computing
Yu, S., Wang, C., Ren, K., & Lou, W. (2010) · 2010 Proceedings IEEE INFOCOM · doi:10.1109/infcom.2010.5462174 · Cited by 1,602
Self-citationA Randomized Protocol for Signing Contracts
Even, S., Goldreich, O., & Lempel, A. (1983) · Advances in Cryptology · doi:10.1007/978-1-4757-0602-4_19 · Cited by 1,450
Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers
Gennaro, R., Gentry, C., & Parno, B. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_25 · Cited by 1,145
Secure Ranked Keyword Search over Encrypted Cloud Data
Wang, C., Cao, N., Li, J., Ren, K., & Lou, W. (2010) · 2010 IEEE 30th International Conference on Distributed Computing Systems · doi:10.1109/icdcs.2010.34 · Cited by 732
Self-citationComputing arbitrary functions of encrypted data
Gentry, C. (2010) · Communications of the ACM · doi:10.1145/1666420.1666444 · Cited by 650
Matrix multiplication via arithmetic progressions
Coppersmith, D., & Winograd, S. (1987) · Proceedings of the nineteenth annual ACM conference on Theory of computing - STOC '87 · doi:10.1145/28395.28396 · Cited by 632
Gaussian Elimination is not Optimal
Trassen, V. (2005) · Cited by 454
Secure multi-party computation problems and their applications: a review and open problems
Du, W., & Atallah, M. J. (2001) · Proceedings of the 2001 workshop on New security paradigms · doi:10.1145/508171.508174 · Cited by 453
How to Securely Outsource Cryptographic Computations
Hohenberger, S., & Lysyanskaya, A. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30576-7_15 · Cited by 361
Secure outsourcing of scientific computations
Atallah, M. J., Pantazopoulos, K. N., Rice, J. R., & Spafford, E. E. (2002) · Advances in Computers · doi:10.1016/s0065-2458(01)80019-x · Cited by 266
Securely outsourcing linear algebra computations
Atallah, M. J., & Frikken, K. B. (2010) · Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security · doi:10.1145/1755688.1755695 · Cited by 263
Uncheatable Distributed Computations
Golle, P., & Mironov, I. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-45353-9_31 · Cited by 256
Private and Cheating-Free Outsourcing of Algebraic Computations
Benjamin, D., & Atallah, M. J. (2008) · 2008 Sixth Annual Conference on Privacy, Security and Trust · doi:10.1109/pst.2008.12 · Cited by 176
Secure outsourcing of sequence comparisons
Atallah, M. J., & Li, J. (2005) · International Journal of Information Security · doi:10.1007/s10207-005-0070-3 · Cited by 154
Secure and Private Collaborative Linear Programming
Li, J., & Atallah, M. J. (2006) · International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom) · doi:10.1109/colcom.2006.361848 · Cited by 61
Solving Linear Programs Using Multiparty Computation
Toft, T. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03549-4_6 · Cited by 50
A Secure Revised Simplex Algorithm for Privacy-Preserving Linear Programming
Vaidya, J. S. (2009) · International Conference on Advanced Information Networking and Applications (AINA) · doi:10.1109/aina.2009.133 · Cited by 29
Cited by
Security Challenges for the Public Cloud
Ren, K., Wang, C., & Wang, Q. (2012) · IEEE Internet Computing · doi:10.1109/mic.2012.14 · Cited by 845
Self-citationExtreme Learning Machines [Trends & Controversies]
Cambria, E., Huang, G.-B., Kasun, L. L. C., Zhou, H., Vong, C. M., Lin, J., Yin, J., Cai, Z., Liu, Q., Li, K., et al. (2013) · IEEE Intelligent Systems · doi:10.1109/mis.2013.140 · Cited by 710
Security and Privacy in Cloud Computing
Xiao, Z., & Xiao, Y. (2013) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2012.060912.00182 · Cited by 596
Security and privacy for storage and computation in cloud computing
Wei, L., Zhu, H., Cao, Z., Dong, X., Jia, W., Chen, Y., & Vasilakos, A. V. (2014) · Information Sciences · doi:10.1016/j.ins.2013.04.028 · Cited by 516
Secure attribute-based data sharing for resource-limited users in cloud computing
Li, J., Zhang, Y., Chen, X., & Xiang, Y. (2018) · Computers & Security · doi:10.1016/j.cose.2017.08.007 · Cited by 461
Metadata
- Authors
- Wang, C., Ren, K., & Wang, J.
- Venue
- 2011 Proceedings IEEE INFOCOM
- Publisher
- IEEE
- Published
- 2011-04
- Pages
- 820-828
- OpenAlex
- W2145166073
- Cited by
- 312
- References
- 28
- FWCI
- 22.83
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.