DETAILED ACTION
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 .
Response to Amendment
The preliminary amendment filed 12/05/2024 has been entered. Claims 24-25 have been amended. Claims 13-23 have been canceled. Claims 26-31 have been added. Claim 1-12 and 24-31 are pending and are examined herein.
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-2, 9-12, 24-26 and 29 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.
As per claims 1-2, 9-12, 24-26 and 29, those claims recite the variable m, n, and p without any definite meaning, does not specify what value the m, n and p represent, how they determined, whether they fixed or variable. As a result, the scope of the claim is unclear because the value of m, n and p could be any arbitrary quantity, leaving the boundaries of the claimed invention uncertain. Accordingly, the recitation of m, n and p renders the claims indefinite.
Claim 24 recites the limitation "the batch" and “the first participant” in lines 5 and 8, respectively. There are insufficient antecedent basis for these limitations in the claim.
Claim 25 recites the limitation "the batch" and “the first participant” in lines 5 and 8, respectively. There are insufficient antecedent basis for these limitations in the claim.
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-2, 7-12, 24-26 and 29 are rejected under 35 U.S.C. 103 as being unpatentable over CN 114647857 (Chen et al.) in view of US 2020/0084049 (Lindell et al.).
Regarding Claim 1, Chen teaches a secure multi-party computation method, used to perform at least one type of target processing on a batch of data, wherein each piece of data in the batch of data is distributed to n participants in a form of shard (a data processing method applied to a first party among a plurality of parties performing multiparty security calculations, …comprising: receiving encrypted data sent by a second party of the plurality of parties, and determining local data for operation with the encrypted data…Splitting the encrypted data into a plurality of first sub-data and splitting the local data into a plurality of second sub-data…performing homomorphic addition operation and/or semi-homomorphic multiplication operation in parallel according to the plurality of first sub-data and the plurality of second sub-data through a plurality of threads, and obtaining an encrypted operation result…The multiple participants can realize the cooperative computation of the business data by utilizing the safe multi-party computation under the condition of not disclosing the respective business data [Page 5, Paras. 5-9]), and the method is performed by any first participant in the n participants (method applied to a first participant of a plurality of participants performing multi-party secure computation [Page 5, Para. 6]), and comprises:
dividing local shards of each piece of data in the batch of data into m groups, and correspondingly allocating the m groups to m groups of threads (Determining the number of threads contained in each thread block; Determining the number of threads required by the encrypted data according to the bit number of the encrypted data and the processable bit number of each thread; Determining the number of required thread blocks according to the number of threads required by the encrypted data and the number of threads contained in each thread block; …allocating a thread for each first sub-data, wherein the thread is used for calculating homomorphic addition results of the first sub-data and the second sub-data with corresponding bits [Page 5, para. 12 to page 6, para. 4]. This discloses partitioning the shard data into a number of group (thread blocks) and assigning each group of data correspondingly to a group of threads); and
performing, on the m groups in parallel by using the m groups of thread, each type of target processing jointly performed with another participant (“calling the corresponding number of thread blocks according to the number of the required thread blocks, and performing homomorphic addition operation and/or semi-homomorphic multiplication operation on the plurality of first sub-data and second sub-data in parallel through a plurality of threads in the called thread blocks” ([Page 6, para. 1]. “…the encrypted data sent by the second party is received by the first party, the local data used for operating the encrypted data is determined, the encrypted data is split into the first sub-data and the second sub-data, homomorphic addition operation and/or semi-homomorphic multiplication operation are carried out in parallel according to the first sub-data and the second sub-data through the threads, and the encrypted operation result is obtained and output” [Page 8, para 3]).
Chen does not explicitly teach, however, Lindell teaches wherein the first participant serves as different secure multi-party computation (MPC) roles in at least some of the m groups of threads, and the different MPC roles perform different target computation and/or target transmission for a type of target processing (Lindell discloses a multi-party computation (MPC) system in which participants are organized into groups, and different groups are assigned different roles within the same overall secure computing process. Lindell teaches “D.sub.3 may be configured to define different roles in the MPC decryption. For example, D.sub.3 may define two node-groups of end-user nodes and define the threshold requirements. …D.sub.3 may define the number of end-user nodes from each node-group, required for the threshold decryption, which approve the transaction. D.sub.3 may also define other end-user nodes with different authorization roles” [¶ 0042]. Lindell further teaches “The generation of the PSK shares may follow the different roles in the threshold decryption. For example, D.sub.3 may generate different key shares with different end-user nodes in different node-groups, in accordance with the different roles of the threshold decryption.” [¶ 0044]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Chen’s thread-group-parallelized MPC method by assigning different MPC roles to different thread group groups of the first participant, as taught by Lindell, because it would increase throughput and resource utilization, a predictable benefit of parallelizing heterogeneous roles across independent thread groups. “The combination of familiar elements according to known methods is likely to be obvious when it does no more than yield predictable results.”, KSR Int’l Co. v. Teleflex Inc. 550 U.S. 398, 416 (2007)).
Regarding Claim 2, Chen teaches the method according to claim 1, wherein performing, on them groups in parallel by using the m groups of threads, each type of the target processing jointly performed with another participant (see, claim 1 rejection above) comprises: jointly performing with another participant (The multiple participants can realize the cooperative computation of the business data by utilizing the safe multi-party computation under the condition of not disclosing the respective business data [Page 5, Para. 3]) by using an ith group of threads and based on a local shard …that is allocated to the ith group of threads (splitting the encrypted data into a plurality of first sub-data … allocating a thread for each first sub-data [Page 5-6]), first computation … to implement a type of target processing (performing homomorphic addition operation and/or semi-homomorphic multiplication operation in parallel according to the first sub-data …through a plurality of threads to obtain an encrypted operation result [Page 5, Para. 10]) first transmission …to another participant (sending the encrypted data to be calculated to other participants…[Page 6, Last para]), wherein the first computation and the first transmission correspond to a first role of the first participant (if the first participant is a data operator in the multiple participants, receiving encrypted data sent by a data provider in the multiple participants; … the first participant is a data provider, splitting data to be calculated, … performing encryption operation… sending the encrypted data to be calculated to other participants… if the first party is a party with a private key, acquiring an encrypted operation result from other parties,… [Page 6, last 4 paras.]).
Chen teaches transmission between participants but not thread-group-to-thread-group, however, Chen does not explicitly teach, Lindell teaches …first transmission with another group of threads to which another shard of the first group is allocated in the another participant… (The multiparty signing server …send a first request to the coordinator to decrypt the encrypted signature. The coordinator …send to the second subset of end-user nodes a second request… receive back from the second subset of end-user nodes the generated shares …combine the shares….[¶ 0004]. end-user node 210 may conduct an MPC process with end-user-key-protection-server 235 to generate the share of the decryption [¶ 0033]. Thus, Lindell teaches shard-level transmission between MPC nodes and performing computation and transmission jointly).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to incorporate Lindell’s teachings of cross-participant exchange of computation shares into Chen’s teaching of parallel shard processing because such incorporation would enable distributed MPC operations at the granularity of thread-allocated shards, thereby improving scalability and enabling secure joint processing across participants.
Regarding Claim 7, Chen teaches the method according to claim 1, wherein dividing the local shards of each piece of data in the batch of data into m groups comprises: equally dividing the local shards of each piece of data in the batch of data into them groups (“splitting the local data into a plurality of second sub-data” [Page 5, Para. 9]. “splitting the encrypted data into a plurality of first sub-data, and splitting the local data into a plurality of second sub-data. …the first sub data and the second sub data have the same bit number…” [Page 10, Para. 5]. Chen teaches equal division, it states that the local/encrypted data is 16 bits, each thread process 8 bits, and the data is split into 2 sub-data, each have 8 bits: “the encrypted data/local data is 1100110001010101, and has 16 bits, each thread can process 8 bits of data, so that the data can be split into 2 sub-data, and each sub-data has 8 bits…” [Page 10, Para. 7]).
Regarding Claim 8, Chen teaches the method according to claim 1, wherein the n participants hold a same quantity of shards for a same piece of data in the batch of data (“…receive encrypted data sent by a second participant in the multiple participants, and determine local data used for performing an operation with the encrypted data;” [Page 18, Para 6]. “…determining the number of threads contained in each thread block; determining the number of threads required by the encrypted data according to the number of bits of the encrypted data and the number of processable bits of each thread;” [Page 5, Para. 10]. “splitting the encrypted data into a plurality of first sub-data, and splitting the local data into a plurality of second sub-data. …the first sub data and the second sub data have the same bit number…” [Page 10, Para. 5]).
Regarding Claim 9, Chen teaches The method according to claim 1, wherein the batch of data are unevenly distributed to the n participants, and an MPC role of each of the n participants is determined based on data currently held by the participant (“The participator B has sample data, the participator A can train the model according to the encrypted sample data of the participator B, and the participator C has a public key and a private key and can decrypt the data. … And then, the participant B encrypts the sample data or the sample characteristics of the participant B according to the public key and transmits the encrypted sample data or the encrypted sample characteristics to the participant A. The participator A encrypts data, such as target variables and the like, of the participator A according to the public key, and trains the model according to the encrypted target variables and the encrypted sample data … the number, functions and the like of the participants can be adjusted” [Page 9, Para. 1-3]. “plurality of participants may include a data provider, a data operator, and a collaborator …any participant can be used as a data provider, a data operator and a collaborator”. [Page 12, last 4 paras.]. “if the first participant is a data operator in the multiple participants, receiving encrypted data sent by a data provider in the multiple participants; …if the first participant is a data provider, splitting the data to be calculated, which is stored locally, into a plurality of third sub-data; …if the first party is a party with a private key, acquiring an encrypted operation result from other parties, and splitting the acquired encrypted operation result into a plurality of fourth sub-data;” [Page 19, last 3 paras to Page 20, first 4 paras.]).
Regarding Claim 10, Chen teaches The method according to claim 1, wherein the m groups comprise a first group, and a type of target processing on the first group is performed by p participants comprising the first participant in the n participants, wherein p<n ((“The participator B has sample data, the participator A can train the model according to the encrypted sample data of the participator B, and the participator C has a public key and a private key and can decrypt the data. … And then, the participant B encrypts the sample data or the sample characteristics of the participant B according to the public key and transmits the encrypted sample data or the encrypted sample characteristics to the participant A. The participator A encrypts data, such as target variables and the like, of the participator A according to the public key, and trains the model according to the encrypted target variables and the encrypted sample data … the number, functions and the like of the participants can be adjusted” [Page 9, Para. 1-3]. “if the first participant is a data operator in the multiple participants, receiving encrypted data sent by a data provider in the multiple participants; …if the first participant is a data provider, splitting the data to be calculated, which is stored locally, into a plurality of third sub-data; …if the first party is a party with a private key, acquiring an encrypted operation result from other parties, and splitting the acquired encrypted operation result into a plurality of fourth sub-data;” [Page 19, last 3 paras to Page 20, first 4 paras.]. Chen teaches a multi-participants secure computation system indifferent participants perform different operation on data, thus, Chen teaches that a particular processing operation can be performed by a subset of the participant rather than by every participant in the system, i.e., p<n).
Regarding Claim 11, Chen teaches the method according to claim 1, wherein them groups of threads comprise different quantities of threads (The number of bits of the split first sub-data and the split second sub-data may be related to the processing capability of the thread of the first party. …the first sub data and the second sub data have the same bit number, and are less than or equal to the processable bit number of each thread [Page 10, Para. 5]).
Regarding Claim 12, Chen teaches the method according to claim 1, wherein then participants run different quantities of threads (“…the number, functions and the like of the participants can be adjusted,…” [Page 9, Para. 7]. “The number of bits of the split first sub-data and the split second sub-data may be related to the processing capability of the thread of the first party…” [Page 10, Para. 5]).
Regarding Claim 24, the claim limitations are identical and/or equivalent in scope to claim 1, therefore, Claim 24 is rejected under the same rationale as claims 1. Chen also teaches a non-transitory computer-readable storage medium, wherein the non-transitory computer-readable storage medium stores a computer program, which when executed by a processor causes the processor to:… (Page 21), as required in Claim 1.
Regarding Claim 25, the claim limitations are identical and/or equivalent in scope to claim 1, therefore, Claim 25 is rejected under the same rationale as claims 1. Chen also teaches a computing device, comprising a memory and a processor, wherein the memory stores executable code, and when executing the executable code, the computing device is caused to:… (Page 21), as required in Claim 1.
Claims 26 and 29 are identical and/or equivalent in scope to claim 2, therefore, Claims 26 and 29 are rejected under the same rationale as claim 2.
Claims 3-6, 27-28 and 30-31are rejected under 35 U.S.C. 103 as being unpatentable over Chen in view of Lindell, and further in view of US 2021/0209247 (Mohassel et al.).
Regarding Claim 3, Chen in view of Lindell do not teach, however, Mohassel teaches the method according to claim 2, wherein the type of target processing is truncation processing (The training computers may desire to compute the truncation of a product of y multiplied by z. … At step S602, the first training computer can truncate the first data share x′.sub.1 by dividing the first share x′.sub.1 by 2.sup.d (i.e., x.sub.1=x′.sub.1/2.sup.d), resulting in a truncated first share x.sub.1 [¶ 0162]), and the different MPC roles comprise a computing party and a receiving party (the first training computer can truncate the first data share x′.sub.1 by dividing the first share x′.sub.1 by 2.sup.d … the first training computer can perform the truncation of x′.sub.1 locally. [¶ 0164]. … the second training computer can transmit the truncated second share x.sub.2 to the first training computer. After receiving the truncated second share x.sub.2, the first training computer can hold the truncated first share x.sub.1 and the truncated second share x.sub.2. [¶ 0168]. After truncating the first share, the first training computer can transmit the truncated first share to the third training computer. The third training computer can receive the truncated first share from the first training computer and can then hold the truncated first share and the truncated third share [¶ 0177]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to apply Mohassel’s truncation operation into Chen’s parallel, multithreaded MPC computation in order to obtain the known benefits of truncation - namely, reducing the size of intermediate/results values and limiting memory requirements, while retaining Chen’s parallel processing benefit of reducing computation time.
Regarding Claim 4, Chen in view of Lindell do not teach, however, Mohassel teaches the method according to claim 3, wherein the first group comprises first data, and the first role is the computing party (the three training computers can store secret-shared data items from the plurality of data clients [¶ 0172]. The training computer performing truncation acts as a computing party); the first computation comprises: generating a first random number within an agreed value range (the second training computer and the third training computer can generate a random value [¶ 0174, Fig. 7, S706]; dividing the first random number by 2 raised to the power oft to obtain a first quotient (after generating the random binary share [r’]B, the three training computers locally truncate [r’]B by removing the bottom d shares to obtain [r]B. The first training computer can truncate r′1 and r′2 to obtain r1 and r2, respectively. The second training computer can truncate r′2 and r′3 to obtain r2 and r3, respectively. The third training computer can truncate r′3 and r′1 to obtain r3 and r1, respectively. …[r]B can be the k−d most significant shares of [r’]B (i.e., r=r′/2d) [¶ 0198]; and determining a first shard of a truncation processing result of the first data based on at least the first quotient, wherein t is a quantity of truncated bits (The first training computer can then truncate (x′−r′)/2d. The second training computer and the third training computer can also compute (x′−r′)/2d in similar manners [¶ 0190]); and the first transmission comprises: sending a difference between a first shard of the first data and the first random number to a second participant serving as the receiving party, so that the second participant determines a second shard of the truncation processing result based on at least the difference, the quantity of truncated bits, and a second shard of the first data that is held by the second participant (the second training computer can transmit the truncated second share to the first training computer. …the first training computer can transmit the truncated first share to the third training computer. [¶¶ 0176-0177]. The truncation can include generating a random value [¶ 0009]. training computers can jointly compute the data item x′ minus the random value r′. …Each of the three training computers can compute a respective result share minus the random arithmetic share resulting in intermediate shares of an intermediate value [¶ 0186]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to apply Mohassel’s truncation operation into Chen’s parallel, multithreaded MPC computation in order to obtain the known benefits of truncation - namely, reducing the size of intermediate/results values and limiting memory requirements, while retaining Chen’s parallel processing benefit of reducing computation time.
Regarding Claim 5, Chen in view of Lindell do not teach, however, Mohassel teaches the method according to claim 3, wherein the first group comprises first data, and the first role is the receiving party (the three training computers can store secret-shared data items from the plurality of data clients [¶ 0172]); the first transmission comprises: receiving, from a second participant serving as the computing party, a difference, calculated by the second participant, between a second shard of the first data that is held by the second participant and a first random number (the second training computer can transmit the truncated second share to the first training computer…truncate the first share of the data item, …transmit the truncated first share to the third training computer. [Fig. 7, S710, S712, ¶¶ 0176-0177]. after computing the first result, …can reveal the first result [Fig. 9B, S910, ¶ 0224] ); and the first computation comprises: summing the difference and a first shard of the first data, and dividing a summation result by 2 raised to the power oft to obtain a second quotient; and determining a first shard of a truncation processing result based on the second quotient (after determining the truncated first result, the three training computers can compute a truncated data item by the truncated random arithmetic share plus the truncated first result [Fig. 9B, S914, ¶ 0226]. after generating the random binary share [r′]B, the three training computers locally truncate [r′]B by removing the bottom d shares to obtain [r]B. …[r]B can be the k−d most significant shares of [r′]B (i.e., r=r′/2d) [Fig. 8, S804, ¶ 0198]. Output [x]A := [r]A +(x′-r′)/2d [Fig. 8, S814]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to apply Mohassel’s truncation operation into Chen’s parallel, multithreaded MPC computation because it would have enabled secure fixed-point arithmetic and scaling operation on shared data, yielding predictable improvements in accuracy and efficiency.
Regarding Claim 6, Chen in view of Lindell do not teach, however, Mohassel teaches the method according to claim 1, wherein the at least one type of target processing comprises some of oblivious transfer (OT), logical quantity to digital quantity conversion, digital quantity to logical quantity conversion, multiplication of a digital quantity and a logical quantity, encrypted-state selection, or out-of-order processing (performing a three-party oblivious transfer among a sender computer, a receiver computer, and a helper computer [¶ 0015]. converting from an arithmetic secret-shared data item to a binary secret-shared data item [¶ 0268]. Compute a sum of the binary secret-shared data item, the binary secret-shared second random value, and the binary secret-shared third random value…[Fig. 16, S1608]. “Determine sum bits and carry bits using full adder circuit in parallel” [Fig. 13, S1306]).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to apply Mohassel’s oblivious transfer (OT) protocol operation into Chen’s parallel, multithreaded MPC computation. Integrating OT into Chen’s shard-based MPC system would have been an obvious and predictable enhancement because OT is a standard MPC primitive used to implement secure branching, encrypted-state selection, and mixed logical/digital operation which would allow supporting secure conditional operation and selection-based MPC flows.
Claims 27 and 30 are identical and/or equivalent in scope to claim 3, therefore, Claims 27 and 30 are rejected under the same rationale as claim 3.
Claims 28 and 31 are identical and/or equivalent in scope to claim 4, therefore, Claims 28 and 31 are rejected under the same rationale as claim 4.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MOHAMMAD YOUSUF A MIAN whose telephone number is (571)272-9206. The examiner can normally be reached Monday-Friday 9am-5: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, ARIO ETIENNE can be reached at 571-272-4001. 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.
/MOHAMMAD YOUSUF A. MIAN/ Examiner, Art Unit 2457
/ARIO ETIENNE/ Supervisory Patent Examiner, Art Unit 2457
Prosecution Insights