An efficient and tunable matrix-disguising method toward privacy-preserving computation

摘要

A matrix is a basic mathematical object that is widely used in various computations. When outsourcing expensive computations to untrusted parties, the involved matrix must be disguised before it's sent out in order to protect the privacy information in it. Some research works on secure computation had presented schemes for protecting the privacy in matrices. However, none of these schemes is defined deliberately for disguising a matrix and thus is neither highly efficient nor flexible. We propose a matrix-disguising method named FMD (fast matrix disguising) that has high time and space efficiency and can tune the trade-off between disguising speed and protecting strength with a parameter. FMD disguises a matrix by multiplying it with a semi-random non-singular matrix which is compose of many bar-shaped sub-matrices. Each of these sub-matrices contains a row/column of random elements with almost the same values. This special matrix structure allows FMD to disguise the original matrix with time complexity proportional to the size of the original matrix. While by adjusting the bar size of the sub-matrices, FMD can smoothly tune between high-disguising speed and high-privacy protection strength. The mathematical analysis and experimental results show that FMD is more efficient than the existing schemes and is especially suitable for resource-limited clients in privacy-preserving computation outsourcing scenarios. Copyright (c) 2015John Wiley & Sons, Ltd.