Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 10/22/2024 has been considered by the examiner.
Specification
The specification and the drawings submitted on 09/24/2024 has been considered by the examiner.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-18 and 23-24 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claims 1 and 23 recites the limitation " the function " in lines 12-13, 23, 30, .
Claims 1 and 23 recites the limitation “their” in lin23.
Claims 1 and 23 recites the limitation “the respective output share of that output” in line 31.
There are insufficient antecedent bases for these limitations in the claims.
Claim 1, in line 8; claim 14, in line 9; claim 23 in line 10 and claim 24, in line 10 recite “the first input and/or or one or more second inputs” in a confusing manner. Particularly the, the connector “and/or or” is unambiguous and hindered determination of scope of the corresponding limitations. Claims 1, 14, 23 and 24 are rendered indefinite.
Claims 1-18 and 23-24 heavily apply use of the term “respective” in ambiguous and confusing manner. Just to give an example, claim 1 lines 16-17 recite
“replacing each specified first input with a respective first splitting gate (SSG), wherein each respective SSG represents a protocol performed by the coordinator to distribute a respective share of a respective secret to each respective party, wherein the respective secret is associated with a respective threshold.”
Under BRI, the examiner gave a dictionary literal meaning to the word “respective”. The word respective is an adjective word used to link two or more entities or individual items to two or more other corresponding entities or individual items in the exact order they were mentioned by indicating a match. In the above recited limitations, the word “respective” tangled relationships among the following entities: the first input, the first splitting gate, a protocol, a share, a secret, a party and a threshold. The examiner provided this limitation just as an example. Other parts of the whole claims 1-18 and 23-24 are riddled with use of “respective” in a confusing manner and therefore hindered a proper claim construction and appraisal for claims scope and boundary.
Dependent claims 2-13 and 15-18 failed to remedy the above identified deficiencies of their corresponding independent claims. Therefore, claims 1-18 and 23-24 are rejected under 35 U.S.C. 112(b) as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor regards as the invention.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claim 24 is rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter. The claim(s) does/do not fall within at least one of the four categories of patent eligible subject matter because claim 24 is directed to “a computer program embodied on computer-readable storage and configured so as, when run on one or more processors of a first party of a plurality of parties of a group”. Under BRI, a neither ” computer program” nor “computer-readable storage” is not a process, or a machine or a composition of matter or a manufacture to be eligible as statutory subject matter. Claim 24 is considered as a computer program per se. Therefore, claim 24 is rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-3, 9-14, 16-18 and 23-24 are rejected under 35 U.S.C. 103 as being unpatentable over STORM et al. (US 20200220851 A1 --- Hereinafter—" STORM”) in view of Joy US 20170353855 A1.
As per claim 1. STORM discloses a computer-implemented method for performing a multi-party computation (MPC) protocol ([0047] A secure multi-party computation (MPC) may allow operation of a function on two datasets without the owner or custodian of each dataset obtaining any proprietary information. MPC is based on a number of cryptographic tools and strategies such as secret sharing),
wherein a group comprises a coordinator ([0097] An aggregator 478. FIG. 4D illustrates an approach 470 to applying SMPC. New input 472 is provided to an aggregator 478)
obtaining a circuit representation of a computable function ([0067] FIG. 4B illustrates 408 the interaction between algorithm provider 410 and a data provider 414. The algorithm provider 410 selects parameters and builds a context associated with the processing of data using the algorithm. The context 416 is communicated to the data provider 414. The algorithm provider synthesizes the algorithm into logic gates 418 and “hides” the algorithm 420 using the principles disclosed herein, such as in FIG. 7. The result of the hiding process includes gates 422 and a general or generic circuit 424. The algorithm provider 410 sends the general circuit 426 to the data provider 414. Next, the algorithm provider generates shares 428 as disclosed herein and the data provider 414 generates shares from the inputs 436. The algorithm provider 410 sends shares 434 to the data provider 414 and the data provider 414 sends shares 442 to the algorithm provider 410. The algorithm provider 410 performs a process using the algorithm provider's gates shares 430 and the data provider's gates shares 432. The data provider 414 performs a process using the algorithm provider's input shares 438 and the data provider's input shares 440. After the generation of the algorithm provider shares from the data provider's inputs, the two parties are ready to start the MPC protocol. See FIG. 6 and associated discussion herein. [0068] The “hiding” occurs as the algorithm provider replaces each gate in the anonymized circuit with a generic circuit and generates the function “general circuit” 424 and stores the information of each gate in a separate table. By replacing each gate with the generic circuit, the circuit is hidden and most of the information of the circuit is transferred to a gates table. What is left is just the location of each gate as is shown in FIG. 7. The hidden circuit 702 in FIG. 7 illustrates an example of what is public and as it could confirm only the location of each gate. The general structure of the circuit is revealed. The security of this approach depends on the security of the MPC method which is used on top of the circuit hiding method as the information regarding each gate is separately stored in the gates table. The computed output of each gate by the other party could not be used to reverse engineer the circuit because the actual output of each gate is not available to the other party and only some part of it is available. The circuit provider only allows the possibility of computing the output of those gates), to be evaluated based on one or more first inputs to generate one or more outputs ([0097] The aggregator 478 receives encrypted data from a data provider 474 which uses the data provider's public key KPd 476. The aggregator also receives an encrypted function f from an algorithm provider 482 which is encrypted under the algorithm provider's public key Kpa 480. Both encryptions are homomorphic encryption which enables the user to compute the encrypted results using only encrypted data, without requiring decryption. The aggregator 478 computes the result 484 using homomorphic encryption. The result can include a function result based on the new-input and the data. At the end of the computation, the data provider 474 and the algorithm provider 482 compute the decryption algorithm using SMPC. The SMPC 486 can be used to decrypt the result, the KSd and the KSa),
wherein each first input is to be either specified or randomly generated ([0097] In the SMPC protocol, the algorithm provider input is its corresponding secret key KSa and the data provider input is its secret key KSd. [0118] For example, the first party (e.g., User A, such as the data provider computing device 102 or the algorithm provider computing device 104), can generate an N by 3 matrix, Beav.sub.A. Beav.sub.A can include first and second columns that are randomly generated, and the third column can contain an operation of the algorithm subset. Beav.sub.A can also be generated randomly in part or perhaps be generated based on a non-random process), and wherein the circuit representation comprises
a plurality of arithmetic gates representing respective functions for operating on one or more of the first inputs and/or or one or more second inputs ([0099] A user or aggregator 510 may receive the encrypted data 504 from the first data provider 502 and the second encrypted data 510 from the second data provider 508 and may receive the encrypted algorithm 520 from the first algorithm provider 518 and the second encrypted algorithm 526 from the second algorithm provider 524. The user or aggregator 510 may execute the algorithm on the data and determine a result that may include a proprietary business process 516. As noted above, the user or aggregator 510 may be one of the first data provider 502 or the second data provider 508, the first algorithm provider 518, the second algorithm provider 5524, or may be a different entity. The aggregator 510 may also be a combination or a hybrid of a respective data provider and/or a respective algorithm provider. The aggregator 510 can also in one aspect receive unencrypted data or algorithms and perform the encryption operation within the aggregator 510);
wherein a second input is a respective output of a respective gate, and ([0100] FIG. 6 illustrates an example circuit 600 associated with an algorithm, in accordance with various embodiments. In some secure multiparty computation (MPC), circuit garbling has been used for secure communication between two participants such as a garbler and an evaluator. The embodiments discussed herein are different from circuit garbling. Multiparty computation (MPC) is able to execute two operations including multiplication (AND) and addition (XOR). As a result, in order to perform complex operations and functions, the operations and functions are to be broken down into AND and XOR operations. The example circuit 600 shown in FIG. 6 includes only XOR, AND, and NOT gates. NOT gates are replaced with XOR gates with a bit of “1” that allows the circuit to represent only AND and XOR gates)
a plurality of directed edges, wherein each directed edge represents a first or second input being supplied to a respective arithmetic gate to be operated on by that respective arithmetic gate ([0102] An algorithm may be encoded into a logical or emulated circuit by converting the algorithm into a specific circuit 600 such as one shown in FIG. 6. The circuit may include a correct number and arrangement of gates such that it represents the algorithm. Each of the specific gates in the circuit may be replaced with generic gate slots. Each of the generic gate slots may be populated with a correct bit pattern to cause the gate to function as it should. The gate information may then be copied into a matrix):
converting the circuit representation of the function to a multi-party representation of the function by: replacing each specified first input with a respective first splitting gate (SSG) ([0067] The algorithm provider 410 sends the general circuit 426 to the data provider 414. Next, the algorithm provider generates shares 428 as disclosed herein and the data provider 414 generates shares from the inputs 436. The algorithm provider 410 sends shares 434 to the data provider 414 and the data provider 414 sends shares 442 to the algorithm provider 410. The algorithm provider 410 performs a process using the algorithm provider's gates shares 430 and the data provider's gates shares 432. The data provider 414 performs a process using the algorithm provider's input shares 438 and the data provider's input shares 440. After the generation of the algorithm provider shares from the data provider's inputs, the two parties are ready to start the MPC protocol);
wherein each respective SSG represents a protocol performed by the coordinator to distribute a respective share of a respective secret to each respective party [0143] Then, each data owner performs a cryptographic private write utilizing a anonymizing cryptographic primitive, such as for example the recent Function Secret Sharing (FSS), or similar mechanisms and alternatives. FSS, and similar, enables each data owner to privately write a message to a particular database row without any aggregation party learning which row was written to. The FSS private write is protected as long as there are more than two data owners participating and as long as there is at least one aggregation party which does not collude),
replacing each randomly generated first input with a respective second splitting gate (JSG) ([0126] At step 946, the data provider can provide the split data sets to the two parties and, using the corresponding Beaver sets, run the split algorithms on the split data sets. In some embodiments, the data can be split into a random share of the full dataset so as to further hide sensitive information (e.g., patterns that expose demographic information, sex, age, race, or other biometrics that expose patient identity),
wherein each respective JSG gate represents a protocol performed by each party to collaboratively generate a respective share of a respective secret ([0118] For example, the first party (e.g., User A, such as the data provider computing device 102 or the algorithm provider computing device 104), can generate an N by 3 matrix, Beav.sub.A. Beav.sub.A can include first and second columns that are randomly generated, and the third column can contain an operation of the algorithm subset. Beav.sub.A can also be generated randomly in part or perhaps be generated based on a non-random process. In this example embodiment, the third column contains the multiplications of the first two columns. The first two columns of the Beaver sets can be randomly generated to mask the actual data (EKG shares), and the third column can be computed depending on the application (multiplication, division, exponential, . . . ). It is preferred that the first two columns be randomly generated to be able to hide the actual data),
making the multi-party representation available to each party, wherein each party is configured to evaluate the function by executing the multi-party representation based on their respective shares of the respective secrets, thereby generating a respective share of each output ([0105] FIG. 8 illustrates 800 the hidden circuit 309 divided into a first split or first subset 310 and a second split or second subset 312. The hidden representation 309 may be divided into two splits or subsets. The first subset of the algorithm 310 may be evaluated by a first party, a first computing device or a first virtual compute environment and the second subset of the algorithm 312 may be evaluated by a second party, a second computing device or a second virtual compute environment. Generally speaking, these different splits of the Boolean logic gate set 309 are separate into different compute spots, locations, portions, physical components or virtual component such that their separate processing can be performed in a separated manner);
executing each SSG by distributing the respective share of the respective secret to each respective party ([0116] The beaver set can be utilized at a time of calculation (e.g., after the algorithm has been encrypted and distributed between the data provider computing device 102 and the algorithm provider computing device 104). After the algorithm has been encrypted, split, and distributed to the two parties, the beaver set can be employed when one or both of the parties are ready to perform the calculations. Since calculating encrypted circuits is slow, reducing the amount of information exchange between the two parties by using Beaver sets (which enable more mathematical calculations to be performed by each party before an exchange is made), will increase the speed and efficiency of the overall algorithm and data processing), and
generating each output of the function, wherein each output is generated based on at least the number of the respective output shares of that output ([0144] A flatten layer can be used to rearrange the shares. A maximum pooling layer 1104B can be used. There are two example approach for maximum pooling. First, if input.sub.A>input.sub.B, the output of the function f=max(input.sub.A, input.sub.B) is A. In such a case, the system can find the maximum of two inputs using SMPC with two communications. In another example, if input.sub.A>input.sub.B, then the output of the function f=max(input.sub.A, input.sub.B) can be input.sub.A. In this case, the system needs to create the comparison circuit and use ((1−(A>B))*B+(A>B)*A to output the greater value. The advantages of this method over the first method is that no party learns anything about the location of the maximum value on the other hand it is expense in terms of computations and time).
STORM does not explicitly disclose wherein the respective secret is associated with a respective threshold, and obtaining a respective share of each output from at least a threshold number of parties, the threshold number corresponding to a circuit threshold associated with the multi-party circuit. Joy, in analogous art however, discloses wherein the respective secret is associated with a respective threshold and obtaining a respective share of each output from at least a threshold number of parties, the threshold number corresponding to a circuit threshold associated with the multi-party circuit ([0137] The figure shows multiple party cryptographic (MPC) setting as the centralized mechanism. In at least one embodiment, each aggregator splits their values into shares using Shamir's Secret Sharing. The shares are distributed across all aggregators so that each aggregator has one share from every other aggregator 212. The share was submitted to each aggregator by the data owner. The aggregators sum these inputs to create an encrypted aggregate 214. The threshold check is calculated by subtracting the threshold from the encrypted aggregate 216. The threshold check is converted to bit representation in order for the aggregators to reveal the most significant bit (MSB) to detect if the aggregate is above or below the threshold 222. If the MSB is set to “0” (greater than the threshold), the servers release the aggregate. Otherwise, no values are released 228, 230. [0139] Data owners contribute their responses 212 (x.sub.1 to x.sub.i) to the aggregators 214, assuming a pre-sampling step. The aggregators compute MPC which only reveals the aggregate output 215 if it is greater than a publicly known threshold value 216. Aggregate output 215 and threshold 216 are received by a threshold circuit 218 which outputs a result value 220, received by a binarization process 222, herein exemplified as extracting only the most-significant bit (MSB) of result 220 in generating binary output 224 to an inverted input of gate 226 along with the Aggregate signal 226, and outputs this binary control signal to reveal 228 controlling whether output 230 reveals the aggregate result. [0144-0145]). Therefore, it would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify the claimed limitations of the aggregator disclosed by STORM to include wherein the respective secret is associated with a respective threshold and obtaining a respective share of each output from at least a threshold number of parties, the threshold number corresponding to a circuit threshold associated with the multi-party circuit. This modification would have been obvious because a person having ordinary skill in the art would have been motivated by the desire to provide capability to perform real-time streaming privacy-preserving personal data collection that scales to hundreds of millions of users while maintaining utility, including accuracy in respect to ground truth, and protecting data owners privacy as suggested by Joy ([0008]).
As pe claim 2. STORM in vie w of Joy discloses the method of claim 1, wherein the multi-party circuit representation comprises,
for each output to be generated, a respective reconstruction gate (RG), and wherein each respective RG gate represents a protocol performed by the coordinator to generate a respective output by interpolating over the respective output shares that are input to the respective RG (STORM [0072] GMW only supports addition and requires online communications to compute multiplications. The reason that GMW doesn't support multiplications is the fact that if the system adds two polynomials, the degree of the polynomials doesn't increase, but if the system multiplies two polynomials, the degree increases, so GMW requires communications to keep the degree of the polynomial low. The main idea of this disclosure is to use a quotient polynomial ring to keep the degree of the polynomial low to be able to reconstruct it using available points (Lagrange polynomial reconstruction). The Chinese Remainder Theorem (CRT) provides a strong tool to compute the reduction of any arbitrary polynomials to the principal ideal (if the principal ideal has enough roots) by knowing the roots of the principal ideal)).
As per claim 3: STORM in vie w of Joy discloses the method of claim 1, wherein the circuit representation comprises one or more inverse gates representing a function configured to output a respective inverse of a respective non-scalar input (STORM [0072] GMW only supports addition and requires online communications to compute multiplications. The reason that GMW doesn't support multiplications is the fact that if the system adds two polynomials, the degree of the polynomials doesn't increase, but if the system multiplies two polynomials, the degree increases, so GMW requires communications to keep the degree of the polynomial low. The main idea of this disclosure is to use a quotient polynomial ring to keep the degree of the polynomial low to be able to reconstruct it using available points (Lagrange polynomial reconstruction). The Chinese Remainder Theorem (CRT) provides a strong tool to compute the reduction of any arbitrary polynomials to the principal ideal (if the principal ideal has enough roots) by knowing the roots of the principal ideal), and
wherein said converting comprises: replacing each of said one or more inverse gates with a respective share inverse gate (IVG), wherein each respective IVG represents a protocol performed by each party to collaboratively generate a respective inverse share of a respective share that is input to the IVG (STORM [0086] In step (5), to compute (a⊕b), party A computes S.sub.AA+S.sub.BA, and Party B computes S.sub.BB×S.sub.AB. In step (6), to compute (aΛb), Party A computes S.sub.AA×S.sub.BA, and Party B computes S.sub.BB×S.sub.AB. These are element—wise multiplications. At step (7), at the end of the computation, both parties share the final results and jointly reconstruct the resulting polynomial P.sub.R using n points (r.sub.1, P.sub.f.sub.1(r.sub.1)), (r.sub.2, P.sub.f.sub.2(r.sub.2)) . . . (r.sub.n, P.sub.f.sub.n(r.sub.n)): [0092] λ.sub.i's are calculated easily and are public information. S.sub.i's are secret shares where half of them are kept by party A and the others are kept by party B. If they share S.sub.i's, the polynomial could be reconstructed and the bit value is revealed. Using the following protocol, two parties can refresh a polynomial. Another way of describing this process is to replace the polynomial with a new polynomial having a smaller coefficient).
As per claim 7: STORM in vie w of Joy discloses the method of claim 1, wherein the protocol performed by the coordinator to distribute a respective share of the respective secret to each respective party comprises Shamir's secret sharing scheme (SSSS) (Joy [0137] multiple party cryptographic (MPC) setting as the centralized mechanism. In at least one embodiment, each aggregator splits their values into shares using Shamir's Secret Sharing).
As per claim 9: STORM in vie w of Joy discloses the method of claim 1, wherein obtaining the circuit representation of the function comprises generating the circuit representation (STORM: ([0067] FIG. 4B illustrates 408 the interaction between algorithm provider 410 and a data provider 414. The algorithm provider 410 selects parameters and builds a context associated with the processing of data using the algorithm. The context 416 is communicated to the data provider 414. The algorithm provider synthesizes the algorithm into logic gates 418 and “hides” the algorithm 420 using the principles disclosed herein, such as in FIG. 7. The result of the hiding process includes gates 422 and a general or generic circuit 424. The algorithm provider 410 sends the general circuit 426 to the data provider 414. Next, the algorithm provider generates shares 428 as disclosed herein and the data provider 414 generates shares from the inputs 436).
As per claim 10: STORM in vie w of Joy discloses the method of claim 1, comprising: for each respective secret generated by the coordinator, sending obfuscated coefficients of a corresponding respective polynomial to each party for verifying the respective secret (STORM [0068] The “hiding” occurs as the algorithm provider replaces each gate in the anonymized circuit with a generic circuit and generates the function “general circuit” 424 and stores the information of each gate in a separate table. By replacing each gate with the generic circuit, the circuit is hidden and most of the information of the circuit is transferred to a gates table. [0068] The “hiding” occurs as the algorithm provider replaces each gate in the anonymized circuit with a generic circuit and generates the function “general circuit” 424 and stores the information of each gate in a separate table. By replacing each gate with the generic circuit, the circuit is hidden and most of the information of the circuit is transferred to a gates table).
As per claim 12: STORM in vie w of Joy discloses the method of claim 1, wherein the computable function is an age verification function (STORM [0049] As an example, an age of a patient, a gender of a patient, and other information may be relevant to a diagnosis. The doctor can utilize multiparty computation to possibly improve the diagnosis).
As per claim 13: STORM in vie w of Joy discloses the method of claim 1, wherein the coordinator is one of the parties (STORM [0065] The data provider computing device 102 or the aggregator 202 may perform the first subset of the algorithm 310 on the first subset of data 304. In addition, the algorithm provider computing device 104 or the aggregator 202 may perform the second subset of the algorithm 312 on the second subset of data 306. The data provider computing device 102 and the algorithm provider computing device 104 (or the aggregator 202) may merge their partial results together to form a final result or answer 402).
As per claim 14: STORM discloses a computer-implemented method of performing a multi-party computation (MPC) protocol ([0047] A secure multi-party computation (MPC) may allow operation of a function on two datasets without the owner or custodian of each dataset obtaining any proprietary information. MPC is based on a number of cryptographic tools and strategies such as secret sharing),
wherein a group comprises a coordinator ([0097] An aggregator 478. FIG. 4D illustrates an approach 470 to applying SMPC. New input 472 is provided to an aggregator 478) and a plurality of parties, and wherein the method is performed by a first one of the parties and comprises:
obtaining a multi-party circuit representation of a computable function converted from a circuit representation of the function ([0067] FIG. 4B illustrates 408 the interaction between algorithm provider 410 and a data provider 414. The algorithm provider 410 selects parameters and builds a context associated with the processing of data using the algorithm. The context 416 is communicated to the data provider 414. The algorithm provider synthesizes the algorithm into logic gates 418 and “hides” the algorithm 420 using the principles disclosed herein, such as in FIG. 7. The result of the hiding process includes gates 422 and a general or generic circuit 424. The algorithm provider 410 sends the general circuit 426 to the data provider 414. Next, the algorithm provider generates shares 428 as disclosed herein and the data provider 414 generates shares from the inputs 436. The algorithm provider 410 sends shares 434 to the data provider 414 and the data provider 414 sends shares 442 to the algorithm provider 410. The algorithm provider 410 performs a process using the algorithm provider's gates shares 430 and the data provider's gates shares 432. The data provider 414 performs a process using the algorithm provider's input shares 438 and the data provider's input shares 440. After the generation of the algorithm provider shares from the data provider's inputs, the two parties are ready to start the MPC protocol. See FIG. 6 and associated discussion herein. [0068] The “hiding” occurs as the algorithm provider replaces each gate in the anonymized circuit with a generic circuit and generates the function “general circuit” 424 and stores the information of each gate in a separate table. By replacing each gate with the generic circuit, the circuit is hidden and most of the information of the circuit is transferred to a gates table. What is left is just the location of each gate as is shown in FIG. 7. The hidden circuit 702 in FIG. 7 illustrates an example of what is public and as it could confirm only the location of each gate. The general structure of the circuit is revealed. The security of this approach depends on the security of the MPC method which is used on top of the circuit hiding method as the information regarding each gate is separately stored in the gates table. The computed output of each gate by the other party could not be used to reverse engineer the circuit because the actual output of each gate is not available to the other party and only some part of it is available. The circuit provider only allows the possibility of computing the output of those gates),
wherein the function is to be evaluated based on one or more first inputs to generate one or more outputs ([0097] The aggregator 478 receives encrypted data from a data provider 474 which uses the data provider's public key KPd 476. The aggregator also receives an encrypted function f from an algorithm provider 482 which is encrypted under the algorithm provider's public key Kpa 480. Both encryptions are homomorphic encryption which enables the user to compute the encrypted results using only encrypted data, without requiring decryption. The aggregator 478 computes the result 484 using homomorphic encryption. The result can include a function result based on the new-input and the data. At the end of the computation, the data provider 474 and the algorithm provider 482 compute the decryption algorithm using SMPC. The SMPC 486 can be used to decrypt the result, the KSd and the KSa),
wherein each first input is to be either specified or randomly generated ([0097] In the SMPC protocol, the algorithm provider input is its corresponding secret key KSa and the data provider input is its secret key KSd. [0118] For example, the first party (e.g., User A, such as the data provider computing device 102 or the algorithm provider computing device 104), can generate an N by 3 matrix, Beav.sub.A. Beav.sub.A can include first and second columns that are randomly generated, and the third column can contain an operation of the algorithm subset. Beav.sub.A can also be generated randomly in part or perhaps be generated based on a non-random process), and
wherein the circuit representation comprises a plurality of arithmetic gates representing respective functions for operating on one or more of the first inputs and/or or one or more second inputs ([0099] A user or aggregator 510 may receive the encrypted data 504 from the first data provider 502 and the second encrypted data 510 from the second data provider 508 and may receive the encrypted algorithm 520 from the first algorithm provider 518 and the second encrypted algorithm 526 from the second algorithm provider 524. The user or aggregator 510 may execute the algorithm on the data and determine a result that may include a proprietary business process 516. As noted above, the user or aggregator 510 may be one of the first data provider 502 or the second data provider 508, the first algorithm provider 518, the second algorithm provider 5524, or may be a different entity. The aggregator 510 may also be a combination or a hybrid of a respective data provider and/or a respective algorithm provider. The aggregator 510 can also in one aspect receive unencrypted data or algorithms and perform the encryption operation within the aggregator 510),
wherein a second input is a respective output of a respective gate ([0100] FIG. 6 illustrates an example circuit 600 associated with an algorithm, in accordance with various embodiments. In some secure multiparty computation (MPC), circuit garbling has been used for secure communication between two participants such as a garbler and an evaluator. The embodiments discussed herein are different from circuit garbling. Multiparty computation (MPC) is able to execute two operations including multiplication (AND) and addition (XOR). As a result, in order to perform complex operations and functions, the operations and functions are to be broken down into AND and XOR operations. The example circuit 600 shown in FIG. 6 includes only XOR, AND, and NOT gates. NOT gates are replaced with XOR gates with a bit of “1” that allows the circuit to represent only AND and XOR gates), and
a plurality of directed edges, wherein each directed edge represents a first or second input being supplied to a respective arithmetic gate to be operated on by that respective arithmetic gate ([0102] An algorithm may be encoded into a logical or emulated circuit by converting the algorithm into a specific circuit 600 such as one shown in FIG. 6. The circuit may include a correct number and arrangement of gates such that it represents the algorithm. Each of the specific gates in the circuit may be replaced with generic gate slots. Each of the generic gate slots may be populated with a correct bit pattern to cause the gate to function as it should. The gate information may then be copied into a matrix), and
wherein the multi-party circuit is generated by:
replacing each specified first input with a respective first splitting gate (SSG) ([0067] The algorithm provider 410 sends the general circuit 426 to the data provider 414. Next, the algorithm provider generates shares 428 as disclosed herein and the data provider 414 generates shares from the inputs 436. The algorithm provider 410 sends shares 434 to the data provider 414 and the data provider 414 sends shares 442 to the algorithm provider 410. The algorithm provider 410 performs a process using the algorithm provider's gates shares 430 and the data provider's gates shares 432. The data provider 414 performs a process using the algorithm provider's input shares 438 and the data provider's input shares 440. After the generation of the algorithm provider shares from the data provider's inputs, the two parties are ready to start the MPC protocol),
wherein each respective SSG represents a protocol performed by the coordinator to distribute a respective share of a respective secret to each respective party ([0143] Then, each data owner performs a cryptographic private write utilizing a anonymizing cryptographic primitive, such as for example the recent Function Secret Sharing (FSS), or similar mechanisms and alternatives. FSS, and similar, enables each data owner to privately write a message to a particular database row without any aggregation party learning which row was written to. The FSS private write is protected as long as there are more than two data owners participating and as long as there is at least one aggregation party which does not collude); and
replacing each randomly generated first input with a respective second splitting gate (JSG) ([0126] At step 946, the data provider can provide the split data sets to the two parties and, using the corresponding Beaver sets, run the split algorithms on the split data sets. In some embodiments, the data can be split into a random share of the full dataset so as to further hide sensitive information (e.g., patterns that expose demographic information, sex, age, race, or other biometrics that expose patient identity),
wherein each respective JSG gate represents a protocol performed by each party to collaboratively generate a respective share of a respective secret ([0118] For example, the first party (e.g., User A, such as the data provider computing device 102 or the algorithm provider computing device 104), can generate an N by 3 matrix, Beav.sub.A. Beav.sub.A can include first and second columns that are randomly generated, and the third column can contain an operation of the algorithm subset. Beav.sub.A can also be generated randomly in part or perhaps be generated based on a non-random process. In this example embodiment, the third column contains the multiplications of the first two columns. The first two columns of the Beaver sets can be randomly generated to mask the actual data (EKG shares), and the third column can be computed depending on the application (multiplication, division, exponential, . . . ). It is preferred that the first two columns be randomly generated to be able to hide the actual data);
evaluating the function by executing the multi-party circuit representation based on a first respective share of each respective secret to generate a first respective share of each output ([0105] FIG. 8 illustrates 800 the hidden circuit 309 divided into a first split or first subset 310 and a second split or second subset 312. The hidden representation 309 may be divided into two splits or subsets. The first subset of the algorithm 310 may be evaluated by a first party, a first computing device or a first virtual compute environment and the second subset of the algorithm 312 may be evaluated by a second party, a second computing device or a second virtual compute environment. Generally speaking, these different splits of the Boolean logic gate set 309 are separate into different compute spots, locations, portions, physical components or virtual component such that their separate processing can be performed in a separated manner); and
sending the first respective share of each output to the coordinator, wherein the coordinator is configured to obtain a respective share of each output ([0144] A flatten layer can be used to rearrange the shares. A maximum pooling layer 1104B can be used. There are two example approach for maximum pooling. First, if input.sub.A>input.sub.B, the output of the function f=max(input.sub.A, input.sub.B) is A. In such a case, the system can find the maximum of two inputs using SMPC with two communications. In another example, if input.sub.A>input.sub.B, then the output of the function f=max(input.sub.A, input.sub.B) can be input.sub.A. In this case, the system needs to create the comparison circuit and use ((1−(A>B))*B+(A>B)*A to output the greater value. The advantages of this method over the first method is that no party learns anything about the location of the maximum value on the other hand it is expense in terms of computations and time),
STORM does not explicitly disclose wherein the respective secret is associated with a respective threshold, and a threshold number of parties, the threshold number corresponding to a circuit threshold, and to generate each output of the function, wherein each output is generated based on at least the threshold number of the respective output shares of that output. Joy, in analogous art however, discloses wherein the respective secret is associated with a respective threshold and a threshold number of parties, the threshold number corresponding to a circuit threshold, and to generate each output of the function, wherein each output is generated based on at least the threshold number of the respective output shares of that output ([0137] The figure shows multiple party cryptographic (MPC) setting as the centralized mechanism. In at least one embodiment, each aggregator splits their values into shares using Shamir's Secret Sharing. The shares are distributed across all aggregators so that each aggregator has one share from every other aggregator 212. The share was submitted to each aggregator by the data owner. The aggregators sum these inputs to create an encrypted aggregate 214. The threshold check is calculated by subtracting the threshold from the encrypted aggregate 216. The threshold check is converted to bit representation in order for the aggregators to reveal the most significant bit (MSB) to detect if the aggregate is above or below the threshold 222. If the MSB is set to “0” (greater than the threshold), the servers release the aggregate. Otherwise, no values are released 228, 230. [0139] Data owners contribute their responses 212 (x.sub.1 to x.sub.i) to the aggregators 214, assuming a pre-sampling step. The aggregators compute MPC which only reveals the aggregate output 215 if it is greater than a publicly known threshold value 216. Aggregate output 215 and threshold 216 are received by a threshold circuit 218 which outputs a result value 220, received by a binarization process 222, herein exemplified as extracting only the most-significant bit (MSB) of result 220 in generating binary output 224 to an inverted input of gate 226 along with the Aggregate signal 226, and outputs this binary control signal to reveal 228 controlling whether output 230 reveals the aggregate result. [0144-0145]). Therefore, it would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify the claimed limitations of the aggregator disclosed by STORM to include wherein the respective secret is associated with a respective threshold and a threshold number of parties, the threshold number corresponding to a circuit threshold, and to generate each output of the function, wherein each output is generated based on at least the threshold number of the respective output shares of that output. This modification would have been obvious because a person having ordinary skill in the art would have been motivated by the desire to provide capability to perform real-time streaming privacy-preserving personal data collection that scales to hundreds of millions of users while maintaining utility, including accuracy in respect to ground truth, and protecting data owners privacy as suggested by Joy ([0008]).
As per claims 16-18: Claims 16-18 directed to have substantially similar corresponding limitations of claims 6-7 and 10-11 respectively and therefore claims 16-18 are rejected with the same rationale given above to reject claims 6-7 and 10-11.
As per claim 23: Claim 23 is directed to a computer program product embodied on non-transitory computer-readable storage media and configured so as, when run on one or more processors of a coordinator of a group comprising the coordinator and a plurality of parties, the one or more processors perform a method for performing a multi-party computation (MPC) protocol, having corresponding limitations of claim 1 and therefore claim 23 is rejected with the same rationale given above to reject claim 1.
As per claim 24: Claim 24 is directed to a computer program embodied on computer-readable storage and configured so as, when run on one or more processors of a first party of a plurality of parties of a group comprising a coordinator and the plurality of parties, to perform a method of performing a multi-party computation (MPC) protocol, having corresponding limitations of claim 1 and therefore claim 24 is rejected with the same rationale given above to reject claim 1.
Claim 11 is rejected under 35 U.S.C. 103 as being unpatentable over STORM et al. (US 20200220851 A1 --- hereinafter—" STORM”) in view of Joy US 20170353855 A1 in further view of GROTH US 20240154820 A1.
As per claim 11: STORM in vie w of Joy does not explicitly disclose wherein the computable function is an ECSDA signature-generating function. GROTH, in analogous art however, discloses wherein the computable function is an ECSDA signature-generating function ([0079-0083] Elliptic Curve Digital Signature Algorithm (ECDSA): The ECDSA is a variant of the Digital Signature Algorithm (DSA) and uses elliptic curve cryptography. More particularly, ECDSA signatures operate over an elliptic curve or a subgroup of an elliptic curve.Threshold Elliptic Curve Digital Signature Algorithm: A threshold signature algorithm based on elliptic curve cryptography, wherein any t secret key shares enable the execution of a valid ECDSA signature under the threshold ECDSA-public key/verification key, while t−1 shares do not suffice to execute a valid ECDSA-signature. Such a threshold Elliptic Curve Digital Signature Algorithm (ECDSA) is e.g. described in the document by Jean-Philippe Aumasson, Adrian Hamelink, Omer Shlomovits: A Survey of ECDSA Threshold Signing. IACR Cryptol. ePrint Arch. 2020: 1390 (2020)). Therefore, it would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify the claimed limitations of the computable function disclosed by STORM in vie w of Joy is to include an ECSDA signature-generating function. This modification would have been obvious because a person having ordinary skill in the art would have been motivated by the desire to provide a distributed network replicated computing clusters which provides enhanced functionalities for performing secure multi-party computations as suggested by GROTH ([0012]).
Allowable Subject Matter
Claims 4-6, 8 and 15 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims. The following is a statement of reasons for the indication of allowable subject matter: After consideration of the applicant’s correspondence filed on September 24, 2024, through examination of the application, claims, and prior art search,
the pertinent prior arts of record, either taken alone or in combination neither anticipates nor renders obvious the claimed subject matter of the following claims when taken together with their respective independent claims including intervening claims
As per claim 4: One or more share multiplication (SecM) gates, where each respective SecM gate represents a function configured to multiply two respective shares input to the SecM gate and output a result of the multiplication to a respective next gate in the multi-party circuit representation, and wherein said converting comprises:
inserting a respective share-redistribution gate (SRG) between each respective SecM gate and the respective next gate, wherein each respective SRG represents a protocol performed by each party to collaboratively generate a new respective share of a respective shared value input to the respective SRG, wherein the new respective share is associated with the circuit threshold, whereas the respective shared value is associated with a higher threshold.
As per claim 5: One or more share multiplication (SecM) gates, where each respective SecM gate represents a function configured to multiply two respective shares input to the SecM gate and output a result of the multiplication to a respective next gate in the multi-party circuit representation, and wherein said converting comprises:
if the respective share that is input to a respective SecM gate has a threshold higher than the threshold of the respective secrets, inserting a respective share-redistribution gate (SRG) between the respective SecM gate and the respective previous gate, wherein each respective SRG represents a protocol performed by each party to collaboratively generate a new respective share of a respective shared value input to the respective SRG, wherein the new respective share is associated with the circuit threshold, whereas the respective shared value is associated with a higher threshold; and
inserting a respective SRG before each respective RG gate for each output to be generated.
As per claim 6: One or more inverse gates representing a function configured to output a respective inverse of a respective non-scalar input, and wherein said converting comprises: replacing each of said one or more inverse gates with a respective share inverse gate (IVG), wherein each respective IVG represents a protocol performed by each party to collaboratively generate a respective inverse share of a respective share that is input to the IVG; wherein the multi-party circuit has a maximum threshold 2t.sub.C≤t.sub.max<N, where N is the number of parties in the group and t.sub.C is the threshold of the respective secrets, wherein the circuit representation comprises one or more share multiplication (SecM) gates, where each respective SecM gate represents a function configured to multiply two respective shares input to the SecM gate and output a result of the multiplication to a respective next gate in the multi-party circuit representation, and wherein said converting comprises:
if the respective share that is input to the respective IVG has a threshold t>t.sub.max−t.sub.C, inserting a respective share-redistribution gate (SRG) between each respective IVG gate and the respective previous gate, wherein each respective SRG represents a protocol performed by each party to collaboratively generate a new respective share of a respective shared value input to the respective SRG, wherein the new respective share is associated with the circuit threshold, whereas the respective shared value is associated with a higher threshold;
if an expected output threshold of the respective share output by a respective SecM gate is higher than t.sub.max, inserting an SRG between one or both of the respective shares that are input to respective the SecM gate and the respective SecM gate; and
inserting a respective SRG before each respective RG gate for each output to be generated.
As per claim 8: Wherein the protocol performed by each party to collaboratively generate a respective share of the respective secret comprises a joint random secret sharing scheme (JRSS) or a joint verifiable random secret sharing scheme (JVRSS).
As per claim 15. Wherein the protocol performed by each party to collaboratively generate a respective share of the respective secret comprises a joint random secret sharing scheme (JRSS) or a joint verifiable secret sharing scheme (JVRSS), and wherein the method comprises using JRSS or JVRSS to generate a first respective share of one or more of the respective secrets.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Yanai et al US 20220069979 A1 discloses servers executing a secure multi-party computation (MPC) protocol that can receive shares of inputs to the MPC protocol from a plurality of clients, where each input is private to each client and where each share is generated from its corresponding input using a threshold secret sharing scheme. Each server can then verify whether the shares of the plurality of inputs are valid/invalid and, for each invalid share, determine whether a client that submitted the invalid share or a server that holds the invalid share is corrupted. If the client that submitted the invalid share is corrupted, each server can ignore the input of that corrupted client during a computation phase of the MPC protocol.
Mohassel et al US 20200259651 A1 describes a collection of cryptographic devices that encrypt or decrypt a message, provided that a threshold number of those devices participate in the encryption process. One cryptographic device generates a commitment message and transmit it to the other selected devices. Those devices may each perform a partial computation using the commitment message, and transmit the partial computations back to the encrypting or decrypting device. The encrypting or decrypting device may use those partial computations to produce a cryptographic key, which may then be used to encrypt or decrypt the message.A1
Eldefrawy et al. US 20220121521 A1 describes a multiparty computing system that includes at least a first compute node and a second compute node, each of the first compute node and the second compute node each configured to execute a multiparty computation. The first compute node is configured to perform first operations of the multiparty computation over a share of first secret data and a share of second secret data; detect a checkpoint event; and, in response to detection of the checkpoint event, save a state of the multiparty computation on the first compute node to a checkpoint storage. In response to detection of a resume event, the first compute node executes a resume protocol with the second compute node, where the resume protocol includes exchanging messages with the second compute node, and determining, based on the messages, an operation in the multiparty computation to be the starting point to resume the multiparty computation.
Contact Information
Any inquiry concerning this communication or earlier communications from the examiner should be directed to TECHANE GERGISO whose telephone number is (571)272-3784. The examiner can normally be reached 9:30am to 6:30pm.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, LINGLAN EDWARDS can be reached at (571) 270-5440. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/TECHANE GERGISO/ Primary Examiner, Art Unit 2408