《表1 协议中各阶段的计算量》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《一种高效安全外包求解大型模线性系统的算法》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

LSMLE协议是高效的。设MM，MA分别表示模q剩余类环Zq中乘法运算与加法运算，SW表示交换操作。在非外包情况下，用户自己求解Ax≡bmodq需要的计算量为O（nσ）MM+O(n3）MA，（2<σ≤3），在外包的情况下，各阶段的计算量如下：在密钥生成阶段，用户需要生成稀疏矩阵和置换矩阵，需要O(n）交换操作。加密阶段，A'=UP1AP2V=U1…UnP1AP2V1…Vn，b'=UP1b=U1…UnP1b，由于矩阵乘法满足结合律并且Ui与Vi的非零元素均为1或-1，因此该阶段不需要做乘法运算，只需要O(n3）MA，同理，验证与解密阶段计算量也是O（n3）MA，综上可知，本地端仅需要O（n3）MA的计算量就可以完成计算任务。表1展示了用户在外包方案中各个阶段的计算量。