基于LU分解的安全外包求解线性代数方程组方法

doi:10.12068/j.issn.1005-3026.2024.04.001

摘要/Abstract

摘要：

由于现有协议的安全性为基于某种安全假设的计算安全，依赖于敌手的计算能力，因此，本文针对恶意敌手模型，使用矩阵伪装技术对方程的系数矩阵进行隐藏，结合矩阵的LU分解（lower‐upper decomposition）算法，提出一种新的信息论安全外包求解线性代数方程组（information‐theoretically secure outsourcing of linear algebraic equations，ITS-OutsLAE）方法.与之前的研究相比，在保持计算和通信复杂度与现有最优方案保持一致的同时，首次将方程组唯一解的安全性提升至信息论安全（完美保密）.给出了形式化的安全性证明，并通过理论分析和实验证明了所提方法的实用性.

关键词: 线性代数方程组, 信息论安全, 安全外包, LU分解, 恶意敌手模型

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

中图分类号:

TP 311.1

冯达, 周福才, 吴淇毓, 李鲍. 基于LU分解的安全外包求解线性代数方程组方法[J]. 东北大学学报（自然科学版）, 2024, 45(4): 457-463.

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.

图/表 7

表1 矩阵伪装算法

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'

表1 矩阵伪装算法

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'

图1 安全计算协议架构

Fig.1 Architecture of secure computing protocol

表2 对A'的LUP分解算法

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$

表2 对A'的LUP分解算法

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$

表3 验证算法

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

表3 验证算法

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

表4 方案对比

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	√

图2 客户端算法效率测试

Fig.2 Algorithm efficiency test on the client side

图3 服务器端算法效率测试

Fig.3 Algorithm efficiency test on the server side

参考文献 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.