高效低存储开销可验证外包求解大规模线性方程组方案

冯达; 周福才; 王强; 吴淇毓

doi:10.7544/issn1000-1239.2019.20180191

高效低存储开销可验证外包求解大规模线性方程组方案

(东北大学软件学院沈阳 110169) (dfengneu@gmail.com)

基金项目: 国家自然科学基金项目(61772127,61472184)；国家科技重大专项基金项目(2013ZX03002006)；辽宁省科技攻关项目(2013217004)；中央高校基本科研业务费专项资金项目(N151704002)

详细信息

中图分类号: TP309
计量
- 文章访问数: 1100
- HTML全文浏览量: 2
- PDF下载量: 308
出版历程
- 发布日期: 2019-04-30

Efficient Verifiable Outsourcing of Solving Large-Scale Linear Equations with Low Storage Overhead

(Software College, Northeastern University, Shenyang 110169)

摘要

摘要: 针对外包求解大规模线性方程组问题，在完全恶意模型中提出一种新的高效低存储开销可验证外包求解大规模线性方程组(efficient verifiable outsourcing of solving large-scale linear equations with low storage overhead, EVLE-LS)方案.首先利用严格对角优势矩阵和伪随机数生成器，构造了伪随机可逆稀疏矩阵生成算法.又将该算法与稀疏矩阵对稠密矩阵的编码解码过程相结合，给出了新的外包线性方程组方案.该方案只需要用户与服务器进行一轮交互，用户检测出云服务器的恶意行为的概率为1，实现完全可验证.此外，与之前已有的需要昂贵存储开销的方案相比，该方案在保证安全性的前提下将用户所需存储开销降到了常数级.最后将方案与其他3种方案进行对比，说明该方案在效率、可验证性和存储开销方面均优于已有方案.
- 云计算 /
- 安全外包 /
- 线性方程组 /
- 严格对角优势矩阵 /
- 伪随机数生成器
Abstract: This paper studies the secure outsourcing problem of large-scale linear equations, and proposes a new secure outsourcing scheme of large-scale linear equations in the fully malicious model. First, we construct a pseudo-random invertible sparse matrix generation algorithm involving pseudo-random number generator and the property of strictly diagonally dominant matrix. Then we combine this algorithm with the process of encoding/decoding dense matrix with sparse matrix and give the new outsourcing scheme. The client in our scheme only needs 1 round interaction with the server and can detect the misbehavior of the server with an overwhelming probability (fully verifiable). In addition, compared with the previous schemes which require expensive storage overhead, our scheme reduces the overhead of storage to a constant level for the first time. We give the theoretical proof of the correctness, privacy and unforgeability of our scheme. Besides, the scheme can successfully handle the equations with no solution with enough privacy in our model. We compare the scheme with others and indicate the proposed scheme is superior to the existing ones in terms of efficiency, verifiability and storage overhead and finally provide the experimental evaluation that demonstrates the efficiency of our algorithms and the storage overhead the client needs.
- cloud computing /
- secure outsourcing /
- linear equations /
- strictly diagonally dominant matrix /
- pseudo-random number generator

HTML全文

参考文献(0)

施引文献(14)

期刊类型引用(7)

1.	魏波，冯乃勤. 基于入侵诱骗的网络拓扑污染攻击防御研究. 计算机仿真. 2024(05): 410-414 . 百度学术
2.	金柯君，于洪涛，吴翼腾，李邵梅，张建朋，郑洪浩. 改进的基于奇异值分解的图卷积网络防御方法. 计算机应用. 2023(05): 1511-1517 . 百度学术
3.	宋国顺. 基于特征加权聚合的传感网络多模式攻击检测方法. 通化师范学院学报. 2023(10): 74-80 . 百度学术
4.	金柯君，于洪涛，李邵梅，张建朋. 基于注意力机制的图卷积网络防御方法. 信息工程大学学报. 2023(06): 718-724 . 百度学术
5.	刘勇. 基于图算法的定向越野数据智能分析系统设计. 自动化与仪器仪表. 2022(08): 159-164 . 百度学术
6.	张瑾，朱桂祥，王宇琛，郑烁佳，陈镜潞. 基于异质图表达学习的跨境电商推荐模型. 电子与信息学报. 2022(11): 4008-4017 . 百度学术
7.	吴翼腾，刘伟，于洪涛. 图神经网络的标签翻转对抗攻击. 通信学报. 2021(09): 65-74 . 百度学术