How to Securely and Efficiently Solve the Large-Scale Modular System of Linear Equations on the Cloud

Cloud-assisted computation empowers resource-constrained clients to efficiently tackle computationally intensive tasks by outsourcing them to resource-rich cloud servers. In the current era of Big Data, the widespread need to solve large-scale modular linear systems of equations ( <tex-math notation="LaTeX">LMLSE</tex-math> ) of the form <tex-math notation="LaTeX">Ax≡ b q</tex-math> poses a significant challenge, particularly for lightweight devices. This paper delves into the secure outsourcing of <tex-math notation="LaTeX">LMLSE</tex-math> under a malicious single-server model and, to the best of our knowledge, introduces the inaugural protocol tailored to this specific context. The cornerstone of our protocol lies in the innovation of a novel matrix encryption method based on sparse unimodular matrix transformations. This novel technique bestows our protocol with several key advantages. First and foremost, it ensures robust privacy for all computation inputs, encompassing <tex-math notation="LaTeX">A,b, q</tex-math> , and the output <tex-math notation="LaTeX">x</tex-math> , as validated by thorough theoretical analysis. Secondly, the protocol delivers optimal verifiability, enabling clients to detect cloud server misbehavior with an unparalleled probability of 1. Furthermore, it boasts high efficiency, requiring only a single interaction between the client and the cloud server, significantly reducing local-client time costs. For an <tex-math notation="LaTeX">m</tex-math> -by- <tex-math notation="LaTeX">n</tex-math> matrix <tex-math notation="LaTeX">A</tex-math> , a given parameter <tex-math notation="LaTeX">λ =ω (log q)</tex-math> , and <tex-math notation="LaTeX">ρ =2.371552</tex-math> , the time complexity is diminished from <tex-math notation="LaTeX">O(max m nρ -1, mρ -2 n² · (log q)²)</tex-math> to <tex-math notation="LaTeX">O((mn+m²)λ log q+mn(log q)²)</tex-math> . The comprehensive results of our experimental performance evaluations substantiate the protocol's practical efficiency and effectiveness.