Secure Outsourcing Method for Solving Linear Algebraic Equations Based on LU Decomposition

doi:10.12068/j.issn.1005-3026.2024.04.001

Abstract

Abstract:

All existing protocols are computationally secure， each of which is based on a certain security assumption and depends on the computational power of the adversary.This paper uses the matrix masking technique to hide the coefficient matrix.Combined with the LU（lower‐upper） decomposition algorithm， a new information‐theoretically secure outsourcing of linear algebraic equations method is proposed in malicious adversarial model.Compared with the previous protocol， the security of the unique solution is improved to information‐theoretic security （perfect secrecy） for the first time， without sacrificing the complexity of computation and communication.A formal security proof is provided， and the practicality is proved theoretically and experimentally.

Key words: linear algebraic equations, information?theoretic security, secure outsourcing, LU decomposition, malicious adversarial model

CLC Number:

TP 311.1

Da FENG, Fu-cai ZHOU, Qi-yu WU, Bao LI. Secure Outsourcing Method for Solving Linear Algebraic Equations Based on LU Decomposition[J]. Journal of Northeastern University(Natural Science), 2024, 45(4): 457-463.

Figures/Tables 7

Table 1 Matrix masking algorithm

Algorithm：

M a s k i n g (k, A, b) → (A', b')

Input：k， $A, b$

Output： $A', b'$

1 Compute $A' = D 1 ? (P π ? A) ? D 2$

2 Compute $b' = D 1 ? (P π ? b)$

3 Output

A', b'

Table 1 Matrix masking algorithm

Algorithm：

M a s k i n g (k, A, b) → (A', b')

Input：k， $A, b$

Output： $A', b'$

1 Compute $A' = D 1 ? (P π ? A) ? D 2$

2 Compute $b' = D 1 ? (P π ? b)$

3 Output

A', b'

Fig.1 Architecture of secure computing protocol

Table 2 LUP decomposition algorithm for A'

Algorithm:

L U P (A') → (L, U, P L U)

Input: $A'$

Output: $L, U, P L U$

1 Initialize $U = A', L = I, P L U = I$

2 forj = 1 : n - 1 do

3 Select i （ ≥ j ） that maximizes |u_ij |

4 Interchange rows of $U : u (j, j : n) ? u (i, j : n)$

5 Interchange rows of $L : l (j, 1 : (j - 1)) ? l (i, 1 : (j - 1))$

6 Interchange rows of $P L U$ $: p (j, :) ? p (i, :)$

7 fori = j + 1 do

8 $l i j = u i j / u j j$

9 fork = j : ndo

10 $u i k = u i k - l i j u j k$

11 end for

12 end for

13 end for

14 Output $L, U, P L U$

Table 2 LUP decomposition algorithm for A'

Algorithm:

L U P (A') → (L, U, P L U)

Input: $A'$

Output: $L, U, P L U$

1 Initialize $U = A', L = I, P L U = I$

2 forj = 1 : n - 1 do

3 Select i （ ≥ j ） that maximizes |u_ij |

4 Interchange rows of $U : u (j, j : n) ? u (i, j : n)$

5 Interchange rows of $L : l (j, 1 : (j - 1)) ? l (i, 1 : (j - 1))$

6 Interchange rows of $P L U$ $: p (j, :) ? p (i, :)$

7 fori = j + 1 do

8 $l i j = u i j / u j j$

9 fork = j : ndo

10 $u i k = u i k - l i j u j k$

11 end for

12 end for

13 end for

14 Output $L, U, P L U$

Table 3 Verification algorithm

Algorithm:

V e r i f y (L, U, P L U, A') → 1 ? o r ? 0

Input: $L, U, P L U, A'$

Output: 1 or 0

1 Initialize c = 1

2 Compute $A'' = P L U A'$

3 fori = 1 : ndo

4 Randomly pick s indices $j 1 ≠ j 2 ∈ {1, …, n}$

5 if （ $∑ k = 1 n l i k u k j 1 ≠ a'' i j 1$ or $∑ k = 1 n l i k u k j 2 ≠ a'' i j 2$ ）

6 c = 0

7 break

8 end if

9 end for

10 Outputc

Table 3 Verification algorithm

Algorithm:

V e r i f y (L, U, P L U, A') → 1 ? o r ? 0

Input: $L, U, P L U, A'$

Output: 1 or 0

1 Initialize c = 1

2 Compute $A'' = P L U A'$

3 fori = 1 : ndo

4 Randomly pick s indices $j 1 ≠ j 2 ∈ {1, …, n}$

5 if （ $∑ k = 1 n l i k u k j 1 ≠ a'' i j 1$ or $∑ k = 1 n l i k u k j 2 ≠ a'' i j 2$ ）

6 c = 0

7 break

8 end if

9 end for

10 Outputc

Table 4 Comparisons with prior protocols

方法	外包类型	计算复杂度	通信复杂度	安全性	可验证性
文献[11]	分布式代理节点	O（n²）	O（n²）	COA	√
文献[15]	云计算服务器	O（n²）	O（n²）	COA	√
ITS-OutsLAE	云计算服务器	O（n²）	O（n²）	COA + ITS	√

Fig.2 Algorithm efficiency test on the client side

Fig.3 Algorithm efficiency test on the server side

References 18

1	Strang G.Introduction to linear algebra［M］.5th ed.Wellesley：Wellesley‐Cambridge Press，2021.
2	Benzi M.Preconditioning techniques for large linear systems：a survey［J］.Journal of Computational Physics，2002，182（2）：418-477.
3	Grcar J F.How ordinary elimination became Gaussian elimination［J］.Historia Mathematica，2011，38（2）：163-218.
4	Gong Z M， Aldeen M， Elsner L.A note on a generalized Cramer’s rule［J］.Linear Algebra and Its Applications，2002，340（1/2/3）：253-254.
5	Qian L， Luo Z G， Du Y J，et al.Cloud computing：an overview［C］//IEEE International Conference on Cloud Computing. Berlin：Springer，2009：626-631.
6	Marston S， Li Z， Bandyopadhyay S，et al.Cloud computing the business perspective［J］.Decision Support Systems，2011，51（1）：176-189.
7	Nandgaonkar S V， Raut A B.A comprehensive study on cloud computing［J］.International Journal of Computer Science and Mobile Computing，2014，3：733-738.
8	Margaris A， Souravlas S， Roumeliotis M.Parallel implementations of the Jacobi linear algebraic systems solve［J］.ArXiv Preprint ArXiv，2014：1403.5805.
9	Mou S S， Liu J， Morse A S.A distributed algorithm for solving a linear algebraic equation［J］.IEEE Transactions on Automatic Control，2015，60（11）：2863-2878.
10	Wang L L， Fullmer D， Morse A S.A distributed algorithm with an arbitrary initialization for solving a linear algebraic equation［C］//2016 American Control Conference （ACC）.Boston：IEEE，2016：1078-1081.
11	Feng D， Zhou F C， He D B，et al.Secure distributed outsourcing of large‑scale linear systems［C］//2022 IEEE 42nd International Conference on Distributed Computing Systems （ICDCS）.Bologna：IEEE，2022：1110-1121.
12	Gennaro R， Gentry C， Parno B.Non‑interactive verifiable computing：outsourcing computation to untrusted workers［C］//Annual Cryptology Conference.Berlin，Heidelberg：Springer，2010：465-482.
13	Goldwasser S， Kalai Y T， Rothblum G N.Delegating computation：interactive proofs for muggles［C］//Proceeding of the 40th ACM Symposium on Theory of Computing （STOC）.New York：ACM，2008：113-122.
14	Benabbas S， Gennaro R， Vahlis Y.Verifiable delegation of computation over large datasets［C］//LNCS 6841：Advances in Cryptology.Berlin：Springer，2011：111-131.
15	Chen F， Xiang T， Yang Y Y.Privacy‑preserving and verifiable protocols for scientific computation outsourcing to the cloud［J］.Journal of Parallel and Distributed Computing，2014，74（3）：2141-2151.
16	Chen X F， Huang X Y， Li J，et al. New algorithms for secure outsourcing of large‑scale systems of linear equations［J］.IEEE Transactions on Information Forensics and Security，2015，10（1）：69-78.
17	Zhao L， Chen L Q.Sparse matrix masking‑based non‑interactive verifiable （outsourced） computation，revisited［J］.IEEE Transactions on Dependable and Secure Computing，2020，17（6）：1188-1206.
18	Shannon C E. Communication theory of secrecy systems［J］.The Bell System Technical Journal，1949，28（4）：656-715.