CN117312743B - Rapid matrix multiplication method in Paillier ciphertext space - Google Patents
Rapid matrix multiplication method in Paillier ciphertext space Download PDFInfo
- Publication number
- CN117312743B CN117312743B CN202311346034.1A CN202311346034A CN117312743B CN 117312743 B CN117312743 B CN 117312743B CN 202311346034 A CN202311346034 A CN 202311346034A CN 117312743 B CN117312743 B CN 117312743B
- Authority
- CN
- China
- Prior art keywords
- matrix
- ciphertext
- vector
- plaintext
- column
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
- G06F17/10—Complex mathematical operations
- G06F17/16—Matrix or vector computation, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F21/00—Security arrangements for protecting computers, components thereof, programs or data against unauthorised activity
- G06F21/60—Protecting data
- G06F21/602—Providing cryptographic facilities or services
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/52—Multiplying; Dividing
- G06F7/523—Multiplying only
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02D—CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE
- Y02D10/00—Energy efficient computing, e.g. low power processors, power management or thermal management
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Mathematical Physics (AREA)
- General Engineering & Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Software Systems (AREA)
- Computing Systems (AREA)
- Databases & Information Systems (AREA)
- Algebra (AREA)
- Health & Medical Sciences (AREA)
- Bioethics (AREA)
- General Health & Medical Sciences (AREA)
- Computer Hardware Design (AREA)
- Computer Security & Cryptography (AREA)
- Complex Calculations (AREA)
Abstract
本发明提供了一种Paillier密文空间中快速矩阵乘法方法。该方法包括：对明文矩阵中的明文元素进行预设精度的编码，得到预处理后的明文矩阵，并计算密文矩阵中密文元素的模逆值，将密文元素的模逆值缓存在存储设备中；利用存储设备中缓存的密文元素的模逆值，将密文矩阵中的个行向量与预处理后的明文矩阵进行并行化的矩阵向量乘法，得到个列向量集合；利用Paillier密文空间中的快速求和方法对个列向量集合中的每个列向量集合沿着纵轴方向进行求和，得到个行向量，并对个行向量沿着纵轴方向进行拼接，得到矩阵乘法结果。
The present invention provides a fast matrix multiplication method in a Paillier ciphertext space. The method comprises: encoding plaintext elements in a plaintext matrix with a preset precision to obtain a preprocessed plaintext matrix, calculating the modular inverse values of the ciphertext elements in the ciphertext matrix, and caching the modular inverse values of the ciphertext elements in a storage device; using the modular inverse values of the ciphertext elements cached in the storage device to multiply the ciphertext elements in the ciphertext matrix; Parallel matrix-vector multiplication of row vectors with the preprocessed plaintext matrix is obtained A set of column vectors; using the fast summation method in Paillier ciphertext space Each column vector set in the column vector set is summed along the vertical axis direction to obtain row vectors, and The row vectors are concatenated along the vertical axis to obtain the matrix multiplication result.
Description
Technical Field
The invention relates to the fields of data security and cryptography, in particular to a rapid matrix multiplication method in a Paillier ciphertext space, electronic equipment and a storage medium.
Background
In the field of privacy computation, the Paillier homomorphic encryption algorithm is a cryptographic method that is widely used and has strict security credentials. The algorithm is used in many privacy-preserving machine learning algorithms and protocols, such as federal learning, privacy set-up, hidden-track queries, and the like.
In the algorithm and protocol based on Paillier homomorphic encryption design, matrix multiplication operation in ciphertext space is a basic cryptography operator, and is widely used in algorithm protocols such as longitudinal linear regression, longitudinal logistic regression, longitudinal neural network and the like. For example, in the vertical logistic regression algorithm, when calculating the gradient in the ciphertext space, a matrix multiplication operation is required by using the local plaintext training data and the received ciphertext residual vector.
However, because the calculation cost of addition and multiplication in the Paillier ciphertext space is large, when the number of elements in the ciphertext matrix and the plaintext matrix is large, the calculation cost of matrix multiplication in the ciphertext space becomes huge, and becomes a calculation efficiency bottleneck of the whole protocol, thereby affecting the effective floor and wide application of the privacy protection protocol.
Disclosure of Invention
In view of the foregoing, the present invention provides a fast matrix multiplication method in a Paillier ciphertext space, an electronic device, and a storage medium, so as to solve at least one of the foregoing problems.
According to a first aspect of the present invention, there is provided a method for fast matrix multiplication in a Paillier ciphertext space, applied to the fields of financial big data, medical big data, cloud computing and federal learning, comprising:
coding the plaintext elements in the plaintext matrix with preset precision to obtain a preprocessed plaintext matrix, calculating the modular inverse value of the ciphertext elements in the ciphertext matrix, and caching the modular inverse value of the ciphertext elements in a storage device;
using the modulo inverse of the ciphertext element cached in the storage device to determine the value of the ciphertext element in the ciphertext matrix The individual row vectors are subjected to parallelized matrix vector multiplication with the preprocessed plaintext matrix to obtainA set of column vectors, wherein,Each set of column vectors includes a plurality of column vectors, being a positive integer greater than or equal to 1;
rapid summation method pair in Paillier ciphertext space Summing each column vector set in the column vector sets along the longitudinal axis direction to obtainIndividual row vectors and pairs ofAnd splicing the row vectors along the longitudinal axis direction to obtain a matrix multiplication result.
According to an embodiment of the present invention, the foregoing encoding of the plaintext elements in the plaintext matrix with a preset precision includes encoding the plaintext elements into a data form having a precision specified by a user according to a floating point number encoding standard specified by the user;
wherein, the data form with the user specified precision is as shown in formula (1):
(1),
wherein, Representing the first in the plaintext matrix shownLine 1The plain text element of the column,Representation and representationA corresponding mantissa portion of the input signal,As a base number, the number of the base number,Is an exponential term section.
According to an embodiment of the present invention, calculating the modulo inverse value of the ciphertext element in the ciphertext matrix, and buffering the modulo inverse value of the ciphertext element in the storage device includes:
Calculating the modular inverse value of the ciphertext element according to a preset modular inverse value calculation formula and a preset Paillier public key, and avoiding repeated calculation of the modular inverse value in the Paillier ciphertext space through the modular inverse value of the ciphertext element cached in the storage device in advance;
The preset modulus inverse value calculation formula is shown as formula (2):
(2),
wherein, Representing the first of the ciphertext matricesLine 1The ciphertext elements of the column,Representation and representationThe corresponding modulus of the inverse value is calculated,Representing a preset Paillier public key.
According to the embodiment of the invention, the modulus inverse value of the ciphertext element cached in the storage device is utilized to divide the ciphertext matrix into ciphertext matricesThe individual row vectors are subjected to parallelized matrix vector multiplication with the preprocessed plaintext matrix to obtainThe set of column vectors includes:
in memory device, constructing a matrix with the same dimension as the plaintext matrix A plurality of cache matrices;
performing matrix vector multiplication on a row vector in the ciphertext matrix and the preprocessed plaintext matrix by using a modulo inverse value of the ciphertext element cached in the storage device to obtain a column vector set;
parallelization repeatedly performs matrix vector multiplication on all row vectors in the ciphertext matrix to obtain A set of column vectors;
Will be The set of column vectors is stored toAnd each buffer matrix stores one column vector set.
According to an embodiment of the present invention, the performing matrix vector multiplication on a row vector in a ciphertext matrix and a preprocessed plaintext matrix by using a modulo inverse value of a ciphertext element cached in a storage device, to obtain a column vector set includes:
Integrating positive numbers in the plaintext line vectors participating in the calculation into positive vectors, and integrating negative numbers in the plaintext line vectors participating in the calculation into negative vectors;
performing element-by-element calculation operation on the ciphertext element and the positive vector to obtain a positive calculation result, and performing element-by-element calculation operation on the modulus inverse value of the ciphertext element and the negative vector to obtain a negative calculation result;
And respectively assigning positive calculation results and negative calculation results to the cache matrix according to the subscript information of the ciphertext elements and the subscript information of the plaintext line vectors.
According to a second aspect of the present invention, there is provided a fast matrix multiplication system in a Paillier ciphertext space, applied to a financial big data field, a medical big data field, a cloud computing field, and a federal learning field, comprising:
The preprocessing module is used for carrying out coding with preset precision on plaintext elements in the plaintext matrix to obtain a preprocessed plaintext matrix, calculating the modulo inverse value of the ciphertext elements in the ciphertext matrix, and caching the modulo inverse value of the ciphertext elements in the storage device;
matrix vector multiplication module for multiplying ciphertext matrix by using modulo inverse value of ciphertext element cached in storage device The individual row vectors are subjected to parallelized matrix vector multiplication with the preprocessed plaintext matrix to obtainA set of column vectors, wherein,Each set of column vectors includes a plurality of column vectors, being a positive integer greater than or equal to 1;
The vector sum-up module is used for summing the vector, rapid summing method pair for utilizing Paillier ciphertext space Summing each column vector set in the column vector sets along the longitudinal axis direction to obtainIndividual row vectors and pairs ofAnd splicing the row vectors along the longitudinal axis direction to obtain a matrix multiplication result.
According to a third aspect of the present invention, there is provided an electronic device comprising:
One or more processors;
storage means for storing one or more programs,
Wherein the one or more programs, when executed by the one or more processors, cause the one or more processors to perform a fast matrix multiplication method in the Paillier ciphertext space.
According to a fourth aspect of the present invention there is provided a computer readable storage medium having stored thereon executable instructions which when executed by a processor cause the processor to perform a method of fast matrix multiplication in a Paillier ciphertext space.
The rapid matrix multiplication method in the Paillier ciphertext space aims to reduce the time overhead of ciphertext space matrix multiplication operation. Different from the traditional matrix multiplication based on the Paillier homomorphic encryption algorithm, the method is characterized in that data are preprocessed, a plaintext matrix is coded with low precision to reduce calculated amount, a modular inverse value of ciphertext in the ciphertext matrix is cached to avoid repeated calculation, and a parallelization calculation framework is adopted to calculate matrix vector multiplication between a plurality of groups of ciphertext vectors and the plaintext matrix simultaneously. In each group of matrix vector multiplication, a parallelization frame is also used for simultaneously calculating element-by-element multiplication between ciphertext and plaintext vector, and all results are summarized to obtain the result of matrix multiplication operation in the whole ciphertext space. The method provided by the invention can reduce repeated modular inverse operation to the greatest extent, and fully utilizes the multi-core computing capability of the CPU, so that the performance and efficiency of matrix multiplication operation in the Paillier ciphertext space can be improved. Meanwhile, the method is based on the Paillier homomorphic encryption algorithm, so that the accuracy and the safety of a calculation result can be ensured.
Drawings
FIG. 1 is a flow chart of a method of fast matrix multiplication in Paillier ciphertext space in accordance with an embodiment of the invention;
FIG. 2 is a diagram of computer time overhead comparisons of different fast matrix multiplications based on Paillier ciphertext space, in accordance with an embodiment of the invention;
FIG. 3 is a schematic diagram of a fast matrix multiplication system in Paillier ciphertext space in accordance with an embodiment of the invention;
Fig. 4 schematically shows a block diagram of an electronic device adapted to implement a fast matrix multiplication method in the Paillier ciphertext space, according to an embodiment of the invention.
Detailed Description
The present invention will be further described in detail below with reference to specific embodiments and with reference to the accompanying drawings, in order to make the objects, technical solutions and advantages of the present invention more apparent.
It should be noted that, in the technical scheme disclosed by the invention, the acquisition of the related plaintext data and ciphertext data is authorized by the related party, and the data is processed, applied and stored under the permission of the related party, so that the related process accords with the rules of laws and regulations, necessary and reliable confidentiality measures are adopted, and the requirements of popular regulations are met.
The method provided by the invention can be applied to various fields such as finance, government affairs, medical treatment and the like. For example, in a financial loan evaluation scenario, a bank or a financial institution has data such as individual deposit, loan history, consumption records of a depositor, in order to improve the loan accuracy of a loan service, the private data of the depositor is usually encrypted by a Paillier homomorphic algorithm, and then is jointly calculated with other internet companies to calculate a matrix multiplication operation in a ciphertext space, so as to obtain the loan risk probability of each depositor. In addition, in the medical cancer diagnosis scene, public and private medical institutions master a certain amount of customer privacy data such as disease history, genetic medical history, medical insurance amount and the like, but the data cannot be shared by each other, so that the private medical institutions encrypt the private data mastered by the institutions by means of Paillier homomorphic algorithm, and then perform matrix multiplication operation on ciphertext space between the data of the public and private hospitals so as to obtain the probability of cancer of each customer.
In order to solve various technical problems in the prior art, the invention provides a rapid matrix multiplication method in a Paillier ciphertext space, which aims to accelerate rapid ciphertext space matrix multiplication operation based on a Paillier homomorphic encryption algorithm.
In order to improve the calculation efficiency of matrix multiplication operation in the Paillier ciphertext space on the premise of ensuring the accuracy of a certain floating point number calculation result, the following optimization strategy is adopted.
First, the data is preprocessed, and each element in the plaintext matrix is encoded with low precision, so as to reduce the amount of computation. And secondly, calculating and caching a modulus inverse value for each ciphertext in the ciphertext matrix so as to avoid repeated calculation. Then, adopting the thought of parallel computing to simultaneously carry out matrix vector multiplication on each row vector in the ciphertext matrix and the plaintext matrix. In the computation of matrix vector multiplication, a parallelization thought is also adopted to compute the element-by-element multiplication of each ciphertext in the ciphertext row vector with the plaintext vector. And finally, summing the column vectors by using a fast summing method on the Paillier ciphertext set to obtain the result of each group of matrix vector multiplication, and splicing the results together to obtain a final calculation result. The optimization strategies reduce the calculation overhead of matrix multiplication operation in the Paillier ciphertext space, thereby improving the performance of the privacy calculation system.
Fig. 1 is a flow chart of a fast matrix multiplication method in the Paillier ciphertext space according to an embodiment of the invention.
As shown in fig. 1, the rapid matrix multiplication method in the Paillier ciphertext space is applied to the financial big data field, the medical big data field, the cloud computing field and the federal learning field, and comprises operations S110 to S130.
In operation S110, a plaintext element in the plaintext matrix is encoded with a preset precision, a preprocessed plaintext matrix is obtained, a modulo inverse value of a ciphertext element in the ciphertext matrix is calculated, and the modulo inverse value of the ciphertext element is cached in a storage device.
The preset precision code may be, for example, IEEE754 floating point code standard.
According to an embodiment of the present invention, the foregoing encoding of the plaintext elements in the plaintext matrix with a preset precision includes encoding the plaintext elements into a data form having a precision specified by a user according to a floating point number encoding standard specified by the user;
wherein, the data form with the user specified precision is as shown in formula (1):
(1),
wherein, Representing the first in the plaintext matrix shownLine 1The plain text element of the column,Representation and representationA corresponding mantissa portion of the input signal,As a base number, the number of the base number,Is an exponential term section.
According to an embodiment of the present invention, calculating the modulo inverse value of the ciphertext element in the ciphertext matrix, and buffering the modulo inverse value of the ciphertext element in the storage device includes:
Calculating the modular inverse value of the ciphertext element according to a preset modular inverse value calculation formula and a preset Paillier public key, and avoiding repeated calculation of the modular inverse value in the Paillier ciphertext space through the modular inverse value of the ciphertext element cached in the storage device in advance;
The preset modulus inverse value calculation formula is shown as formula (2):
(2),
wherein, Representing the first of the ciphertext matricesLine 1The ciphertext elements of the column,Representation and representationThe corresponding modulus of the inverse value is calculated,Representing a preset Paillier public key.
The low-precision coding and the calculation of the modular inverse value of the plaintext matrix and the ciphertext matrix are respectively performed in the data preprocessing stage of the method, namely, the data preprocessing is required to be performed on the ciphertext matrix and the plaintext matrix before the matrix multiplication operation in the ciphertext space is performed.
At the low-precision encoding sub-stage of the plaintext matrix, for each element in the plaintext matrixEncodes it into code according to IEEE 754 floating point number code standardForm of the type whereinFor the mantissa portion of the floating point number,As a base number, the number of the base number,Is an exponential term section. After the floating point number is subjected to low-precision coding, the generated mantissa part has smaller numerical value, and according to the Paillier ciphertext multiplication property, when the subsequent multiplication operation is performed with the ciphertext, the mantissa is used as an exponent item of the modular exponentiation operation, so that the calculation overhead of the ciphertext multiplication operation can be effectively reduced by the smaller mantissa.
In the sub-stage of calculating the modulus inverse value of the ciphertext matrix and caching the calculation result, for each element in the ciphertext matrixCalculating the modulus inverse valueAnd buffer so as to satisfyWhereinIs the Paillier public key. Therefore, when the ciphertext space multiplication operation is carried out on each ciphertext and a plurality of different negative number plaintext, repeated calculation of the modulus inverse value can be effectively avoided, and the calculation efficiency is further improved.
In operation S120, the modulo inverse value of the ciphertext element cached in the storage device is used to determine the value of the ciphertext matrixThe individual row vectors are subjected to parallelized matrix vector multiplication with the preprocessed plaintext matrix to obtainA set of column vectors, wherein,Each set of column vectors includes a plurality of column vectors, which are positive integers greater than or equal to 1.
According to the embodiment of the invention, the modulus inverse value of the ciphertext element cached in the storage device is utilized to divide the ciphertext matrix into ciphertext matricesThe individual row vectors are subjected to parallelized matrix vector multiplication with the preprocessed plaintext matrix to obtainThe column vector set comprises constructing, in the memory device, a matrix having the same dimensions as the plaintext matrixMatrix vector multiplication is carried out on one row vector in the ciphertext matrix and the preprocessed plaintext matrix by utilizing the modular inverse value of the ciphertext element cached in the storage device to obtain a column vector setSets of column vectorsThe set of column vectors is stored toAnd each buffer matrix stores one column vector set.
According to the embodiment of the invention, the matrix vector multiplication is carried out on one row vector in the ciphertext matrix and the preprocessed plaintext matrix by utilizing the modulo inverse value of the ciphertext element cached in the storage device to obtain a column vector set, wherein the step of integrating positive numbers in the plaintext row vector participating in calculation into positive vectors and integrating negative numbers in the plaintext row vector participating in calculation into negative vectors comprises the steps of carrying out element-by-element calculation on the ciphertext element and the positive vectors to obtain positive calculation results and carrying out element-by-element calculation on the modulo inverse value of the ciphertext element and the negative vector to obtain negative calculation results, and the positive calculation results and the negative calculation results are respectively assigned to the cache matrix according to subscript information of the ciphertext element and subscript information of the plaintext row vector.
In operation S130, the pair is summed using a fast sum method in the Paillier ciphertext spaceSumming each column vector set in the column vector sets along the longitudinal axis direction to obtainIndividual row vectors and pairs ofAnd splicing the row vectors along the longitudinal axis direction to obtain a matrix multiplication result.
The operations S120 to S130 belong to the parallelization matrix multiplication stage of the method of the present invention, and after completing the data preprocessing of the plaintext matrix and the ciphertext matrix related to the operation S110, the processed ciphertext matrix multiplication operation is completed by adopting a parallel computing framework.
The parallelization matrix multiplication stage comprises two sub-stages, namely a parallelization calculation ciphertext vector and plaintext matrix multiplication sub-stage and a final output sub-stage for summarizing intermediate results.
Parallelization calculation of ciphertext vector and plaintext matrix multiplication sub-stage, for each row vector of ciphertext matrixParallelization calculation of ciphertext vectorAnd plaintext matrixMultiplication of (2). Firstly, a buffer memory matrix with the same size as a plaintext matrix is createdIts dimension is alsoThen the ciphertext vector and plaintext matrix multiplication calculation process is broken down into the following two sub-processes:
(1) Element-by-element multiplication between single ciphertext and plaintext row vector by parallelization calculation Each ciphertext of (a)Parallelizing and calculating corresponding plaintext row vectorMultiplication element by element, storing the calculated ciphertext line vector in the first buffer matrixLines, i.e.. In the calculationWhen the method is used, the method further disassembles and groupsIntegration of positive numbers in (a) into vectorsIn (1) willIs integrated into a vectorIn then simultaneously calculateAndElement-by-element multiplication over two groupings, where the computation isWhen needed to be utilized toFor accelerating the calculation process. Finally, the calculation results on the two groups are assigned back according to the corresponding relation of the element subscriptsIs a kind of medium.
(2) Summing each column vector of the buffer matrix, namely obtaining the buffer matrix with the size ofCiphertext matrix of (a). Then, along the longitudinal axis, summing each column vector by using a fast summing method on the Paillier dense culture set to finally obtain the vector with the dimension ofResult vector of (a)。
Summarizing intermediate results to generate final output sub-stage, wherein each ciphertext row vector in the parallelization calculation ciphertext vector and plaintext matrix multiplication sub-stage is multiplied by plaintext matrix calculation to obtain dimension as followsCiphertext row vector of (2)Will beThe row vectors are spliced along the longitudinal axis direction to obtain the final result matrixThe calculation process is completed.
The rapid matrix multiplication method in the Paillier ciphertext space aims to reduce the time overhead of ciphertext space matrix multiplication operation. Different from the traditional matrix multiplication based on the Paillier homomorphic encryption algorithm, the method is characterized in that data are preprocessed, a plaintext matrix is coded with low precision to reduce calculated amount, a modular inverse value of ciphertext in the ciphertext matrix is cached to avoid repeated calculation, and a parallelization calculation framework is adopted to calculate matrix vector multiplication between a plurality of groups of ciphertext vectors and the plaintext matrix simultaneously. In each group of matrix vector multiplication, a parallelization frame is also used for simultaneously calculating element-by-element multiplication between ciphertext and plaintext vector, and all results are summarized to obtain the result of matrix multiplication operation in the whole ciphertext space. The method provided by the invention can reduce repeated modular inverse operation to the greatest extent, and fully utilizes the multi-core computing capability of the CPU, so that the performance and efficiency of matrix multiplication operation in the Paillier ciphertext space can be improved. Meanwhile, the method is based on the Paillier homomorphic encryption algorithm, so that the accuracy and the safety of a calculation result can be ensured.
In summary, the method for fast matrix multiplication in ciphertext space provided by the invention optimizes the data preprocessing and parallelization calculation, effectively reduces the calculation cost, and improves the efficiency and performance of algorithm protocols. The method is suitable for various privacy protection fields, such as federal learning, privacy set interaction, anonymous query and the like. The method provided by the invention is simple to implement, easy to deploy, capable of protecting data privacy and safety, and wide in application prospect.
To further illustrate the effectiveness and advantages of the above methods provided by the present invention, the above methods provided by the present invention are validated by an experiment.
FIG. 2 is a diagram of computer time overhead versus different fast matrix multiplications based on Paillier ciphertext space, according to an embodiment of the invention.
The testing environment of the invention is MacOS Ventura 13.3.1 operating system, 1.4GHz four-Core Intel Core i5 CPU,8G memory. Figure 2 illustrates the comparison of the computational time overhead of two methods at 4 different matrix sizes, 32x32, 64x64, 128x128, 256x256, respectively, with the plaintext and ciphertext matrices being the same size. In each case, firstly fixing the random seed to be 0, randomly generating a plaintext matrix by using Numpy packets, and then encrypting the plaintext matrix by using an open source python-paillier homomorphic encryption library to obtain a ciphertext matrix with the same size. The floating point number encoding precision is fixed at 0.001.
In the ordinate, the "cipher_ matmul" represents the traditional ciphertext matrix multiplication, and is calculated by calling a matmul () function wrapped by Numpy, and the "fast_cipher_ matmul" represents the rapid matrix multiplication method in the Paillier ciphertext space.
TABLE 1 comparison of cipher_matmul and fast_cipher_ matmul runtime
The experimental results show that as shown in table 1, the operation time of the fast matrix multiplication method in the Paillier ciphertext space on four matrixes with different scales is obviously faster than that of the traditional ciphertext matrix multiplication method. Specifically, from the speed ramp up ratio of table 1 (i.e., cipher_ matmul/fast_cipher_ matmul), the run times were increased by 10.1 times, 11.3 times, 11.6 times, and 11.0 times, respectively, which fully validated the method.
Fig. 3 is a schematic diagram of a fast matrix multiplication system in the Paillier ciphertext space according to an embodiment of the invention.
As shown in fig. 3, the fast matrix multiplication system 300 in the Paillier ciphertext space is applied to the financial big data field, the medical big data field, the cloud computing field and the federal learning field, and comprises a preprocessing module 310, a matrix vector multiplication module 320 and a vector summarization module 330.
The preprocessing module 310 is configured to perform coding with preset precision on plaintext elements in the plaintext matrix, obtain a preprocessed plaintext matrix, calculate a modulo inverse value of ciphertext elements in the ciphertext matrix, and cache the modulo inverse value of the ciphertext elements in the storage device;
Matrix vector multiplication module 320 for multiplying the ciphertext matrix by the modulo inverse of the ciphertext element cached in the storage device The individual row vectors are subjected to parallelized matrix vector multiplication with the preprocessed plaintext matrix to obtainA set of column vectors, wherein,Each set of column vectors includes a plurality of column vectors, being a positive integer greater than or equal to 1;
Vector summary module 330 for summing the pair using a fast summing method in the Paillier ciphertext space Summing each column vector set in the column vector sets along the longitudinal axis direction to obtainIndividual row vectors and pairs ofAnd splicing the row vectors along the longitudinal axis direction to obtain a matrix multiplication result.
The method for fast matrix multiplication in the Paillier ciphertext space provided by the invention is described in further detail below with reference to specific embodiments.
In the embodiment of the invention, the random seed of the Numpy packet is fixed to be 0, and the random module is used for randomly generating the random seed with the scale of 0Plaintext matrix of (2)Next, a key pair of 1024 bits in length is created using a python-paillier open source library, where the public key isThe private key is. Using public keysPair matrixEach element in the ciphertext matrix is encrypted to obtain the ciphertext matrix. Then calculate according to the following procedure。
The rapid matrix multiplication method in the Paillier ciphertext space comprises two stages, namely a data preprocessing stage and a parallelization matrix multiplication stage.
In the data preprocessing stage, firstly, the plaintext matrix is encoded with low precision, wherein the fixed floating point number encoding precision is 0.001, and the plaintext matrix is encoded by means of an encoding () function in a python-paillier packetEach element in the list is coded with low precision, and the coded result is assigned backIs a kind of medium.
Secondly, calculating the modulus inverse of the ciphertext matrix and caching the calculation result, namely calculating the ciphertext matrix by means of invert () function in gmpy open source libraryThe modulo inverse of each element in (a), i.eWhereinIs a public keyIs a part of the same. The final obtained modular inverse matrix isAnd caching the calculation result.
In the parallelization matrix riding stage, firstly, parallelization calculation of ciphertext vector and plaintext matrix multiplication are performed, namely, each row vector of the ciphertext matrix is multiplied byParallelization calculation of ciphertext vectorSame plaintext matrixMultiplication of (2). First, a buffer matrix with the same size as the plaintext matrix is createdIts dimension is alsoThen, two sub-processes are calculated, namely (1) parallelization calculation of element-by-element multiplication between single ciphertext and plaintext row vector, namely, pairEach ciphertext of (a)Parallelizing and calculating corresponding plaintext row vectorMultiplication by element and order. In the calculationWhen in use, forFurther disassembled and grouped, the methodThe medium positive numbers are integrated into vectorsIn (1) willIs integrated into a vectorIn the meantime, calculateAndElement-by-element multiplication on two groupings. In the calculationWhen needed to be utilized toFor accelerating the calculation process. Finally, the calculation results on the two groups are assigned back according to the corresponding relation of the element subscripts(2) Summing each column vector of the buffer matrix, namely obtaining the buffer matrix with the size ofCiphertext matrix of (a). Then, along the longitudinal axis, summing each column vector by using a fast summing method on the Paillier dense culture set to finally obtain the vector with the dimension ofResult vector of (a)。
Second, summarizing the intermediate results to produce a final output of each ciphertext row vector in the above stepsSame plaintext matrixAll the dimensions obtained after the multiplication are calculated asCiphertext row vector of (2)Then the 16 row vectors are spliced together along the longitudinal axis direction to obtain the final result matrixThe calculation is completed.
Fig. 4 schematically shows a block diagram of an electronic device adapted to implement a fast matrix multiplication method in the Paillier ciphertext space, according to an embodiment of the invention.
As shown in fig. 4, an electronic device 400 according to an embodiment of the present invention includes a processor 401 that can perform various appropriate actions and processes according to a program stored in a Read Only Memory (ROM) 402 or a program loaded from a storage section 408 into a Random Access Memory (RAM) 403. The processor 401 may include, for example, a general purpose microprocessor (e.g., a CPU), an instruction set processor and/or an associated chipset and/or a special purpose microprocessor (e.g., an Application Specific Integrated Circuit (ASIC)), or the like. Processor 401 may also include on-board memory for caching purposes. Processor 401 may include a single processing unit or multiple processing units for performing the different actions of the method flow in accordance with an embodiment of the invention.
In the RAM 403, various programs and data necessary for the operation of the electronic device 400 are stored. The processor 401, the ROM 402, and the RAM 403 are connected to each other by a bus 404. The processor 401 performs various operations of the method flow according to the embodiment of the present invention by executing programs in the ROM 402 and/or the RAM 403. Note that the program may be stored in one or more memories other than the ROM 402 and the RAM 903. The processor 401 may also perform various operations of the method flow according to an embodiment of the present invention by executing programs stored in one or more memories.
According to an embodiment of the invention, the electronic device 400 may further comprise an input/output (I/O) interface 405, the input/output (I/O) interface 405 also being connected to the bus 404. The electronic device 400 may also include one or more of an input section 406 including a keyboard, mouse, etc., an output section 407 including a Cathode Ray Tube (CRT), liquid Crystal Display (LCD), etc., and speaker, etc., a storage section 408 including a hard disk, etc., and a communication section 409 including a network interface card such as a LAN card, modem, etc., connected to the I/O interface 405. The communication section 409 performs communication processing via a network such as the internet. The drive 410 is also connected to the I/O interface 405 as needed. A removable medium 411 such as a magnetic disk, an optical disk, a magneto-optical disk, a semiconductor memory, or the like is installed on the drive 410 as needed, so that a computer program read therefrom is installed into the storage section 408 as needed.
The present invention also provides a computer-readable storage medium that may be included in the apparatus/device/system described in the above embodiments, or may exist alone without being assembled into the apparatus/device/system. The computer-readable storage medium carries one or more programs which, when executed, implement methods in accordance with embodiments of the present invention.
According to embodiments of the invention, the computer-readable storage medium may be a non-volatile computer-readable storage medium, which may include, for example, but is not limited to, a portable computer diskette, a hard disk, a Random Access Memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can contain, or store a program for use by or in connection with an instruction execution system, apparatus, or device. For example, according to embodiments of the invention, the computer-readable storage medium may include ROM 402 and/or RAM 403 and/or one or more memories other than ROM 402 and RAM 403 described above.
The flowcharts and block diagrams in the figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, which comprises one or more executable instructions for implementing the specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams or flowchart illustration, and combinations of blocks in the block diagrams or flowchart illustration, can be implemented by special purpose hardware-based systems which perform the specified functions or acts, or combinations of special purpose hardware and computer instructions.
The above embodiments are further described in detail with respect to the objects, technical solutions and advantageous effects of the present invention, and it should be understood that the above are only embodiments of the present invention, and not as an attempt to limit the application of the doctrine of equivalents to the details of the invention, the invention should be construed in light of the number of equivalents and alternatives falling within the spirit and scope of the invention.
Claims (6)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311346034.1A CN117312743B (en) | 2023-10-18 | 2023-10-18 | Rapid matrix multiplication method in Paillier ciphertext space |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311346034.1A CN117312743B (en) | 2023-10-18 | 2023-10-18 | Rapid matrix multiplication method in Paillier ciphertext space |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN117312743A CN117312743A (en) | 2023-12-29 |
| CN117312743B true CN117312743B (en) | 2025-03-11 |
Family
ID=89284625
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202311346034.1A Active CN117312743B (en) | 2023-10-18 | 2023-10-18 | Rapid matrix multiplication method in Paillier ciphertext space |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN117312743B (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112988237A (en) * | 2021-04-21 | 2021-06-18 | 深圳致星科技有限公司 | Paillier decryption system, chip and method |
| CN116049907A (en) * | 2023-02-13 | 2023-05-02 | 北极雄芯信息科技(天津)有限公司 | Paillier homomorphic encryption processor and processing method thereof |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7725730B2 (en) * | 2002-08-09 | 2010-05-25 | Emc Corporation | Cryptographic methods and apparatus for secure authentication |
| CN116484395A (en) * | 2023-03-08 | 2023-07-25 | 蚂蚁区块链科技(上海)有限公司 | Security calculation method based on privacy data and related equipment |
| CN116628713A (en) * | 2023-05-15 | 2023-08-22 | 支付宝(杭州)信息技术有限公司 | Privacy calculation method, device, electronic equipment and machine-readable storage medium |
-
2023
- 2023-10-18 CN CN202311346034.1A patent/CN117312743B/en active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112988237A (en) * | 2021-04-21 | 2021-06-18 | 深圳致星科技有限公司 | Paillier decryption system, chip and method |
| CN116049907A (en) * | 2023-02-13 | 2023-05-02 | 北极雄芯信息科技(天津)有限公司 | Paillier homomorphic encryption processor and processing method thereof |
Also Published As
| Publication number | Publication date |
|---|---|
| CN117312743A (en) | 2023-12-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US11539515B2 (en) | High-precision privacy-preserving real-valued function evaluation | |
| Hardy et al. | Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption | |
| Blatt et al. | Optimized homomorphic encryption solution for secure genome-wide association studies | |
| CN111143894B (en) | Method and system for improving safe multi-party computing efficiency | |
| Wang et al. | VLSI design of a large-number multiplier for fully homomorphic encryption | |
| Bogdanov et al. | High-performance secure multi-party computation for data mining applications | |
| CN113761469B (en) | Highest bit carry calculation method for protecting data privacy | |
| US20210167959A1 (en) | Safe token storage | |
| Ibarrondo et al. | Banners: Binarized neural networks with replicated secret sharing | |
| CN118249980A (en) | Privacy protection machine learning method and device based on homomorphic encryption and security outsourcing matrix | |
| Huang et al. | Optimized CPU–GPU collaborative acceleration of zero-knowledge proof for confidential transactions | |
| CN117595992A (en) | Method and processor for accelerating execution of number theory transformation NTT | |
| Corena et al. | Secure and fast aggregation of financial data in cloud-based expense tracking applications | |
| CN113626841B (en) | Multi-party security calculation-based selection problem processing method | |
| Tian et al. | Privacy-preserving logistic regression with improved efficiency | |
| CN117312743B (en) | Rapid matrix multiplication method in Paillier ciphertext space | |
| CN118468339A (en) | A GPU-based homomorphic ciphertext face concealment query method and system | |
| Riasi et al. | Privacy-Preserving Verifiable Neural Network Inference Service | |
| US11985221B2 (en) | Efficient masking of secure data in ladder-type cryptographic computations | |
| CN116743349A (en) | Paillier ciphertext summation method, system, device and storage medium | |
| CN116011015A (en) | A privacy-preserving entity recognition tool based on secure multi-party computing technology | |
| Wang et al. | Popcorn: Paillier meets compression for efficient oblivious neural network inference | |
| CN117353898B (en) | Fully homomorphic encryption method, system, terminal and medium for floating point number plaintext | |
| CN118504038B (en) | Hypothesis testing method and device for privacy-preserving generalized linear models | |
| US11962562B2 (en) | Anonymous message board server verification |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |