WO2025065854A1 - Data processing method and system for protecting privacy, and device - Google Patents

Abstract

A data processing method and system for protecting privacy, and a device. The method comprises: a device of a first party performing the following operations: acquiring first ciphertext and second ciphertext; determining a first parameter value and a second parameter value on the basis of a first number of first coefficients in each of a first plaintext polynomial and a second plaintext polynomial corresponding to the first ciphertext and the second ciphertext; performing homomorphic calculation on the basis of the first parameter value, the second parameter value, the first ciphertext and the second ciphertext, so as to obtain third ciphertext, wherein a third plaintext polynomial corresponding to the third ciphertext comprises the first number of first coefficients; sending the third ciphertext to a device of a second party; and the device of the second party decrypting the third ciphertext, so as to obtain the third plaintext polynomial, and acquiring the first number of first coefficients from the third plaintext polynomial.

Description

A data processing method, device and system for protecting privacy

This application claims priority to the Chinese patent application filed with the State Intellectual Property Office of China on September 28, 2023, with application number 202311282679.3 and application name “A privacy-protecting data processing method, device and system”, the entire contents of which are incorporated by reference in this application.

Technical Field

The embodiments of this specification belong to the field of data processing technology, and more particularly, to a data processing method, device, and system for protecting privacy.

Background Art

In some multi-party data processing scenarios, usually including matrix holders and vector holders, the matrix holders and vector holders need to complete the calculation of the inner product of the matrix and the vector while protecting the privacy data of each party. In the related technology, based on the ring-based learning tolerable fault (RLWE) homomorphic encryption algorithm, multiple row vectors in the matrix can be converted into multiple first plaintext polynomials, the target vector can be converted into a second plaintext polynomial, the second plaintext polynomial is encrypted to obtain a first ciphertext, and each first plaintext polynomial is multiplied with the first ciphertext to obtain multiple second ciphertexts, and the plaintext polynomials corresponding to the multiple second ciphertexts include the inner product values of each row vector in the matrix and the target vector.

Summary of the invention

The object of the present invention is to provide a data processing solution, by which computing resources and storage resources can be saved and communication traffic can be reduced.

A first aspect of the present specification provides a data processing method for protecting privacy, the method being performed by a device of a first party and a device of a second party, wherein the second party possesses a public key for homomorphic encryption and a private key corresponding to the public key, the method comprising:

The first party's device performs the following operations:

Obtain a first ciphertext and a second ciphertext, wherein the first ciphertext and the second ciphertext are homomorphic ciphertexts of a first plaintext polynomial and a second plaintext polynomial, respectively, the first ciphertext and the second ciphertext correspond to the public key, and the first plaintext polynomial and the second plaintext polynomial are polynomials in the same polynomial space;

Determine a first parameter value and a second parameter value based on a first number of first coefficients as target coefficients in the first plaintext polynomial and the second plaintext polynomial, wherein the first parameter value is used to homomorphically replace the homomorphic ciphertext. In the homomorphic calculation of the conversion, the second parameter value is used in the homomorphic calculation of homomorphic multiplication on the homomorphic ciphertext; based on the first parameter value, the second parameter value, the first ciphertext and the second ciphertext, a homomorphic calculation is performed to obtain a third ciphertext, and a third plaintext polynomial corresponding to the third ciphertext includes the first coefficient of the first number;

sending the third ciphertext to a device of the second party;

The device of the second party decrypts the third ciphertext based on the private key to obtain the third plaintext polynomial, and obtains the first coefficient of the first number from the third plaintext polynomial.

A second aspect of this specification provides a privacy-protecting data processing method, comprising:

Obtaining a first ciphertext and a second ciphertext, wherein the first ciphertext and the second ciphertext are homomorphic ciphertexts of a first plaintext polynomial and a second plaintext polynomial, respectively, and the first plaintext polynomial and the second plaintext polynomial are polynomials in the same polynomial space;

Determine a first parameter value and a second parameter value based on a first number of first coefficients as target coefficients in the first plaintext polynomial and the second plaintext polynomial, the first parameter value being used in a homomorphic calculation of homomorphic replacement of a homomorphic ciphertext, and the second parameter value being used in a homomorphic calculation of homomorphic multiplication of a homomorphic ciphertext;

A third ciphertext is obtained by performing homomorphic calculation based on the first parameter value, the second parameter value, the first ciphertext, and the second ciphertext, wherein a third plaintext polynomial corresponding to the third ciphertext includes a first coefficient of the first number.

A third aspect of the present specification provides a computing device, including:

an acquiring unit, configured to acquire a first ciphertext and a second ciphertext, wherein the first ciphertext and the second ciphertext are homomorphic ciphertexts of a first plaintext polynomial and a second plaintext polynomial, respectively, and the first plaintext polynomial and the second plaintext polynomial are polynomials in the same polynomial space;

a determining unit, configured to determine a first parameter value and a second parameter value based on a first number of first coefficients as target coefficients in the first plaintext polynomial and the second plaintext polynomial, the first parameter value being used in a homomorphic calculation of homomorphic replacement of a homomorphic ciphertext, and the second parameter value being used in a homomorphic calculation of homomorphic multiplication of a homomorphic ciphertext;

A computing unit is configured to perform homomorphic computing based on the first parameter value, the second parameter value, the first ciphertext, and the second ciphertext to obtain a third ciphertext, wherein a third plaintext polynomial corresponding to the third ciphertext includes the first coefficient of the first number.

A fourth aspect of the present specification provides a privacy-protecting data processing system, the system comprising a first party's device and a second party's device, wherein the second party has a public key for homomorphic encryption and a private key corresponding to the public key,

The first party's device is used to perform the following operations:

Obtain a first ciphertext and a second ciphertext, wherein the first ciphertext and the second ciphertext are homomorphic ciphertexts of a first plaintext polynomial and a second plaintext polynomial, respectively, the first ciphertext and the second ciphertext correspond to the public key, and the first plaintext polynomial and the second plaintext polynomial are polynomials in the same polynomial space;

Determine a first parameter value and a second parameter value based on a first number of first coefficients as target coefficients in the first plaintext polynomial and the second plaintext polynomial, the first parameter value being used in a homomorphic calculation of homomorphic replacement of a homomorphic ciphertext, and the second parameter value being used in a homomorphic calculation of homomorphic multiplication of a homomorphic ciphertext;

Performing homomorphic calculation based on the first parameter value, the second parameter value, the first ciphertext, and the second ciphertext to obtain a third ciphertext, wherein a third plaintext polynomial corresponding to the third ciphertext includes a first coefficient of the first number;

sending the third ciphertext to a device of the second party;

The device of the second party is used to decrypt the third ciphertext based on the private key to obtain the third plaintext polynomial, and obtain the first coefficient of the first number from the third plaintext polynomial.

A fifth aspect of the present specification provides a computer-readable storage medium having a computer program stored thereon, which, when executed in a computer, causes the computer to execute the method described in the second aspect.

A sixth aspect of the present specification provides a computing device, including a memory and a processor, wherein the memory stores executable code, and when the processor executes the executable code, the method described in the second aspect is implemented.

The embodiments of the present specification provide a privacy-protecting data processing method. Through the scheme of this embodiment, multiple ciphertexts can be homomorphically calculated based on the number of target coefficients in each ciphertext, so that in a data processing process of two ciphertexts, the two ciphertexts are packaged into a packaged ciphertext, so that the plaintext corresponding to the packaged ciphertext includes all the target coefficients corresponding to the two ciphertexts, and the packaged ciphertext can be sent to the device of the second party so that the device of the second party obtains all the target coefficients corresponding to the two ciphertexts. Compared with the existing scheme, the amount of communication data between the first party device and the second party device is reduced while achieving the same effect, and the calculation complexity is also reduced, saving calculation resources.

BRIEF DESCRIPTION OF THE DRAWINGS

In order to more clearly illustrate the technical solutions of the embodiments of this specification, the drawings required for use in the description of the embodiments will be briefly introduced below. Obviously, the drawings described below are only some embodiments recorded in this specification. For ordinary technicians in this field, other drawings can be obtained based on these drawings without paying creative labor.

FIG1 is a system structure diagram of an embodiment;

FIG2 is a flow chart of a method for data processing in an embodiment of the present specification;

FIG3 is a schematic diagram of a process in which a matrix holder executes the method shown in FIG2 ;

FIG4 is a schematic diagram of a process in which a matrix holder packages multiple ciphertexts in accordance with an embodiment of the present specification;

FIG5 shows a flow chart of a method for data processing in another embodiment of the present specification;

FIG. 6 is an architecture diagram of a computing device in an embodiment of this specification.

DETAILED DESCRIPTION

In order to enable those skilled in the art to better understand the technical solutions in this specification, the technical solutions in the embodiments of this specification will be described clearly and completely below in conjunction with the drawings in the embodiments of this specification. Obviously, the described embodiments are only part of the embodiments of this specification, not all of the embodiments. Based on the embodiments in this specification, all other embodiments obtained by ordinary technicians in this field without creative work should fall within the scope of protection of this specification.

The solution in the embodiments of this specification is based on the homomorphic encryption algorithm. The homomorphic encryption algorithm includes the following six algorithms:

(1) Key generation algorithm (KeyGen), which is used to generate private key sk and public key pk.

Let the plaintext space be a polynomial space The degree of the polynomial space is less than N, where N is a power of 2, such as 4096, 8192, etc. The coefficient is an integer in [0, q). The ciphertext space corresponding to the plaintext space is A polynomial in R _q can be randomly generated by a key generation algorithm as the private key sk, and each coefficient of the polynomial is subject to a discrete Gaussian distribution with a standard deviation of χ _σ . Then, a public key pk = (-a*sk + e, a) can be generated, where a is a randomly generated polynomial in R _q , and e←χ _σ .

(2) Encoding algorithm (Encode), used to convert the plaintext vector Convert to a polynomial v∈R _q .

(3) Encryption algorithm, used to encrypt the plaintext polynomial v into ciphertext (the ciphertext is in the form of two polynomials) using the public key. Specifically, let pk = (p ₀ , p ₁ ), then the ciphertext Here c ₁ =u*p ₁ +e ₁ , c ₀ =u*p ₀ +e ₀ +v, where v is the plaintext polynomial.

(4) Decryption algorithm: This decryption algorithm is used to decrypt the ciphertext into a plaintext polynomial. Suppose the ciphertext ct = (c ₀ , c ₁ ), then v ≈ (c ₀ + c ₁ *sk) mod q is the decrypted plaintext polynomial.

(5) Decoding algorithm (Decode), which is used to convert the plaintext polynomial into a plaintext vector.

(6) Homomorphic computation, including homomorphic addition, homomorphic multiplication, homomorphic substitution, etc.

Specifically, in homomorphic addition, for plaintext polynomial m and plaintext polynomial t, E(m+t)=E(m)+E(t), where plaintext polynomial m and plaintext polynomial t are polynomials in the same polynomial space, and E() represents the ciphertext obtained by homomorphically encrypting the ciphertext polynomial; in homomorphic multiplication, E(t*m)=t*E(m), in a homomorphic multiplication, E( ^xi *m)= ^xi *E(m); in homomorphic substitution, assuming that the ciphertext of the polynomial m(x) is ct(x), then ct( ^xt )=E(m( ^xt )).

FIG1 is a system structure diagram in one embodiment. As shown in FIG1 , the system may include a device 101 of a matrix holder P0 and a device 102 of a vector holder P1. The device 101 stores an m-row n-column matrix owned by the matrix holder P0, and the device 102 stores an n-dimensional vector owned by the vector holder P1. In order to protect the privacy data of the matrix holder P0 and the vector holder P1 respectively, the device 102 may generate a private key sk and a public key pk for homomorphic encryption. The device 102 may use the public key pk to homomorphically encrypt the vector, generate a ciphertext of the vector (i.e., the ciphertext of the plaintext polynomial corresponding to the vector), and send the ciphertext to the device 101. The device 101 may convert each row vector of the matrix into at least one plaintext polynomial, and then calculate a ciphertext containing an inner product result based on the at least one plaintext polynomial and the ciphertext of the vector, and send the ciphertext containing the inner product result to the device 102, so that the device 102 can obtain the inner product of each row vector of the matrix and the vector by homomorphically decrypting the ciphertext containing the inner product result using the private key sk. The ciphertext containing the inner product means that the plaintext polynomial corresponding to the ciphertext includes the inner product.

The embodiments of this specification can be applied to scenarios such as multi-party joint modeling. In this scenario, the matrix holder P0 is, for example, a model party that provides a model, and the matrix held in the model party is, for example, a parameter matrix in the model. The vector holder is, for example, a data party that provides feature data. After the data party sends the ciphertext containing the vector to the model party, the model party can input the ciphertext into the model, so that the model outputs the ciphertext containing the inner product.

The embodiments of this specification can also be used in the scenario of private information retrieval. In this scenario, the device 101 of the matrix holder P0 is, for example, a server storing a database, the database storing data in the form of a matrix, and the device 102 is a user device. When the user device needs to query the i-th column of the matrix, it can construct a vector for querying data, where the i-th component of the vector is 1 and the other components are 0.

For example, the matrix W owned by the matrix holder is a 4*4 matrix:

Among them, it can be considered that W includes four row vectors

When the device 102 needs to query the data in the second column of the matrix, it can construct a vector for querying the data.

in, Representation vector With vector The inner product of is,

That is, by adding the vector Set as the vector above, by calculating the matrix W and the vector The product of gets a column of matrix W. When multiplying, by calculating the row vectors included in the matrix W and the vector The inner product of matrix W and vector Based on this, in order to protect the privacy data of the matrix holder and the vector holder, the above calculation can be performed based on the homomorphic encryption algorithm.

Specifically, the vector holder can use the vector Convert to polynomial v = 0 + x + 0x ² + 0x ³ = x, use the homomorphic encryption public key pk to encrypt the polynomial v, and obtain the ciphertext Cv = E(v) of the polynomial v, where E() represents the homomorphic encryption algorithm. The ciphertext Cv includes two ciphertext polynomials (C _v0 , C _v1 ). The vector holder can send the ciphertext Cv to the matrix holder.

The matrix holder can include the four row vectors of matrix W Convert to 4 polynomials:
w ₀ = 1-4x-3x ² -2x ³ ,
w ₁ =3-6x-5x ² -4x ³ ,
w ₂ =2-5x-4x ² -3x ³ ,
w ₃ =4-7x-6x ² -5x ³ .

Where, w ₀ ×v＝(1-4x-3x ² -2x ³ )×(0+x+0x ² +0x ³ )
=(1×0-4x×0x ³ -3x ² ×0x ² -2x ³ ×x)+…
=(1×0-4×0x ⁴ -3×0x ⁴ -2×1x ⁴ )+… (1)

In the above formula (1), "..." represents other terms of powers of x, which are not specifically written here. As mentioned above, in the homomorphic encryption algorithm, the plaintext space is a polynomial space R _q , and the degree in the polynomial space is less than 4, where N=4. In the polynomial space of N=4, x ⁴ can be set to -1, so that the above formula (1) can be converted to:

That is, the constant term in the polynomial of w ₀ ×v is

Similar to formula (2), we can conclude that

According to the homomorphic encryption algorithm, E(w×v)←w×E(v). Therefore, the matrix holder can calculate the product w _i ×Cv of the polynomial w _i (i is any value from 0 to 3) and the homomorphic ciphertext Cv of the polynomial v to obtain the ciphertext C _wi =E(w _i ×v)= _{w i} ×Cv corresponding to w i ×v, and send the four ciphertexts C _w0 ~C _w3 to the vector holder. Among them, the product of the polynomial w _i and the homomorphic ciphertext Cv of the polynomial v is w _i ×(C _v0 ,C _v1 )=(w _i ×C _v0 ,w _i ×C _v1 ). The vector holder can C _w0 ~ C _w3 are decrypted to obtain each polynomial w _i ×v. Constant terms can be obtained from each polynomial w _i ×v, thereby obtaining each Thus, the second column of the matrix W can be obtained. In this way, during the data query process, the server cannot know the specific data queried by the user, thereby protecting the user's privacy. At the same time, the user cannot obtain the data of other columns in the matrix W, thereby protecting the server's data privacy.

In the above process, after the matrix holder calculates the four ciphertexts C _w0 ~ C _w3 , it needs to send the four ciphertexts to the vector holder, so that the vector holder can obtain the constant terms in the plaintext polynomials corresponding to the four ciphertexts. Therefore, the amount of communication data between the matrix holder and the vector holder is large.

The embodiment of this specification provides a data processing method for protecting privacy, whereby a server can pack multiple ciphertexts into one ciphertext, so that the plaintext polynomial corresponding to the packed ciphertext includes all coefficients that need to be retained in the multiple plaintext polynomials corresponding to the multiple ciphertexts, and send the packed ciphertext to a user device. The data processing method provided by the embodiment of this specification reduces the amount of communication data compared to the solution in the related art.

FIG2 is a flowchart of a privacy-preserving data processing method in an embodiment of the present specification, which method is executed by, for example, a vector holder and a matrix holder.

As shown in FIG. 2 , in step S210 , the vector holder generates a ciphertext Cv of the vector.

As mentioned above, the vector holder can pre-generate the private key sk and public key pk for homomorphic encryption. Convert to a plaintext polynomial v, use the public key pk to encrypt the plaintext polynomial v, and obtain a ciphertext Cv of the plaintext polynomial v, wherein the ciphertext Cv includes two ciphertext polynomials.

Specifically, in one embodiment, as described above, the vector For example, a 4-dimensional vector, that is, n=4 in Figure 1, It can be converted into a polynomial v = 0 + x + 0x ² + 0x ³ = x. The vector holder uses the public key pk to encrypt the plaintext polynomial v to obtain the ciphertext Cv.

In step S520, the vector holder sends the ciphertext Cv to the matrix holder.

In step S530, the matrix holder converts the matrix W it owns into multiple plaintext polynomials, and multiplies the multiple plaintext polynomials with the ciphertext Cv respectively to obtain multiple ciphertexts.

Specifically, the matrix W is, for example, a 4*4 matrix

The matrix holder can include the four row vectors of matrix W Convert to 4 polynomials:
w ₁₀ ＝1-4x ⁵ -3x ⁶ -2x ⁷ ,
w ₁₁ =3-6x ⁵ -5x ⁶ -4x ⁷ ,
w ₁₂ = 2-5x ⁵ -4x ⁶ -3x ⁷ ,
w ₁₃ = 4-7x ⁵ -6x ⁶ -5x ⁷ .

Afterwards, the matrix holder can generate plaintext polynomial y0 based on plaintext polynomials _w10 and _w12 , and generate plaintext polynomial y1 based on _w11 and _w13 :
y0＝w ₁₀ +x ⁴ ×w ₁₂ ＝1+5x+4x ² +3x ³ +2x ⁴ -4x ⁵ -3x ⁶ -2x ⁷ ,
y1＝w ₁₁ +x ⁴ ×w ₁₃ ＝1+7x+6x ² +5x ³ +4x ⁴ -6x ⁵ -5x ⁶ -4x ⁷ .

It is assumed that the degree of the polynomial space to which the plaintext polynomials y0 and y1 belong is less than 8, that is, N of the polynomial space = 8, and x ⁸ = -1 in the polynomial space.

The matrix holder can obtain two ciphertexts y0×Cv and y1×Cv by multiplying the plaintext polynomials y0 and y1 with the ciphertext Cv respectively, and the two ciphertexts can be represented as C1 and C2 respectively. As mentioned above, y0×Cv＝E(y0×v), y1×Cv＝E(y1×v),

in,

in, Representation vector With vector The inner product of .

That is to say, the constant coefficient of the plaintext polynomial y0×v corresponding to the ciphertext C1 is the row vector With vector The inner product of the ciphertext C1, the coefficients of the x ⁴ terms in the plaintext polynomial y0×v are row vectors With vector The inner product of the constant term coefficient and the ^x4 term coefficient in the plaintext polynomial corresponding to the ciphertext C1 need to be provided to the vector holder.

Similarly,

That is to say, the constant coefficient of the plaintext polynomial y1×v corresponding to the ciphertext C2 is the row vector With vector The inner product of the ciphertext C2, the coefficients of the x ⁴ terms in the plaintext polynomial y1×v are row vectors With vector The inner product of the constant term coefficient and the ^x4 term coefficient in the plaintext polynomial corresponding to the ciphertext C2 need to be provided to the vector holder.

It can be understood that the matrix W and vector This is merely exemplary and is not intended to limit the scope of the embodiments of this specification. In one embodiment, the matrix W2 of the matrix holder includes, for example: There are 8 row vectors in total. We can convert the row vectors into Convert them into polynomials w ₂₀ , w ₂₁ , …w ₂₇ respectively.

Similar to the above, the matrix holder can generate plaintext polynomial y ₂₀ based on plaintext polynomials w ₂₀ and w ₂₄ , generate plaintext polynomial y ₂₁ based on w ₂₁ and w ₂₅ , generate plaintext polynomial y ₂₂ based on plaintext polynomials w ₂₂ and w ₂₆ , and generate plaintext polynomial y ₂₃ based on plaintext polynomials w ₂₃ and w ₂₇ , that is:
y ₂₀ = w ₂₀ + x ⁴ × w ₂₄ ,
y ₂₁ =w ₂₁ +x ⁴ ×w ₂₅ ,
y _{2 2} =w _{2 2} +x ⁴ ×w _{2 6} ,
y ₂₃ =w ₂₃ +x ⁴ ×w ₂₇ ,

Similarly, by multiplying the plaintext polynomials y ₂₀ ˜y ₂₃ by the ciphertext Cv respectively, four ciphertexts y ₂₀ ×Cv ˜y ₂₃ ×Cv are obtained. The four ciphertexts can be represented as C ₂₁ ˜C ₂₄ respectively.

Referring to the above formula (3) and formula (4), similarly, the four plaintext polynomials corresponding to the ciphertexts C ₂₁ to C ₂₄ can be obtained:

That is, the constant term coefficient and the ^x4 term coefficient in each of the four plaintext polynomials corresponding to the ciphertexts C ₂₁ to C ₂₄ need to be provided to the vector holder.

In step S240, the matrix holder packages multiple ciphertexts to obtain a ciphertext Cq.

In one example, the matrix holder obtains the ciphertext C1 and ciphertext C2 as described above. As described above, the number of coefficients (ie, target coefficients) that need to be provided to the vector holder in the plaintext polynomials corresponding to the ciphertext C1 and the ciphertext C2 is 2 respectively.

As shown in FIG. 2 , the matrix holder may perform packaging processing on the ciphertext C1 and the ciphertext C2 by executing steps S241 and S243 .

Specifically, in step S241, the matrix holder determines the first parameter value and the second parameter value based on the number of target coefficients in the plaintext polynomial Vi and the plaintext polynomial Vj corresponding to the ciphertext Ci and the ciphertext Cj.

The first parameter value is the number of times x in the ciphertext is homomorphically replaced, and the second parameter is The value is the number of powers of x used to perform homomorphic multiplication on the ciphertext.

In one implementation, based on the number of coefficients 2 ^s that need to be retained in the plaintext polynomials Vi and Vj, 2 ^s should be less than or equal to N, and the first parameter value may be determined to be 2 ^s +1 and the second parameter value to be N/2 ^s .

FIG3 is a schematic diagram of the process of the matrix holder executing step S240. As shown in FIG3, assuming that the ciphertext C1 corresponds to the plaintext polynomial V1 (i.e., y0×v), and the ciphertext C2 corresponds to the plaintext polynomial V2 (i.e., y1×v), the form of the plaintext polynomial V1 corresponding to the ciphertext C1 is, for example, V1=v ₀ +v ₁ x+…v _N x ^N , assuming N=8, and the boxes arranged in sequence in FIG3 represent the coefficients of the various items in the plaintext polynomial V1, where "*" represents the coefficients of the unconcerned items in the plaintext polynomial V1. In the above example, the specific form of V1 can be V1=2+…+3x ⁴ +…, and the specific form of V2 can be V2==4+…+5x ⁴ +…. As described above, the coefficients of the constant term and the N/2th term (i.e., x ⁴ term) in the plaintext polynomial V1 and the plaintext polynomial V2 are vector inner products, i.e., 2 and 3 in the first and fifth boxes in V1 in FIG3, and 4 and 5 in the first and fifth boxes in V2, i.e., the number of target coefficients to be retained in the plaintext polynomial V1 and the plaintext polynomial V2 is 2+2=4 in total. Accordingly, the first parameter value can be determined to be 5, and the second parameter value can be determined to be 8/4=2.

In step S243, the matrix holder performs homomorphic calculation based on the first parameter value, the second parameter value, the ciphertext Ci and the ciphertext Cj to obtain the ciphertext Ck.

Referring to Figure 3, the matrix holder can first perform homomorphic replacement on both ciphertext C1 and ciphertext C2 based on the first parameter value, that is, replace x in ciphertext C1 with x ⁵ , and replace x in ciphertext C2 with x ^5. Specifically, replace x in the two polynomials included in ciphertext C1 with x ⁵ , and replace x in the two polynomials included in ciphertext C2 with x ⁵ .

Among them, based on the principle of homomorphic substitution, replacing x in the ciphertext C1 with x ⁵ is equivalent to replacing x in the plaintext polynomial V1 with x ⁵ , that is, converting the plaintext polynomial V1 into the following form:
V1(x ⁵ )＝v ₀ +v ₁ x ⁵ +…v _N x ^5N (5)

The constant term in the plaintext polynomial V1(x ⁵ ) is the same as the constant term in the plaintext polynomial V1.

Formula (5) mod (x ^N +1), that is, replace x ^N in formula (5) with -1, so that the polynomial space of V1 (x ⁵ ) corresponds to the polynomial space of the plaintext polynomial. After this processing, the polynomial space in formula (5) That is to say, after homomorphic substitution, The coefficients of the term become the coefficients of the plaintext polynomial V1 The negative of the coefficient of the term. Similarly, That is to say, after homomorphic substitution, The coefficients of the term become the coefficients of the plaintext polynomial V1 The negative number of the coefficient of the term. In addition, That is to say, after homomorphic substitution, The coefficients of the terms are the same as those in the plaintext polynomial V1 The coefficients of the terms are the same.

In the case of N=8, referring to FIG3, after homomorphic substitution of ciphertext C1, ciphertext C1(x ⁵ ) corresponding to plaintext polynomial V1(x ⁵ ) is obtained. Compared with plaintext polynomial V1, plaintext polynomial V1(x ⁵ ) has constant terms and ^{x 4 (} i.e. ) has the same coefficient as the corresponding term in the plaintext polynomial V1. ^The coefficient of x ² (i.e. ) and x ⁶ (i.e. ) are respectively the negatives of the coefficients of the corresponding terms in the plaintext polynomial V1.

In this way, by adding the ciphertext C1 to the ciphertext C1(x ⁵ ), the constant term and the coefficient of the x ⁴ term of the corresponding plaintext polynomial V1+V1(x ⁵ ) are twice the coefficient of the corresponding term in the plaintext polynomial V1. That is, as shown in FIG3 , the constant term and the coefficient of the x ⁴ term of the plaintext polynomial (V1+V1(x ⁵ ))/2 are the same as the coefficient of the corresponding term in the plaintext polynomial V1, and its x ² (i.e. ) and x ⁶ (i.e. ) becomes zero. Specifically, adding the ciphertext C1 to the ciphertext C1(x ⁵ ) is to add the first polynomial of the ciphertext C1 to the first polynomial of C1(x ⁵ ), and to add the second polynomial of the ciphertext C1 to the second polynomial of C1(x ⁵ ), to obtain two new ciphertext polynomials.

Similarly, the ciphertext C2 is processed to obtain the ciphertext (C2+C2(x ⁵ ))/2, which corresponds to the plaintext polynomial (V2+V2(x ⁵ ))/2. As shown in FIG3 , the coefficients of the constant term and the x ⁴ term of the plaintext polynomial (V2+V2(x ⁵ ))/2 are the same as those of the plaintext polynomial V2, and its x ² (i.e. ) and x ⁶ (i.e. ) becomes zero.

Afterwards, the ciphertext (C2+C2(x ⁵ ))/2 can be homomorphically multiplied based on the second parameter value to obtain the ciphertext x ² ×(C2+C2(x ⁵ ))/2, which corresponds to the plaintext polynomial x ² ×(V2+V2(x ⁵ ))/2. Specifically, x ² is multiplied by the two polynomials of (C2+C2(x ⁵ ))/2 respectively to obtain two new ciphertext polynomials. Referring to Figure 3, the coefficients in the plaintext polynomial x ² ×(V2+V2(x ⁵ ))/2 are obtained by processing the coefficients in the plaintext polynomial (V2+V2(x ⁵ ))/2 as follows: each of the coefficients of the 1st to 6th items in the plaintext polynomial (V2+V2(x ⁵ ))/2 is moved backward by two grids, and the 7th and 8th items are multiplied by -1 and moved to the first grid and the second grid. After the homomorphic multiplication process, the coefficients that need to be retained in x ² ×(V2+V2(x ⁵ ))/2 correspond to the positions of the items with coefficients of 0 in (V1+V1(x ⁵ ))/2, and the items with coefficients of zero in x ² ×(V2+V2(x ⁵ ))/2 correspond to the positions of the coefficients that need to be retained in (V1+V1(x ⁵ ))/2. Therefore, referring to FIG3 , by adding (C1+C1(x ⁵ ))/2 to the ciphertext x ² ×(C2+C2(x ⁵ ))/2, the ciphertext C3 is obtained, and its corresponding plaintext polynomial (V1+V1(x ⁵ ))/2+x ² ×(V2+V2(x ⁵ ))/2 (i.e., plaintext polynomial V3) includes all the coefficients that need to be retained in the plaintext polynomials V1 and V2, i.e., 2, 4, 3, and 5. According to formula (3) and formula (4) above, it can be concluded that the ciphertext C3 corresponds to the plaintext polynomial That is, the coefficients in the plaintext polynomial V3 include the row vectors of the matrix W and the vector The inner product of .

In one implementation, the ciphertext C3 may be transformed by the following homomorphic computation:
C3＝(C1+C1(x ⁵ )+x ² ×(C2+C2(x ⁵ )))/2＝(C1+x ² ×C2+(C1(x ⁵ )+x ² ×C2(x ⁵ )))/2
=(C1+x ² ×C2+(C1(x ⁵ )-x ²⁺⁸ ×C2(x ⁵ )))/2
=(C1+x ² ×C2+(C1(x ⁵ )-(x ⁵ ) ² ×C2(x ⁵ )))/2
=(C1+x ² ×C2+(C1-x ² ×C2)(x ⁵ ))/2 (6)

According to formula (6), the matrix holder can first perform homomorphic multiplication on the ciphertext C2 to obtain x ² ×C2. Then, the matrix holder can calculate the ciphertext C1-x ² ×C2. Then, it only needs to perform a homomorphic replacement on the ciphertext C1-x ² ×C2, that is, replace x in the ciphertext C1-x ² ×C2 with x ⁵ to obtain the ciphertext C3, thereby saving computing resources.

It can be understood that the embodiments of this specification are not limited to setting the first parameter value to ^2s +1 and the second parameter value to N/ ^2s . For example, when 2s ⁺¹ is less than or equal to N, the first parameter value can be set to 2s ⁺¹ +1, and the second parameter value can be set accordingly based on the first parameter value. For example, when the degree of the polynomial space is less than 16, when the first parameter value is set to 9, a homomorphic replacement of x ⁹ is performed on one of the two ciphertexts, so that the ciphertext can be converted similarly to the above, so that the 2nd (i.e., 16/8) coefficient, the 6th (i.e., 16*3/8) coefficient, the 10th (i.e., 16*5/8) coefficient, and the 14th (i.e., 16*7/8) coefficient of the plaintext polynomial corresponding to the ciphertext after the conversion are set to 0, and by setting the second parameter value accordingly according to the first parameter value, the coefficients that need to be retained in the plaintext polynomial corresponding to the other ciphertext of the two ciphertexts can be packed into at least one of the 2nd coefficient, the 6th coefficient, the 10th coefficient, and the 14th coefficient in the plaintext polynomial corresponding to the final ciphertext.

In the case where the matrix holder only packages two ciphertexts C1 and C2, the obtained ciphertext C3 is also the ciphertext Cq to be sent to the vector holder.

In another case, the matrix holder obtains, for example, the above-mentioned four ciphertexts C ₂₁ -C ₂₄ , and the matrix holder may iteratively execute steps S241 and S243 in FIG. 2 to pack the four ciphertexts C ₂₁ -C ₂₄ into one ciphertext, so that the packaged ciphertext includes all coefficients that need to be retained in the plaintext polynomials corresponding to the four ciphertexts C ₂₁ -C ₂₄ .

FIG4 is a schematic diagram of the process of packing four ciphertexts in an embodiment of the present specification. As shown in FIG4, assuming that the two values in the plaintext polynomial corresponding to each ciphertext are the coefficients that need to be retained in the plaintext polynomial, the matrix holder can first perform step S241 in FIG2 on the ciphertexts C ₂₁ and C ₂₃ , where similar to the process shown in FIG3, the number of coefficients that need to be retained in the plaintext polynomials C ₂₁ and V ₂₅ is 4, so the first parameter value is 5 and the second parameter value is 2. Then, the matrix holder performs step S243, and similar to the process shown in FIG3, obtains the ciphertext C ₂₅ , and the plaintext polynomial V ₂₅ corresponding to the ciphertext C ₂₅ includes the four coefficients that need to be retained in the plaintext polynomials V ₂₁ and V ₂₅ .

Then, the matrix holder can perform step S241 in FIG. 2 on the ciphertext C ₂₂ and C ₂₄ , where the number of coefficients to be retained in the plaintext polynomials C ₂₂ and V ₂₄ is 4, so the first parameter value is 5 and the second parameter value is 2. The party executes step S243 to obtain the ciphertext C ₂₆ , and the plaintext polynomial V ₂₆ corresponding to the ciphertext C ₂₆ includes the four coefficients that need to be retained in the plaintext polynomials V ₂₂ and V ₂₄ .

After obtaining the ciphertexts C ₂₅ and C ₂₆ , the matrix holder may perform step S241 in FIG. 2 on the ciphertexts C ₂₅ and C ₂₆ , wherein the number of coefficients to be retained in the plaintext polynomial C ₂₅ corresponding to the ciphertext C ₂₅ and the plaintext polynomial V ₂₆ corresponding to the ciphertext C ₂₆ is 4+4=8, therefore, the first parameter value is 8+1=9, and the second parameter value is 8/8=1. In this case, s=l+h, wherein 2 ^l is the number of ciphertexts initially participating in the data processing process (i.e., C ₂₁ to C ₂₄ , a total of 4), 2 ^h is the number of coefficients to be retained in the plaintext polynomial corresponding to each initial ciphertext (i.e., 2), 2 ^l+h =2 ^l ×2 ^h , i.e., the number of all coefficients to be retained included in all ciphertexts initially participating in the data processing process.

Afterwards, the matrix holder executes step S243. Similar to the process shown in Figure 3, the matrix holder may replace x in the ciphertexts C ₂₅ and C ₂₆ with x ⁹ , and perform homomorphic multiplication of the ciphertext C ₂₆ +C ₂₆ (x ⁹ ) with x to obtain x×(C ₂₆ +C ₂₆ (x ⁹ )), and add C ₂₅ +C ₂₅ 5(x ⁹ ) to x×(C ₂₆ +C ₂₆ (x ⁹ )) to obtain the ciphertext C ₂₇ =((C ₂₅ +C ₂₅ (x ⁹ ))+x×(C ₂₆ +C ₂₆ (x ⁹ )))/2. The plaintext polynomial V ₂₇ corresponding to the ciphertext is =((V ₂₅ +V ₂₅ (x ⁹ ))+x×(V ₂₆ +V ₂₆ (x ^{9 )} ) )))/2 As shown in FIG4 , it includes all coefficients that need to be retained in the plaintext polynomials V ₂₁ to V _24. In this case, the ciphertext C ₂₇ obtained by the matrix holder is the ciphertext Cq to be sent to the vector holder.

That is to say, the matrix holder can package multiple ciphertexts in the form of a binary tree, so that the final ciphertext includes the coefficients that need to be retained in each plaintext polynomial corresponding to all the ciphertexts.

Referring to the processing process shown in FIG4 , for the four ciphertexts C ₂₁ to C ₂₄ arranged in sequence, by packing the odd-numbered items and the even-numbered items in the four ciphertexts respectively, in the plaintext polynomial V ₂₇ corresponding to the obtained ciphertext C ₂₇ , the coefficients of the first to fourth items arranged in sequence are respectively the four constant items of the plaintext polynomials V ₂₁ to V ₂₄ , and the position order of the four coefficients in the plaintext polynomial V ₂₇ is consistent with the arrangement order of the plaintext polynomials V ₂₁ to V ₂₄ respectively corresponding thereto (i.e., the arrangement order of the ciphertexts C ₂₁ to C ₂₄ ), and the coefficients of the fifth to eighth items are respectively the four x ⁴ coefficients of the plaintext polynomials V ₂₁ to V ₂₄ , and the position order of the four coefficients in the plaintext polynomial V ₂₇ is consistent with the arrangement order of the plaintext polynomials V ₂₁ to V ₂₄ respectively corresponding thereto.

In step S250, the matrix holder sends the ciphertext Cq to the vector holder.

In step S260, the vector holder decrypts the ciphertext Cq, obtains the plaintext polynomial Vq, and obtains multiple vector inner products from the plaintext polynomial Vq.

Specifically, in the above example, the vector holder can use the private key sk to decrypt the ciphertext C3 and obtain the above plaintext polynomial V3, so that the row vectors and vectors of the matrix W can be obtained from the coefficients of the constant term, ^x2 term, ^x4 term and ^x6 term in V3. The inner product of .

In another example above, the vector holder can use the private key sk to decrypt the ciphertext C ₂₇ and obtain the above plaintext The term V ₂₇ , thus the row vectors and vectors of the matrix W2 can be obtained from the coefficients of the 8 terms in V ₂₇ The inner product of .

Through the scheme in this embodiment, the matrix holder packs multiple ciphertexts into one ciphertext and only needs to send one ciphertext to the vector holder. Then, multiple target coefficients included in multiple plaintext polynomials corresponding to the multiple ciphertexts can be provided to the vector holder without sending multiple ciphertexts to the vector holder, thereby reducing the amount of communication data between the matrix holder and the vector holder.

It can be understood that the application scenario shown in FIG. 2 is only an example scenario of the data processing solution in an embodiment of this specification, and the embodiment of this specification is not limited thereto, but can be applied to other scenarios where multiple ciphertexts need to be packaged. FIG. 5 shows a flow chart of a method for data processing in another embodiment of this specification. The method can be executed by any computing device.

As shown in FIG. 5 , first in step S510 , the ciphertext Ci corresponding to the plaintext polynomial Vi and the ciphertext Cj corresponding to the plaintext polynomial Vj are obtained.

Among them, the ciphertext Ci and the ciphertext Cj are ciphertexts based on the same homomorphic encryption public key pk. The plaintext polynomial Vi corresponding to the ciphertext Ci is in the form of, for example, Vi=v _i0 +v _i1 x+…v _iN x ^N , and the plaintext polynomial Vj corresponding to the ciphertext Cj is in the form of, for example, Vj=v _j0 +v _j1 x+…v _jN x ^N . In one case, the ciphertext Ci and the ciphertext Cj can be ciphertexts obtained by directly encrypting the corresponding plaintext polynomials with the public key pk. In another case, the ciphertext Ci and the ciphertext Cj can be ciphertexts obtained by performing homomorphic calculations on homomorphically encrypted ciphertexts, such as the ciphertexts C ₂₅ and C ₂₆ mentioned above.

In step S520, a first parameter value and a second parameter value are determined based on the number of target coefficients in the plaintext polynomial Vi and the plaintext polynomial Vj.

The first parameter value is the number of times x in the ciphertext is homomorphically replaced, and the second parameter value is the number of times x is homomorphically multiplied.

In one implementation, based on the number of coefficients 2 ^s that need to be retained in the plaintext polynomial Vi and the plaintext polynomial Vj, 2 ^s should be less than or equal to N, and the first parameter value can be determined to be 2 ^s +1 and the second parameter value to be N/2 ^s . It can be understood that the embodiments of this specification are not limited to setting the first parameter value to 2 ^s +1 and setting the second parameter value to N/2 ^s . For example, when 2 ^s+1 is less than or equal to N, the first parameter value can be set to 2 ^s+1 +1, and the second parameter value can be set accordingly according to the first parameter value.

For example, there are a total of 4 target coefficients that need to be retained in the plaintext polynomial Vi and the plaintext polynomial Vj, so the first parameter value can be determined to be 5 and the second parameter value to be N/4.

In one implementation, s=l+h, where ^2l is the number of ciphertexts initially participating in the data processing process, ^2h is the number of coefficients that need to be retained in the plaintext polynomial corresponding to each initial ciphertext, ^{and 2l+h} = ^2l × ^2h , that is, the number of all coefficients that need to be retained included in all ciphertexts initially participating in the data processing process.

In step S230, homomorphic calculation is performed based on the first parameter value, the second parameter value, the ciphertext Ci and the ciphertext Cj to obtain the ciphertext Ck.

Assuming that the first parameter value is 5 and the second parameter value is N/4, the computing device can first perform homomorphic replacement on both ciphertext Ci and ciphertext Cj based on the first parameter value, that is, replace x in ciphertext Ci with x ⁵ , and replace x in ciphertext Cj with x ^5. Specifically, replace x in the two polynomials included in ciphertext Ci with x ⁵ , and replace x in the two polynomials included in ciphertext Cj with x ⁵ .

Among them, based on the principle of homomorphic substitution, replacing x in the ciphertext Ci with x ⁵ is equivalent to replacing x in the plaintext polynomial Vi with x ⁵ , that is, converting the plaintext polynomial Vi into the following form:
Vi(x ⁵ )＝v ₀ +v ₁ x ⁵ +…v _N x ^5N

Referring to the derivation above, after homomorphic substitution, the plaintext polynomial Vi(x ⁵ ) The coefficients of the terms are the same as those in the plaintext polynomial Vi The coefficients of the terms are the same, and the plaintext polynomial Vi(x ⁵ ) Item and The coefficients of the terms are the negatives of the coefficients of the corresponding terms in the plaintext polynomial Vi.

In this way, by adding the ciphertext Ci to the ciphertext Ci(x ⁵ ), the coefficients of the constant term and the x ⁴ term of the plaintext polynomial Vi+Vi(x ⁵ ) corresponding to the ciphertext are twice the coefficients of the corresponding terms in the plaintext polynomial Vi. and The coefficient of the term becomes zero. Specifically, adding the ciphertext Ci to the ciphertext Ci(x ⁵ ) is to add the first polynomial of the ciphertext Ci to the first polynomial of Ci(x ⁵ ), and to add the second polynomial of the ciphertext Ci to the second polynomial of Ci(x ⁵ ), to obtain two new ciphertext polynomials.

Similarly, the ciphertext Cj is processed to obtain the ciphertext Cj+Cj(x ⁵ ), and ^the constant terms and The coefficient of the term is twice the coefficient of the corresponding term in the plaintext polynomial Vj. and The coefficient of the term becomes zero.

Afterwards, the ciphertext (Cj+Cj(x ⁵ ))/2 can be homomorphically multiplied based on the second parameter value to obtain the ciphertext The ciphertext corresponds to the plaintext polynomial Specifically, Multiply the two polynomials with (Cj+Cj(x ⁵ ))/2 respectively to obtain two new ciphertext polynomials. After the homomorphic multiplication process, The coefficients that need to be retained in correspond to the positions of the items with coefficients of 0 in Vj+Vj(x ⁵ ). The terms with zero coefficients in Vi+Vi(x ⁵ ) correspond to the coefficient positions that need to be retained in Vi+Vi(x ⁵ ). Add together to get the ciphertext Ck, whose corresponding plaintext polynomial Includes all the coefficients that need to be retained in the plaintext polynomial Vi and the plaintext polynomial Vj.

In one implementation, the conversion may be performed by the following homomorphic computation:

According to the above formula, the computing device can first perform homomorphic multiplication on the ciphertext Cj to obtain The computing device can then calculate the ciphertext Then only the ciphertext Perform a homomorphic replacement, that is, the ciphertext By replacing x in with x ⁵ , the ciphertext Ck can be obtained, thus saving computing resources.

Referring to the above description, when the computing device performs a packing process on M ciphertexts, the multiple ciphertexts may be packed based on the structure of a binary tree. When M is a power of 2, the ciphertexts in the multiple ciphertexts may be firstly combined in pairs to obtain multiple ciphertext pairs, each ciphertext pair may be packed to obtain M/2 ciphertexts, and then the M/2 ciphertexts may be packed in pairs, and so on, until a ciphertext Cq is obtained, so that the plaintext polynomial corresponding to the ciphertext Cq includes all coefficients that need to be retained in the M plaintext polynomials corresponding to the M ciphertexts. It can be understood that when M is not a power of 2, multiple ciphertexts can still be packaged based on the binary tree structure. For example, when M=3, assuming that the ciphertexts Ci, Cj, and Ck are packaged, the computing device can first package the ciphertexts Ci and Cj to obtain the ciphertext Ct, and then package the ciphertext Ct and the ciphertext Ck to obtain the final ciphertext Cq, so that the plaintext polynomial corresponding to the ciphertext Cq includes all the coefficients that need to be retained in the three plaintext polynomials corresponding to the ciphertexts Ci, Cj, and Ck.

After the computing device obtains the ciphertext Cq by packaging multiple ciphertexts, it can send the ciphertext Cq to another device to provide multiple target coefficients in the plaintext polynomial corresponding to the ciphertext Cq to the other device.

Through the scheme of this embodiment, multiple ciphertexts can be homomorphically calculated based on the number of coefficients that need to be retained in each ciphertext, so that in a packing process of two ciphertexts, the two ciphertexts are packed into a packed ciphertext, so that the plaintext polynomial corresponding to the packed ciphertext includes all the target coefficients that need to be retained corresponding to the two ciphertexts, thereby saving computational complexity and storage resources required for storing ciphertexts, and reducing the amount of communication data required to provide the target coefficients to other devices.

FIG6 is an architecture diagram of a computing device in an embodiment of this specification, including:

An acquiring unit 61 is configured to acquire a first ciphertext and a second ciphertext, wherein the first ciphertext and the second ciphertext are homomorphic ciphertexts of a first plaintext polynomial and a second plaintext polynomial, respectively, and the first plaintext polynomial and the second plaintext polynomial are polynomials in the same polynomial space;

a determining unit 62, configured to determine a first parameter value and a second parameter value based on a first number of first coefficients to be retained in the first plaintext polynomial and the second plaintext polynomial, the first parameter value being used in a homomorphic calculation of homomorphic replacement of a homomorphic ciphertext, and the second parameter value being used in a homomorphic calculation of homomorphic multiplication of a homomorphic ciphertext;

The calculation unit 63 is used to perform homomorphic calculation based on the first parameter value, the second parameter value, the first ciphertext and the second ciphertext to obtain a third ciphertext, wherein a third plaintext polynomial corresponding to the third ciphertext includes the first coefficient of the first number.

The embodiments of the present specification also provide a computer-readable storage medium on which a computer program is stored. When the computer program is executed in a computer, the computer is caused to execute the method shown in FIG. 2 or FIG. 5 .

A computing device is also provided in an embodiment of the present specification, including a memory and a processor, wherein the memory stores executable code, and when the processor executes the executable code, the method shown in FIG. 2 or FIG. 5 is implemented.

In the 1990s, improvements to a technology could be clearly distinguished as hardware improvements (for example, improvements to the circuit structure of diodes, transistors, switches, etc.) or software improvements (improvements to the method flow). However, with the development of technology, many improvements to the method flow today can be regarded as direct improvements to the hardware circuit structure. Designers almost always obtain the corresponding hardware circuit structure by programming the improved method flow into the hardware circuit. Therefore, it cannot be said that an improvement in a method flow cannot be implemented using a hardware entity module. For example, a programmable logic device (PLD) (such as a field programmable gate array (FPGA)) is such an integrated circuit whose logical function is determined by the user's programming of the device. Designers can "integrate" a digital system on a PLD by programming it themselves, without having to ask a chip manufacturer to design and produce a dedicated integrated circuit chip. Moreover, nowadays, instead of manually making integrated circuit chips, this kind of programming is mostly implemented by "logic compiler" software, which is similar to the software compiler used when developing and writing programs. The original code before compilation must also be written in a specific programming language, which is called hardware description language (HDL). There is not only one HDL, but many types, such as ABEL (Advanced Boolean Expression Language), AHDL (Altera Hardware Description Language), Confluence, CUPL (Cornell University Programming Language), HDCal, JHDL (Java Hardware Description Language), Lava, Lola, MyHDL, PALASM, RHDL (Ruby Hardware Description Language), etc. The most commonly used ones are VHDL (Very-High-Speed Integrated Circuit Hardware Description Language) and Verilog. Those skilled in the art should also be aware that it is easy to program the method flow in the above-mentioned hardware description languages slightly and program it into the integrated circuit. It is easy to obtain the hardware circuit that implements the logic method flow.

The controller may be implemented in any suitable manner, for example, the controller may take the form of a microprocessor or processor and a computer readable medium storing a computer readable program code (e.g., software or firmware) executable by the (micro)processor, a logic gate, a switch, an application specific integrated circuit (ASIC), a programmable logic controller, and an embedded microcontroller, examples of which include but are not limited to the following microcontrollers: ARC 625D, Atmel AT91SAM, Microchip PIC18F26K20, and Silicone Labs C8051F320, and the memory controller may also be implemented as part of the control logic of the memory. It is also known to those skilled in the art that in addition to implementing the controller in a purely computer readable program code manner, the controller may be implemented in the form of a logic gate, a switch, an application specific integrated circuit, a programmable logic controller, and an embedded microcontroller by logically programming the method steps. Therefore, such a controller may be considered as a hardware component, and the means for implementing various functions included therein may also be considered as a structure within the hardware component. Or even, the means for implementing various functions may be considered as both a software module for implementing the method and a structure within the hardware component.

The systems, devices, modules or units described in the above embodiments may be implemented by computer chips or entities, or by products with certain functions. A typical implementation device is a server system. Of course, the present application does not exclude that with the development of computer technology in the future, the computer that implements the functions of the above embodiments may be, for example, a personal computer, a laptop computer, a vehicle-mounted human-computer interaction device, a cellular phone, a camera phone, a smart phone, a personal digital assistant, a media player, a navigation device, an email device, a game console, a tablet computer, a wearable device, or a combination of any of these devices.

Although one or more embodiments of the present specification provide method operation steps as described in the embodiments or flow charts, more or less operation steps may be included based on conventional or non-creative means. The order of steps listed in the embodiments is only one way of executing the order of many steps, and does not represent the only execution order. When the device or terminal product in practice is executed, it can be executed in sequence or in parallel according to the method shown in the embodiments or the drawings (for example, a parallel processor or a multi-threaded processing environment, or even a distributed data processing environment). The term "include", "include" or any other variant thereof is intended to cover non-exclusive inclusion, so that the process, method, product or equipment including a series of elements includes not only those elements, but also includes other elements that are not explicitly listed, or also includes elements inherent to such a process, method, product or equipment. In the absence of more restrictions, it is not excluded that there are other identical or equivalent elements in the process, method, product or equipment including the elements. For example, if the words first, second, etc. are used to represent the name, they do not represent any specific order.

For the convenience of description, the above devices are described in various modules according to their functions. Of course, when implementing one or more of the present specification, the functions of each module can be implemented in the same or more software and/or hardware, or the module implementing the same function can be implemented by a combination of multiple sub-modules or sub-units, etc. The device embodiments described above are only schematic. For example, the division of the units is only a logical function division. There may be other division methods in actual implementation. For example, multiple units or components can be combined or integrated into another system, or some features can be ignored or not executed. Another point is that the mutual coupling or direct coupling or communication connection shown or discussed can be through some interfaces, indirect coupling or communication connection of devices or units, which can be electrical, mechanical or other forms.

The present invention is described with reference to the flowchart and/or block diagram of the method, device (system), and computer program product according to the embodiment of the present invention. It should be understood that each process and/or box in the flowchart and/or block diagram, as well as the combination of the process and/or box in the flowchart and/or block diagram can be implemented by computer program instructions. These computer program instructions can be provided to a processor of a general-purpose computer, a special-purpose computer, an embedded processor or other programmable data processing device to produce a machine, so that the instructions executed by the processor of the computer or other programmable data processing device produce a device for implementing the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable data processing device to work in a specific manner, so that the instructions stored in the computer-readable memory produce a manufactured product including an instruction device that implements the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

These computer program instructions may also be loaded onto a computer or other programmable data processing device so that a series of operational steps are executed on the computer or other programmable device to produce a computer-implemented process, whereby the instructions executed on the computer or other programmable device provide steps for implementing the functions specified in one or more processes in the flowchart and/or one or more boxes in the block diagram.

In a typical configuration, a computing device includes one or more processors (CPU), input/output interfaces, network interfaces, and memory.

Memory may include non-permanent storage in a computer-readable medium, in the form of random access memory (RAM) and/or non-volatile memory, such as read-only memory (ROM) or flash memory (flash RAM). Memory is an example of a computer-readable medium.

Computer-readable media include permanent and non-permanent, removable and non-removable media that can store information by any method or technology. Information can be computer-readable instructions, data structures, program modules or other Data. Examples of computer storage media include, but are not limited to, phase change memory (PRAM), static random access memory (SRAM), dynamic random access memory (DRAM), other types of random access memory (RAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technology, compact disk read-only memory (CD-ROM), digital versatile disk (DVD) or other optical storage, magnetic cassettes, magnetic tape disk storage, graphene storage or other magnetic storage devices or any other non-transmission media that can be used to store information that can be accessed by a computing device. As defined herein, computer-readable media does not include transitory media such as modulated data signals and carrier waves.

It should be understood by those skilled in the art that one or more embodiments of the present specification may be provided as a method, system or computer program product. Therefore, one or more embodiments of the present specification may take the form of a complete hardware embodiment, a complete software embodiment or an embodiment combining software and hardware. Moreover, one or more embodiments of the present specification may take the form of a computer program product implemented on one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) containing computer-usable program code.

One or more embodiments of the present specification may be described in the general context of computer-executable instructions executed by a computer, such as program modules. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform specific tasks or implement specific abstract data types. One or more embodiments of the present specification may also be practiced in distributed computing environments where tasks are performed by remote processing devices connected through a communication network. In a distributed computing environment, program modules may be located in local and remote computer storage media, including storage devices.

Each embodiment in this specification is described in a progressive manner, and the same and similar parts between the embodiments can be referred to each other, and each embodiment focuses on the differences from other embodiments. In particular, for the system embodiment, since it is basically similar to the method embodiment, the description is relatively simple, and the relevant parts can be referred to the partial description of the method embodiment. In the description of this specification, the description of the reference terms "one embodiment", "some embodiments", "example", "specific example", or "some examples" means that the specific features, structures, materials or characteristics described in conjunction with the embodiment or example are included in at least one embodiment or example of this specification. In this specification, the schematic representation of the above terms does not necessarily target the same embodiment or example. Moreover, the specific features, structures, materials or characteristics described can be combined in any one or more embodiments or examples in a suitable manner. In addition, those skilled in the art can combine and combine the different embodiments or examples described in this specification and the features of different embodiments or examples without contradiction.

The above description is only an example of one or more embodiments of the present specification and is not intended to limit one or more embodiments of the present specification. For those skilled in the art, one or more embodiments of the present specification may have various Any modification, equivalent substitution, improvement, etc. made within the spirit and principle of this specification shall be included in the scope of the claims.

Claims (16)

A privacy-protecting data processing method, the method being executed by a device of a first party and a device of a second party, wherein the second party possesses a public key for homomorphic encryption and a private key corresponding to the public key, the method comprising: The first party's device performs the following operations: Obtain a first ciphertext and a second ciphertext, wherein the first ciphertext and the second ciphertext are homomorphic ciphertexts of a first plaintext polynomial and a second plaintext polynomial, respectively, the first ciphertext and the second ciphertext correspond to the public key, and the first plaintext polynomial and the second plaintext polynomial are polynomials in the same polynomial space; Determine a first parameter value and a second parameter value based on a first number of first coefficients as target coefficients in the first plaintext polynomial and the second plaintext polynomial, the first parameter value being used in a homomorphic calculation of homomorphic replacement of a homomorphic ciphertext, and the second parameter value being used in a homomorphic calculation of homomorphic multiplication of a homomorphic ciphertext; perform homomorphic calculation based on the first parameter value, the second parameter value, the first ciphertext, and the second ciphertext to obtain a third ciphertext, the third plaintext polynomial corresponding to the third ciphertext including the first number of first coefficients; sending the third ciphertext to a device of the second party; The device of the second party decrypts the third ciphertext based on the private key to obtain the third plaintext polynomial, and obtains the first coefficient of the first number from the third plaintext polynomial. According to the method of claim 1, the first coefficients as target coefficients in the first plaintext polynomial and the second plaintext polynomial at least include coefficients of constant terms and coefficients of x ^N/2 terms. According to the method of claim 1 or 2, the performing homomorphic calculation based on the first parameter value, the second parameter value, the first ciphertext and the second ciphertext includes: performing homomorphic replacement on the first ciphertext based on the first parameter value to obtain a fourth ciphertext, wherein the coefficients of at least the ^xi item and the ^xj item in a fourth plaintext polynomial corresponding to the fourth ciphertext are negative numbers of the coefficients of the ^xi item and the ^xj item in the first plaintext polynomial, and wherein the coefficients of the ^xi item and the ^xj item in the first plaintext polynomial are not the target coefficients in the first plaintext polynomial. According to the method of claim 3, the performing homomorphic calculation based on the first parameter value, the second parameter value, the first ciphertext and the second ciphertext also includes: performing homomorphic replacement on the second ciphertext based on the first parameter value to obtain a fifth ciphertext, performing homomorphic multiplication on the sum of the second ciphertext and the fifth ciphertext based on the second parameter value to obtain a sixth ciphertext, the coefficients of the xi- ^th term and the xj ^- th term of the sixth plaintext polynomial corresponding to the sixth ciphertext are the target coefficients in the second plaintext polynomial, the coefficients of the terms in the sixth plaintext polynomial corresponding to the first coefficient in the first plaintext polynomial are zero, and the third ciphertext is obtained by adding the sixth ciphertext to the first ciphertext and the fourth ciphertext. The method according to claim 1 or 2, wherein the first parameter value, the second parameter value, The homomorphic calculation of the first ciphertext and the second ciphertext includes: performing homomorphic multiplication on the second ciphertext based on the second parameter value to obtain a seventh ciphertext, performing homomorphic replacement on the difference between the first ciphertext and the seventh ciphertext based on the first parameter value to obtain an eighth ciphertext, and obtaining the third ciphertext based on adding the first ciphertext to the seventh ciphertext and the eighth ciphertext. The method according to claim 1 further comprises: the device of the second party uses the public key to homomorphically encrypt a ninth plaintext polynomial to obtain a ninth ciphertext, the coefficients of the ninth plaintext polynomial corresponding to the first vector, and sending the ninth ciphertext to the device of the first party, The device of the first party multiplies the tenth plaintext polynomial and the eleventh plaintext polynomial by the ninth ciphertext respectively to obtain the first ciphertext and the second ciphertext, wherein the coefficient of the tenth plaintext polynomial corresponds to the second vector and the third vector, and the coefficient of the eleventh plaintext polynomial corresponds to the fourth vector and the fifth vector, The first coefficients of the first number include an inner product of the second vector and the first vector, an inner product of the third vector and the first vector, an inner product of the fourth vector and the first vector, and an inner product of the fifth vector and the first vector. The method according to claim 1, further comprising: Obtain a twelfth ciphertext and a thirteenth ciphertext, wherein the twelfth ciphertext and the thirteenth ciphertext are homomorphic ciphertexts of a twelfth plaintext polynomial and a thirteenth plaintext polynomial, respectively, the twelfth ciphertext and the thirteenth ciphertext correspond to the public key, and the twelfth plaintext polynomial and the thirteenth plaintext polynomial are polynomials in the polynomial space; Determine a third parameter value and a fourth parameter value based on the second number of the second coefficients as the target coefficients in the twelfth plaintext polynomial and the thirteenth plaintext polynomial, the third parameter value being used in a homomorphic calculation of homomorphic replacement of the homomorphic ciphertext, and the fourth parameter value being used in a homomorphic calculation of homomorphic multiplication of the homomorphic ciphertext; Perform homomorphic calculation based on the third parameter value, the fourth parameter value, the twelfth ciphertext, and the thirteenth ciphertext to obtain the first ciphertext. According to the method of claim 1, the degree of the polynomials included in the polynomial space is less than N, N is a power of 2, the first number is a power of 2, and the first number is less than or equal to N. The method according to claim 8, wherein the first parameter value is equal to the first number plus 1, and the second parameter value is equal to N/first number. A data processing method for protecting privacy, comprising: Obtain a first ciphertext and a second ciphertext, wherein the first ciphertext and the second ciphertext are homomorphic ciphertexts of a first plaintext polynomial and a second plaintext polynomial, respectively, and the first plaintext polynomial and the second plaintext polynomial are the same polymorphic polynomial. Polynomials in term space; Determine a first parameter value and a second parameter value based on a first number of first coefficients as target coefficients in the first plaintext polynomial and the second plaintext polynomial, the first parameter value being used in a homomorphic calculation of homomorphic replacement of a homomorphic ciphertext, and the second parameter value being used in a homomorphic calculation of homomorphic multiplication of a homomorphic ciphertext; A third ciphertext is obtained by performing homomorphic calculation based on the first parameter value, the second parameter value, the first ciphertext, and the second ciphertext, wherein a third plaintext polynomial corresponding to the third ciphertext includes a first coefficient of the first number. The method according to claim 10 is performed by a device of a first party, and further comprises: sending the third ciphertext to a device of a second party, wherein the second party possesses a private key corresponding to the third ciphertext. According to the method of claim 10, the obtaining of the first ciphertext and the second ciphertext comprises obtaining a first group of ciphertext pairs and a second group of ciphertext pairs, each group of ciphertext pairs comprising the first ciphertext and the second ciphertext, the obtaining of the third ciphertext comprises obtaining a third ciphertext corresponding to the first group of ciphertext pairs and a third ciphertext corresponding to the second group of ciphertext pairs, and the method further comprises: The data processing is performed using the two third ciphertexts as the first ciphertext and the second ciphertext in a third ciphertext pair to obtain a third ciphertext corresponding to the third ciphertext pair, wherein the plaintext polynomial corresponding to the third ciphertext corresponding to the third ciphertext pair includes the target coefficients in the plaintext polynomials corresponding to the first ciphertext pair and the second ciphertext pair. The method according to claim 12 further includes: obtaining four ciphertexts arranged in sequence, sequentially forming the first group of ciphertext pairs with the two ciphertexts ranked first and third, and sequentially forming the second group of ciphertext pairs with the two ciphertexts ranked second and fourth. A computing device comprising: an acquiring unit, configured to acquire a first ciphertext and a second ciphertext, wherein the first ciphertext and the second ciphertext are homomorphic ciphertexts of a first plaintext polynomial and a second plaintext polynomial, respectively, and the first plaintext polynomial and the second plaintext polynomial are polynomials in the same polynomial space; a determining unit, configured to determine a first parameter value and a second parameter value based on a first number of first coefficients as target coefficients in the first plaintext polynomial and the second plaintext polynomial, the first parameter value being used in a homomorphic calculation of homomorphic replacement of a homomorphic ciphertext, and the second parameter value being used in a homomorphic calculation of homomorphic multiplication of a homomorphic ciphertext; a computing unit, configured to calculate a first ciphertext based on the first parameter value, the second parameter value, the first ciphertext and the first The two ciphertexts are homomorphically calculated to obtain a third ciphertext, and a third plaintext polynomial corresponding to the third ciphertext includes the first coefficient of the first number. A privacy-preserving data processing system includes a device of a first party and a device of a second party, wherein the second party has a public key for homomorphic encryption and a private key corresponding to the public key. The first party's device is used to perform the following operations: Obtain a first ciphertext and a second ciphertext, wherein the first ciphertext and the second ciphertext are homomorphic ciphertexts of a first plaintext polynomial and a second plaintext polynomial, respectively, the first ciphertext and the second ciphertext correspond to the public key, and the first plaintext polynomial and the second plaintext polynomial are polynomials in the same polynomial space; Determine a first parameter value and a second parameter value based on a first number of first coefficients as target coefficients in the first plaintext polynomial and the second plaintext polynomial, the first parameter value being used in a homomorphic calculation of homomorphic replacement of a homomorphic ciphertext, and the second parameter value being used in a homomorphic calculation of homomorphic multiplication of a homomorphic ciphertext; Performing homomorphic calculation based on the first parameter value, the second parameter value, the first ciphertext, and the second ciphertext to obtain a third ciphertext, wherein a third plaintext polynomial corresponding to the third ciphertext includes a first coefficient of the first number; sending the third ciphertext to a device of the second party; The device of the second party is used to decrypt the third ciphertext based on the private key to obtain the third plaintext polynomial, and obtain the first coefficient of the first number from the third plaintext polynomial. A computing device comprises a memory and a processor, wherein the memory stores executable code, and when the processor executes the executable code, the method described in any one of claims 10 to 12 is implemented.