CN115065456A - Improved homomorphic multiplication encryption method supporting floating-point operation - Google Patents

Abstract

Translated fromChinese

该发明为一种支持浮点运算的改进同态乘法加密方法，该加密方法包括步骤：SA，生成所述加密算法的密钥,密钥包括公钥以及私钥；所述的公钥为Paillier生成的公钥pk_Paillier；所述的私钥为{sk_Paillier,g,a,L_K,M_K,c}；所述的g和a为随机数，L_K和M_K为随机正整数；SB，对明文M进行加密，生成随机扰动参数k，k为有界正整数，范围为(L_K,M_K)；使用私钥对明文M加密后得到密文C，密文C＝(Enc_Paillier(c×k),m×g^k×a)；SC，解密所述密文C，使用所述sk_Paillier解密得到所述c×k，通过公式M＝M×g^k×a/g^c×k×a/c得到明文M。本申请的技术方案比传统的方案改进之处包括支持浮点型数据加解密和乘法同态运算以及加解密性能更优。

The invention is an improved homomorphic multiplication encryption method that supports floating point operations. The encryption method includes the steps of: SA, generating a key of the encryption algorithm, and the key includes a public key and a private key; the public key is Paillier The generated public key pk_Paillier ; the private key is {sk_Paillier , g, a, L_K , M_K , c}; the g and a are random numbers, and L_K and M_K are random positive integers; SB, encrypt the plaintext M, and generate a random perturbation parameter k, where k is a bounded positive integer, and the range is (L_K , M_K ); after encrypting the plaintext M with the private key, the ciphertext C is obtained, and the ciphertext C=(Enc_Paillier (c×k), m×g^k×a ); SC, decrypt the ciphertext C, use the sk_{Paillier to} decrypt to obtain the c×k, through the formula M=M×g^k×a /g^{c ×k×a/c} to get the plaintext M. The improvements of the technical solution of the present application over the traditional solution include support for floating-point data encryption and decryption and multiplication homomorphic operations, and better encryption and decryption performance.

Description

Translated fromChinese

一种支持浮点运算的改进同态乘法加密方法An Improved Homomorphic Multiplication Encryption Method Supporting Floating-Point Operations

技术领域technical field

本申请涉及计算机技术领域，具体涉及一种支持浮点运算的改进同态乘法加密方法。The present application relates to the field of computer technology, and in particular to an improved homomorphic multiplication encryption method supporting floating-point operations.

背景技术Background technique

现有的密码体制一般可分为两种，即对称密码体制和公钥密码体制。Existing cryptosystems can generally be divided into two types, namely symmetric cryptosystems and public key cryptosystems.

对称密码体制需要通信双方A和B共享一密钥K，并且要保证A和B在协商密码的时候，信道是保密且保真的。这就导致了密钥分发的问题和密钥的管理问题。与对称密码体制不同，公钥密码体制仅要求密钥的交换是保真的，并不要求其是保密的。每个实体选择一个密钥对(公钥，私钥)，其中公钥对外是公开的，私钥是保密的，这种密钥对需具备一个特点：仅由公钥不能计算出私钥。由于每一个实体都具有唯一的私钥，因此可以提供数据源和数据完整性的认证以及不可否认性服务。这样，公钥密码圆满地解决了上述对称密码面临的三个问题。Symmetric cryptosystem requires both parties A and B to share a key K, and it is necessary to ensure that when A and B negotiate a password, the channel is kept secret and authentic. This leads to key distribution problems and key management problems. Unlike symmetric cryptosystems, public key cryptosystems only require the exchange of keys to be fidelity, but not to be kept secret. Each entity selects a key pair (public key, private key), in which the public key is open to the outside world, and the private key is kept secret. This key pair must have a characteristic: the private key cannot be calculated only from the public key. Since each entity has a unique private key, it can provide authentication and non-repudiation services of data origin and data integrity. In this way, public key cryptography satisfactorily solves the three problems faced by the above-mentioned symmetric cryptography.

在公钥密码体制中，虽然RSA是目前主流的加密机制，但是RSA目前却面临着越来越严重的来自安全方面的挑战，同时由于RSA的分组长度太大，为了保证安全性，n至少也要600比特，使其运算代价大大升高，加解密速度也受到限制，相比于对称密码算法慢了几个数量级，若这个长度继续增加，不利于数据格式的标准化。公钥密码方案较保护密钥方案处理速度慢，因此，通常把公钥密码与专用密钥技术结合起来实现最佳性能。即用公共密钥技术在通信双方之间传送专用密钥，而用专用密钥来对实际传输的数据进行加解密。同时，公钥加密也用来对专用密钥进行加密。In the public key cryptosystem, although RSA is the current mainstream encryption mechanism, RSA is currently facing more and more serious challenges from security. It requires 600 bits, which greatly increases the computational cost and limits the speed of encryption and decryption. Compared with the symmetric cryptographic algorithm, it is several orders of magnitude slower. If the length continues to increase, it is not conducive to the standardization of the data format. Public-key cryptography is slower to process than protected-key schemes, so public-key cryptography is usually combined with private-key techniques to achieve the best performance. That is, the public key technology is used to transmit the private key between the two communicating parties, and the private key is used to encrypt and decrypt the actually transmitted data. At the same time, public key encryption is also used to encrypt the private key.

现代加密方式已经嵌入无数的数字系统和组件，成为保护数据安全性和隐私相关的必要工具。但是密码学现在最大的限制，在于需要处理和分析敏感数据的时候必须先对加密的数据进行解密。然而，包括医疗、法律、制造商、金融和在线选举等在内，有大量的领域需要对数据进行分析处理；如果能不使用加密密钥就直接对数据进行分析处理，就能达到目标的同时，还可以确保数据的隐私性。Modern encryption methods have become embedded in countless digital systems and components, becoming a necessary tool for protecting data security and privacy. But the biggest limitation of cryptography now is that the encrypted data must be decrypted before processing and analyzing sensitive data. However, there are a large number of areas including medical, legal, manufacturers, finance and online elections that require analytical processing of data; if the data can be analyzed directly without the use of encryption keys, the goal can be achieved while at the same time , which also ensures data privacy.

此外，大数据时代下，对数据的统计分析已被广泛应用于研究和生活领域，数据拥有者鉴于个人电脑无法执行大量的数据计算或者耗时很长，希望寻求第三方合作，利用其计算能力来处理分析数据。由于数据的隐私性，数据持有者希望第三方在对数据进行计算的同时能保护数据的隐私，同态加密应运而生，同态加密不是一成不变的，从上个世纪七十年代的纯理论到如今也有近五十多年的发展历史，可以简单区别为部分同态加密和完全同态加密(FHE)等类型，主要区别为同态加法或同态乘法计算的连续性能力。完全同态加密技术也经历多代升级，不同的同态加密技术在对算力的要求及计算效率上也可能存在极大的不同。In addition, in the era of big data, statistical analysis of data has been widely used in research and life. Since personal computers cannot perform a large number of data calculations or take a long time, they hope to seek third-party cooperation and use their computing power. to process analytical data. Due to the privacy of the data, the data holder hopes that the third party can protect the privacy of the data while calculating the data. Homomorphic encryption came into being. Homomorphic encryption is not immutable. From the pure theory in the 1970s Up to now, it has a development history of nearly 50 years. It can be simply distinguished into partial homomorphic encryption and fully homomorphic encryption (FHE). The main difference is the continuity ability of homomorphic addition or homomorphic multiplication. Fully homomorphic encryption technology has also undergone multiple generations of upgrades, and different homomorphic encryption technologies may also have great differences in computing power requirements and computing efficiency.

在数据“可用不可见”的情况，同态加密技术能直接处理密文，然后解密密文结果与明文预期计算结果相同。目前同态加密仅适用于整型数据的加解密运算操作，加解密涉及繁琐的计算过程，从而较为低效，密文的运算次数也存在一定缺陷，支持无限次运算的同态加密算法都是在有限次算法的基础上再加上自举(bootstrap)来实现，如果不加自举，则需要添加重加密的步骤，把经过多次计算后的密文变成新鲜密文。In the case of "available and invisible" data, homomorphic encryption can directly process the ciphertext, and then decrypt the ciphertext and the result is the same as the expected calculation result of the plaintext. At present, homomorphic encryption is only suitable for the operation of encryption and decryption of integer data. Encryption and decryption involve cumbersome calculation process, which is relatively inefficient. The number of operations of ciphertext also has certain defects. Homomorphic encryption algorithms that support infinite operations are all On the basis of the limited number of algorithms, bootstrap is added. If no bootstrap is added, a re-encryption step needs to be added to turn the ciphertext after multiple calculations into fresh ciphertext.

现有的同态加密根据密文对运算形势的要求可分为半同态加密和全同态加密。半同态加密支持对密文进行部分形式的计算，如仅支持加法、仅支持乘法、支持有限次加法和乘法，半同态加密主要包括RSA算法和ELGamal算法为代表的乘法同态加密、以Paillier算法为代表的加法同态加密。全同态加密支持密文进行任意形式的计算，全同态加密算法起源于2009年Gentry提出额度方案，后续的方案大多数是基于格代数结构构造。全同态加密方案的发展应用并不如半同态加密方案应用成熟，加法同态Paillier算法应用最为成熟，但Paillier算法对与小整型的数据加解密速率和密文的运算效率较好，对大整型数据的运算效率相对较低，且不适用于浮点数的近似计算。目前较为实用的半同态乘法加密ELGamal算法是在数字签名中应用较为广泛的同态加密算法，其可以实现随机加密的效果，安全性较高，但密钥的传输以及密钥管理还存在些许问题。Existing homomorphic encryption can be divided into semi-homomorphic encryption and fully homomorphic encryption according to the requirements of ciphertext on the operation situation. Semi-homomorphic encryption supports partial forms of computation on ciphertext, such as only addition, only multiplication, and limited addition and multiplication. Semi-homomorphic encryption mainly includes multiplicative homomorphic encryption represented by RSA algorithm and ELGamal The Paillier algorithm is represented by additive homomorphic encryption. Fully homomorphic encryption supports ciphertext for any form of calculation. The fully homomorphic encryption algorithm originated from the quota scheme proposed by Gentry in 2009, and most of the subsequent schemes are constructed based on lattice algebraic structures. The development and application of the fully homomorphic encryption scheme is not as mature as that of the semi-homomorphic encryption scheme. The application of the additive homomorphic Paillier algorithm is the most mature. The operation efficiency of large integer data is relatively low, and it is not suitable for approximate calculation of floating point number. At present, the more practical semi-homomorphic multiplication encryption ELGamal algorithm is a homomorphic encryption algorithm widely used in digital signatures. It can achieve the effect of random encryption and has high security, but there are still some problems in key transmission and key management. question.

全同态加密算法仍处于以学术界研究为主的发展阶段，现有方案均存在计算和存储开销大等无法规避的性能问题，距离高效的工程应用还有着不小的差距，同时面临国际与国内相关标准的缺失。The fully homomorphic encryption algorithm is still in the development stage mainly based on academic research. The existing solutions all have unavoidable performance problems such as high computing and storage overhead, and there is still a big gap from efficient engineering applications. Lack of relevant domestic standards.

因此，在尝试同态加密落地应用时，可以考虑利用Paillier加法同态加密算法等较为成熟且性能较好的半同态加密算法，解决只存在加法或者数乘同态运算需求的应用场景，或通过将复杂计算需求转化为只存在加法或数乘运算的形式实现全同态的近似替代。Therefore, when trying to apply homomorphic encryption to the ground, consider using more mature and better-performing semi-homomorphic encryption algorithms such as Paillier's additive homomorphic encryption algorithm to solve application scenarios that only require addition or multiplication homomorphic operations, or Fully homomorphic approximate substitution is achieved by transforming complex computational requirements into a form where only addition or multiplication operations exist.

发明内容SUMMARY OF THE INVENTION

该发明的目的是克服了上述现有技术中的缺点，提供一种可以实际投入使用的全同态的近似替代加密算法：一种支持浮点运算的改进同态乘法加密方法。The purpose of the invention is to overcome the above-mentioned shortcomings in the prior art, and to provide a fully homomorphic approximate replacement encryption algorithm that can be put into practical use: an improved homomorphic multiplication encryption method supporting floating-point operations.

为了实现上述的目的，该发明具有如下构成：In order to achieve the above-mentioned purpose, this invention has the following constitution:

一种支持浮点运算的改进同态乘法加密方法，包括步骤：An improved homomorphic multiplication encryption method supporting floating-point operations, including steps:

SA，生成所述加密算法的密钥,密钥包括公钥以及私钥；所述的公钥为Paillier生成的公钥pk_Paillier；所述的私钥为{sk_Paillier,g,a,L_K,M_K，c}；所述的g、a和c为随机数，L_K和M_K为随机正整数；SA, generates the key of the encryption algorithm, and the key includes a public key and a private key; the public key is the public key pk_{Paillier generated by Paillier} ; the private key is {sk_Paillier , g, a, L_K , M_K , c}; the g, a and c are random numbers, and L_K and M_K are random positive integers;

SB，对明文M进行加密，生成随机扰动参数k，k为有界正整数，范围为(L_K,M_K)；使用私钥对明文M加密后得到密文C，密文C＝(Enc_Paillier(c×k),M×g^k×a)；其中，c是随机生成的整数，作为私钥的一部分；SB, encrypt the plaintext M, and generate a random perturbation parameter k, where k is a bounded positive integer with a range of (L_K , M_K ); after encrypting the plaintext M with the private key, the ciphertext C is obtained, where the ciphertext C=(Enc_Paillier (c×k), M×g^k×a ); where c is a randomly generated integer as part of the private key;

SC，解密所述密文C，已知私钥的情况下，使用所述sk_Paillier解密得到所述c×k，通过公式M＝(M×g^k×a)/g^c×k×a/c得到明文M。SC, decrypt the ciphertext C, when the private key is known, use the sk_{Paillier to} decrypt to obtain the c×k, through the formula M=(M×g^k×a )/g^{c×k×a/ c} gets plaintext M.

在优选的所述的支持浮点运算的改进同态乘法加密方法中，所述的明文M及密文C分别为明文集和密文集，通过所述的步骤SB加密多个明文，将明文M₁至M_t加密为密文C₁至C_t；In the preferred improved homomorphic multiplication encryption method supporting floating-point operations, the plaintext M and the ciphertext C are respectively a plaintext set and a ciphertext set, and the plaintext M is encrypted by encrypting a plurality of plaintexts through the step SB.₁ to M_t are encrypted as ciphertext C₁ to C_t ;

所述的加密方法还包括步骤SB2，对所述的密文C₁至C_t进行乘法运算。The encryption method further includes a step SB2 of multiplying the ciphertexts C₁ to C_t .

在优选的所述的支持浮点运算的改进同态乘法加密方法中，SB2，对密文集进行乘法运算，C₁×C₂＝(Enc_Paillier(c×k₁+c×k₂),M₁×M₂×g^(k1+k2)×a。In the preferred improved homomorphic multiplication encryption method supporting floating point operation, SB2, multiplication operation is performed on the ciphertext set, C₁ ×C₂ =(Enc_Paillier (c×k₁ +c×k₂ ),M₁ ×M₂ ×g^(k1+k2)×a .

在优选的所述的支持浮点运算的改进同态乘法加密方法中，所述的步骤SC具体为：解密所述进行乘法运算后的密文，使用所述sk_Paillier解密得到所述c×k，通过公式

得到明文M₁×M₂。In the preferred improved homomorphic multiplication encryption method supporting floating point operations, the step SC is specifically: decrypting the ciphertext after the multiplication operation, using the sk_Paillier decryption to obtain the c×k , by the formula

The plaintext M₁ ×M₂ is obtained.

在优选的所述的支持浮点运算的改进同态乘法加密方法中，所述的L_K和M_K之间需要满足M_K＝(p+1)×L_K/p，其中p为大于2的正整数，L_K取超过100的整数。In the preferred improved homomorphic multiplication encryption method supporting floating-point operations, the relationship between L_K and M_K needs to satisfy M_K =(p+1)×L_K /p, where p is greater than 2 A positive integer of , L_K is an integer over 100.

在优选的所述的支持浮点运算的改进同态乘法加密方法中，所述的p取值大于10。In the preferred improved homomorphic multiplication encryption method supporting floating point operations, the value of p is greater than 10.

在优选的所述的支持浮点运算的改进同态乘法加密方法中，所述的g和a为随机浮点数。In the preferred improved homomorphic multiplication encryption method supporting floating-point operations, the g and a are random floating-point numbers.

本申请还包括一种支持浮点运算的改进同态乘法加密系统，包括密钥生成模块、加密模块以及解密模块；The present application also includes an improved homomorphic multiplication encryption system supporting floating point operations, including a key generation module, an encryption module and a decryption module;

所述的密钥生成模块用于生成所述加密算法的密钥,密钥包括公钥以及私钥；所述的公钥为Paillier生成的公钥pk_Paillier；所述的私钥为{sk_Paillier,g,a,L_K,M_K，c}；所述的g和a为随机浮点数，L_K和M_K为随机正整数；Described key generation module is used to generate the key of described encryption algorithm, and key comprises public key and private key; Described public key is the public key pk_Paillier that Paillier generates; Described private key is {sk_Paillier , g, a, L_K , M_K , c}; the g and a are random floating-point numbers, and L_K and M_K are random positive integers;

所述的加密模块用于生成随机扰动参数k，k为有界正整数，范围为(L_K,M_K)；对明文M进行加密，使用私钥对明文M加密后得到密文C，密文C＝(Enc_Paillier(c×k),M×g^k×a)；The described encryption module is used to generate random disturbance parameter k, where k is a bounded positive integer, and the range is (L_K , M_K ); the plaintext M is encrypted, and the ciphertext C is obtained after encrypting the plaintext M with a private key, and the encrypted Text C=(Enc_Paillier (c×k), M×g^k×a );

所述的解密模块解密所述密文C，使用所述sk_Paillier解密得到所述c×k，通过公式m＝m×g^k×a/g^c×k×a/c得到明文M。The decryption module decrypts the ciphertext C, uses the sk_{Paillier to} decrypt to obtain the c×k, and obtains the plaintext M through the formula m=m×g^k×a /g^c×k×a/c .

本申请还包括一种计算机存储介质，其上存储有计算机可读指令，所述计算机可读指令可被处理器执行以实现上述加密方法。The present application also includes a computer storage medium having computer-readable instructions stored thereon, the computer-readable instructions being executable by a processor to implement the encryption method described above.

本申请为一种支持浮点运算的改进同态乘法加密方法，该加密方法包括步骤：SA，生成所述加密算法的密钥,密钥包括公钥以及私钥；所述的公钥为Paillier生成的公钥pk_Paillier；所述的私钥为{sk_Paillier,g,a,L_K,M_K，c}；所述的g、a、c为随机数，L_K和M_K为随机正整数；SB，对明文M进行加密，生成随机扰动参数k，k为有界正整数，范围为(L_K,M_K)；使用私钥对明文M加密后得到密文C，密文C＝(Enc_Paillier(c×k),m×g^k×a)；SC，解密所述密文C，使用所述sk_Paillier解密得到所述c×k，通过公式M＝M×g^k×a/g^c×k×a/c得到明文M。本申请的技术方案比传统的方案改进之处包括支持浮点型数据加解密和乘法同态运算以及加解密性能更优。The present application relates to an improved homomorphic multiplication encryption method supporting floating-point operations. The encryption method includes the steps of: SA, generating a key of the encryption algorithm, and the key includes a public key and a private key; the public key is Paillier The generated public key pk_Paillier ; the private key is {sk_Paillier , g, a, L_K , M_K , c}; the g, a, and c are random numbers, and L_K and M_K are random positive Integer; SB, encrypt the plaintext M, and generate a random perturbation parameter k, where k is a bounded positive integer with a range of (L_K , M_K ); use the private key to encrypt the plaintext M to obtain the ciphertext C, where the ciphertext C= (Enc_Paillier (c×k), m×g^k×a ); SC, decrypt the ciphertext C, use the sk_{Paillier to} decrypt to obtain the c×k, through the formula M=M×g^k×a / g^c×k×a/c to get the plaintext M. The improvements of the technical solution of the present application over the traditional solution include support for floating-point data encryption and decryption and multiplication homomorphic operations, and better encryption and decryption performance.

附图说明Description of drawings

图1为本发明优选的加密方法的步骤示意图；Fig. 1 is the step schematic diagram of the preferred encryption method of the present invention;

图2为本发明优选的步骤SB2乘法运算的步骤示意图；Fig. 2 is the preferred step SB2 multiplication step schematic diagram of the present invention;

图3为本发明优选的加密系统的结构示意图。FIG. 3 is a schematic structural diagram of a preferred encryption system of the present invention.

具体实施方式Detailed ways

下面将结合附图对本公开实施例中的技术方案进行清楚、完整地描述，显而易见地，所描述的实施例仅仅是本发明的部分实施例，而不是全部的实施例。基于本公开实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，也属于本发明保护的范围。The technical solutions in the embodiments of the present disclosure will be clearly and completely described below with reference to the accompanying drawings. Obviously, the described embodiments are only some of the embodiments of the present invention, but not all of the embodiments. Based on the embodiments of the present disclosure, all other embodiments obtained by those of ordinary skill in the art without creative efforts also fall within the protection scope of the present invention.

本申请为一种支持浮点运算的改进同态乘法加密方法，基于混合Paillier和ELGamal算法的半同态乘法加密方案，该方案充分利用了Paillier算法和ELGamal算法的优点，Paillier算法只用于处理小范围内的整数加解密运算，可以在保持较高的加解密效率以及密文运算效率的同时，保证数据运算的准确性。Paillier算法可用来加密随机扰动数k，随机扰动数k是ELGamal算法每次加密都需要用到c*k中的一部分，k的取值范围在[L_k，M_k]中波动，以保证每次加密使用的c*k都是一次性的，若c*k重复使用，那么会造成即使攻击者不知道密钥的情况下，也可能破译出密文，不利于安全性。Paillier算法将加密后的Enc_paillier(k)作为传输密文二元组中第一个元素，ELGamal算法可以支持重加密(re-cypher)，在不暴露明文的情况下，对密钥进行交换，从而得到新鲜密文。This application is an improved homomorphic multiplication encryption method that supports floating-point operations. It is a semi-homomorphic multiplication encryption scheme based on the mixed Paillier and ELGamal algorithms. This scheme makes full use of the advantages of the Paillier algorithm and the ELGamal algorithm. The Paillier algorithm is only used for processing Integer encryption and decryption operations in a small range can maintain high encryption and decryption efficiency and ciphertext operation efficiency while ensuring the accuracy of data operations. The Paillier algorithm can be used to encrypt the random perturbation number k. The random perturbation number k is a part of c*k that needs to be used in each encryption of the ELGamal algorithm. The value range of k fluctuates in [L_k , M_k ] to ensure that every encryption The c*k used in the secondary encryption are all one-time use. If c*k is used repeatedly, the ciphertext may be deciphered even if the attacker does not know the key, which is not conducive to security. The Paillier algorithm uses the encrypted Enc_paillier (k) as the first element in the transmission ciphertext two-tuple, and the ELGamal algorithm can support re-encryption (re-cypher), exchanging keys without exposing the plaintext, Thus, fresh ciphertext is obtained.

当前已有的同态加密，仅适用于整数型数据的有限次运算，对大量数据运算效率低，无法广泛应用到实际工程应用中，存在密钥管理困难的问题。基于混合Paillier算法和ELGamal算法的半同态乘法加密方案，在保证数据运算准确性和安全性的情况下，大大提高了加解密的效率，使其可以适用于浮点数的加解密运算。The existing homomorphic encryption is only suitable for a limited number of operations on integer data, and the operation efficiency for a large amount of data is low, so it cannot be widely used in practical engineering applications, and there is a problem of difficult key management. The semi-homomorphic multiplication encryption scheme based on the hybrid Paillier algorithm and the ELGamal algorithm greatly improves the efficiency of encryption and decryption while ensuring the accuracy and security of data operations, making it suitable for encryption and decryption of floating-point numbers.

应当知晓的是，本申请为基于Paillier算法和ELGamal算法优化的加密算法，因此，Paillier算法及ELGamal算法作为本申请的现有技术，其技术方案都可直接应用于本申请，并与本申请的技术方案结合。It should be known that this application is an encryption algorithm optimized based on Paillier algorithm and ELGamal algorithm, therefore, Paillier algorithm and ELGamal algorithm are the prior art of this application, and their technical solutions can be directly applied to this application, and are compatible with this application. Combining technical solutions.

如图1所示，为本申请的支持浮点运算的改进同态乘法加密方法，包括步骤：As shown in Figure 1, the improved homomorphic multiplication encryption method supporting floating-point operations of the present application includes the steps:

SA，生成所述加密算法的密钥,密钥包括公钥以及私钥；所述的公钥为Paillier生成的公钥pk_Paillier；所述的私钥为{sk_Paillier,g,a,L_K,M_K,c}；所述的g、a和c为随机数，L_K和M_K为随机正整数；SA, generates the key of the encryption algorithm, and the key includes a public key and a private key; the public key is the public key pk_{Paillier generated by Paillier} ; the private key is {sk_Paillier , g, a, L_K ,M_K ,c}; the g, a and c are random numbers, and L_K and M_K are random positive integers;

SB，对明文M进行加密，生成随机扰动参数k，k为有界正整数，范围为(L_K,M_K)；使用私钥对明文M加密后得到密文C，密文C＝(Enc_Paillier(c×k),M×g^k×a)；其中，c是随机生成的整数，作为私钥的一部分；SB, encrypt the plaintext M, and generate a random perturbation parameter k, where k is a bounded positive integer with a range of (L_K , M_K ); after encrypting the plaintext M with the private key, the ciphertext C is obtained, where the ciphertext C=(Enc_Paillier (c×k), M×g^k×a ); where c is a randomly generated integer as part of the private key;

SC，解密所述密文C，已知私钥的情况下，使用所述sk_Paillier解密得到所述c×k，通过公式M＝(M×g^k×a)/g^c×k×a/c得到明文M。SC, decrypt the ciphertext C, when the private key is known, use the sk_{Paillier to} decrypt to obtain the c×k, through the formula M=(M×g^k×a )/g^{c×k×a/ c} gets plaintext M.

具体地说，步骤SA为密钥生成步骤，生成内容包括公钥以及私钥，所述的公钥为paillier算法的公钥pk_Paillier和一张映射表，使用特定的算法生成一张映射表，该映射表内容为本申请密文C二元组的对应关系。即Enc_Paillier(c×Δk)与g^Δk×a的对应关系，该映射关系下的扰动参数k值相同。Specifically, step SA is a key generation step, and the generated content includes a public key and a private key, and the public key is the public key pk Paillier of the_paillier algorithm and a mapping table, and a mapping table is generated using a specific algorithm, The content of the mapping table is the corresponding relationship of the ciphertext C two-tuple of the application. That is, the corresponding relationship between Enc_Paillier (c×Δk) and g^Δk×a , the perturbation parameter k value under this mapping relationship is the same.

所述的私钥包括Paillier算法私钥sk_Paillier，随机数g和a，随机正整数L_K和M_K以及c。优选地，所述的g和a为随机浮点数。The private key includes the Paillier algorithm private key sk_Paillier , random numbers g and a, random positive integers L_K and M_K and c. Preferably, the g and a are random floating point numbers.

所述的L_K和M_K之间需要满足M_K＝(p+1)×L_K/p，其中p为大于2的正整数，优选地L_K取超过100的整数，所述的p取值大于10，所述的p取值越大越安全。在(L_K,M_K)的范围内选取k，作为随机扰动参数。The relationship between L_K and M_K needs to satisfy M_K =(p+1)×L_K /p, where p is a positive integer greater than 2, preferably L_K is an integer exceeding 100, and the p is If the value is greater than 10, the larger the value of p is, the safer it is. Select k in the range of (L_K , M_K ) as a random disturbance parameter.

步骤SB为加密步骤，是以私钥来对明文M进行加密处理的过程，首先用paillier算法私钥sk_Paillier加密随机扰动参数k，加密后记录为Enc_Paillier(c×k)；其次是对明文数据M进行ELGamal算法类似的换算，记录为m×g^k×a，两者共同构成密文C二元组(Enc_Paillier(c×k),M×g^k×a)。然后把密文C和公钥发送给第三方进行同态运算，此时公钥的作用仅用于同态运算。Step SB is the encryption step, which is the process of encrypting the plaintext M with the private key. First, encrypt the random disturbance parameter k with the private key sk_Paillier of the Paillier algorithm, and record it as Enc_Paillier (c×k) after encryption; The data M is converted similar to the ELGamal algorithm and recorded as m×g^k×a , and the two together form the ciphertext C binary group (Enc_Paillier (c×k), M×g^k×a ). Then, the ciphertext C and the public key are sent to a third party for homomorphic operation. At this time, the function of the public key is only used for homomorphic operation.

密文二元组第一个元素是通过paillier算法加密后得到k的加密结果。用于通信双方传输k的值可以大大提高方案的安全性；二元组第二个元素是明文M通过算法以及随机浮点数g、a加密后形成的加密数，用于保护明文数据M不被泄露。The first element of the ciphertext two-tuple is the encryption result of k obtained after encryption by the paillier algorithm. The value of k used by both communicating parties to transmit the value of k can greatly improve the security of the scheme; the second element of the two-tuple is the encrypted number formed by the encryption of the plaintext M through the algorithm and random floating point numbers g and a, which is used to protect the plaintext data M from being encrypted. Give way.

步骤SC为解密过程，解密所述密文C，使用所述paillier算法私钥sk_Paillier解密得到所述c×k，c×k＝Dec_Paillier(Enc_Paillier(c×k))，在已知随机浮点数g、a的情况下，将求得的k代入明文计算函数M＝M×g^k×a/g^c×k×a/c，最终计算得明文M的数值。Step SC is the decryption process, decrypt the ciphertext C, use the Paillier algorithm private key sk_{Paillier to} decrypt to obtain the c×k, c×k=Dec_Paillier (Enc_Paillier (c×k)), in a known random In the case of floating-point numbers g and a, the obtained k is substituted into the plaintext calculation function M=M×g^k×a /g^c×k×a/c , and the value of the plaintext M is finally calculated.

本申请是基于paillier算法和ELGamal算法的半同态加密乘法方案，符合乘法的同态性，密文相乘解密后等于明文相乘的结果。在密文二元组相乘运算时，二元组第一个元素采用paillier算法进行加密，满足加法的同态性，即密文相乘解密等于明文相加的结果，二元组第二个元素则采用数学相乘运算的规则进行运算。通过相乘运算生成一个新的二元组，即运算后的密文二元组。通过算法解密，得到的结果与明文相乘的结果一致。This application is a semi-homomorphic encryption multiplication scheme based on the paillier algorithm and the ELGamal algorithm, which conforms to the homomorphism of multiplication, and the multiplication and decryption of ciphertext is equal to the result of multiplying plaintext. In the multiplication operation of ciphertext two-tuple, the first element of the two-tuple is encrypted by the paillier algorithm, which satisfies the homomorphism of addition, that is, the multiplication and decryption of the ciphertext is equal to the result of adding the plaintext, and the second element of the two-tuple is encrypted. Elements are calculated using the rules of mathematical multiplication. A new two-tuple is generated by the multiplication operation, that is, the ciphertext two-tuple after the operation. Through algorithm decryption, the result obtained is consistent with the result of multiplying the plaintext.

本申请的技术方案对传统同台加密算法的一个改进方案，新方案适用于浮点数类型的数据加密和乘法运算，且加解密速度比传统同态加密更加快。The technical solution of the present application is an improvement to the traditional same-stage encryption algorithm. The new solution is suitable for data encryption and multiplication operations of floating point type, and the encryption and decryption speed is faster than that of traditional homomorphic encryption.

在优选的所述的支持浮点运算的改进同态乘法加密方法中，所述的明文M及密文C分别为明文集和密文集，通过所述的步骤SB加密多个明文，将明文M₁至M_t加密为密文C₁至C_t；In the preferred improved homomorphic multiplication encryption method supporting floating-point operations, the plaintext M and the ciphertext C are respectively a plaintext set and a ciphertext set, and the plaintext M is encrypted by encrypting a plurality of plaintexts through the step SB.₁ to M_t are encrypted as ciphertext C₁ to C_t ;

所述的加密方法还包括如图2所示的步骤SB2，对所述的密文C₁至C_t进行乘法运算。The encryption method further includes step SB2 as shown in FIG. 2 , performing multiplication operations on the ciphertexts C₁ to C_t .

优选地，乘法运算由第三方进行，第三方获取密文C后对其运算后，将结果发送至解密方。本申请请乘法运算具体为：Preferably, the multiplication operation is performed by a third party, and after the third party obtains the ciphertext C and operates on it, the result is sent to the decryption party. In this application, the multiplication operation is specifically:

步骤SB2，对密文集进行乘法运算，两个相乘的密文分别为Step SB2, multiply the ciphertext set, and the two multiplied ciphertexts are respectively

C₁×C₂＝(Enc_Paillier(c×k₁+c×k₂),M₁×M₂×g^(k1+k2)×a。C₁ ×C₂ =(Enc_Paillier (c×k₁ +c×k₂ ),M₁ ×M₂ ×g^(k1+k2)×a .

针对上述的相乘运算，对应的所述的解密步骤SC具体为：解密所述进行乘法运算后的密文，使用所述sk_Paillier解密得到所述c×k，通过公式

得到明文M₁×M₂。For the above multiplication operation, the corresponding decryption step SC is specifically: decrypt the ciphertext after the multiplication operation, use the sk_Paillier decryption to obtain the c×k, and use the formula

The plaintext M₁ ×M₂ is obtained.

应当知晓的是，本申请说明书及权利要求中记载的明文M及密文C的下标，仅用于示例及方便说明，不作为对明文及密文数量的限制以及特定指代。使用本申请技术方案的任意数量的明文及密文都属于本申请的保护范围。It should be known that the subscripts of the plaintext M and the ciphertext C recorded in the description and claims of this application are only used for example and convenient description, and are not intended to limit or specify the quantity of plaintext and ciphertext. Any number of plaintexts and ciphertexts using the technical solutions of the present application belong to the protection scope of the present application.

本申请还包括一种支持浮点运算的改进同态乘法加密系统，包括密钥生成模块、加密模块以及解密模块；The present application also includes an improved homomorphic multiplication encryption system supporting floating point operations, including a key generation module, an encryption module and a decryption module;

所述的密钥生成模块用于生成所述加密算法的密钥,密钥包括公钥以及私钥；所述的公钥为Paillier生成的公钥pk_Paillier；所述的私钥为{sk_Paillier,g,a,L_K,M_K,c}；所述的g、a、c为随机浮点数，L_K和M_K为随机正整数；Described key generation module is used to generate the key of described encryption algorithm, and key comprises public key and private key; Described public key is the public key pk_Paillier that Paillier generates; Described private key is {sk_Paillier ,g,a,L_K ,M_K ,c}; the g, a, c are random floating-point numbers, and L_K and M_K are random positive integers;

所述的加密模块用于生成随机扰动参数k，k为有界正整数，范围为(L_K,M_K)；对明文M进行加密，使用私钥对明文M加密后得到密文C，密文C＝(Enc_Paillier(c×k),M×g^k×a)；The described encryption module is used to generate random disturbance parameter k, where k is a bounded positive integer, and the range is (L_K , M_K ); the plaintext M is encrypted, and the ciphertext C is obtained after encrypting the plaintext M with a private key, and the encrypted Text C=(Enc_Paillier (c×k), M×g^k×a );

所述的解密模块解密所述密文C，使用所述sk_Paillier解密得到所述c×k，通过公式m＝m×g^k×a/g^c×k×a/c得到明文M。The decryption module decrypts the ciphertext C, uses the sk_{Paillier to} decrypt to obtain the c×k, and obtains the plaintext M through the formula m=m×g^k×a /g^c×k×a/c .

所述的明文M及密文C分别为明文集和密文集，第三方端可对多个明文进行运算，将明文M₁至M_t加密为密文C₁至C_t；该第三方端对所述的密文C₁至C_t进行乘法运算。The plaintext M and the ciphertext C are respectively a set of plaintexts and a set of ciphertexts, and the third-party terminal can perform operations on a plurality of plaintexts, and encrypt the plaintexts M₁ to M_t into cipher texts C₁ to C_t ; The ciphertexts C₁ to C_t are multiplied.

第三方端对密文集进行乘法运算，C₁×C₂＝(Enc_Paillier(c×k₁+c×k₂),M1×M2×g^(k1+k2)×a。The third-party terminal performs a multiplication operation on the ciphertext set, C₁ ×C₂ =(Enc_Paillier (c×k₁ +c×k₂ ), M1×M2×g^(k1+k2)×a .

接收到第三方端运算后的密文，所述的解密模块解密所述进行乘法运算后的密文，使用所述sk_Paillier解密得到所述c×k，通过公式

得到明文M₁×M₂。After receiving the ciphertext after the third-party terminal operation, the decryption module decrypts the ciphertext after the multiplication operation, and uses the sk_{Paillier to} decrypt to obtain the c×k, through the formula

The plaintext M₁ ×M₂ is obtained.

本申请还包括一种计算机存储介质，其上存储有计算机可读指令，所述计算机可读指令可被处理器执行以实现上述加密方法。上述加密方法中的技术方案都可直接应用于计算机可读指令中。The present application also includes a computer storage medium having computer-readable instructions stored thereon, the computer-readable instructions being executable by a processor to implement the encryption method described above. The technical solutions in the above encryption methods can be directly applied to computer-readable instructions.

对上述的加密算法进行执行测试实验，在确保正确性和性能的情况下，对大量数据进行加解密，单线程测试，并测试数据加解密时间以及数据运算时间；如下表所示，表一为实验内容，表二为实验结果。Carry out the test experiment on the above encryption algorithm, under the condition of ensuring the correctness and performance, perform encryption and decryption on a large amount of data, single-threaded test, and test the data encryption and decryption time and data operation time; as shown in the following table, Table 1 is The experimental content, Table 2 is the experimental results.

表一实验内容Table 1 Experimental content

表二实验结果Table 2 Experimental results

经过实验测试，在计算器可计算的精度范围内，可以保证数据加解密的正确性和时间开销，浮点型数据加解密性能相对于整数加解密性能更优，耗时更小。基于Paillier算法和ELGamal算法的半同态乘法加密方案比传统的方案改进之处包括支持浮点型数据加解密和乘法同态运算以及加解密性能更优。After experimental tests, the correctness and time overhead of data encryption and decryption can be guaranteed within the accuracy range that the calculator can calculate. The performance of floating-point data encryption and decryption is better than that of integer encryption and decryption, and the time-consuming is less. Compared with the traditional scheme, the semi-homomorphic multiplication encryption scheme based on Paillier algorithm and ELGamal algorithm is improved, including support for floating-point data encryption and decryption and multiplication homomorphic operation, and better encryption and decryption performance.

如本申请和权利要求书中所示，一般说来，术语“包括”与“包含”仅提示包括已明确标识的步骤和元素，而这些步骤和元素不构成一个排它性的罗列，方法或者设备也可能包含其他的步骤或元素。As shown in this application and in the claims, in general, the terms "comprising" and "comprising" only imply the inclusion of specifically identified steps and elements, and these steps and elements do not constitute an exclusive list, method or Equipment may also contain other steps or elements.

除非另外具体说明，否则在这些实施例中阐述的部件、相对布置、功能、数值并不限制本发明的范围。同时，显而易见的，为了便于叙述，附图中所示的各个部分的尺寸并不是按照实际的比例关系绘制的。对于相关领域普通技术人员已知的技术、方法和设备暂不做详细描述，但在适当情况下，所述技术、方法和设备应当被视为授权说明书的一部分。在这里示出的和讨论的所有示例中，任何具体值应被解释为仅仅是实例性的，而不是作为限制。因此，步骤性实施例的其他示例可以具有不同的先后顺序。The components, relative arrangements, functions, values set forth in these embodiments do not limit the scope of the invention unless specifically stated otherwise. Meanwhile, it is obvious that the dimensions of the various parts shown in the accompanying drawings are not drawn according to the actual proportional relationship for convenience of description. Techniques, methods, and devices known to those of ordinary skill in the relevant art will not be described in detail, but where appropriate, the techniques, methods, and devices should be considered as part of the authorized specification. In all examples shown and discussed herein, any specific value should be construed as illustrative only and not as limiting. Accordingly, other examples of step-by-step embodiments may have different sequences.

上面是对本发明的说明，而不应被认为是对其的限制。尽管描述了本发明的若干示例性实施例，但本领域技术人员将容易地理解，在不背离本发明的技术特征的前提下可以对示例性实施例进行许多修改。因此，所有这些修改都意图包含在权利要求书所限定的本发明范围内。应当理解，上面是对本发明的说明，而不应被认为是限于所公开的特定实施例，并且对所公开的实施例以及其他实施例的修改意图包含在所附权利要求书的范围内。本发明由权利要求书及其等效物限定。The above is an illustration of the present invention and should not be construed as limiting it. Although several exemplary embodiments of the present invention have been described, those skilled in the art will readily appreciate that many modifications can be made to the exemplary embodiments without departing from the technical characteristics of the present invention. Accordingly, all such modifications are intended to be included within the scope of this invention as defined in the claims. It is to be understood that the foregoing descriptions of the invention are not to be considered limited to the particular embodiments disclosed, and that modifications to the disclosed embodiments, as well as other embodiments, are intended to be included within the scope of the appended claims. The invention is defined by the claims and their equivalents.

Claims (9)

Translated fromChinese

1.一种支持浮点运算的改进同态乘法加密方法，其特征在于，包括步骤：1. an improved homomorphic multiplication encryption method supporting floating point operation, is characterized in that, comprises the steps:SA，生成所述加密算法的密钥，密钥包括公钥以及私钥；所述的公钥为Paillier生成的公钥pk_Paillier；所述的私钥为{sk_Paillier,g,a,L_K,M_K,c}；所述的g、a和c为随机数，L_K和M_K为随机正整数；SA, generates the key of the encryption algorithm, and the key includes a public key and a private key; the public key is the public key pk_{Paillier generated by Paillier} ; the private key is {sk_Paillier , g, a, L_K ,M_K ,c}; the g, a and c are random numbers, and L_K and M_K are random positive integers;SB，对明文M进行加密，生成随机扰动参数k，k为有界正整数，范围为(L_K,M_K)；使用私钥对明文M加密后得到密文C，密文C＝(Enc_Paillier(c×k),M×g^k×a)；其中，c是随机生成的整数，作为私钥的一部分；SB, encrypt the plaintext M, and generate a random perturbation parameter k, where k is a bounded positive integer with a range of (L_K , M_K ); after encrypting the plaintext M with the private key, the ciphertext C is obtained, where the ciphertext C=(Enc_Paillier (c×k), M×g^k×a ); where c is a randomly generated integer as part of the private key;SC，解密所述密文C，已知私钥的情况下，使用所述sk_Paillier解密得到所述c×k，通过公式M＝(M×g^k×a)/g^c×k×a/c得到明文M。SC, decrypt the ciphertext C, when the private key is known, use the sk_{Paillier to} decrypt to obtain the c×k, through the formula M=(M×g^k×a )/g^{c×k×a/ c} gets plaintext M.2.根据权利要求1所述的支持浮点运算的改进同态乘法加密方法，其特征在于，所述的明文M及密文C分别为明文集和密文集，通过所述的步骤SB加密多个明文，将明文M₁至M_t加密为密文C₁至C_t；2. the improved homomorphic multiplication encryption method supporting floating-point operation according to claim 1, is characterized in that, described plaintext M and ciphertext C are respectively plaintext set and ciphertext set, and encrypts many by described step SB. the plaintexts M₁ to M_t are encrypted into ciphertexts C₁ to C_t ;所述的加密方法还包括步骤SB2，对所述的密文C₁至C_t进行乘法运算。The encryption method further includes a step SB2 of multiplying the ciphertexts C₁ to C_t .3.根据权利要求2所述的支持浮点运算的改进同态乘法加密方法，其特征在于，SB2，对密文集进行乘法运算，C₁×C₂＝(Enc_Paillier(c×k₁+c×k₂),M₁×M₂×g^(k1+k2)×a。3. The improved homomorphic multiplication encryption method supporting floating point operation according to claim 2, is characterized in that, SB2, carries out multiplication operation to ciphertext set, C₁ ×C₂ =(Enc_Paillier (c×k₁ +c ×k₂ ), M₁ ×M₂ ×g^(k1+k2)×a .4.根据权利要求2所述的支持浮点运算的改进同态乘法加密方法，其特征在于，所述的步骤SC具体为：解密所述进行乘法运算后的密文，使用所述sk_Paillier解密得到所述c×k，通过公式

得到明文M₁×M₂。4. the improved homomorphic multiplication encryption method supporting floating point operation according to claim 2, is characterized in that, described step SC is specifically: decrypt the described ciphertext after multiplication operation, use described sk_{Paillier to} decrypt to get the c×k, by formula

The plaintext M₁ ×M₂ is obtained.5.根据权利要求1所述的支持浮点运算的改进同态乘法加密方法，其特征在于，所述的L_K和M_K之间需要满足M_K＝(p+1)×L_K/p，其中p为大于2的正整数，L_K取超过100的整数。5. The improved homomorphic multiplication encryption method supporting floating-point operations according to claim 1, wherein the L_K and the M_K need to satisfy the M_K =(p+1)×L_K /p , where p is a positive integer greater than 2, and L_K is an integer greater than 100.6.根据权利要求1所述的支持浮点运算的改进同态乘法加密方法，其特征在于，所述的p取值大于10。6 . The improved homomorphic multiplication encryption method supporting floating-point operations according to claim 1 , wherein the value of p is greater than 10. 7 .7.根据权利要求1所述的支持浮点运算的改进同态乘法加密方法，其特征在于，所述的g和a为随机浮点数。7 . The improved homomorphic multiplication encryption method supporting floating-point operations according to claim 1 , wherein the g and a are random floating-point numbers. 8 .8.一种支持浮点运算的改进同态乘法加密系统，其特征在于，包括密钥生成模块、加密模块以及解密模块；8. an improved homomorphic multiplication encryption system supporting floating point operations, characterized in that, comprising a key generation module, an encryption module and a decryption module;所述的密钥生成模块用于生成所述加密算法的密钥,密钥包括公钥以及私钥；所述的公钥为Paillier生成的公钥pk_Paillier；所述的私钥为{sk_Paillier,g,a,L_K,M_K，c}；所述的g和a为随机浮点数，L_K和M_K为随机正整数；Described key generation module is used to generate the key of described encryption algorithm, and key comprises public key and private key; Described public key is the public key pk_Paillier that Paillier generates; Described private key is {sk_Paillier , g, a, L_K , M_K , c}; the g and a are random floating-point numbers, and L_K and M_K are random positive integers;所述的加密模块用于生成随机扰动参数k，k为有界正整数，范围为(L_K,M_K)；对明文M进行加密，使用私钥对明文M加密后得到密文C，密文C＝(Enc_Paillier(c×k),M×g^k×a)；The described encryption module is used to generate random disturbance parameter k, where k is a bounded positive integer, and the range is (L_K , M_K ); the plaintext M is encrypted, and the ciphertext C is obtained after encrypting the plaintext M with a private key, and the encrypted Text C=(Enc_Paillier (c×k), M×g^k×a );所述的解密模块解密所述密文C，使用所述sk_Paillier解密得到所述c×k，通过公式M＝M×g^k×a/g^c×k×a/c得到明文M。The decryption module decrypts the ciphertext C, uses the sk_{Paillier to} decrypt to obtain the c×k, and obtains the plaintext M through the formula M=M×g^k×a /g^c×k×a/c .9.一种计算机存储介质，其上存储有计算机可读指令，其特征在于，所述计算机可读指令可被处理器执行以实现上述权利要求1～7中的加密方法。9. A computer storage medium having computer-readable instructions stored thereon, wherein the computer-readable instructions can be executed by a processor to implement the encryption method in the above claims 1-7.

Images