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 .
Claims 1-20 are pending for examination.
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.
Claim 14 is 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.
Since Claim 14 depends on Claim 8, the meaning of “AHE” is unclear. This issue could be overcome by spelling-out the acronym the first time it appears in each (independent) 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-3, 6-10, 15-17 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over NPL: “DHSA: Efficient Double Homomorphic Secure Aggregation for Cross-Silo Federated learning” (Liu et al.) in view of US 20210143987 (Xu et al.).
Regarding Claim 1, Liu teaches a method, comprising: receiving, by a server, from a client of a plurality of clients, an encrypted client input represented by a client input encrypted with a client symmetric key ([Page 2821, 2nd para] Liu teaches a secure aggregation scheme, named doubly homomorphic secure aggregation (DHSA). DHSA comprises two protocols: the homomorphic model aggregation (HMA) protocol and the masking seed agreement (MSA) protocol. [Sec. 4.2.1, Pages 2831-2833 and Fig. 3] Liu teaches a plurality of clients coordinated by server A, wherein each client u encrypts its client input xu with a client-specific masking seed ku [i.e., client symmetric key] and uploads the encrypted client input yu to the server: “Then, they upload masked model update yu = xu + G(ku) to the server.”);
receiving, from the client, an encrypted client symmetric key represented by the client symmetric key… ([Sec. 4.2.2; Pages 2833-2835], Liu teaches each client encrypts its client-specific masking seed ku using a common public key cpk and transmits the resulting ciphertext ctu to the server: “each client encrypts the masking seeds with the common public key before sending it to the server.” [Fig. 4] Encryption and Aggregation : ctu = MKBFV.Enc(cpk, ku));
combining the encrypted client input with a combination of encrypted client inputs received from at least a subset of the plurality of clients ([Sec. 4.2.1, Page 2831] Liu teaches the server receives the masked client inputs yu and combines them: “The server aggregates the uploaded data of online clients”. [Fig. 3, server step 1] “Collect yu of all clients, and do the aggregation to return
PNG
media_image1.png
44
190
media_image1.png
Greyscale
mod P”);
combining the encrypted client symmetric key with a combination of encrypted client symmetric keys received from at least the subset of the plurality of clients ([Sec. 4.2.2, Page 2835] Liu teaches combining the ciphertexts encrypting the client’s masking seeds: “the server aggregates all the received ciphertexts to return the encrypted sum over all masking seeds which is ct = Σ ctu”);
transmitting, … the combination of encrypted client symmetric keys ([Sec. 4.2.2, page 2835] Liu teaches the combined ciphertext is subject to a public-key-switching and decryption procedure involving the clients possessing the applicable secret-key material: ReEnc(ct)=Enc(pkr , Dec(sk,ct)) which can be decrypted with the re-encryption secret key skr . Finally, related clients utilize skr to decrypt the received ciphertexts ctr and obtain the demasking seeds);
receiving, … a decrypted aggregated key produced by decrypting, using a secret key corresponding to the public key, the combination of encrypted client symmetric keys ([Sec. 4.2.2, Page 2832]] Liu teaches decrypting the combination of encrypted client masking seeds to obtain aggregate demasking key: “the demasking seeds which are the sum of the masking seeds of corresponding clients” [Also see Fig. 4 Final decryption steps]; and
decrypting, using the decrypted aggregated key, the combination of encrypted client inputs to obtain an aggregated representation of a plurality of client inputs ([Fig. 3, Sec. 5.1], Liu teaches decrypting the combined masked client inputs y0 using decrypted aggregate key k0: x0 = y0 – G(k0), thereby obtaining: x0 ≈ Ʃ xu ).
Liu does not explicitly teach employing a separate Key server as that decryptor and does not teach “public key received by the client from a decryptor”, however, Xu teaches a separate Key Server 105 responsible for generating the decryption applicable to a selected aggregation [Fig. 7, block 730-750]. Key Server 105 generates encryption keys and provided them to the participants: “the Key Server 105 generates and transmits a unique individual key to the selected participant.” [¶ 0083].
It would have been obvious to one of the ordinary skill in the art before the effective filing date of the claimed invention to modify Liu’s DHSA method according to particular two-layer homomorphic cryptographic relationship, while Xu teaches central key management and delivery of an aggregate-specific decryption key to the Aggregator. The modification would predictably reduce processing and communication required at the client by implementing a separate key server.
Regarding Claim 2, Liu teaches the method of claim 1, wherein the encrypted client input is produced by encrypting the client input by a key-additive homomorphic encryption (KAHE) scheme with the client symmetric key ([Abstract], Liu proposes a Doubly Homomorphic Secure Aggregation (DHSA) scheme for cross-silo FL, which utilizes multi-key homomorphic encryption (MKHE) and seed homomorphic pseudorandom generator (SHPRG) as cryptographic primitives. [Sec. 3.2], Multi-key Homomorphic Encryption (MKHE) is a cryptosystem in which each party generates its own keys, and the specific operation can be performed on ciphertexts encrypted by different parties. The decryption of the obtained new ciphertexts is achieved by combining the respective secret keys associated with these ciphertexts).
Regarding Claim 3, Liu teaches the method of claim 1, wherein the encrypted client symmetric key is produced by encrypting the client symmetric key by an additive homomorphic encryption (AHE) scheme with the public key (Liu teaches encrypting each client masking key ku using the common public key cpk: ctu = MKBFV.Enc(cpk, ku). Liu further teaches homomorphically adding those ciphertexts: ct = Ʃ ctu to obtain an encrypted representation of k0 = Ʃ ku. Liu explain thar “homomorphic multiplication is not involved in the proposed protocol, only the linear version of the two types of MK-BFV schemes” [Sec. 3.2] Thus, Liu uses the linear/additive functionality of MK-BFV to encrypt and additively combine the client symmetric keys. Accordingly, Liu’s MK-BFV implementation constitutes an AHE scheme for purpose of the claimed operation).
Regarding Claim 6, Liu teaches The method of claim 1, wherein the decryptor is implemented by a subset of the plurality of clients ([Page 2829] for FL scenarios, all clients perform distributed decryption under the coordination of the server. [Page 2839] DHSA enables the final decryption done by clients).
Regarding Claim 7, Liu does not explicitly teach, however, Xu teaches the method of claim 1, wherein the decryptor is implemented by one or more dedicated computing devices ([¶ 0030], the Key Server 105 handles the provisioning and distribution of keys, as well as the validation of the aggregation vector. [¶ 0087], the Key Server 105 generates a corresponding private key for decrypting the set of participant responses, based on the aggregation vector. …the Key Server 105 then returns this secret key to the aggregator).
It would have been obvious to one of the ordinary skill in the art before the effective filing date of the claimed invention to incorporate Xu’s dedicated Key Server into Liu to offload key-management and decryption functions from the clients and to condition release of the aggregate decryption key on satisfaction of Xu’s aggregated-vector validation criteria, thereby improving security and operational reliability.
Regarding Claim 13, Liu teaches the system of claim 8, …comprising: receiving, … a public key; generating the client symmetric key by a Key-Additive Homomorphic Encryption (KAHE) scheme ([Page 2833] Each client generates a pair of secret and public keys individually, and the common public key is computed for encryption based on the individual public keys. Here, the same public parameter is taken as the input of the key-generation algorithm so that the multi-key homomorphic arithmetic is supported. [Page 2830] “ku is the SHPRG seed generated by data owner u”. The client specific seed ku corresponds to the client symmetric key used in Liu’s see-homomorphic masking scheme. Lui further teaches the key-additive relationship Ʃi G(ki) ≈ G (Ʃi ki). Accordingly, Liu teaches generating client symmetric key use in a KAHE scheme);
producing the encrypted client input by encrypting the client input by the KAHE scheme using the client symmetric key ([Page 2830], data owner u encrypts its local modal update by yu = xu + G(ku). Here, xu corresponds to client input, ku corresponds to the client symmetric key, G(ku) is the pseudorandom mask produced from that key, and yu corresponds to the encrypted client input. Since Liu teaches Ʃi G(ki) ≈ G (Ʃi ki), Liu’s masking encryption has the claimed key-additive homomorphic property); and producing the encrypted client symmetric key by encrypting the client symmetric key by an Additive Homomorphic Encryption (AHE) scheme using the public key ([Page 2834] “…each client encrypts the masking seeds with the common public key before sending it to the server. Then the server aggregates all the received ciphertexts to return the encrypted sum over all masking seeds,”. Since the masking seed ku corresponds to the client symmetric key, Liu teaches encrypting that key using the common public key. Kiu further teaches [Page 2829] “invoke the Compact MK-BFV scheme …The aggregation of ciphertexts is done in accordance with the conventional ciphertexts additive operation”. Liu’s MK-BFV scheme therefore corresponds to the claimed AHE scheme).
However, Liu does not explicitly teach, Xu teaches a second memory; and a second processing device coupled to the memory, the second processing device to perform operations of the client ([Fig. 6 0076] the Participant 120 includes a Processor 610, Memory 615, Storage 620, a Network Interface 625, and one or more I/O Interfaces 630. …the Processor 610 retrieves and executes programming instructions stored in Memory 615), the operations comprising: receiving, from the decryptor, a public key… ([0054], the Key Server 105 generates a unique and individual key for each participant in the federated learning system. … distributes the unique public keys to the indicated participants, such that each participant receives its own key. Thus, Xu teaches receiving, at the client/participant, a public key from a dedicated key server/decryptor).
It would have been obvious to one of the ordinary skill in the art before the effective filing date of the claimed invention by incorporating Xu’s conventional processor-memory architecture would have predictably provided the computing components needed to execute Liu’s client-side encryption operations and incorporating Xu’s Key server would also have centralized public key provisioning and permitted validation of aggregation requests before releasing decryption information, thereby improving key-management efficiency and preventing unauthorized recovery of individual client contributions.
Regarding Claim 14, Liu teaches the system of claim 8, farther comprising …generating an AHE key pair comprising the secret key and the public key ([Page 2833], “Each client generates a pair of secret and public keys individually, and the common public key is computed for encryption based on the individual public keys. … one leader client generates the re-encryption key pair…”. The generated public and secret keys are used with Liu’s MK-BFV homomorphic encryption scheme, which supports additive ciphertext operations); receiving, from the server, the combination of encrypted client symmetric keys ([], “each client encrypts the masking seeds with the common public key before sending to the server. Then, the server aggregates all the received ciphertexts to return the encrypted sum over all masking seeds”. Thus, the encrypted masking seeds correspond to the encrypted client symmetric keys, and the encrypted sum returned by the server corresponds to the claimed combination); producing the decrypted key by decrypting, using the secret key, the combination of encrypted client symmetric keys ([Page 2834, 1st para] Liu teaches that the encrypted sum over the client masking seeds is encrypted according to “ReEnc(ct)=Enc(pkr , Dec(sk,ct))” and that “Finally, related clients utilize skr to decrypt the received ciphertexts ctr and obtain the demasking seeds.”. Thus, Liu teaches using the secret key skr to decrypt the encrypted combination and obtain the aggregated or demasking key).
Liu does not explicitly teach, however, Xu teaches a second memory; and a second processing device coupled to the memory, the second processing device to perform operations of the decryptor ([Fig. 5, ¶ 0071], the Key Server 105 includes a Processor 510, Memory 515, Storage 520, a Network Interface 525, and one or more I/O Interfaces 530. Thus, Xu teaches the Key Server performs cryptographic key-management and decryption-key operation); Xu further teaches transmitting the decrypted key to the server ([¶ 0075], Validation Component 550 generates and transmits a corresponding secret key to the Aggregator).
It would have been obvious to one of the ordinary skill in the art before the effective filing date of the claimed invention to apply Xu’s arrangements to Liu’s encrypted aggregated masking seed, because it would have predictably centralized the computationally intensive key-generation and decryption operations, reducing processing and coordination among the clients and enabled the server to remove the aggregate mask only after the aggregation request satisfied Xu’s security and quorum criteria.
Regarding Claim 8, the claim limitations are identical and/or equivalent in scope to claim 1, therefore, Claim 8 is rejected under the same rationale as claim 1. Since, Liu further discloses the server can perform aggregation directly on ciphertexts [Page 2821], therefore, Liu inherently discloses the claimed “A system comprising: a memory; and a processing device coupled to the memory, the processing device to perform operations” as claimed in claim 8.
Regarding Claims 9 and 10, the claim limitations are identical and/or equivalent in scope to claims 2 and 3, therefore, Claims 9 and 10 are rejected under the same rationale as claims 2 and 3.
Regarding Claim 15, the claim limitations are identical and/or equivalent in scope to claim 1, therefore, Claim 15 is rejected under the same rationale as claim 1. Since, Liu further discloses the server can perform aggregation directly on ciphertexts [Page 2821], therefore, Liu inherently discloses the claimed “A non-transitory computer-readable storage medium comprising executable instructions that, when executed by a processing device of a server, cause the processing device to perform operations” as claimed in claim 15.
Regarding Claims 16, 17 and 20, the claim limitations are identical and/or equivalent in scope to claims 2, 3 and 6, respectively, therefore, Claims 16, 17 and 20 are rejected under the same rationale as claims 2, 3 and 6.
Claims 4, 11 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over Liu in view of Xu, and further in view of US 2022/0188446 (Vinayagamurthy et al.).
Regarding Claim 4, Liu in view of Xu do not explicitly teach, however, Vinayagamurthy teaches the method of claim 1, further comprising: generating an aggregation proof demonstrating that each encrypted client input is included at most once in the combination of encrypted client inputs; and sending the aggregation proof to a verifier for validation ([¶ 0044], the service provider can generate proofs regarding …an accuracy of the responses provided to the client. [¶¶ 0053-0054], the knowledge proof has public input (e.g., the query, the hash and signature for each of the data owners) …the service provider provides proof that the function of the aggregate response is a function of the individual response … The service provider also provides proof that for each response included in the aggregated response … response matches the hash corresponding to each individual data owner … This proof can then be verified by any verification entity using a verification routine. …Any verifier can run the verification routine to verify the proof ).
It would have been obvious to one of the ordinary skill in the art before the effective filing date of the claimed invention to incorporate Vinayagamurthy’s proof-generation technique to require each authenticated response commitment to appear no more than once in the aggregation computation into Liu and Xu. Because such incorporation would have been a predictable verification rule that preserves the accuracy of aggregation and allowing a client to verify that the service provider performed the aggregation correctly.
Regarding Claims 11 and 18, the claim limitations are identical and/or equivalent in scope to claim 4, therefore, Claims 11 and 18 are rejected under the same rationale as claim 4.
Claims 5, 12 and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Liu in view of Xu, and further in view of US 2022/0067176 (Charles).
Regarding Claim 5, Liu in view of Xu do not explicitly teach, however, Charles teaches the method of claim 1, wherein receiving the decrypted aggregated key further comprises: receiving a respective portion of the decrypted aggregated key from each decryptor of at least threshold number of decryptors of a distributed set of decryptors; and combining the portions of the decrypted aggregated key to obtain the decrypted aggregated key ([¶ 0051], Clients can request partial decryption shares for a given ciphertext from a threshold number of replicas (i.e., nodes with valid partial decryption keys (e.g., key shares)). Each replica may evaluate whether the requesting client is entitled to access the encrypted message …the replica will respond with a partial decryption share for the ciphertext. …Once the client receives a threshold number of correct shares, these correct shares can be combined to recover the original message. [¶ 0069], the API 604 may receive partial decryption shares 702, 704, and 706 from nodes 708, 710, and 712 respectively, …only a threshold number of valid partial decryption shares are required. [¶ 0049], combining a threshold number of valid decryption shares to recover decrypted plaintexts. [¶ 0105], Once the API has received at least 3 valid shares, it may reconstruct the document encryption key).
It would have been obvious to one of the ordinary skill in the art before the effective filing date of the claimed invention to incorporate Charles’s distributed threshold-decryption technique with the combined teachings of Liu and Xu, because such incorporation would have predictably reduced reliance on a single decryptor and prevented any single node from processing sufficient key material to decrypt the aggregated key.
Regarding Claims 12 and 19, the claim limitations are identical and/or equivalent in scope to claim 5, therefore, Claims 12 and 19 are rejected under the same rationale as claim 5.
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
/MOUSTAFA M MEKY/Primary Examiner, Art Unit 2457
Prosecution Insights