CN113626841B - Multi-party security calculation-based selection problem processing method - Google Patents

Abstract

The embodiment of this specification provides a method for processing selection problems based on multi-party secure computing. By constructing an embedding q of the set X into the vector space, m original images P ₁ , P ₂ , ..., P _m are mapped to the vector space, such as the set The corresponding vectors Q ₁ , Q ₂ , ... , Q _m are obtained, and then the images f(P ₁ ), f(P ₂ ), ... , f(P _m ) of the m original images P ₁ , P ₂ , ... , P _m under the mapping f are converted into outputs when the polynomial g takes the vector elements of the vectors Q ₁ , Q ₂ , ... , Q _m as inputs respectively. Based on this, by running the multi-party secure computation protocol, the first party holding the mapping f can obtain the first shard of g(Q ₁ ), g(Q ₂ ),..., g(Q _m ) as the first shard of f(P ₁ ), f(P ₂ ),..., f(P _m ), and the second party holding P ₁ , P ₂ ,..., P _m can obtain the second shard of g(Q ₁ ), g(Q ₂ ),..., g(Q _m ) as the second shard of f(P ₁ ), f(P ₂ ),..., f(P _m ).

Description

A method for solving selection problems based on multi-party secure computation

Technical Field

The present invention relates to the field of information technology, and in particular to a method for processing selection problems based on multi-party secure computing.

Background Art

Secure multi-party computation is also called multi-party secure computation, which means that multiple parties jointly calculate the result of a function without revealing the input data of each party of the function. The result of the calculation is stored in a shared form among multiple parties or disclosed to one or more of the parties. Therefore, through secure multi-party computation, the participating parties can calculate the result of the function without exposing their original data.

Some secure multi-party computation processes involve selection problems, which can be described as selecting m elements from a set of n elements (referred to as the n-choose-m problem). Currently, it is desirable to provide a method for processing selection problems based on secure multi-party computation.

Summary of the invention

One of the embodiments of the present specification provides a method for processing selection problems based on multi-party secure computing. Participants in the secure computing include a first party and a second party; the first party holds a private single shot f, which is a single shot from set X to set A; the second party holds m private original images P ₁ , P ₂ ,…, P _m , and the m original images P ₁ , P ₂ ,…, P _m all belong to set X, and the number of elements in set X is n; the first party and the second party share a single shot q, which is used to map the elements of set X to a preset vector space; the method is executed by the device of the first party, and includes: obtaining a polynomial g corresponding to the single shot f and the single shot q; wherein the output of the polynomial g when taking each vector element of the image of any element in set X under the single shot q as input is equal to the image of the element under the single shot f; obtaining the polynomial h ₀ ; the polynomial obtained by the first square h ₀ and the linear transformation matrix σ obtained by the second square and the polynomial h ₁ satisfy the polynomial The two slices of the complex polynomial obtained under the action of the linear transformation matrix σ are polynomials h ₀ and h ₁ ; wherein the linear transformation matrix σ is used for vector operations to change the positions of the elements in the vector, and the action makes the output of the complex polynomial when the vector elements of the operation result of the linear transformation matrix σ and the first vector are input equal to the polynomial output when each vector element of the first vector is used as input; receiving from the second party's device the vectors corresponding to Q ₁ , Q ₂ , ..., Q _m respectively Among them, Q ₁ ,Q ₂ ,…,Q _m are the images of m original images P ₁ ,P ₂ ,…,P _m under the single shot q, Each vector in is the result of the operation of the linear transformation matrix σ and the corresponding vector in Q ₁ , Q ₂ ,…, Q _m ; the calculation polynomial h ₀ is respectively The output when each vector element of is input Based on Get the first slice of [f(P ₁ ),f(P ₂ ),…,f(P _m )]; get the polynomial δg, And the polynomial δg is sent to the device of the second party, so that the device of the second party can obtain the second fragment of [f(P ₁ ), f(P ₂ ), …, f(P _m )].

One of the embodiments of the present specification provides a selection problem processing system based on multi-party secure computing. Participants in the secure computing include a first party and a second party; the first party holds a private single shot f, and the single shot f is a single shot from set X to set A; the second party holds m private original images P ₁ , P ₂ ,…, P _m , and the m original images P ₁ , P ₂ ,…, P _m all belong to set X, and the number of elements in set X is n; the first party and the second party share a single shot q, and the single shot q is used to map the elements of set X to a preset vector space; the system is implemented on the device of the first party, and includes: a first acquisition module, which is used to obtain a polynomial g corresponding to the single shot f and the single shot q; wherein the output of the polynomial g when taking the vector elements of the image of any element in set X under the single shot q as input is equal to the image of the element under the single shot f; a second acquisition module, which is used to obtain the polynomial h ₀ ; the polynomial obtained by the first square h ₀ and the linear transformation matrix σ obtained by the second square and the polynomial h ₁ satisfy the polynomial The two slices of the complex polynomial obtained under the action of the linear transformation matrix σ are polynomials h ₀ and h ₁ ; wherein the linear transformation matrix σ is used for vector operations to change the positions of the elements in the vector, and the action makes the output of the complex polynomial when the vector elements of the operation result of the linear transformation matrix σ and the first vector are input equal to the polynomial output when each vector element of the first vector is used as input; a first receiving module, used to receive from the second party's device the data corresponding to Q ₁ , Q ₂ , ..., Q _m respectively Among them, Q ₁ ,Q ₂ ,…,Q _m are the images of m original images P ₁ ,P ₂ ,…,P _m under the single shot q, Each vector in is the result of the operation of the linear transformation matrix σ and the corresponding vector in Q ₁ , Q ₂ ,…, Q _m ; the first calculation module is used to calculate the polynomial h ₀ respectively The output when each vector element of is input Based on Obtaining a first slice of [f(P ₁ ), f(P ₂ ), …, f(P _m )]; a first sending module, used to obtain a polynomial δg, And the polynomial δg is sent to the device of the second party, so that the device of the second party can obtain the second fragment of [f(P ₁ ), f(P ₂ ), …, f(P _m )].

One of the embodiments of the present specification provides a method for processing selection problems based on multi-party secure computing. Participants in the secure computing include a first party and a second party; the first party holds a private single shot f, which is a single shot from set X to set A; the second party holds m private original images P ₁ , P ₂ , …, P _m , and the m original images P ₁ , P ₂ , …, P _m all belong to set X, and the number of elements in set X is n; the first party and the second party share a single shot q, and the single shot q is used to map the elements of set X to a preset vector space; the method is executed by a device of the second party, and includes: obtaining images Q ₁ , Q ₂ , …, Q _m of the m original images P ₁ , P ₂ , …, P _m under the single shot q; obtaining a linear transformation matrix σ and a polynomial h ₁ ; the polynomial obtained by the first party h ₀ and the linear transformation matrix σ obtained by the second square and the polynomial h ₁ satisfy the polynomial The two slices of the complex polynomial obtained under the action of the linear transformation matrix σ are polynomials h ₀ and h ₁ ; wherein the linear transformation matrix σ is used for vector operations to change the positions of the elements in the vector, and the action makes the output of the complex polynomial when the vector elements of the operation result of the linear transformation matrix σ and the first vector are input equal to the polynomial The output when each vector element of the first vector is used as input; calculate the corresponding values of Q ₁ , Q ₂ , …, Q _m respectively and will is sent to the device of the first party so that the device of the first party can obtain the first fragment of [f(P ₁ ), f(P ₂ ), …, f(P _m )]; wherein, Each vector in is the result of the operation of the linear transformation matrix σ and the corresponding vector in Q ₁ ,Q ₂ ,…,Q _m ; the polynomial δg is received from the device of the first party, The output of the polynomial g when it takes the vector elements of the image of any element in the set X under the single shot q as input is equal to the image of the element under the single shot f; the output of the polynomial δg when it takes the vector elements of Q ₁ ,Q ₂ ,…,Q _m as input is δg(Q ₁ ),δg(Q ₂ ),…,δg(Q _m ), and the output of the polynomial h _{1 ...} The output when each vector element of is input Based on δg(Q ₁ ),δg(Q ₂ ),…,δg(Q _m ) and Obtain the second slice of [f(P ₁ ),f(P ₂ ),…,f(P _m )].

One of the embodiments of the present specification provides a selection problem processing system based on multi-party secure computing. Participants in the secure computing include a first party and a second party; the first party holds a private single shot f, which is a single shot from set X to set A; the second party holds m private original images P ₁ , P ₂ , …, P _m , and the m original images P ₁ , P ₂ , …, P _m all belong to set X, and the number of elements in set X is n; the first party and the second party share a single shot q, and the single shot q is used to map the elements of set X to a preset vector space; the system is implemented on the device of the second party, and includes: a third acquisition module, used to obtain images Q ₁ , Q ₂ , …, Q _m of the m original images P ₁ , P ₂ , …, P _m under the single shot q; a fourth acquisition module, used to obtain a linear transformation matrix σ and a polynomial h ₁ ; the polynomial obtained by the first party h ₀ and the linear transformation matrix σ obtained by the second square and the polynomial h ₁ satisfy the polynomial The two slices of the complex polynomial obtained under the action of the linear transformation matrix σ are polynomials h ₀ and h ₁ ; wherein the linear transformation matrix σ is used for vector operations to change the positions of the elements in the vector, and the action makes the output of the complex polynomial when the vector elements of the operation result of the linear transformation matrix σ and the first vector are input equal to the polynomial The output when each vector element of the first vector is used as input; the second sending module is used to calculate the corresponding values of Q ₁ , Q ₂ , ..., Q _m respectively and will is sent to the device of the first party so that the device of the first party can obtain the first fragment of [f(P ₁ ), f(P ₂ ), …, f(P _m )]; wherein, Each vector in is the operation result of the linear transformation matrix σ and the corresponding vector in Q ₁ , Q ₂ ,…, Q _m ; the second receiving module is used to receive the polynomial δg from the device of the first party, The output of the polynomial g when taking the vector elements of the image of any element in the set X under the single shot q as input is equal to the image of the element under the single shot f; the second calculation module is used to: calculate the output δg(Q ₁ ),δg(Q 2 ),…,δg(Q _m ) of the polynomial δg when taking the vector elements of Q ₁ ,Q ₂ ,…,Q _m as input respectively, and calculate the output of the polynomial h ₁ when taking the vector elements of Q 1 ,Q ₂ ,…,Q m respectively. The output when each vector element of is input Based on δg(Q ₁ ),δg(Q ₂ ),…,δg(Q _m ) and Obtain the second slice of [f(P ₁ ),f(P ₂ ),…,f(P _m )].

One of the embodiments of this specification provides a selection problem processing device based on multi-party secure computing. The device includes a processor and a storage device, the storage device is used to store instructions, and when the processor executes the instructions, the selection problem processing method based on multi-party secure computing as described in any embodiment of this specification is implemented.

BRIEF DESCRIPTION OF THE DRAWINGS

This specification will be further described in the form of exemplary embodiments, which will be described in detail by the accompanying drawings. These embodiments are not restrictive, and in these embodiments, the same number represents the same structure, wherein:

FIG1 is an exemplary interactive flow chart of a method for processing a selection problem based on multi-party secure computing according to some embodiments of this specification;

FIG. 2 is a diagram showing how to obtain a polynomial according to some embodiments of the present specification. An exemplary interaction diagram of h ₀ ,h ₁ and the linear transformation matrix σ;

3 is an exemplary module diagram of a selection problem processing system based on multi-party secure computing implemented on a first party's device according to some embodiments of this specification;

FIG. 4 is an exemplary module diagram of a selection problem processing system based on multi-party secure computation implemented on a second party's device according to some embodiments of the present specification.

DETAILED DESCRIPTION

In order to more clearly illustrate the technical solutions of the embodiments of this specification, the following is a brief introduction to the drawings required for the description of the embodiments. Obviously, the drawings described below are only some examples or embodiments of this specification. For ordinary technicians in this field, this specification can also be applied to other similar scenarios based on these drawings without creative work. Unless it is obvious from the language environment or otherwise explained, the same reference numerals in the figures represent the same structure or operation.

It should be understood that the "system", "device", "unit" and/or "module" used herein are a method for distinguishing different components, elements, parts, portions or assemblies at different levels. However, if other words can achieve the same purpose, the words can be replaced by other expressions.

As shown in this specification, unless the context clearly indicates an exception, the words "a", "an", "a kind" and/or "the" do not refer to the singular, but also include the plural. Generally speaking, the terms "include" and "comprise" only indicate the inclusion of the steps and elements that have been clearly identified, and these steps and elements do not constitute an exclusive list. The method or device may also include other steps or elements.

Flowcharts are used in this specification to illustrate the operations performed by the system according to the embodiments of this specification. It should be understood that the preceding or following operations are not necessarily performed precisely in order. Instead, the steps may be processed in reverse order or simultaneously. At the same time, other operations may also be added to these processes, or one or more operations may be removed from these processes.

In mathematics, a "group" refers to an algebraic structure that satisfies closure, associativity, identity, and inverse binary operations, including Abelian groups, homomorphisms, and conjugation classes. The multiplication symbol "*" (which can be omitted when there is no ambiguity) or the addition symbol "+" can usually be used as the symbol of the binary operation, but it should be noted that the binary operation is not necessarily equivalent to multiplication or addition in the four arithmetic operations. The result of one or more binary operations on several elements can be called a composite value.

The binary operation of the group satisfies: 1. The closure law, for any elements a and b in G, a*b is still in G; 2. The associative law, for any elements a, b and c in G, (a*b)*c＝a*(b*c); 3. There is an identity element (also called the unit element), there is an element e in G such that a*e＝e*a; 4. There is an inverse element, for any element a in G, there is b in G such that a*b＝b*a＝e, a and b are inverse elements of each other, and e is the identity element here. It is worth noting that for the binary operation represented by "+", e can also be called the zero element, and the inverse element can also be called the negative element. For any elements a and b in G, a-b can represent a+(the inverse element of b). The order of group operations is very important. Combining element a with element b may not necessarily produce the same result as combining element b with element a, that is, the commutative law a*b＝b*a may not always hold. A group that satisfies the commutative law is called an Abelian group (commutative group), and a group that does not satisfy the commutative law is called a non-Abelian group (non-commutative group). An Abelian group consists of its own set G and the binary operation *.

In mathematics, a mapping is often equivalent to a function. For example, suppose A and B are two non-empty sets. If for each element x in A, according to a certain rule (or law) f, there is always a unique element y in B corresponding to it, then the corresponding rule f is called a mapping from A to B, A can be called the initial set, and B can be called the final set. It is denoted as f: A→B, y is called the image of x, denoted as y＝f(x), and x is called the preimage of y. Set A is called the domain of the mapping f, and set B is called the codomain of f. Furthermore, if different preimages under the mapping f have different images, then the mapping f is called injective (or incident/embedded). In other words, f is injective, and when f(a)＝f(b), then a＝b (if a≠b, then f(a)≠f(b)).

Furthermore, the present specification relates to a quotient group based on a (non-negative) integer Abelian group, whose mathematical representation can be G:=Z/nZ, wherein Z is a (non-negative) integer set, n is a positive integer, the Z on the left side of the "/" indicates that the group elements are integer multiples of 1, and the nZ on the right side of the "/" indicates that the modulus of the group is n, and the quotient group Z/nZ is a cyclic group of order n with remainders modulo n.

It is worth noting that since computing devices usually use a fixed number of bits (such as bits) to store the values generated during the calculation process, multi-party collaborative calculations frequently use modular addition, multiplication (hereinafter referred to as modular addition, modular multiplication), etc. In this specification, unless otherwise specified, mathematical representations involving symbols can be understood as modular addition and modular multiplication rather than four arithmetic operations, and related terms (such as summation, sum, multiplication, product, etc.) are also understood as modular addition and modular multiplication rather than four arithmetic operations.

In some distributed scenarios, multi-party secure computation is required to obtain the target operation result, where security can refer to the correctness of the output result and the confidentiality of the input and output information. For example, in some machine learning scenarios, one party holds private feature data and the other party holds private label data. If the target operation result about the private data (feature data/label data) is directly calculated, once the target operation result is leaked, the private data may be deduced. To this end, both parties can each obtain a sum shared shard of the private data x, and the sum of the sum shared shards of the private data x obtained by both parties is x. Then, both parties run the secure computation protocol and each obtain a sum shared shard of the target operation result f(x). The sum of the sum shared shards of the target operation result f(x) obtained by both parties is f(x). In a multi-party secure computation involving two parties, if an attacker wants to know the private data, he needs to obtain the sum shared shards of the two parties (hereinafter referred to as shards).

Some secure multi-party computation processes involve a selection problem, which can be described as selecting m elements from a set containing n elements. The selection problem can be equivalent to: there exists a mapping f and m pre-images P ₁ , P ₂ , …, P _m , and the images f(P ₁ ), f(P ₂ ), …, f(P _m ) of the m pre-images P ₁ , P ₂ , …, P _m under the mapping f are calculated. Wherein, the mapping f is a mapping from set X to set A, and the m pre-images P ₁ , P ₂ , …, P _m all belong to set X, and the number of elements of set X is n. In some embodiments, for group addition and group multiplication, set A can be an Abelian group, such as Z/nZ. The participants in the secure computation include a first party and a second party, the first party holds a private mapping f, and the second party holds a private m pre-images P ₁ , P ₂ , …, P _m . In the secure computing process, the first party does not want to expose the private f to the outside, and the second party does not want to expose the private m pre-images P ₁ , P ₂ , …, P _m to the outside.

As an example only, in a distributed machine learning scenario, the feature party holds feature data of a large number of samples (such as n samples), while the label party holds label data of the samples. During training, the feature party and the label party need to align the samples so that training can be performed based on data of at least m samples (these m samples are shared by the feature party and the label party) out of the n samples. Specifically, the feature party holds the correspondence between the IDs and feature data of the n samples (which may be recorded as mapping f), and the label party holds at least the correspondence between the IDs of the m samples (i.e., m original images P ₁ , P ₂ ,…, P _m ) and label data. For the same sample, the ID of the feature party is the same as the ID of the label party. During training, the label party needs to obtain the slices of feature data corresponding to the IDs of the m samples from the feature party, and the feature party needs to obtain the slices of feature data of the m samples, but does not know which samples these slices belong to. It can be understood that the data security here includes two aspects: on the one hand, the feature party does not want to disclose more information from the mapping f to the label party. In other words, the feature party only wants to provide the label party with at most partial information (such as shards) of the feature data of m samples out of n samples; on the other hand, the label party does not want the feature party to know which samples of the n samples the label data of the m samples held by the label party specifically correspond to, that is, the label party does not want to disclose the IDs of the m samples to the feature party. For the allocation of shards of feature data, it is necessary to ensure data security, and the feature party and the label party each obtain their own shards of the feature data of the m samples through collaborative calculation, that is, both parties need to securely calculate the images f(P ₁ ), f(P ₂ ), …, f(P _m ) of the m original images P ₁ , P ₂ , …, P _m under the mapping f.

In view of this, the embodiment of this specification provides a method for processing selection problems based on multi-party secure computing. Embed q, map the m original images P ₁ ,P ₂ ,…,P _m to the vector space, such as the set The corresponding vectors Q ₁ , Q ₂ , …, Q _m are obtained, and then the images f(P ₁ ), f(P ₂ ), …, f(P _m ) of the m original images P ₁ , P ₂ , …, P _m under the mapping f are converted into the outputs when the polynomial g takes the vector elements of the vectors Q ₁ , Q ₂ , …, Q _m as inputs (denoted as g(Q ₁ ), g(Q ₂ ), …, g(Q _m )). Among them, the set is a set of vectors of m dimensions and Hamming weight k, each vector element of the vector (hereinafter referred to as 0/1 vector) is 0 or 1, and Q ₁ , Q ₂ , …, Q _m are respectively images of m original images P ₁ , P ₂ , …, P _m under embedding q. Based on this, by running the multi-party secure computation protocol, the first party holding the mapping f can obtain the first slice of g(Q ₁ ), g(Q ₂ ), …, g(Q _m ) as the first slice of f(P ₁ ), f(P ₂ ), …, f(P _m ), and the second party holding the m original images P ₁ , P ₂ , …, P _m can obtain the second slice of g(Q ₁ ), g(Q ₂ ), …, g(Q _m ) as the second slice of f(P ₁ ), f(P ₂ ), …, f(P _m ).

Figure 1 is an exemplary interactive flow chart of a selection problem processing method based on multi-party secure computation according to some embodiments of this specification. In Figure 1, the step with suffix 1 is performed by the first party holding the secret mapping f, and the step with suffix 2 is performed by the second party holding the secret m original images P ₁ , P ₂ , ..., P _m .

Step 110 - 1 , obtaining a polynomial g corresponding to the mapping f and the embedding q.

Step 110 - 2 , obtaining images Q ₁ , Q ₂ , …, Q _m of m original images P ₁ , P ₂ , …, P _m under embedding q.

Among them, embedding q is shared by the first party and the second party, that is, embedding q is the common knowledge of the first party and the second party. Embedding q is also an injection q. According to the definition of an injection, an injection must satisfy that the number of elements in the final set is not less than the number of elements in the initial set. Therefore, for the set X to the set The embedding q satisfies the set The number of elements in is not less than the number of elements n in set X, that is, For more details about the mapping f and embedding q, please refer to the previous description.

The polynomial g belongs to the polynomial set A[x ₁ ,x ₂ ,…,x _m ] _k . The polynomials in the polynomial set A[x ₁ ,x ₂ ,…,x _m ] _k have the following characteristics: 1. They are homogeneous polynomials of m-ary kth degree, and x ₁ ,x ₂ ,…,x _m represent the m input elements of the polynomial; 2. The coefficients of each monomial are all elements in the set A. For ease of understanding, the structure of the polynomials in the polynomial set A[x ₁ ,x ₂ ,…,x _m ] _k (hereinafter referred to as target polynomials) can be expressed in the following mathematical form:

in, Monomial The coefficients are elements in the set A. Each monomial can be obtained by selecting k input elements from the m input elements x ₁ ,x ₂ ,…,x _m of the polynomial, so each target polynomial is given by It consists of monomials.

gather Each vector element of the m-dimensional 0/1 vector can be used as the input of the target polynomial, and the set The Hamming weight of the 0/1 vector is k (that is, there are only k vector elements in the 0/1 vector that are 1). Combined with the structure of the target polynomial, we can see that the polynomial g is the image of any element in the set X (denoted as P) under the embedding q (that is, the set The output (denoted as g(Q)) when each vector element of the 0/1 vector in (denoted as Q) is input is equal to the coefficient of a monomial of the polynomial g, which is an element in the set A.

Based on this, we found a way to convert f(P) into g(Q) for calculation. Specifically, the polynomial g corresponding to the mapping f and the embedding q satisfies: the output (denoted as g(Q)) of the polynomial g when it takes the vector elements of the image (denoted as Q) of any element in the set X (denoted as P) under the single shot q is equal to the image of the element under the single shot f (denoted as f(P)), that is, g(Q) = f(P).

In some embodiments, in order to ensure that all possible values of the output of the polynomial g can cover all possible values of the image under the mapping f (not exceeding the number of elements in the set A, denoted as |A|), the number of monomials of the polynomial g (that is, the number of monomial coefficients, is ) can be greater than or equal to the number of elements in set A, that is,

The polynomial set A[x ₁ ,x ₂ ,…,x _m ] _k has some mathematical properties, so that after converting f(P) to g(Q), the slices of g(Q) can be obtained through appropriate mathematical transformation. Of course, the slices of g(Q) can be used as the slices of f(P). For specific details, please refer to the relevant description below.

Step 120-1, obtain the polynomial h ₀ .

Step 120 - 2 , obtaining a linear transformation matrix σ and a polynomial h ₁ .

The first square obtains the polynomial h ₀ and the linear transformation matrix σ and polynomial h ₁ obtained by the second square can satisfy The origin of this relationship is explained in detail below.

First, let’s introduce The mathematical meaning of . Representing polynomials The composite polynomial obtained under the action of the linear transformation matrix σ. When the linear transformation matrix σ is operated with the vector, such as matrix multiplication, the position of the elements in the vector can be changed. σ ^-1 represents the inverse matrix of the linear transformation matrix σ. When it is operated again with the result of the previous operation, the position of the elements can be restored to obtain the vector. The action makes the output of the composite polynomial when the vector elements of the matrix product of the linear transformation matrix σ and the first vector are taken as input equal to the polynomial The output when the vector elements of the first vector are input. To facilitate understanding of the effect of the linear transformation matrix on the polynomial, let the first vector be V (now take the column vector as an example), and the matrix product of the linear transformation matrix σ and the first vector is the vector Right now Will Substitute the vector elements of as input into the composite polynomial We can get a polynomial with each vector element of V as input Right now In other words, the inverse matrix σ ^-1 of the linear transformation matrix σ and the matrix product of the second vector (which may be recorded as column vector Y) (i.e., σ ^-1 Y) are substituted as input into the polynomial You can get a polynomial with each vector element of Y as input Right now

It should be noted that based on If a polynomial g belongs to the set of polynomials A[x ₁ ,x ₂ ,…,x _m ] _k , then the composite polynomial also belongs to this set; for modular addition, the polynomial set A[x ₁ ,x ₂ ,…,x _m ] _k can form a group, so the polynomials in this set can be Split into two pieces, namely, polynomial h ₀ and polynomial h ₁ (these two pieces also belong to the set). In fact, a computer can store a polynomial by storing its individual monomial coefficients, and accordingly, a computer can perform operations on the polynomial by performing operations on the monomial coefficients.

For the specific implementation of step 120 - 1 and step 120 - 2 , please refer to FIG. 2 and its related description.

Step 130 - 1 , calculating the polynomial δg, and sending the polynomial δg to the device of the second party.

in, The first party device obtains the polynomial g and the polynomial Then, δg can be calculated locally. Then, the first party's device can send the polynomial δg to the second party's device, so that the second party's device can obtain the second fragment of g(Q ₁ ), g(Q ₂ ), …, g(Q _m ) as the second fragment of f(P ₁ ), f(P ₂ ), …, f(P _m ).

Step 130-2, calculate and will Sent to the first party's device.

in, After the second-party device obtains the linear transformation matrix σ and Q ₁ ,Q ₂ ,…,Q _m , it can calculate locally Then, the second party's device can The first party device is sent to the first party device so that the first party device can obtain the first fragment of g(Q ₁ ), g(Q ₂ ), …, g(Q _m ) as the first fragment of f(P ₁ ), f(P ₂ ), …, f(P _m ).

Step 140-1, receiving from the second party's device

Step 150-1, calculate the polynomial h ₀ respectively The output when each vector element of is input Based on Obtain the first fragment of f(Q ₁ ), f(Q ₂ ), …, f(Q _m ).

In some embodiments, the first party's device may directly As the first fragment of g(Q ₁ ), g(Q ₂ ), …, g(Q _m ), the first fragment of f(P ₁ ), f(P ₂ ), …, f(P _m ) is obtained. Accordingly, the second party's device can calculate The second slices of g(Q ₁ ), g(Q ₂ ), …, g(Q _m ) are obtained, that is, the second slices of f(P ₁ ), f(P ₂ ), …, f(P _m ) are obtained.

Step 140 - 2 : Receive polynomial δg from the first party's device.

Step 150-2, calculate the outputs δg(Q ₁ ), δg(Q ₂ ), …, δg(Q _m ) of the polynomial δg when the vector elements of Q ₁ , Q ₂ , …, Q _m are used as inputs, and calculate the polynomial h ₁ when the vector elements of Q 1 , Q 2 , …, Q m are used as inputs. The output when each vector element of is input Based on δg(Q ₁ ),δg(Q ₂ ),…,δg(Q _m ) and Obtain the second fragment of f(Q ₁ ), f(Q ₂ ), …, f(Q _m ).

In some embodiments, the second party's device may calculate The second fragments of g(Q ₁ ), g(Q ₂ ), …, g(Q _m ) are obtained, that is, the second fragments of f(P ₁ ), f(P ₂ ), …, f(P _m ) are obtained. Accordingly, the first party's device can As the first fragment of g(Q ₁ ), g(Q ₂ ), …, g(Q _m ), the first fragment of f(P ₁ ), f(P ₂ ), …, f(P _m ) is obtained.

Understandably, based on That is, g(Q) = δg(Q) + h ₀ (σQ) + h ₁ (σQ). The specific method of calculating g(Q) in the example of this specification can be appropriately adjusted, and the adjusted embodiment is still within the scope of this specification. As an example only, the first party's device can calculate After obtaining the first fragment of g(Q ₁ ), the second party's device can calculate A second slice of g(Q ₁ ) is obtained, where k is the common knowledge of the first party and the second party.

Recalling the above content, the first vector V can also be a row vector, then we have The row vector Substitute the vector elements of as input into the composite polynomial The polynomial with each vector element of the row vector V as input can be obtained Right now Accordingly, Regardless of whether the first vector is a row vector or a column vector, the effect of the inverse matrix σ ^-1 of the linear transformation matrix σ on the polynomial g makes the output of the composite polynomial when it takes the vector elements of the matrix product of the linear transformation matrix σ and the first vector as input equal to the polynomial The output when each vector element of the first vector is used as input only differs in whether the relevant matrix (such as σ, σ ⁻¹ ) is a left-multiplied vector or a right-multiplied vector.

In some embodiments, the linear transformation matrix σ may be a reversible matrix (referred to as a reversible 0/1 matrix) whose matrix elements are 0 or 1. Such a reversible matrix may be obtained by a pseudo-random function or by randomly transforming the rows and/or columns of the identity matrix. Since the linear transformation matrix σ will generate an operation with the vector Q, and the vector Q is originally a vector whose vector elements are 0 or 1 (i.e., each vector element occupies 1 bit), if the linear transformation matrix σ whose matrix elements are 0 or 1 (i.e., each matrix element occupies 1 bit) is used, the calculated Each vector element can also be stored with 1 bit, which can save transmission to the greatest extent. (See step 130-2) The generated communication volume.

FIG. 2 is a diagram showing how to obtain a polynomial according to some embodiments of the present specification. An exemplary interaction diagram of h ₀ , h ₁ and the linear transformation matrix σ.

As shown in Figure 2, the two parties involved in the secure computation can obtain the polynomial with the assistance of a third-party device. h ₀ ,h ₁ and the linear transformation matrix σ. First, the third-party device can obtain The polynomial h ₀ ,h ₁ and the linear transformation matrix σ, and then transform the polynomial h ₀ is sent to the first party's device, and the polynomial h ₁ and the linear transformation matrix σ are sent to the second party's device.

In order to save communication traffic, a pseudo-random function can be used to generate polynomials h ₀ ,h ₁ and one or more data in the linear transformation matrix σ. The pseudo-random function accepts a seed as input to randomly generate a value (which can be controlled within a certain size range, such as within the set A) or other types of data (such as a reversible matrix). When the seed is fixed, a fixed value or other types of data with a fixed value can be generated. Based on this, for the polynomial For any data in h ₀ ,h ₁ and the linear transformation matrix σ, the participants in the secure computing can agree on a seed in advance with the third-party device to generate the same (equal) data using a pseudo-random function without communication.

For example, by agreeing on a seed in advance, the first-party device and the third-party device can use a pseudo-random function to generate a polynomial The monomial coefficients of the polynomial The polynomial coefficients of the polynomial h ₀ are generated using a pseudo-random function to obtain the polynomial h ₀ . Accordingly, by agreeing on a seed in advance, the second-party device and the third-party device can generate a reversible linear transformation matrix σ using a pseudo-random function. The third-party device generates the polynomial h ₀ and the linear transformation matrix σ, we can Calculate (if ) calculate the polynomial h ₁ and send the polynomial h ₁ to the device of the second party.

For another example, by agreeing on a seed in advance, the second party's device and the third party's device can use a pseudo-random function to generate the monomial coefficients of the polynomial h ₁ to obtain the polynomial h ₁ , and use a pseudo-random function to generate a reversible linear transformation matrix σ. Accordingly, by agreeing on a seed in advance, the first party's device and the third party's device can use a pseudo-random function to generate the polynomial The monomial coefficients of the polynomial Third-party device generator polynomial h ₁ and the linear transformation matrix σ, we can Calculate (if ) calculate the polynomial h ₀ and send the polynomial h ₀ to the device of the first party.

In some embodiments, the polynomial may also be generated by the first party and/or the second party's device h ₀ ,h ₁ and one or more data in the linear transformation matrix σ, and send the generated one or more data to the third-party device, so that the third-party device can be based on the data provided by the first party and/or the second party and Evaluating Polynomials h ₀ ,h ₁ and the data to be calculated in the linear transformation matrix σ. Usually, at least one of the polynomials h ₀ and h ₁ needs to have its monomial coefficients calculated by a third-party device and the calculated monomial coefficients sent to the device of the corresponding party.

In some embodiments, for a fixed mapping f, multiple rounds of secure computation may be performed, and each round securely computes the images f(P ₁ ), f(P ₂ ), …, f(P _m ) of a group of original images (each group includes m original images P ₁ , P ₂ , …, P _m ) under the mapping f. For example, in the distributed machine learning scenario described above, assuming that the label party holds the label data of 2 ⁷ samples, the label party may divide the 2 ⁷ samples into 4 groups, each with 2 ⁵ samples. That is, the feature party and the label party may perform 4 rounds of secure computation, and each round securely computes the shards of the feature data corresponding to the IDs of the 2 ⁵ samples.

It is worth noting that when the mapping f remains unchanged, fixing the embedding q can make the polynomial g corresponding to the mapping f and the embedding q unchanged. Further fixing the polynomial The polynomial δg can also remain unchanged. Therefore, the polynomial δg can be transmitted only once in multiple rounds of secure computing.

Compared with directly and securely calculating the images of all original images under the mapping f, dividing all original images into several groups and performing multiple rounds of secure calculations can obtain a smaller m. A small m can reduce the dimensions of a series of data (such as vectors P and Q, matrix σ, and the number of monomials contained in a single polynomial), thereby alleviating the storage and processing pressures during the calculation process.

It should be noted that the above description of the relevant process is only for example and explanation, and does not limit the scope of application of this specification. For those skilled in the art, various modifications and changes can be made to the process under the guidance of this specification. However, these modifications and changes are still within the scope of this specification.

FIG3 is an exemplary module diagram of a selection problem processing system based on multi-party secure computation according to some embodiments of this specification. System 300 can be implemented on a first party's device. As shown in FIG3 , system 300 may include a first obtaining module 310, a second obtaining module 320, a first receiving module 330, a first calculating module 340, and a first sending module 350.

The first obtaining module 310 may be used to obtain a polynomial g corresponding to the single shot f and the single shot q.

The second obtaining module 320 can be used to obtain the polynomial h ₀ .

The first receiving module 330 may be used to receive data from a device of the second party.

The first calculation module 340 can be used to calculate the polynomial h ₀ respectively as The output when each vector element of is input

The first sending module 350 may be used to obtain the polynomial δg, and send the polynomial δg to the second party's device, so that the second party's device can obtain the second fragment of f(P ₁ ), f(P ₂ ), …, f(P _m ).

FIG4 is an exemplary module diagram of a selection problem processing system based on multi-party secure computation according to some embodiments of this specification. System 400 can be implemented on a first party's device. As shown in FIG4 , system 400 may include a third obtaining module 410, a fourth obtaining module 420, a second sending module 430, a second receiving module 440, and a second computing module 450.

The third obtaining module 410 may be used to obtain images Q ₁ , Q ₂ , ..., Q _m of m original images P ₁ , P ₂ , ..., P _m under a single shot q.

The fourth obtaining module 420 may be used to obtain a linear transformation matrix σ and a polynomial h ₁ .

The second sending module 430 can be used to calculate and will Sent to the first party's device.

The second receiving module 440 may be configured to receive the polynomial δg from a device of the first party.

The second calculation module 450 can be used to calculate the outputs δg(Q ₁ ), δg(Q 2 ), …, δg(Q m ) of the polynomial δg when the vector elements of Q ₁ , Q 2 , …, Q _m are used as inputs, and calculate the outputs δg(Q ₁ ), δg(Q ₂ ), …, δg(Q _m ) of the polynomial h ₁ when the vector elements of Q 1 , Q 2 , …, Q m are used as inputs. The output when each vector element of is input Based on δg(Q ₁ ),δg(Q ₂ ),…,δg(Q _m ) and Obtain the second fragment of f(Q ₁ ), f(Q ₂ ), …, f(Q _m ).

For more details about the systems 300 , 400 and their modules, please refer to the process 100 and its related description.

It should be understood that the systems and modules shown in Figures 3 and 4 can be implemented in various ways. For example, in some embodiments, the system and its modules can be implemented by hardware, software, or a combination of software and hardware. Among them, the hardware part can be implemented using dedicated logic; the software part can be stored in a memory and executed by an appropriate instruction execution system, such as a microprocessor or dedicated design hardware. Those skilled in the art will understand that the above methods and systems can be implemented using computer executable instructions and/or included in processor control codes, such as carrier media such as disks, CDs or DVD-ROMs, programmable memories such as read-only memories (firmware), or data carriers such as optical or electronic signal carriers. Such codes are provided on the system and its modules of this specification. Not only can the hardware circuits such as ultra-large-scale integrated circuits or gate arrays, semiconductors such as logic chips, transistors, or programmable hardware devices such as field programmable gate arrays, programmable logic devices, etc. be implemented, they can also be implemented with software such as executed by various types of processors, and can also be implemented by a combination of the above hardware circuits and software (e.g., firmware).

It should be noted that the above description of the system and its modules is only for convenience of description and cannot limit this specification to the scope of the embodiments. It is understandable that for those skilled in the art, after understanding the principle of the system, it is possible to arbitrarily combine the modules or form a subsystem to connect with other modules without deviating from this principle. For example, in some embodiments, the first acquisition module 310 and the second acquisition module 320 can be two modules or can be combined into one module. Such variations are all within the scope of protection of this specification.

The beneficial effects that may be brought about by the embodiments of this specification include but are not limited to: providing a method for processing the n-choose-m problem based on multi-party secure computing, which can protect the data privacy of both parties of the computing. It should be noted that different embodiments may produce different beneficial effects. In different embodiments, the beneficial effects that may be produced may be any one or a combination of the above, or any other possible beneficial effects.

The basic concepts have been described above. Obviously, for those skilled in the art, the above detailed disclosure is only for example and does not constitute a limitation on the embodiments of this specification. Although not explicitly stated here, those skilled in the art may make various modifications, improvements and corrections to the embodiments of this specification. Such modifications, improvements and corrections are suggested in the embodiments of this specification, so such modifications, improvements and corrections still belong to the spirit and scope of the exemplary embodiments of this specification.

At the same time, this specification uses specific words to describe the embodiments of this specification. For example, "one embodiment", "an embodiment", and/or "some embodiments" refer to a certain feature, structure or characteristic related to at least one embodiment of this specification. Therefore, it should be emphasized and noted that "one embodiment" or "an embodiment" or "an alternative embodiment" mentioned twice or more in different positions in this specification does not necessarily refer to the same embodiment. In addition, certain features, structures or characteristics in one or more embodiments of this specification can be appropriately combined.

In addition, it will be appreciated by those skilled in the art that the various aspects of the embodiments of this specification may be illustrated and described by a number of patentable categories or situations, including any new and useful process, machine, product or combination of substances, or any new and useful improvements thereto. Accordingly, the various aspects of the embodiments of this specification may be performed entirely by hardware, entirely by software (including firmware, resident software, microcode, etc.), or by a combination of hardware and software. The above hardware or software may all be referred to as "data blocks", "modules", "engines", "units", "components" or "systems". In addition, the various aspects of the embodiments of this specification may be represented as a computer product located in one or more computer-readable media, the product including computer-readable program code.

A computer storage medium may include a propagated data signal containing computer program code, for example, in baseband or as part of a carrier wave. The propagated signal may be in a variety of forms, including electromagnetic, optical, etc., or a suitable combination. A computer storage medium may be any computer-readable medium other than a computer-readable storage medium, which can be connected to an instruction execution system, device or apparatus to communicate, propagate or transmit the program for use. The program code on the computer storage medium may be transmitted via any suitable medium, including radio, cable, fiber optic cable, RF, or similar media, or any combination of the above media.

The computer program coding required for the operation of each part of the embodiment of this specification can be written in any one or more programming languages, including object-oriented programming languages such as Java, Scala, Smalltalk, Eiffel, JADE, Emerald, C++, C#, VB.NET, Python, etc., conventional procedural programming languages such as C language, VisualBasic, Fortran2003, Perl, COBOL2002, PHP, ABAP, dynamic programming languages such as Python, Ruby and Groovy, or other programming languages, etc. The program coding can be run completely on the user's computer, or run on the user's computer as an independent software package, or partly run on the user's computer and partly run on the remote computer, or run completely on the remote computer or processing equipment. In the latter case, the remote computer can be connected to the user's computer by any network form, such as a local area network (LAN) or a wide area network (WAN), or connected to an external computer (e.g., by the Internet), or in a cloud computing environment, or used as a service such as software as a service (SaaS).

In addition, unless explicitly stated in the claims, the order of the processing elements and sequences described in the embodiments of this specification, the use of alphanumeric characters, or the use of other names are not intended to limit the order of the processes and methods of the embodiments of this specification. Although the above disclosure discusses some invention embodiments that are currently considered useful through various examples, it should be understood that such details are only for illustrative purposes, and the attached claims are not limited to the disclosed embodiments. On the contrary, the claims are intended to cover all modifications and equivalent combinations that are consistent with the essence and scope of the embodiments of this specification. For example, although the system components described above can be implemented by hardware devices, they can also be implemented only by software solutions, such as installing the described system on an existing processing device or mobile device.

Similarly, it should be noted that in order to simplify the description of the embodiments disclosed in this specification, thereby helping to understand one or more embodiments of the invention, in the above description of the embodiments of this specification, multiple features are sometimes combined into one embodiment, figure or description thereof. However, this disclosure method does not mean that the features required by the objects of the embodiments of this specification are more than the features mentioned in the claims. In fact, the features of the embodiments are less than all the features of the single embodiment disclosed above.

Each patent, patent application, patent application publication, and other materials, such as articles, books, specifications, publications, documents, etc., cited in this specification are hereby incorporated by reference in their entirety. Except for application history documents that are inconsistent with or conflicting with the contents of this specification, documents that limit the broadest scope of the claims of this specification (currently or later attached to this specification) are also excluded. It should be noted that if the descriptions, definitions, and/or use of terms in the materials attached to this specification are inconsistent or conflicting with the contents described in this specification, the descriptions, definitions, and/or use of terms in this specification shall prevail.

Finally, it should be understood that the embodiments described in this specification are only used to illustrate the principles of the embodiments of this specification. Other variations may also fall within the scope of the embodiments of this specification. Therefore, as an example and not a limitation, alternative configurations of the embodiments of this specification may be considered consistent with the teachings of this specification. Accordingly, the embodiments of this specification are not limited to the embodiments explicitly introduced and described in this specification.

Claims (19)

1. A method for processing selection problems based on multi-party secure computing, wherein: Participants in secure computing include a first party and a second party; the first party holds a private single shot f, which is a single shot from set X to set A; the second party holds m private original images P ₁ , P ₂ , …, P _m , and the m original images P ₁ , P ₂ , …, P _m all belong to set X, and the number of elements of set X is n; the first party and the second party share a single shot q, and the single shot q is used to map the elements of set X to a preset vector space to obtain vectors Q ₁ , Q ₂ , …, Q _m ; the method is executed by a device of the first party, and includes: Obtain a polynomial g corresponding to the single shot f and the single shot q; wherein the output of the polynomial g when taking the vector elements of the image of any element in the set X under the single shot q as input is equal to the image of the element under the single shot f; Using pseudo-random functions to obtain polynomials h ₀ ; the polynomial obtained by the first square h ₀ and the linear transformation matrix σ obtained by the second square and the polynomial h ₁ satisfy Polynomial The two slices of the complex polynomial obtained under the action of the linear transformation matrix σ are polynomials h ₀ and h ₁ ; wherein the linear transformation matrix σ is used to operate with the vector to change the position of the elements in the vector, and the action makes the output of the complex polynomial when the vector elements of the operation result of the linear transformation matrix σ and the first vector are input equal to the polynomial output when each vector element of the first vector is used as input; the first vector is a row vector or a column vector; Receive the data corresponding to Q ₁ , Q ₂ , …, Q _m from the second party's device Among them, Q ₁ ,Q ₂ ,…,Q _m are the images of m original images P ₁ ,P ₂ ,…,P _m under the single shot q, Each vector in is the result of the operation of the linear transformation matrix σ and the corresponding vector in Q ₁ ,Q ₂ ,…,Q _m ; Calculate the polynomial h ₀ respectively The output when each vector element of is input and will as the first fragment of [f(P ₁ ),f(P ₂ ),…,f(P _m )]; Obtain the polynomial δg, And the polynomial δg is sent to the device of the second party, so that the device of the second party can obtain the second fragment of [f(P ₁ ), f(P ₂ ), …, f(P _m )]. 2. The method of claim 1, wherein the vector in the vector space is m-dimensional and has a Hamming weight of k, and each vector element of the vector is 0 or 1; Polynomial g, h ₀ ,h ₁ are both m-dimensional k-degree homogeneous polynomials, polynomial g, The monomial coefficients in h ₀ and h ₁ are all elements in set A. 3. The method according to claim 1, wherein the polynomial is obtained h ₀ , including: Generate polynomials using pseudo-random functions The monomial coefficients of The monomial coefficients of the polynomial h ₀ are generated using a pseudorandom function to obtain the polynomial h ₀ . 4. The method according to claim 1, wherein the polynomial is obtained h ₀ , including: Generate polynomials using pseudo-random functions The monomial coefficients of The monomial coefficients of the polynomial h ₀ are received from a third-party device to obtain the polynomial h ₀ . 5 . The method of claim 1 , wherein the operation is a matrix product, and each matrix element of the linear transformation matrix σ is 0 or 1. 6. The method of claim 2, wherein the number of elements in the vector space is Greater than or equal to the number of elements in set A. 7. The method of claim 2, wherein the m-dimensional k-order homogeneous polynomial is expressed as Among them, a _i1,i2…ik are elements in set A. 8. A selection problem processing system based on multi-party secure computing, wherein: Participants in secure computing include a first party and a second party; the first party holds a private single shot f, which is a single shot from set X to set A; the second party holds m private original images P ₁ , P ₂ , …, P _m , and the m original images P ₁ , P ₂ , …, P _m all belong to set X, and the number of elements of set X is n; the first party and the second party share a single shot q, and the single shot q is used to map the elements of set X to a preset vector space to obtain vectors Q ₁ , Q ₂ , …, Q _m ; the system is implemented on a device of the first party, and includes: A first obtaining module is used to obtain a polynomial g corresponding to the single shot f and the single shot q; wherein the output of the polynomial g when taking the vector elements of the image of any element in the set X under the single shot q as input is equal to the image of the element under the single shot f; The second acquisition module is used to obtain the polynomial using a pseudo-random function h ₀ ; the polynomial obtained by the first square h ₀ and the linear transformation matrix σ obtained by the second square and the polynomial h ₁ satisfy Polynomial The two slices of the complex polynomial obtained under the action of the linear transformation matrix σ are polynomials h ₀ and h ₁ ; wherein the linear transformation matrix σ is used to operate with the vector to change the position of the elements in the vector, and the action makes the output of the complex polynomial when the vector elements of the operation result of the linear transformation matrix σ and the first vector are input equal to the polynomial output when each vector element of the first vector is used as input; the first vector is a row vector or a column vector; The first receiving module is used to receive from the second party's device the data corresponding to Q ₁ , Q ₂ , ..., Q _m respectively. Among them, Q ₁ ,Q ₂ ,…,Q _m are the images of m original images P ₁ ,P ₂ ,…,P _m under the single shot q, Each vector in is the result of the operation of the linear transformation matrix σ and the corresponding vector in Q ₁ ,Q ₂ ,…,Q _m ; The first calculation module is used to calculate the polynomial h ₀ respectively. The output when each vector element of is input and will as the first fragment of [f(P ₁ ),f(P ₂ ),…,f(P _m )]; The first sending module is used to obtain the polynomial δg, And the polynomial δg is sent to the device of the second party, so that the device of the second party can obtain the second fragment of [f(P ₁ ), f(P ₂ ), …, f(P _m )]. 9. A selection problem processing device based on multi-party secure computing, comprising a processor and a storage device, wherein the storage device is used to store instructions, and when the processor executes the instructions, the method as claimed in any one of claims 1 to 7 is implemented. 10. A method for processing selection problems based on multi-party secure computing, wherein: Participants in secure computing include a first party and a second party; the first party holds a private single shot f, which is a single shot from set X to set A; the second party holds m private original images P ₁ , P ₂ , …, P _m , and the m original images P ₁ , P ₂ , …, P _m all belong to set X, and the number of elements of set X is n; the first party and the second party share a single shot q, and the single shot q is used to map the elements of set X to a preset vector space to obtain vectors Q ₁ , Q ₂ , …, Q _m ; the method is executed by a device of the second party, and includes: Obtain images Q ₁ , Q ₂ , …, Q _m of m original images P ₁ , P ₂ , …, P _m under the single shot q; The linear transformation matrix σ and the polynomial h ₁ are obtained by using a pseudo-random function; the polynomial obtained by the pseudo-random function in the first party h ₀ and the linear transformation matrix σ obtained by the second square and the polynomial h ₁ satisfy Polynomial The two slices of the complex polynomial obtained under the action of the linear transformation matrix σ are polynomials h ₀ and h ₁ ; wherein the linear transformation matrix σ is used to operate with the vector to change the position of the elements in the vector, and the action makes the output of the complex polynomial when the vector elements of the operation result of the linear transformation matrix σ and the first vector are input equal to the polynomial output when each vector element of the first vector is used as input; the first vector is a row vector or a column vector; Calculate the corresponding values of Q ₁ ,Q ₂ ,…,Q _m and will is sent to the device of the first party so that the device of the first party can obtain the first fragment of [f(P ₁ ), f(P ₂ ), …, f(P _m )]; wherein, Each vector in is the result of the operation of the linear transformation matrix σ and the corresponding vector in Q ₁ ,Q ₂ ,…,Q _m ; receiving the polynomial δg from the first party's device, The output of the polynomial g when it takes the vector elements of the image of any element in the set X under the single shot q as input is equal to the image of the element under the single shot f; Calculate the outputs δg(Q 1 ),δg(Q 2 ),…,δg(Q m ) of the polynomial δg when the vector elements of Q ₁ ,Q ₂ ,…,Q _m are used as inputs, and calculate the outputs δg(Q ₁ ),δg(Q ₂ ),…,δg(Q _m ) of the polynomial h ₁ when the vector elements of Q 1 ,Q 2 ,…,Q m are used as inputs. The output when each vector element of is input Based on δg(Q ₁ ),δg(Q ₂ ),…,δg(Q _m ) and The second fragment of [f(P ₁ ), f(P ₂ ), …, f(P _m )] is obtained by calculation. 11. The method of claim 10, wherein the vector in the vector space is m-dimensional and has a Hamming weight of k, and each vector element of the vector is 0 or 1; Polynomial g, h ₀ ,h ₁ are both m-dimensional k-degree homogeneous polynomials, polynomial g, The monomial coefficients in h ₀ and h ₁ are all elements in set A. 12. The method according to claim 10, wherein obtaining the linear transformation matrix σ and the polynomial h ₁ comprises: Generate a linear transformation matrix σ using a pseudo-random function; The monomial coefficients of the polynomial h ₁ are generated using a pseudorandom function to obtain the polynomial h ₁ . 13. The method according to claim 10, wherein obtaining the linear transformation matrix σ and the polynomial h ₁ comprises: Generate a linear transformation matrix σ using a pseudo-random function; The monomial coefficients of the polynomial h ₁ are received from a third-party device to obtain the polynomial h ₁ . 14. The method of claim 10, wherein the method based on δg(Q ₁ ), δg(Q ₂ ), ..., δg(Q _m ) and The second slice of [f(P ₁ ),f(p ₂ ),…,f(P _m )] is obtained, including: calculate The second fragment of [f(P ₁ ),f(P ₂ ),…,f(P _m )] is obtained. 15. The method of claim 10, wherein the operation is a matrix product, and each matrix element of the linear transformation matrix σ is 0 or 1. 16. The method of claim 11, wherein the number of elements in the vector space is Greater than or equal to the number of elements in set A. 17. The method of claim 11, wherein the m-dimensional k-order homogeneous polynomial is expressed as Among them, a _i1,i2…ik are elements in set A. 18. A selection problem processing system based on multi-party secure computing, wherein: Participants in secure computing include a first party and a second party; the first party holds a private single shot f, which is a single shot from set X to set A; the second party holds m private original images P ₁ , P ₂ , …, P _m , and the m original images P ₁ , P ₂ , …, P _m all belong to set X, and the number of elements of set X is n; the first party and the second party share a single shot q, and the single shot q is used to map the elements of set X to a preset vector space to obtain vectors Q ₁ , Q ₂ , …, Q _m ; the system is implemented on a device of the second party, and includes: A third obtaining module is used to obtain images Q ₁ , Q ₂ , ..., Q _m of m original images P ₁ , P ₂ , ..., P _m under a single shot q; The fourth acquisition module is used to obtain the linear transformation matrix σ and the polynomial h ₁ by using a pseudo-random function; the polynomial obtained in the first side h ₀ and the linear transformation matrix σ obtained by the second square and the polynomial h ₁ satisfy Polynomial The two slices of the complex polynomial obtained under the action of the linear transformation matrix σ are polynomials h ₀ and h ₁ ; wherein the linear transformation matrix σ is used to operate with the vector to change the position of the elements in the vector, and the action makes the output of the complex polynomial when the vector elements of the operation result of the linear transformation matrix σ and the first vector are input equal to the polynomial output when each vector element of the first vector is used as input; the first vector is a row vector or a column vector; The second sending module is used to calculate the corresponding values of Q ₁ , Q ₂ , …, Q _m and will is sent to the device of the first party so that the device of the first party can obtain the first fragment of [f(P ₁ ), f(P ₂ ), …, f(P _m )]; wherein, Each vector in is the result of the operation of the linear transformation matrix σ and the corresponding vector in Q ₁ ,Q ₂ ,…,Q _m ; The second receiving module is configured to receive the polynomial δg from the device of the first party, The output of the polynomial g when it takes the vector elements of the image of any element in the set X under the single shot q as input is equal to the image of the element under the single shot f; The second calculation module is used to calculate the output δg(Q ₁ ), δg(Q 2 ), …, δg(Q m ) of the polynomial δg when the vector elements of Q ₁ , Q 2 , …, Q _m are used as input, and calculate the output δg(Q ₁ ), δg(Q ₂ ), …, δg(Q _m ) of the polynomial h ₁ when the vector elements of Q 1 , Q 2 , …, Q m are used as input. The output when each vector element of is input Based on δg(Q ₁ ),δg(Q ₂ ),…,δg(Q _m ) and The second fragment of [f(P ₁ ), f(P ₂ ), …, f(P _m )] is obtained by calculation. 19. A selection problem processing device based on multi-party secure computing, comprising a processor and a storage device, wherein the storage device is used to store instructions, and when the processor executes the instructions, the method as claimed in any one of claims 10 to 17 is implemented.