基于明文相似矩阵的对称全同态加密方法

摘要

本发明提出一种基于明文相似矩阵的对称全同态加密方法，用于解决现有对称全同态加密效率低的技术问题。实现步骤为：用户根据要求生成两个长度相等的大素数，并根据生成的大素数构建剩余类环，根据剩余类环构建一般线性群，计算同态计算公钥和对称密钥，使用对称密钥对明文矩阵的相似矩阵进行加密，使用对称密钥对密文矩阵进行解密；云服务器使用同态计算公钥对密文矩阵进行同态计算；用户使用对称密钥对同态密文矩阵进行解密。本发明密钥选取和加密过程简单，将明文矩阵随机隐藏，提高加密算法的安全性，在密文计算过程中没有引入噪声，可以根据需求对密文矩阵进行任意计算。本发明可用于云计算、大数据环境等对重要数据的全程密态保护。

说明书

技术领域

本发明属于信息安全领域，涉及一种对称的全同态加密方法，具体涉及一种基于明文相似矩阵的对称全同态加密方法，可应用于云计算、大数据环境等对重要数据的全程密态保护，在对密文数据不进行解密的情况下完成对明文数据的计算。

背景技术

随着互联网的发展，尤其是云计算概念的诞生，人们在加密数据搜索与处理等方面的需求日益增加。但是对于大数据的处理，用户就必须委托给第三方(云)来进行操作；用户在云端存储的数据可能包含一些敏感信息，所以在将数据存储到云端之前必须对数据进行加密保护；然而，明文数据一旦被加密，明文数据结构会发生变化，一些在明文数据上的操作将不再适用于密文数据。

同态加密是一种新型的加密算法，对密文数据进行同态运算得到一个输出，将这一输出进行解密，其结果与用同一方法处理未加密的原始数据得到的输出结果相等，这种加密方法的优点是可以直接对密文数据进行计算，而不用等到解密后在进行处理，但缺陷是只能对密文数据进行有限次的同态运算或只能对密文数据进行单一代数运算(加或乘)。然而，单运算同态密码和浅同态密码同态计算功能受限，例如，Paillier密码体制、Damgard-Jurik密码体制等只能满足加法同态；RSA密码体制、ElGamal等只能满足乘法同态；BGN密码体制满足任意次加法同态和一次的乘法同态。

全同态加密是在同态加密的基础上提出来的，全同态加密可以根据用户要求，允许第三方对密文数据进行任意计算，且对密文数据的计算结果进行解密即得到对应明文数据的计算结果，而在整个处理过程中无需对数据进行解密；其意义在于，从根本上解决重要数据的隐私保护和密文数据的计算相互冲突的瓶颈问题。全同态加密方法的基本步骤包括：参数生成，密钥选取，对明文消息加密，对密文消息解密，对密文消息进行同态计算。

2009年Gentry设计了第一个基于格的全同态密码体制，实现了历史性的跨越。然而，一些全同态密码方案由于加密方案中密文存在噪声，所以当密文计算到一定程度，其噪声将超过上限，对这样的密文解密将可能失败。还有一些对称全同态密码方案，由于过程繁琐导致效率低下。例如，2017年Khalil Hariss、Hassan Noura和Abed Ellatif Samhat在论文“Fully Enhanced Homomorphic Encryption algorithm of MORE approach for realworld applications”(Journal of Information SecurityandApplications.2017.Pages 233-242)中提出了一种改进的用于随机化和加密的矩阵运算的对称全同态加密算法。该方法的具体步骤是：两个用户协商一对秘密参数：一个私密钥、一个初始向量IV，使用哈希算法生成64-bits的动态密钥DK；使用动态置换密钥DK_p生成一个置换盒π＝[p_i]_1≤i≤N，将其用于输入的明文消息；基于动态扩散密钥DK_d和流密码算法(例如：RC4),两个用户共享一个秘密序列s，使用重构函数将先前的秘密序列s变换为w个尺寸为的小矩阵，使用矩阵生成方程构建包含w个矩阵和其逆矩阵的矩阵密钥库；创建另一个置换盒Δ＝[δ_i]_1≤i≤H，Δ的尺寸为H，使用动态选择密钥DK_s选择一个名为k的密钥块，k经过置换盒Δ的作用，生成序列从序列中选出下标为δ_k的密钥，这样就生成了一对密钥矩阵这一对密钥矩阵就作为相应矩阵块的动态加密密钥；使用动态选择算法从矩阵密钥库中选择动态加密密钥，用动态的选择密钥对明文消息进行分块加密；解密过程是加密过程的一个逆过程，用户拥有动态密钥DK和初始向量IV就可以生成一切秘密参数，用MORE算法进行解密。该方案可以实现对称的全同态加密，但是不足之处在于密钥选取过程繁琐，在加密过程中需要对明文消息进行分块加密，导致效率低。

发明内容

本发明的目的是针对上述现有技术的缺陷，提出了一种基于明文相似矩阵的对称全同态加密方法，用于解决现有对称全同态加密效率低的技术问题。

为实现上述目的，本发明采取的技术方案，包括如下步骤：

(1)参数生成：用户根据安全要求随机生成两个长度相等的大素数p和q；

(2)用户构建剩余类环和一般线性群，实现步骤为:

(2.1)用户构建关于大素数p的剩余类环和关于大素数q的剩余类环

(2.2)用户利用剩余类环构建模p意义下的所有n阶可逆矩阵构成的一般线性群同时利用剩余类环构建模q意义下的所有n阶可逆矩阵构成的一般线性群

(3)用户计算同态计算公钥和对称密钥，实现步骤为：

(3.1)用户计算RSA模数N，N＝pq，并将RSA模数N作为同态计算公钥；

(3.2)用户在一般线性群中随机选取一个n阶可逆矩阵A，并求取可逆矩阵A模p意义下的逆矩阵A^-1，A、A^-1和p构成对称密钥sk，sk＝(A,A^-1,p)；

(4)用户对明文矩阵进行加密，实现步骤为：

(4.1)用户根据需要在一般线性群中选取k个n阶可逆的明文矩阵并分别计算k个明文矩阵M_k的相似矩阵其中，k≥2，是明文矩阵M_k中第i行第j列的元素，是相似矩阵B_k中第i行第j列的元素；

(4.2)用户在一般线性群中随机选取k个n阶矩阵并根据中国剩余定理计算k个密文矩阵

其中，是矩阵D_k中第i行第j列的元素，是密文矩阵C_k中第i行第j列的元素且对任意的i,j＝1,2,…,n满足同余式方程组：

(5)用户对密文矩阵进行解密，实现步骤为：

(5.1)用户通过同余式构建k个n阶矩阵

(5.2)用户对k个n阶矩阵B_k左乘矩阵A^-1，右乘矩阵A，得到k个明文矩阵M_k≡A^-1B_kA(modp)；

(6)云服务器对密文矩阵进行同态计算，实现步骤为：

(6.1)云服务器根据用户需要，从k个密文矩阵C_k中选取明文矩阵M₁、M₂、M₁′和M₂′对应的密文矩阵C₁、C₂、C₁′和C₂′，其中明文矩阵M₁、M₂、M₁′和M₂′相同或不同；

(6.2)云服务器使用同态计算公钥N，对密文矩阵C₁和C₂进行同态加法计算，同时对密文矩阵C₁′和C₂′进行同态乘法计算，得到同态加法密文矩阵C₊和同态乘法密文矩阵C_×；

(7)用户对同态加法密文矩阵C₊和同态乘法密文矩阵C_×进行解密，得到对应明文矩阵M₊和M_×。

本发明与现有技术相比，具有以下优点：

1.本发明利用随机生成的大素数构建剩余类环，根据剩余类环构建一般线性群，在构建的一般线性群中进行密钥选取，并且使用相似矩阵对明文矩阵进行加密，过程简单，与现有技术相比，提高了效率。

2.本发明在加密过程中对明文矩阵的相似矩阵进行加密，在解密时，通过乘矩阵的逆矩阵，结果满足矩阵乘自身的逆矩阵等于单位矩阵，从而计算过程不会引入噪声，支持对密文矩阵进行任意次的同态计算，满足用户的需求。

3.本发明在加密过程中对明文矩阵的相似矩阵进行加密，使得明文矩阵被其相似矩阵随机隐藏，提高了加密方法的安全性。

附图说明

图1为本发明的实现流程图。

具体实施方式

以下结合附图和具体实施例，对本发明作进一步详细说明。

步骤1)参数生成：用户根据安全要求随机生成两个长度相等的大素数p和q，取p和q的长度均为1024比特；

步骤2)用户构建剩余类环和一般线性群，实现步骤为:

步骤2.1)用户构建关于大素数p的剩余类环和关于大素数q的剩余类环

步骤2.2)用户利用剩余类环构建模p意义下的所有n阶可逆矩阵构成的一般线性群利用剩余类环构建模q意义下的所有n阶可逆矩阵构成的一般线性群

步骤3)用户计算同态计算公钥和对称密钥，实现步骤为：

步骤3.1)用户计算RSA模数N，N＝pq，并将RSA模数N作为同态计算公钥；

步骤3.2)用户在一般线性群中随机选取一个n阶可逆矩阵A，并求取可逆矩阵A模p意义下的逆矩阵A^-1，A、A^-1和p构成对称密钥sk，sk＝(A,A^-1,p)；

步骤4)用户对明文矩阵进行加密，实现步骤为：

步骤4.1)用户根据需要在一般线性群中选取k个n阶可逆的明文矩阵并分别计算k个明文矩阵M_k的相似矩阵其中，k≥2，是明文矩阵M_k中第i行第j列的元素，是相似矩阵B_k中第i行第j列的元素；

步骤4.2)用户在一般线性群中随机选取k个n阶矩阵并根据中国剩余定理计算k个密文矩阵

其中，是矩阵D_k中第i行第j列的元素，是密文矩阵C_k中第i行第j列的元素且对任意的i,j＝1,2,…,n满足同余式方程组：

步骤5)用户对密文矩阵进行解密，实现步骤为：

步骤5.1)用户通过同余式构建k个n阶矩阵

步骤5.2)用户对k个n阶矩阵B_k左乘矩阵A^-1，右乘矩阵A，得到k个明文矩阵M_k≡A^-1B_kA(modp)；

步骤6)云服务器对密文矩阵进行同态计算，实现步骤为：

步骤6.1)云服务器根据用户需要，从k个密文矩阵C_k中选取明文矩阵M₁、M₂、M₁′和M₂′对应的密文矩阵C₁、C₂、C₁′和C₂′，其中明文矩阵M₁、M₂、M₁′和M₂′相同或不同；

步骤6.2)云服务器使用同态计算公钥N，对密文矩阵C₁和C₂进行同态加法计算，同时对密文矩阵C₁′和C₂′进行同态乘法计算，得到同态加法密文矩阵C₊和同态乘法密文矩阵C_×，对密文矩阵C₁和C₂进行同态加法计算的公式为：

C₊≡C₁+C₂(modN)，

对密文矩阵C₁′和C₂′进行同态乘法计算的公式为：

C_×≡C₁′×C₂′(modN)；

步骤7)用户对同态加法密文矩阵C₊和同态乘法密文矩阵C_×进行解密，得到对应明文矩阵M₊和M_×，实现步骤为：

步骤7.1)用户通过同态加法密文矩阵和同余式(c₊)_ij≡(b₊)_ij(mod>

步骤7.2)用户通过同态乘法密文矩阵和同余式(c_×)_ij≡(b_×)_ij(mod>

步骤7.3)用户对n阶矩阵B₊左乘矩阵A^-1，右乘矩阵A，得到明文矩阵M₊≡A^-1B₊A(modp)，其中M₊＝M₁+M₂；

步骤7.4)用户对n阶矩阵B_×左乘矩阵A^-1，右乘矩阵A，得到明文矩阵M_×≡A^-1B_×A(modp)，其中M_×＝M₁′×M₂′。