安全高效的可验证大型线性方程组求解外包计算方案

doi:10.11959/j.issn.2096-109x.2017.00161

网络与信息安全学报 ›› 2017, Vol. 3 ›› Issue (6): 1-7.doi: 10.11959/j.issn.2096-109x.2017.00161

• 学术论文 • 下一篇

安全高效的可验证大型线性方程组求解外包计算方案

张兴兰,刘祥

北京工业大学信息学部，北京 100124

修回日期:2017-03-26 出版日期:2017-06-01 发布日期:2017-06-21
作者简介:张兴兰（1970-），女，山西吕梁人，博士，北京工业大学教授，主要研究方向为密码学和安全协议。|刘祥（1990-），男，河南焦作人，北京工业大学硕士生，主要研究方向密码学和外包计算。
基金资助:
国家自然科学基金资助项目(61272044)

Secure efficient and verifiable large linear equations solve outsourcing computing scheme

Xing-lan ZHANG,Xiang LIU

Faculty of Information Technology,Beijing University of Technology,Beijing 100124,China

Revised:2017-03-26 Online:2017-06-01 Published:2017-06-21
Supported by:
The National Natural Science Foundation of China(61272044)

摘要/Abstract

摘要：

针对目前大型线性方程组求解在外包计算中遇到的用户信息泄露、计算结果被篡改等问题，提出一种安全高效的可验证外包计算方案。通过随机置换和线性方程组的恒等变换，构造了新的具备相似解的线性方程组，避免了当前数据伪装方案易受求解公因式法攻击的问题，同时提高了客户端的验证效率，降低了空间复杂度。性能分析表明，该方案具有极高的效率。

关键词: 云外包计算, 解线性方程组, 可验证性

Abstract:

A secure,efficient and verifiable outsourcing computation scheme was proposed based on the current problems of leaking users information and tampering with the calculating results,which were encountered while solving large-scale linear equations in outsourcing computation.A new linear equation with similarity solutions was constructed based on the constant transformation between random permutation and linear equations.It avoids the problem that the current data camouflage scheme is easily attacked by solving common factor method.It also improves the verification effciency and reduces the complexity of space.The performance analysis shows that the scheme is highly efficient.

Key words: outsourcing cloud computing, solving linear equations, verifiability

中图分类号:

TP309.7

张兴兰,刘祥. 安全高效的可验证大型线性方程组求解外包计算方案[J]. 网络与信息安全学报, 2017, 3(6): 1-7.

Xing-lan ZHANG,Xiang LIU. Secure efficient and verifiable large linear equations solve outsourcing computing scheme[J]. Chinese Journal of Network and Information Security, 2017, 3(6): 1-7.

图/表 3

图1

表1

本文协议与相关文献的协议性能比较"

文献	获取输入数据概率	获取输出数据概率	计算复杂度	验证效率
文献[12]	${(\frac{1}{n!})}^{2} {(\frac{1}{q^{n}})}^{2}$	${(\frac{1}{n!})}^{2} {(\frac{1}{q^{n}})}^{2}$	O(n ²)	O (n)
文献[13]	${(\frac{1}{n!})}^{2} {(\frac{1}{q^{n}})}^{2}$	${(\frac{1}{n!})}^{2} {(\frac{1}{q^{n}})}^{2}$	O(n ²)	O(n ²)
文献[14]	${(\frac{1}{n!})}^{2} {(\frac{1}{q^{n}})}^{2}$	${(\frac{1}{n!})}^{2} {(\frac{1}{q^{n}})}^{2}$	O(n ²)	O(n ²)
本文	$\frac{1}{{[(m + t)!]}^{2}} \frac{1}{{[(n + t)!]}^{2}} \frac{1}{q^{m + l + 1}}$	$\frac{1}{(n + t)!} \frac{1}{q^{2}}$	O(n ²)	O (n)

表1

图2

参考文献 14

[1]	冯登国, 张敏, 张妍 ,等. 云计算安全研究[J]. 软件学报, 2011,22(1): 71-83.
	FENG D G , ZHANG M , ZHANG Y ,et al. Study on cloud computing security[J]. Journal of Software, 2011,22(1): 71-83.
[2]	SHAMIR A . How to share a secret[J]. Communications of the ACM, 1979,22(11): 612-613.
[3]	WANG C , REN K . Secure and practical outsourcing of linear programming in cloud computing[C]// IEEE Infocom. 2011: 820-828.
[4]	任艳丽, 谷大武, 蔡建兴 ,等. 隐私保护的可验证多元多项式外包计算方案[J]. 通信学报, 2015,36(8): 23-30.
	REN Y L , GU D W , CAI J X ,et al. Verifiably private outsourcing scheme for multivariate polynomial evaluation[J]. Journal on Communications, 2015,36(8): 23-30.
[5]	WANG C , REN K , WANG J ,et al. Harnessing the cloud for securely solving large-scale systems of linear equations[C]// The 31st International Conference on Distributed Computing Systems. 2011: 549-558.
[6]	FIORE D , GENNARO R . Publicly verifiable delegation of large polynomials and matrix computations,with applications[C]// ACM Conference on Computer and Communications Security. 2012: 501-512.
[7]	邬国欣 . 矩阵运算可验证安全外包计算协议的研究[D]. 西安:西安电子科技大学, 2014.
	WU G X . On verifiable and secure outsourcing protocols for matrix operations[D]. Xi'an:Xidian University, 2014.
[8]	ATALLAH M , FRIKKEN K . Securely outsourcing linear algebra computations[C]// ACM Symposium on Information,Computer and Communications Security. 2010: 48-59.
[9]	ATALLAH M J , PANTAZOPOULOS K N , RICE J R ,et al. Secure outsourcing of scientific computations[J]. Adv Comput, 2001,54(1): 216-272.
[10]	ATALLAH M J , FRIKKEN K . Securely outsourcing linear algebra computations[C]// The 5th ACM Symposium on Information,Computer and Communications Security. 2010: 48-59.
[11]	PAYMAN M . Efficient and secure delegation of linear algebra[J]. IACR Cryptology Eprint Archive, 2011: 1-33.
[12]	胡杏, 裴定一, 唐春明 ,等. 可验证安全外包矩阵计算及其应用[J]. 中国科学:信息科学, 2013,43(7): 842-852.
	HU X , PEI D Y , TANG C M ,et al. Verifiable and secure outsourcing of matrix calculation and its application[J]. Scientia Sinca Informationis, 2013,43(7): 842-852.
[13]	CHEN X , HUANG X , LI J ,et al. New algorithms for secure outsourcing of large-scale systems of linear equations[J]. IEEE Trans on Information Forensics and Security, 2015,10(1): 69-78.
[14]	蔡建兴, 任艳丽 . 大型线性方程组求解的可验证外包算法[J]. 计算机应用研究, 2017(2).
	CAI J X , REN Y L . Verifiable outsourcing algorithm for large-scale systems of linear equations[J]. Application Research of Computers, 2017(2).

安全高效的可验证大型线性方程组求解外包计算方案

Secure efficient and verifiable large linear equations solve outsourcing computing scheme

在线阅读

pdf下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 14

相关文章 1

Metrics

推荐阅读 0