基于LU分解的安全外包求解线性代数方程组方法
Secure Outsourcing Method for Solving Linear Algebraic Equations Based on LU Decomposition
冯达 1周福才 1吴淇毓 1李鲍1
作者信息
- 1. 东北大学 软件学院,辽宁 沈阳 110169
- 折叠
摘要
由于现有协议的安全性为基于某种安全假设的计算安全,依赖于敌手的计算能力,因此,本文针对恶意敌手模型,使用矩阵伪装技术对方程的系数矩阵进行隐藏,结合矩阵的LU分解(lower-upper decomposition)算法,提出一种新的信息论安全外包求解线性代数方程组(information-theoretically secure outsourcing of linear algebraic equations,ITS-OutsLAE)方法.与之前的研究相比,在保持计算和通信复杂度与现有最优方案保持一致的同时,首次将方程组唯一解的安全性提升至信息论安全(完美保密).给出了形式化的安全性证明,并通过理论分析和实验证明了所提方法的实用性.
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.
关键词
线性代数方程组/信息论安全/安全外包/LU分解/恶意敌手模型Key words
linear algebraic equations/information-theoretic security/secure outsourcing/LU decomposition/malicious adversarial model引用本文复制引用
基金项目
国家自然科学基金(62072090)
国家自然科学基金(62202090)
国家自然科学基金(62173101)
辽宁省自然科学基金医工交叉联合基金(2022-YGJC-24)
中央高校基本科研业务费专项(N2217009)
出版年
2024
NETL
NSTL
万方数据