一种云外包解大规模线性方程组的方法

摘要

本发明公开了一种云外包解大规模线性方程组的方法，这是一种基于初等变换矩阵的非交互的云外包计算方案。初等变换矩阵具有比较低的计算复杂度，每次初等变换矩阵的乘积都只消耗O(n)的时间复杂度。加密一个普通的n阶矩阵，只需要n个初等变换矩阵，即可加密矩阵中的每一个元素。解大规模线性方程组问题可以写为Φ:Ax＝b，其中A是一个n×n的可逆矩阵，x,b是一个n×1的向量。在外包解大规模线性方程组的协议中，需要保护参数A,b与结果x的隐私。本发明利用初等变换矩阵对参数A,x,b进行加密处理，从而提高了降低了客户端处理问题的复杂度，设计出了客户端只需要O(n²)复杂度的协议，提高了计算效率。同时，本发明是一种非交互协议，客户端无需在问题求解阶段与服务器进行交互，只需要提交计算请求，即可获得外包计算结果。

主权项

云外包解大规模线性方程组的方法，是客户端的计算能力无法对大规模线性方程组进行求解的情况下，采用外包的方式，对线性方程组进行加密，交给第三方服务器进行计算，服务器对加密后的问题进行处理，返回加密的结果给客户端，客户端对结果进行加密和验证，其特征在于以下步骤：(1)密钥生成KeyGen(n)→(SK)，客户端根据原始方程组Φ:Ax＝b中矩阵A的阶n，来生成密钥SK，并保证密钥SK仅被客户端知道：1)客户端根据矩阵的阶n，生成两个1,2,…,n的置换π₁,π₂；2)根据置换π₁,π₂，客户端随机选取2n个随机整数值r₁,r₂,…r_2n，然后根据公式(1)和公式(2)得到2n个n×n初等变换矩阵A_k,B_k,1≤k≤n：3)令P₁＝A₁A₂…A_n，P₁^‑1＝A_n^‑1A_n‑1^‑1…A₁^‑1，P₂＝B₁B₂…B_n，P₂^‑1＝B_n^‑1B_n‑1^‑1…B₁^‑1；4)密钥为SK＝P₁,P₂,π₁,π₂,r₁,…,r_2n,A,b；(2)问题加密LEEncrypt(Φ,SK)→(Φ')，客户端根据密钥生成阶段生成的密钥SK对原始问题Φ:Ax＝b进行加密，加密方式如下：1)客户端对原始问题Φ:Ax＝b进行加密得到Φ':A'x'＝b'；其中，A'＝P₁AP₂，x'＝P₂^‑1x，b'＝P₁b，根据初等变换矩阵与普通矩阵乘积只需要O(n)的时间复杂度的性质，对上述式子进行计算，该阶段的时间复杂度为O(n²)；2)客户端将加密后的问题Φ':A'x'＝b'发送给服务器，客户端只需要将参数A',b'发送给服务器即可；(3)问题求解LESolve(Φ')→(x')，服务器拿到客户端的加密问题Φ':A'x'＝b'之后，利用常规线性方程组求解方法对加密问题进行求解：1)服务器拿到问题Φ':A'x'＝b'之后，使用目前最好的算法来求解线性方程组问题；2)服务器得到问题的结果x'之后，将他们返回给客户端；(4)问题解密LEDecrypt(x',SK)→(x₁)：客户端根据密钥P₁,P₂,A,b和从服务器返回的结果x'，计算x₁＝P₂^‑1x'，因为P₂^‑1是一系列初等矩阵的乘积，因此该步骤的计算也只需要O(n²)的时间复杂度；(5)结果验证ResultVerify(SK,x₁)→(x∪⊥)：如果Ax₁＝b，代表服务器确实对加密后的问题进行了解密，并且返回了正确的结果x'，因此服务器在该协议中城市，客户端输出x＝x₁；反之，证明了服务器在该协议中对客户端进行了欺骗，输出⊥。