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

摘要

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

关键词

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