Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

8-2018

Abstract

We address overdetermined systems of linear equations, where the number of unknowns is smaller than the number of equations so that only approximate solutions exist instead of exact solutions. Such systems are prevalent in many areas of science and engineering, and finding the optimal solutions is mathematically known as the linear least squares (LLS) problem. Real-world overdetermined systems are often large-scale and computationally expensive to solve. Consequently, we are interested in connecting the LLS problem with cloud computing, where a resource-constrained client outsources the problem to a powerful but untrusted cloud. Among several security considerations is that the input of and solution to the LLS problem usually contain the client’s private information, which necessitates privacy-preserving outsourcing. In this paper, we present a construction called Sells, which employs a mathematical method called QR decomposition to solve the above problem, in a masked yet verifiable manner. One advantage of adopting QR decomposition is that in certain circumstances, solving a batch of LLS problems only requires fully executing Sells once, where certain intermediate result can be reused and the overall efficiency is greatly improved. Theoretical analysis shows that our proposal is verifiable, recoverable, and privacy-preserving. Experiments demonstrate that a client can benefit from the scheme not only reduced computation cost but also accelerated problem solving.

Keywords

linear equations, overdetermined system, linear least squares, cloud computing, verifiable outsourcing, privacy preservation, secure computation, data outsourcing, computational integrity, privacy-enhancing technologies

Discipline

Databases and Information Systems | Information Security

Publication

Proceedings of the 14th International Conference, SecureComm 2018, Singapore, August 8-10

Volume

254

First Page

529

Last Page

548

ISBN

9783030017002

Identifier

10.1007/978-3-030-01701-9_29

Publisher

Springer

City or Country

Cham

Comments

Cited by: 5

Additional URL

https://doi.org/10.1007/978-3-030-01701-9_29

Download

Share

COinS