In this project, the PIs study secure computation outsourcing in cloud computing with the focus on widely applicable engineering computing and optimization problems. Their methodology is to explicitly decompose computations into public programs and private data and leverage the structures of specific computations for achieving desirable trade-offs among security, efficiency, and practicality.
The PIs propose to organize the mechanisms into a hierarchy where computation can be represented at various abstraction levels, and then explore a systematic methodology consisting of the following three methods: (1) problem transformations that encrypt the data such that the computation can be performed on the same abstraction level, (2) procedure transformations that leverage the mechanisms defined at a lower abstraction level as a subroutine for secure computation outsourcing, and (3) structural-preserving transformations that further improve the practical efficiency of mechanisms by maintaining favorable problem structures.
The PIs expect the outcomes of this research to be adopted by application developers, who will build applications to support secure computation outsourcing either privately for end-users within the same organization, or for public end-users resembling the practices of software-as-a-service (SaaS).
Cloud computing enables end-users with limited computational resources to outsource large-scale computational tasks to the cloud, where massive computational power can be economically 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 protect sensitive workload information. However, this is a very difficult task due to a number of challenges that have to be met simultaneously. Firstly, such a mechanism has to be practically feasible in terms of computational complexity. Secondly, it has to provide sound security huarantee without restricted system assumptions. Thirdly, it also has to enable substantial computational savings at the end-user's side as compared to the amount of the efforts that otherwise has to be committed to solve the problem locally. These challenges practically exclude the applicability of the existing techniques developed in the context of secure multi-party computation and fully homomorphic encryption. This project investigates secure computation outsourcing mechanisms in public cloud based on algorithmic innovations. We address the issues not only to protect sensitive workload information but to validate the integrity of the computation result. Our focus is on widely applicable engineering computing and optimization problems. By explicitly decomposing computations into public programs and private data, we leverage the structures of specific computations for achieving desirable trade-offs among security, efficiency, and practicality. We organize the mechanisms into a hierarchy where computation can be represented at various abstraction levels, and then explore a systematic methodology consisting of problem transformations that encrypt the data such that the computation can be performed on the same abstraction level; and procedure transformations that leverage the mechanisms defined at a lower abstraction level as a subroutine for secure computation outsourcing. In addition, we initiate investigations into structural-preserving transformations that maintain favorable problem structures like sparsity to futher improve the practical efficiency. Our proposed outsourcing mechanisms include secure outsourcing linear programming (LP) in cloud. For this mechanism, we explore problem transformation to protect the constraints as well as the feasible region of the LP problem via an affine mapping without introducing much overhead. To validate the computation result without redoing the LP, we further apply the fundamental duality theorem of LP computation and derive the necessary and sufficient conditions that correct result must satisfy, aiming to achieve an efficient yet robust design. We then extend the application of the duality theorem to convex optimization problems, and obtain a proof-carrying mechanism that outsources this important engineering optimization to the cloud. We further combine secure outsourcing LP with compressed sensing to build a novel outsourced image recovery service architecture on the cloud with privacy assurance that address the difficulty to manage exponentially generated large-scale image datasets. Moreover, a theorectically sound mechanism to outsource the solution of systems of linear equations (LE) to cloud is investigated leveraging procedure transformation that decomposing LE problems into lower-level matrix-vector operations. This mechanism is in turn extended to securely outsource large differential algebraic equations to the cloud, which is essential to simulate large-scale power grids for the design of reliable and robust integrated circuits. This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.