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

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

作　　者：冯达 周福才[1] 吴淇毓 李鲍 FENG Da;ZHOU Fu-cai;WU Qi-yu;LI Bao(School of Software,Northeastern University,Shenyang 110169,China)

机构地区：[1]东北大学软件学院,辽宁沈阳110169

出　　处：《东北大学学报（自然科学版）》2024年第4期457-463,506,共8页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(62072090,62202090,62173101);辽宁省自然科学基金医工交叉联合基金资助项目(2022-YGJC-24);中央高校基本科研业务费专项资金资助项目(N2217009)。

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

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

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]