法律状态公告日
法律状态信息
法律状态
2019-09-03
授权
授权
2019-05-21
实质审查的生效 IPC(主分类):G06F17/16 申请日:20190109
实质审查的生效
2019-04-26
公开
公开
技术领域
本发明属于云计算技术领域，具体涉及一种高效求解大尺度矩阵行列式的可验证外包计算方法、客户端及云计算系统。
背景技术
云计算的概念一经提出，就受到了广泛的关注。云计算将计算分布在大量的分布式计算机上，而非本地计算机或远程服务器中。一方面，云计算提供了强大的计算能力，使客户免去了购买和维护设备之苦；另一方面，云可以使用极其廉价的节点构造云，云的通用性使资源利用率大幅提升。然而，随着云计算的快速发展，相关的安全问题成为了一大难题。同态加密是一种有效的手段，但就目前来看，其效率较低，难以投入到实际使用中来。
外包计算是云计算中的重要应用，通过云计算，客户端将计算密集型任务托付给计算能力强大的云。大尺度矩阵行列式(即大规模矩阵行列式)的计算是一种对计算能力要求很高的计算，其计算复杂度为Ο(n3)，在矩阵的尺寸n很大时，计算会变得很繁杂，然而它在科研、通讯、工程等领域都是一个经常性的问题。外包计算的出现可以帮助客户快捷且方便地解决该难题。然而，在利用外包计算方式来解决大尺度矩阵行列式计算前，有两个至关重要的问题需要解决：(1)客户端应当能够知道自己得到的结果是否正确。即一方面，硬件的故障或者软件的漏洞可能导致计算结果错误；另一方面，敌对的或者自私的服务端可能会有意将错误注入到计算中，或者发送回一个似乎正确的结果，来减少对计算资源的使用。(2)另一个关键的问题是数据的隐私性。即用户的数据可能是敏感且贵重的，但在外包计算过程中，这些数据的输入和结果的输出会被对方出于好奇或者有预谋地获得。比如一些公司的商业机密，或者研究所内重要的观察数据，云端可以将这些信息卖给客户的竞争对手，或者存储起来以备后用。这些都属于外包计算的隐私性问题。虽然正确性与隐私性对外包计算至关重要，隐私对个体和商业公司来说，更是至关重要的问题。
基于上面的两个问题，一个能够保护客户数据隐私、可验证结果和高效率的大尺度矩阵行列式外包计算协议就显得尤为重要。目前针对矩阵行列式的外包计算协议主要有以下几种。
(1)2014年版协议，该协议在2014年由任晓霞等人提出，协议的威胁模型(其一般可分为两种：半诚实模型和恶意模型，目的在于将来自云计算服务器等的威胁模型化；半诚实模型——云计算服务器会忠实地执行协议，计算客户的需求，但是它会记录所有的信息，并以此来推测出客户的隐私信息；另外，云计算服务器自身也有被攻击和窃取信息的可能；恶意模型——可以不遵从协议的规定，云计算服务器甚至可以任意发送一个值作为计算结果来节省自己的计算资源，同时不希望客户检测到)是半诚实模型，协议利用了置换函数，对原矩阵进行盲化加密(任晓霞，黄宏宇，《安全高效的大矩阵行列式计算云外包协议.计算机工程与应用》，2014，50(10)，82-86)。所述2014年版协议的子算法如下：(a)密钥生成算法KeyGen(1λ)→K,P；(b)问题产生算法(即论文中的加密算法Enc，可以理解为对要外包的问题进行保密)ProbGen(X,K,P)→Y；(c)矩阵计算算法DCSol(Y)→det(Y)；(d)解密算法Dec(det(Y))→det(X)。
所述2014年版协议的实现过程如下：假设明文矩阵X∈Rn×n，置换函数利用柯西的两行表示法，可以表示为：
首先，客户端调用密钥生成算法，随机产生密钥空间K＝{a1,···an}，以及一个随机的置换函数P；然后，客户端调用问题产生算法，根据K和P，产生一个矩阵M，
所述2014年版协议确实实现了外包协议可对密文进行可控有意义的操作，也达到了减少用户计算量的目的:M的行列式的值可以很简单地由下式算出：
(2)2015年甲版协议，该协议于2015年由申银杰提出，大致是对2014年版协议的改进，该协议中对矩阵的加密利用了两次置换函数，并加入验证机制(申银杰，《可验证的安全矩阵行列式计算云外包协议.计算机与现代化》，2015年第5期，103-106)。
所述2015年甲版协议的子算法构成仅在2014年版协议的基础上加入了验证算法，这里不再赘述。
所述2015年甲版协议的原理和2014年版协议基本相同，但做出了很多改进，在隐私性上有了提升，同时加入了验证算法。该协议的大致框架如下：首先，客户端调用密钥生成算法，随机产生密钥空间K＝{a1,···an}，{b1,···bn}，{c1,···cn}，{d1,···dn}以及四个随机的置换函数P1,P2,P3,P4；然后，客户端调用问题产生算法，产生四个矩阵
所述2015年甲版协议在2014年版协议的基础上，加强了问题产生算法的隐私性，并加入了对云服务器返回的结果的检测机制，虽然增加了本地的计算量，但依旧很好地达到了外包计算协议的初衷。但是，该协议的加密环节依旧相对薄弱，对于用户的隐私保护不够强(Shaojing Fu,Yunpeng Yu,Ming Xu,《Practical Privacy-Preserving Outsourcingof Large-Scale Matrix Determinant Computation in the Cloud》,In Proceedings of3rd International Conference on Cloud Computing and Security-ICCCS 2017,LNCS10603,Springer,Pages:3-15,2017)。
(3)2015年乙版协议，该协议于2015年由廖晓峰等人提出，主要思想是将矩阵作为一个更大的矩阵的子矩阵放入其中，之后利用置换函数对大矩阵进行加密，其威胁模型为恶意云模型和半诚实模型(Xinyu Lei,Xiaofeng Liao,Tingwen Huang,Huaqing Li,《Cloud Computing Service:The Case of Large Matrix Determinant Computation》,IEEE Transactions on Services Computing,Pages:688-700,Volume:8,Issue:5,Sept./Oct.2015)。
在介绍所述2015年乙版协议前，介绍一条引理：
Lemma1:考虑矩阵A∈Rn×n,B∈Rm×n,C∈Rm×m，那么有：
所述2015年乙版协议的子算法包括如下：
(a)密钥生成算法keyGen：输入加密参数κ，该参数指定了一个正整数m和三个密钥空间，其中的元素随机取得：{α1,α2…,αm}←Kα，{β1,β2…,βm+n}←Kβ,{γ1,γ2…,γm+n}←Kγ，三个密钥空间均不包括0；矩阵B∈Rm×n，B内的元素0个数随机在{0，1，2，····nm}；产生两个置换函数π1,π2；
(b)问题产生算法ProbGen：客户端构造对角矩阵D＝diag(α1,α2…,αm)，
(c)计算算法DCsol:与前面协议要求云端直接返回行列式值不同，该协议要求云端返回Y的上三角矩阵U和下三角矩阵L。这两个矩阵满足Y＝LU；
(d)解密算法Dec：客户端计算：
(e)验证算法Ver:客户端首先生成一个向量r∈(n+m)×1，其元素在{0，1}内随机选择；计算：W＝L×(Ur)-Y×r；如果(W≠(0,…0)T)，那么说明计算有误，拒绝接受该结果。该过程重复l次，若结果均是W＝(0,…0)T，那么客户接受该计算结果。
所述2015年乙版协议首先是将明文矩阵放入一个更大的矩阵T中，之后对T进行置换操作，并乘以一个因子对原矩阵进行加密，以获得更佳的加密效果。在验证手段上，该协议采用了概率性的验证算法，在运算l次后，验证算法出错的概率
(4)2017年版协议，该协议于2017年由徐明等人提出，所述2017年版协议与2015年乙版协议的思路大致相同，即将明文矩阵放在一个大尺寸的矩阵中，但并非用置换函数进行加密，而是利用一个稀疏的随机矩阵进行加密。该协议的威胁模型同样是恶意云模型和半诚实模型。
所述2017年版协议的子算法大致如下：
(a)密钥生成算法KeyGen(κ)→Kα,m,b1,…,bm,c1,c2,…,cm,s1,…,sm：输入加密参数κ，客户端生成密钥空间{α1,α2…，αm}←Kα，一个正整数m，以及3m个向量：b1,b2,…,bm∈Rn×1，c1,c2,…,cm∈Rm×1，s1,s2,…,sm∈Rn×1,g1,…,gm∈Rm×1；
(b)问题产生算法(即论文中的加密算法Enc，可以理解为对要外包的问题进行保密)ProbGen(Kα,m,b1,…,bm,c1,c2,…,cm,s1,…,sm)→Y：客户端构造对角矩阵D＝diag(d1,d2…,dm)，计算X”＝XD；构造矩阵
(c)计算算法DCSol(Y)→L,U:算法要求云端返回Y的上三角矩阵U和下三角矩阵L。这两个矩阵满足Y＝LU；
(d)解密算法Dec(L,U)→det(X)：计算：
C和G矩阵的尺寸m×m＜＜n×n；
(e)验证算法与2015年乙版协议的验证算法相同，这里不再赘述。
所述2017年版协议作为2015年乙版协议的改进版，解决了2015年乙版协议中存在的可能会泄露用户明文矩阵的0元素的个数的问题(当然，隐私性不如2015年乙版协议的2014年版协议和2015年甲版协议也显然存在着这种问题)。验证算法的随机性依旧是不足的地方，本地的计算量也较前者增加了。
以上就是目前的几种针对大尺度矩阵行列式计算的外包计算协议，可以看到，目前几种协议的加密手段是使用置换函数或者利用一个更大的稀疏矩阵进行加密，然而使用置换函数对矩阵的基本行列变换加密性不足，会泄露矩阵的结构信息。因此，前述2014年版协议、2015年甲版协议和2015年乙版协议在使用中均存在风险，尤其是前两种协议，加密手段单一，隐私性不足；在验证手段上，前述2017年版协议的验证算法又具有随机性。总之，目前的相关协议都或多或少地存在着问题和不足。
发明内容
为了解决现有关于大尺度矩阵行列式的外包计算协议在隐私性、正确性、高效性和可验证性方面所存在的不足问题，本发明目的在于提供一种高效求解大尺度矩阵行列式的可验证外包计算方法、客户端及云计算系统。
本发明所采用的技术方案为：
一种高效求解大尺度矩阵行列式的可验证外包计算方法,包括如下步骤：
S101.生成密钥矩阵集{A1,A2,…,Ax,…,Aξ}和{B1,B2,…,Bx,…,Bξ}，其中，密钥矩阵Ax和Bx分别为具有n*n个元素的非奇异方阵，密钥矩阵Ax中的主对角线元素或副对角线元素为随机正整数，密钥矩阵Bx中的主对角线元素或副对角线元素为随机正整数，密钥矩阵Ax中的第d列元素和密钥矩阵Bx中的第d行元素分别为随机非零实数，密钥矩阵Ax和Bx中其余元素为零，n为不小于1000的正整数，ξ为不小于3的正整数，x为不大于ξ的正整数，d为不大于n的随机正整数；
S102.在导入具有n*n个元素的且为非奇异矩阵的明文矩阵X后，按照如下步骤S201～S202对所述明文矩阵X进行加密：
S201.根据所述明文矩阵X生成验证矩阵集{X2,X3,…,Xy,…,Xξ}，其中，验证矩阵Xy的元素除第m行元素或第m列元素之外与所述明文矩阵X相同，并在数组[((X2)m)k,((X3)m)k,…,((Xy)m)k,…,((Xξ)m)k]中仅有一个元素与(Xm)k相同，其余元素为零，(Xy)m和Xm分别为所述验证矩阵Xy和所述明文矩阵X中的第m行元素或(Xy)m和Xm分别为所述验证矩阵Xy和所述明文矩阵X中的第m列元素，((Xy)m)k和(Xm)k分别为(Xy)m和Xm中的第k个元素，y为大于1且不大于ξ的正整数，m,k分别为不大于n的随机正整数；
S202.针对所述明文矩阵X及各个验证矩阵Xy，分别按照如下公式进行加密，得到加密矩阵集{Y1,Y2,…,Yy,…,Yξ}：
S103.将所述加密矩阵集{Y1,Y2,…,Yy,…,Yξ}上传至云计算服务器，并在经过外包计算方式的云计算后，获取对应的行列式值集{det(Y1),det(Y2),…,det(Yz),…,det(Yξ)}，其中，det(Yz)为对应加密矩阵Yz的行列式值，z为不大于ξ的正整数；
S104.按照如下公式得到所述明文矩阵X及各个验证矩阵Xy的行列式值：
S105.验证det(X)是否等于det(X2)+det(X3)+…+det(Xy)+…+det(Xξ)，若等于则接受所述明文矩阵X的行列式值为det(X)，否则拒绝接受。
优化的，在所述步骤S101中，按照如下(1)或(2)方式确定密钥矩阵Ax中的元素，以及按照如下(3)或(4)方式确定密钥矩阵Bx中的元素：
(1)：
(2)：
(3)：
(4)：
式中，Oij为密钥矩阵Ax或密钥矩阵Bx中的第i行第j列元素，Ran为针对元素Oij而随机产生的非零实数，δ为克罗内克函数，cp为随机正整数列Kc:{c1,c2,…,cp,…,cλ}中的元素，i和j分别为不大于n的正整数，λ为不小于3且远小于
进一步优化的，参数Ran为将参数i+j导入随机算法后产生的随机非零实数。
进一步优化的，在所述步骤S202之前还包括如下步骤：
S301.根据所述明文矩阵X生成非零元素列值数列Kr:{r1,r2,…,rq,…,rλ}，其中，rq为在所述明文矩阵X中第cq行内某个非零元素的对应列值，cq为所述随机正整数列Kc中的第q个元素，q为不大于λ的正整数；
S302.针对各个密钥矩阵Bx，将第cp行与第rq行互换，得到新的非奇异方阵，其中，cp为在所述随机正整数列Kc中随机选择的一个元素，rq为在所述非零元素列值数列Kr中随机选择的一个元素。
具体的，在所述步骤S301中，按照如下方式确定所述非零元素列值数列Kr:{r1,r2,…,rq,…,rλ}中的各个元素rq：
将在所述明文矩阵X中第cq行内第一个非零元素的对应列值确定为rq，或者将在所述明文矩阵X中第cq行内随机一个非零元素的对应列值确定为rq。
进一步优化的，参数ξ为输入的或随机产生的正整数；和/或，参数λ为将输入参数κ导入随机算法后产生的随机正整数。
优化的，在所述步骤S103之前还包括如下步骤：将所述加密矩阵集{Y1,Y2,…,Yy,…,Yξ}的排列顺序随机置乱。
优化的，在所述步骤S104中，按照如下公式求得det(Ax)和det(Bx)：
式中，{a1,a2,…an-λ}为密钥矩阵Ax中仅主对角线元素或副对角线元素为非零元素的行列序号集合，{b1,b2,…bn-λ}为密钥矩阵Bx中仅主对角线元素或副对角线元素为非零元素的行列序号集合，{d1,d2,…dλ}为密钥矩阵Ax和Bx中整行元素或整列元素为非零元素的行列序号集合，i为不大于n的正整数，λ为不小于3且远小于
本发明所采用的另一种技术方案为：
一种用于实现前述可验证外包计算方法的客户端，包括密钥生成模块、问题产生模块、收发模块、解密模块和验证模块，其中，所述问题产生模块包括验证矩阵生成单元和矩阵加密单元；
所述密钥生成模块，用于生成密钥矩阵集{A1,A2,…,Ax,…,Aξ}和{B1,B2,…,Bx,…,Bξ}，其中，密钥矩阵Ax和Bx分别为具有n*n个元素的非奇异方阵，密钥矩阵Ax和Bx中的主对角线元素分别为随机非零实数或密钥矩阵Ax和Bx中的副对角线元素分别为随机非零实数，密钥矩阵Ax中的第d列元素和密钥矩阵Bx中的第d行元素分别为随机非零实数，密钥矩阵Ax和Bx中其余元素为零，n为不小于1000的正整数，ξ为不小于3的正整数，x为不大于ξ的正整数，d为不大于n的随机正整数；
所述问题产生模块通信连接所述密钥生成模块，用于在导入具有n*n个元素的且为非奇异矩阵的明文矩阵X后，对所述明文矩阵X进行加密；
所述验证矩阵生成单元，用于根据所述明文矩阵X生成验证矩阵集{X2,X3,…,Xy,…,Xξ}，其中，验证矩阵Xy的元素除第m行元素或第m列元素之外与所述明文矩阵X相同，并在数组[((X2)m)k,((X3)m)k,…,((Xy)m)k,…,((Xξ)m)k]中仅有一个元素与(Xm)k相同，其余元素为零，(Xy)m和Xm分别为所述验证矩阵Xy和所述明文矩阵X中的第m行元素或(Xy)m和Xm分别为所述验证矩阵Xy和所述明文矩阵X中的第m列元素，((Xy)m)k和(Xm)k分别为(Xy)m和Xm中的第k个元素，y为大于1且不大于ξ的正整数，m,k分别为不大于n的随机正整数；
所述矩阵加密单元分别通信连接所述明文矩阵分解单元，用于针对所述明文矩阵X及各个验证矩阵Xy，分别按照如下公式进行加密，得到加密矩阵集{Y1,Y2,…,Yy,…,Yξ}：
所述收发模块通信连接所述问题产生模块，用于将所述加密矩阵集{Y1,Y2,…,Yy,…,Yξ}上传至云计算服务器，并在经过云计算后获取对应的行列式值集{det(Y1),det(Y2),…,det(Yz),…,det(Yξ)}，其中，det(Yz)为对应加密矩阵Yz的行列式值，z为不大于ξ的正整数；
所述解密模块分别通信连接所述收发模块和所述密钥生成模块，用于按照如下公式得到所述明文矩阵X及各个验证矩阵Xy的行列式值：
所述验证模块通信连接所述解密模块，用于验证det(X)是否等于det(X2)+det(X3)+…+det(Xy)+…+det(Xξ)，若等于则接受所述明文矩阵X的行列式值为det(X)，否则拒绝接受。
本发明所采用的另一种技术方案为：
一种云计算系统，包括云计算服务器和如前所述的客户端；
所述云计算服务器通信连接所述客户端的收发模块，用于在收到加密矩阵集{Y1,Y2,…,Yy,…,Yξ}后，通过外包计算方式，云计算得到对应的行列式值集{det(Y1),det(Y2),…,det(Yz),…,det(Yξ)}，并将云计算结果反馈给所述收发模块。
本发明的有益效果为：
(1)本发明创造提供了一种针对求解大尺度矩阵行列式的新外包计算协议，可使拥有较少计算资源/计算能力弱的客户端在面临求解大尺度矩阵行列式时(尤其是针对大尺度稠密矩阵对应的行列式计算)，可以将整个行列式的计算任务外包给计算能力强大的云计算服务器，并提供有给客户端可靠的验证方法，从而满足当前在隐私性(云侧不可得知明文矩阵的数据)、正确性(在云侧是半诚实模型或恶意模型时，依然能够保证客户端能够检测返回结果是否正确)、高效性(客户端计算量远小于计算明文矩阵行列式所需的计算量)和可验证性(能够确定地而非以某个不可忽略的概率得出服务器所返结果的正确与否)等方面的要求，便于实际应用和推广。
(2)所述可验证外包计算方法的加密/解密框架与传统的加密协议框架不同，即问题产生算法和验证算法都是在客户端进行的，没有传统加密协议框架中较慢的公钥交换过程，效率高且安全，并保证了按次交付的灵活性。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1是本发明提供的可验证外包计算方法的流程示意图。
图2是本发明提供的实现可验证外包计算方法的客户端结构示意图。
图3是本发明提供的云计算系统的结构示意图。
具体实施方式
下面结合附图及具体实施例对本发明作进一步阐述。在此需要说明的是，对于这些实施例方式的说明用于帮助理解本发明，但并不构成对本发明的限定。
本文中术语“和/或”，仅仅是一种描述关联对象的关联关系，表示可以存在三种关系，例如，A和/或B，可以表示：单独存在A，单独存在B，同时存在A和B三种情况，本文中术语“/和”是描述另一种关联对象关系，表示可以存在两种关系，例如，A/和B，可以表示：单独存在A，单独存在A和B两种情况，另外，本文中字符“/”，一般表示前后关联对象是一种“或”关系。
实施例一
如图1所示，本实施例提供的所述高效求解大尺度矩阵行列式的可验证外包计算方法，包括如下步骤。
S101.生成密钥矩阵集{A1,A2,…,Ax,…,Aξ}和{B1,B2,…,Bx,…,Bξ}，其中，密钥矩阵Ax和Bx分别为具有n*n个元素的非奇异方阵，密钥矩阵Ax中的主对角线元素或副对角线元素为随机正整数，密钥矩阵Bx中的主对角线元素或副对角线元素为随机正整数，密钥矩阵Ax中的第d列元素和密钥矩阵Bx中的第d行元素分别为随机非零实数，密钥矩阵Ax和Bx中其余元素为零，n为不小于1000的正整数，ξ为不小于3的正整数，x为不大于ξ的正整数，d为不大于n的随机正整数。
在所述步骤S101中，优化的，参数ξ为输入的或随机产生的正整数，其可由用户在客户端操作界面上输入得到，典型取值为ξ＝3。n为待计算明文矩阵X以及密钥矩阵Ax和Bx的维数，密钥矩阵Ax和Bx的矩阵元素可分别举例如下：
或者，
由于密钥矩阵Ax和Bx分别为具有n*n个元素的非奇异方阵，具有行列式不为0的特点，即det(Ax)≠0和det(Bx)≠0，可以满足后续步骤S104的计算需求。
在所述步骤S101中，优化的，可以但不限于按照如下(1)或(2)方式确定密钥矩阵Ax中的元素，以及按照如下(3)或(4)方式确定密钥矩阵Bx中的元素：
(1)：
(2)：
(3)：
(4)：
式中，Oij为密钥矩阵Ax或密钥矩阵Bx中的第i行第j列元素，Ran为针对元素Oij而随机产生的非零实数，δ为克罗内克函数，cp为随机正整数列Kc:{c1,c2,…,cp,…,cλ}中的元素，i和j分别为不大于n的正整数，λ为不小于3且远小于
S102.在导入具有n*n个元素的且为非奇异矩阵的明文矩阵X后，按照如下步骤S201～S202对所述明文矩阵X进行加密。其中，所述明文矩阵X可由用户在客户端操作界面上直接输入或从其它设备导出得到，由于参数n为不小于1000的正整数，所述明文矩阵X即为大尺度矩阵或大规模矩阵，若直接计算矩阵行列式的值，将需要很高的计算能力，其计算复杂度为Ο(nn3)，矩阵尺寸n越大，计算越繁杂。
S201.根据所述明文矩阵X生成验证矩阵集{X2,X3,…,Xy,…,Xξ}，其中，验证矩阵Xy的元素除第m行元素或第m列元素之外与所述明文矩阵X相同，并在数组[((X2)m)k,((X3)m)k,…,((Xy)m)k,…,((Xξ)m)k]中仅有一个元素与(Xm)k相同，其余元素为零，(Xy)m和Xm分别为所述验证矩阵Xy和所述明文矩阵X中的第m行元素或(Xy)m和Xm分别为所述验证矩阵Xy和所述明文矩阵X中的第m列元素，((Xy)m)k和(Xm)k分别为(Xy)m和Xm中的第k个元素，y为大于1且不大于ξ的正整数，m,k分别为不大于n的随机正整数。
在所述步骤S201中，由于对所述明文矩阵X中的其他行或列，不做分解，由此可使所述明文矩阵X与所有验证矩阵Xy具有如下关系：det(X)＝det(X2)+det(X3)+…+det(Xy)+…+det(Xξ)。
S202.针对所述明文矩阵X及各个验证矩阵Xy，分别按照如下公式进行加密，得到加密矩阵集{Y1,Y2,…,Yy,…,Yξ}：
在所述步骤S204中，以ξ＝3为例，可以得到如下加密矩阵集{Y1,Y2,Y3}：
Y1＝A1XB1,Y2＝A2X2B2,Y3＝A3X3B3。
在所述步骤S202之前，还可以根据所述明文矩阵X对密钥矩阵进行修正，优化的，还包括如下步骤S301～S302。
S301.根据所述明文矩阵X生成非零元素列值数列Kr:{r1,r2,…,rq,…,rλ}，其中，rq为在所述明文矩阵X中第cq行内某个非零元素的对应列值，cq为所述随机正整数列Kc中的第q个元素，q为不大于λ的正整数。在所述步骤S301中，可以但不限于按照如下方式确定所述非零元素列值数列Kr:{r1,r2,…,rq,…,rλ}中的各个元素rq：将在所述明文矩阵X中第cq行内第一个非零元素(沿列序号增加方向或列序号减小方向)的对应列值确定为rq，或者将在所述明文矩阵X中第cq行内随机一个非零元素的对应列值确定为rq。
S302.针对各个密钥矩阵Bx，将第cp行与第rq行互换，得到新的非奇异方阵，其中，cp为在所述随机正整数列Kc中随机选择的一个元素，rq为在所述非零元素列值数列Kr中随机选择的一个元素。通过前述步骤S301～S302，可以控制右乘矩阵的结构，避免暴露所述明文矩阵的“0”元素数量，进一步保证用户数据的隐私性。此外，为了确保变换后的密钥矩阵Bx的行列式不为零(在后续步骤S104中，需该行列式作为分母使用)，需要重新检验新密钥矩阵Bx是否仍为非奇异方阵，如果检验发现新密钥矩阵Bx为奇异方阵，则需重新生成一个密钥矩阵来替代，直到在互换后得到新的非奇异方阵。
S103.将所述加密矩阵集{Y1,Y2,…,Yy,…,Yξ}上传至云计算服务器，并在经过外包计算方式的云计算后，获取对应的行列式值集{det(Y1),det(Y2),…,det(Yz),…,det(Yξ)}，其中，det(Yz)为对应加密矩阵Yz的行列式值，z为不大于ξ的正整数。
在所述步骤S103之前，优化的，为了避免云计算服务器感知所述明文矩阵X的位置，进一步提升数据隐私性，还包括如下步骤：将所述加密矩阵集{Y1,Y2,…,Yy,…,Yξ}的排列顺序随机置乱。如此在获取来自云计算服务器的行列式值集后，还需按照前述置乱规则逆向恢复该行列式值集中各个元素的排列顺序，得到与所述加密矩阵集{Y1,Y2,…,Yy,…,Yξ}对应的行列式值集{det(Y1),det(Y2),…,det(Yz),…,det(Yξ)}。此外，在将所述加密矩阵集{Y1,Y2,…,Yy,…,Yξ}上传至云计算服务器后，采用外包计算方式的云计算方法为现有方法。
S104.按照如下公式得到所述明文矩阵X及各个验证矩阵Xy的行列式值：
在所述步骤S104中，优化的，按照如下公式求得det(Ax)和det(Bx)：
式中，{a1,a2,…an-λ}为密钥矩阵Ax中仅主对角线元素或副对角线元素为非零元素的行列序号集合，{b1,b2,…bn-λ}为密钥矩阵Bx中仅主对角线元素或副对角线元素为非零元素的行列序号集合，{d1,d2,…dλ}为密钥矩阵Ax和Bx中整行元素或整列元素为非零元素的行列序号集合，i为不大于n的正整数，λ为不小于3且远小于
S105.验证det(X)是否等于det(X2)+det(X3)+…+det(Xy)+…+det(Xξ)，若等于则接受所述明文矩阵X的行列式值为det(X)，否则拒绝接受。
针对前述步骤S101～S105的技术效果，可以ξ＝3为例，进行如下分析。
(1)正确性：在问题产生算法中(即步骤S102的内容)，加密矩阵Y1＝A1XB1，显然有：det(Y1)＝det(A1XB1)＝det(A1)det(B1)det(X)，即
式中，Mmi、(M2)mi和(M3)mi分别是与相应元素对应的代数余子式。由于X、X2和X3的非分解行矩阵或非分解列矩阵是相等的，所以有Mmi＝(M2)mi＝(M3)mi，因此必然有：
使得本实施例的解密过程和验证过程均是正确的。
(2)隐私性：本实施例并未使用传统的置换函数，而是使用了精心设计的特殊稀疏矩阵来进行加密，确保了矩阵的数据信息不会泄露。特别地，对矩阵的一些特征，比如0元素的数量，该协议也能保证不会泄露。本实施例中所使用的特殊稀疏矩阵可以比χ型稀疏矩阵更好地对明文数据提供隐私性。
(3)可验证性：所有的明文矩阵通过不同的加密矩阵进行加密，在加密矩阵没有被敌手得知的情况下，敌手没有办法得到任何关于行列式值的信息，而客户端可在解密后通过验证det(X)＝det(X2)+det(X3)来确定服务器端是否正确地进行了行列式的计算。如果敌手想要伪造行列式的值，那么这个敌手必须同时伪造客户端所发送的其他所有行列式的值，并且使得这些伪造的行列式的值满足det(X)＝det(X2)+det(X3)，这意味着敌手成功的概率是可忽略的，而客户端可以概率1来验证所收到的结果。因此通过本实施例中的所述方法，能够确定地而非以某个不可忽略的概率得出服务器所返结果的正确与否。
(4)高效性：客户端本地运行的算法主要有：密钥生成算法keyGen(即步骤S101的内容)，问题产生算法ProbGen(即步骤S102的内容)，验证算法Verify的解密过程(即步骤S104的内容),验证算法Verify的验证过程(即步骤S105的内容)。问题产生算法的时间复杂度为Ο(nn2)，验证过程和解密过程的时间复杂度分别为Ο(λλ3)和Ο(nn)。相比计算明文矩阵行列式的时间复杂度Ο(nn3)，在n很大时，客户端的计算量远小于云计算服务器的计算量。
将本实施例方法与现有的外包计算协议所需的计算时间做比较，列出如下表1：
表1.本实施例与各协议的计算时间比较
其中，R表示一次取随机数操作所需时间，池1表示一次浮点数乘运算操作所需时间，池2表示一次浮点数加运算操作所需时间。
在效率上，从表1可以看到，本实施例的计算复杂度是低于协议2015年乙版协议和2017年版协议；在隐私性上，本实施例的隐私性至少与2017年版协议相当，较协议2014年版协议、2015年甲版协议和2015年乙版协议，本实施例保护了加密协议框架的结构特征；在验证算法上，本实施例的验证结果并非概率性的验证，而是确定性验证过程，因此其验证结果更为可靠。
将本实施例方法与本地运算求解大尺度矩阵行列式值所需的计算时间做比较，列出如下表2：
表2.本实施例与本地运算的计算时间比较
在时间上，从表2可以看到，采用本实施例方法在客户端侧的时间开销明显低于本地运算的时间开销，可大大降低客户端的运算能力配置需求，具有明显的进步。
综上分析，本实施例的问题产生算法的隐私性目前是最有保障的(即具有可证明的隐私性)，客户端在本地的计算量与其它几种协议相比较，较2014年版协议和2015年甲版协议高，但明显小于2015年乙版协议和2017年版协议；在验证算法上，本协议的验证过程为确定性验证过程，较2015年乙版协议和2017年版协议的概率性验证更可靠，且所需的计算量更低。
综上，采用本实施例所提供的高效求解大尺度矩阵行列式的可验证外包计算方法，具有如下技术效果：
(1)本实施例提供了一种针对求解大尺度矩阵行列式的新外包计算协议，可使拥有较少计算资源/计算能力弱的客户端在面临求解大尺度矩阵行列式时(尤其是针对大尺度稠密矩阵对应的行列式计算)，可以将整个行列式的计算任务外包给计算能力强大的云计算服务器，并提供有给客户端可靠的验证方法，从而满足当前在隐私性(云侧不可得知明文矩阵的数据)、正确性(在云侧是半诚实模型或恶意模型时，依然能够保证客户端能够检测返回结果是否正确)、高效性(客户端计算量远小于计算明文矩阵行列式所需的计算量)和可验证性(能够确定地而非以某个不可忽略的概率得出服务器所返结果的正确与否)等方面的要求，便于实际应用和推广。
(2)所述可验证外包计算方法的加密/解密框架与传统的加密协议框架不同，即问题产生算法和验证算法都是在客户端进行的，没有传统加密协议框架中较慢的公钥交换过程，效率高且安全，并保证了按次交付的灵活性。
实施例二
如图2所示，本实施例提供了一种实现前述实施例一的客户端，包括密钥生成模块、问题产生模块、收发模块、解密模块和验证模块，其中，所述问题产生模块包括验证矩阵生成单元和矩阵加密单元；
所述密钥生成模块，用于生成密钥矩阵集{A1,A2,…,Ax,…,Aξ}和{B1,B2,…,Bx,…,Bξ}，其中，密钥矩阵Ax和Bx分别为具有n*n个元素的非奇异方阵，密钥矩阵Ax中的主对角线元素或副对角线元素为随机正整数，密钥矩阵Bx中的主对角线元素或副对角线元素为随机正整数，密钥矩阵Ax中的第d列元素和密钥矩阵Bx中的第d行元素分别为随机非零实数，密钥矩阵Ax和Bx中其余元素为零，n为不小于1000的正整数，ξ为不小于3的正整数，x为不大于ξ的正整数，d为不大于n的随机正整数；
所述问题产生模块通信连接所述密钥生成模块，用于在导入具有n*n个元素的且为非奇异矩阵的明文矩阵X后，对所述明文矩阵X进行加密；
所述验证矩阵生成单元，用于根据所述明文矩阵X生成验证矩阵集{X2,X3,…,Xy,…,Xξ}，其中，验证矩阵Xy的元素除第m行元素或第m列元素之外与所述明文矩阵X相同，并在数组[((X2)m)k,((X3)m)k,…,((Xy)m)k,…,((Xξ)m)k]中仅有一个元素与(Xm)k相同，其余元素为零，(Xy)m和Xm分别为所述验证矩阵Xy和所述明文矩阵X中的第m行元素或(Xy)m和Xm分别为所述验证矩阵Xy和所述明文矩阵X中的第m列元素，((Xy)m)k和(Xm)k分别为(Xy)m和Xm中的第k个元素，y为大于1且不大于ξ的正整数，m,k分别为不大于n的随机正整数；
所述矩阵加密单元分别通信连接所述明文矩阵分解单元，用于针对所述明文矩阵X及各个验证矩阵Xy，分别按照如下公式进行加密，得到加密矩阵集{Y1,Y2,…,Yy,…,Yξ}：
所述收发模块通信连接所述问题产生模块，用于将所述加密矩阵集{Y1,Y2,…,Yy,…,Yξ}上传至云计算服务器，并在经过云计算后获取对应的行列式值集{det(Y1),det(Y2),…,det(Yz),…,det(Yξ)}，其中，det(Yz)为对应加密矩阵Yz的行列式值，z为不大于ξ的正整数；
所述解密模块分别通信连接所述收发模块和所述密钥生成模块，用于按照如下公式得到所述明文矩阵X及各个验证矩阵Xy的行列式值：
所述验证模块通信连接所述解密模块，用于验证det(X)是否等于det(X2)+det(X3)+…+det(Xy)+…+det(Xξ)，若等于则接受所述明文矩阵X的行列式值为det(X)，否则拒绝接受。
本实施例的工作过程和技术效果，可参照实施例一毫无疑议的推导得到，于此不再赘述。
实施例三
如图3所示，本实施例提供了一种包括前述实施例二的云计算系统，包括云计算服务器和如实施例二所述的客户端；所述云计算服务器通信连接所述客户端的收发模块，用于在收到加密矩阵集{Y1,Y2,…,Yy,…,Yξ}后，通过外包计算方式，云计算得到对应的行列式值集{det(Y1),det(Y2),…,det(Yz),…,det(Yξ)}，并将云计算结果反馈给所述收发模块。本实施例的工作过程和技术效果，同样可参照实施例一毫无疑议地推导得到，于此不再赘述。
本发明不局限于上述可选的实施方式，任何人在本发明的启示下都可得出其他各种形式的产品。上述具体实施方式不应理解成对本发明的保护范围的限制，本发明的保护范围应当以权利要求书中界定的为准，并且说明书可以用于解释权利要求书。
机译： 客户端，服务器，云计算系统和云计算方法
机译： 一种基于客户端服务器的基于防虚假，可验证且易于证明的基于公平令牌的游戏的系统及其实现方法
机译： 一种基于客户端服务器的基于防虚假，可验证且易于证明的基于公平令牌的游戏的系统及其实现方法
