大型线性方程组求解的可验证外包算法-计算机应用研究.PDF

第３４卷第２期 计 算 机 应 用 研 究 Ｖｏｌ３４Ｎｏ２ 　 　 ２０１７年２月　 ＡｐｐｌｉｃａｔｉｏｎＲｅｓｅａｒｃｈｏｆＣｏｍｐｕｔｅｒｓ Ｆｅｂ．２０１７ 大型线性方程组求解的可验证外包算法 蔡建兴，任艳丽 （上海大学通信与信息工程学院，上海２００４４４） 摘　要：随着云计算的发展，可验证的外包计算受到了越来越多的关注。对普通用户来说，大型线性方程组的 求解是一个困难问题，可通过外包计算进行解决。现有的大型线性方程组外包求解方案计算效率较低或计算结 果无法完全验证。提出了一个可验证的大型线性方程组求解的外包计算协议。在完全保护用户隐私的前提下， 所提方案大大提高了用户的计算效率。与同类方案相比，所提方案降低了用户的计算代价，且用户可以完全验 证服务器的外包计算结果。实验表明，所提方案用户的计算时间远小于直接计算所用的时间，且小于服务器的 计算时间。 关键词：云计算；外包计算；可验证；大型线性方程组 中图分类号：ＴＰ３０９２　　　文献标志码：Ａ　　　文章编号：１００１３６９５（２０１７）０２０５３６０３ ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１００１３６９５．２０１７．０２．０４８ Ｖｅｒｉｆｉａｂｌｅｏｕｔｓｏｕｒｃｉｎｇａｌｇｏｒｉｔｈｍｆｏｒｌａｒｇｅｓｃａｌｅ ｓｙｓｔｅｍｓｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓ  ＣａｉＪｉａｎｘｉｎｇ，ＲｅｎＹａｎｌｉ （ＳｃｈｏｏｌｏｆＣｏｍｍｕｎｉｃａｔｉｏｎ＆ＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＳｈａｎｇｈａｉＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２００４４４，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｗｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｃｌｏｕｄｃｏｍｐｕｔｉｎｇ，ｖｅｒｉｆｉａｂｌｅｏｕｔｓｏｕｒｃｉｎｇｃｏｍｐｕｔａｔｉｏｎａｒｅｇｅｔｔｉｎｇｍｏｒｅａｎｄｍｏｒｅａｔｔｅｎｔｉｏｎｓ． Ｆｏｒｏｒｄｉｎａｒｙｕｓｅｒｓ，ｔｈｅｌａｒｇｅｓｃａｌｅｓｙｓｔｅｍｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓｉｓａｄｉｆｆｉｃｕｌｔｐｒｏｂｌｅｍ．Ｉｔｃａｎｂｅｓｏｌｖｅｄｔｈｒｏｕｇｈｏｕｔｓｏｕｒｃｉｎｇｃｏｍｐｕ ｔａｔｉｏｎ．Ｔｈｅｏｕｔｓｏｕｒｃｉｎｇｓｃｈｅｍｅｆｏｒｌａｒｇｅｓｃａｌｅｓｙｓｔｅｍｓｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓａｌｗａｙｓｈａｓａｌｏｗｃｏｍｐｕｔａｔｉｏｎａｌｅｆｆｉｃｉｅｎｃｙｏｒｃａｎ’ｔｂｅ ｆｕｌｌｙｖｅｒｉｆｉａｂｌｅｎｏｗａｄａｙｓ．Ｔｈｉｓｐａｐｅｒｐｒｏｐｏｓｅｄａｖｅｒｉｆｉａｂｌｅｏｕｔｓｏｕｒｃｉｎｇｐｒｏｔｏｃｏｌｆｏｒｌａｒｇｅｓｃａｌｅｓｙｓｔｅｍｓｏｆｌｉｎｅａｒｅｑｕａｔｉｏｎｓ．Ｔｈｅ ｐｒｏｐｏｓｅｄｐｒｏｔｏｃｏｌｇｒｅａｔｌｙｉｍｐｒｏｖｅｄｔｈｅｕｓｅｒ’ｓｃｏｍｐｕｔａｔｉｏｎａｌｅｆｆｉｃｉｅｎｃｙｗｈｅｎｆｕｌｌｙｐｒｏｔｅｃｔｕｓｅｒｐｒｉｖａｃｙ．Ｃｏｍｐａｒｅｄｗｉｔｈｔｈｅ ｓｔａｔｅｏｆｔｈｅａｒｔｓｃｈｅｍｅｓ，ｔｈｅｐｒｏｐｏｓｅｄｓｃｈｅｍｅｒｅｄｕｃｅｄｕｓｅｒｃｏｍｐｕｔａｔｉｏｎａｌｃｏｓｔ，ａｎｄｕｓｅｒｃｏｕｌｄｆｕｌｌｙｖｅｒｉｆｙｔｈｅｃｏｍｐｕｔａｔｉｏｎｒｅ ｓｕｌｔｏｕｔｐｕｔｆｒｏｍｓｅｒｖｅｒ．Ｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｕｓｅｒｃｏｍｐｕｔｉｎｇｔｉｍｅｉｓｆａｒｌｅｓｓｔｈａｎｄｉｒｅｃｔｃａｌｃｕｌａｔｉｏｎｔｉｍｅ，ａｎｄｌｅｓｓｔｈａｎｔｈｅ ｃｏｍｐｕｔａｔｉｏｎｔｉｍｅｏｆｔｈｅｓｅｒｖｅｒ． Ｋｅｙ