Securely Outsourcing Linear Algebra Computations

摘要

We give improved protocols for the secure and private out sourcing of linear algebra computations, that enable a client to securely outsource expensive algebraic computations (like the multiplication of large matrices) to a remote server, such that the server learns nothing about the customer's private input or the result of tim computation, and any attempted corruption of the answer by the server is detected with high probability. The computational work performed at the client is lincar in the size of its input and does not require the client to locally carry out any expensive encryptions of such input. The computational burden on the server is proportional to the time complexity of the current practically used algo rithms for solving the algebraic problem (e.g., proportional to n3 for multiplying two n×n matrices). The improvements we give are: (i) whereas the previous work required more than one remote server and assumed they do not collude, our solution works with a single server (but readily accommo dates many, for improved performance); (ii) whereas the pre vious work required a server to carry out expensive crypto graphic computations (e.g., homomorphic encryptions), our solution does not make use of any such expensive crypto graphic primitives; and (iii) whereas in previous work collu sion by the servers against the client revealed to them the client's inputs, our scheme is resistant to such collusion, As in previous work, we maintain the property that the scheme enables the client to detect any attempt by the server(s) at corruption of the answer, even when the attempt is collusive and coordinated among the servers.