TY - JOUR

T1 - Weave elgamal encryption for secure outsourcing algebraic computations over p

AU - Chen, Yi Ruei

AU - Shen, Shiuan Tzuo

AU - Tzeng, Wen-Guey

PY - 2017/1/1

Y1 - 2017/1/1

N2 - This paper addresses the secure outsourcing problem for large-scale matrix computation to a public cloud. We propose a novel public-key weave ElGamal encryption (WEE) scheme for encrypting a matrix over the fieldp. The scheme has the echelon transformation property. We can apply a series of elementary row/column operations to transform an encrypted matrix under our WEE scheme into the row/column echelon form. The decrypted result matches the result of the corresponding operations performed on the original matrix. For security, our WEE scheme is shown to be entry irrecoverable for non-zero entries under the computational Diffie-Hellman assumption. By using our WEE scheme, we propose five secure outsourcing protocols of Gaussian elimination, Gaussian-Jordan elimination, matrix determinant, linear system solver, and matrix inversion. Each of these protocols preserves data privacy for clients (data owners). Furthermore, the linear system solver and matrix inversion protocols provide a cheating-resistant mechanism to verify correctness of computation results. Our experimental result shows that our protocols gain efficiency significantly for an outsourcer. Our outsourcing protocol solves a linear system of n = 1,000 equations and m = 1,000 unknown variables about 472 times faster than a non-outsourced version. The efficiency gain is more substantial when (n, m) gets larger. For example, when n = 10,000 and m = 10,000, the protocol can solve it about 56,274 times faster. Our protocols can also be easily implemented in parallel computation architecture to get more efficiency improvement.

AB - This paper addresses the secure outsourcing problem for large-scale matrix computation to a public cloud. We propose a novel public-key weave ElGamal encryption (WEE) scheme for encrypting a matrix over the fieldp. The scheme has the echelon transformation property. We can apply a series of elementary row/column operations to transform an encrypted matrix under our WEE scheme into the row/column echelon form. The decrypted result matches the result of the corresponding operations performed on the original matrix. For security, our WEE scheme is shown to be entry irrecoverable for non-zero entries under the computational Diffie-Hellman assumption. By using our WEE scheme, we propose five secure outsourcing protocols of Gaussian elimination, Gaussian-Jordan elimination, matrix determinant, linear system solver, and matrix inversion. Each of these protocols preserves data privacy for clients (data owners). Furthermore, the linear system solver and matrix inversion protocols provide a cheating-resistant mechanism to verify correctness of computation results. Our experimental result shows that our protocols gain efficiency significantly for an outsourcer. Our outsourcing protocol solves a linear system of n = 1,000 equations and m = 1,000 unknown variables about 472 times faster than a non-outsourced version. The efficiency gain is more substantial when (n, m) gets larger. For example, when n = 10,000 and m = 10,000, the protocol can solve it about 56,274 times faster. Our protocols can also be easily implemented in parallel computation architecture to get more efficiency improvement.

KW - Cloud computing

KW - Data privacy

KW - Linear algebra

KW - Linear system

KW - Secure outsourcing

UR - http://www.scopus.com/inward/record.url?scp=85050031957&partnerID=8YFLogxK

U2 - 10.6688/JISE.2017.33.1.14

DO - 10.6688/JISE.2017.33.1.14

M3 - Article

AN - SCOPUS:85050031957

VL - 33

SP - 233

EP - 250

JO - Journal of Information Science and Engineering

JF - Journal of Information Science and Engineering

SN - 1016-2364

IS - 1

ER -