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 . This office action is in response to the amendment filed on 03/09/2026. Claims 1-20 are currently pending in the filing of 03/09/2026, claims 1-20 were pending in the previous filing of 1/30/2024, with no claims having been added or cancelled since the previous filing.
Response to Applicant’s Amendments / Arguments Regarding 35 U.S.C. § 103
The applicant’s remarks, on pages 6-12 of the response / amendment, the applicant argues the features which allegedly distinguish over the previously cited references cited in the 35 U.S.C. § 103 rejections.
The examiner has included the applicant’s arguments below, single spaced with the applicant’s underlining. The examiner’s emphasis to the applicant’s arguments, which are single spaced, are included in bold, and the examiner’s responses to the applicant’s arguments are included below, in double space format. The substance of the applicant’s arguments start on the bottom half of page 6 to page 11, which are included below:
A server for performing an operation on a homomorphic ciphertext, the server
being configured to:
receive a first homomorphic ciphertext, a public key, and a first hierarchical
Galois key set from a client device;
in response to a request for generating a second hierarchical Galois key set for
performing a rotation operation on the first homomorphic ciphertext, generate the second hierarchical Galois key set, based on the public key and the first hierarchical
Galois key set; and
in case that a decomposition operation for a first Galois key included in the
second hierarchical Galois key set overlaps with a decomposition operation for a second Galois key, first perform the decomposition operation for the first Galois key, and then substitute the decomposition operation for the second Galois key with a result of the decomposition operation for the first Galois key.
(emphasis added).
As set forth above, claim 1 relates to a server for performing an operation on a
homomorphic ciphertext. The server is configured to receive a first homomorphic ciphertext,
page 6 above
a public key, and a first hierarchical Galois key set from a client device. In response to a request for generating a second hierarchical Galois key set for performing a rotation operation on the first homomorphic ciphertext, the server generate the second hierarchical Galois key set, based on the public key and the first hierarchical Galois key set. In case that a decomposition operation for a first Galois key included in the second hierarchical Galois key set overlaps with a decomposition operation for a second Galois key, the server first perform the decomposition operation for the first Galois key, and then substitute the decomposition operation for the second Galois key with a result of the decomposition operation for the first Galois key. It is respectfully submitted that Park and Bossuat do not disclose the above emphasized claim limitations.
For example, although the Office Action acknowledges that Park fails to disclose the emphasized features "in case that a decomposition operation for a first Galois key included in the second hierarchical Galois key set overlaps with a decomposition operation for a second Galois key, first perform the decomposition operation for the first Galois key, and then substitute the decomposition operation for the second Galois key with a result of the decomposition operation for the first Galois key", the Office Action contends that the Abstract, and pages 587-588, 591, 594, 597-598 of Bossuat discloses these features. (Office Action, p. 4-5). Applicant respectfully traverses this rejection.
Bossuat relates to improvements in the key-switching procedure applied to ciphertext rotations. Bossuat, p. 587-588. Specifically, Bossuat discloses pre-computing the decomposition of the ciphertext component and reusing the decomposition for rotations of the same ciphertext when performing rotations of the ciphertext. Bossuat, p. 597; Sec. 4; p. 598; Sec. 4.2 ("when several rotations have to be applied on the same ciphertext, [a]qai can be
Page 7 above
pre-computed and re-used for each subsequent rotation... This technique proposed by Halevi et al., called hoisting").
That is, the decomposition in Bossuat is not applied to key generation, rather, the decomposition operation is operated on ciphertext for a key-switching procedure (e.g., optimized hoisting-rotations), as shown in Algorithm 4 of Bossuat. See Bossuat, p. 597. Here, the inputs of Algorithm 4 are the ciphertext, e.g., ct, and a set of rotation keys and the output is a list of the rotation of ct. Bossuat, p. 599.
The applicant above, as emphasized, argues that “decomposition in Bossuat is not applied to key generation rather, the decomposition operation is operated on ciphertext for a key-switching procedure”, as emphasized above. Examiner asserts that cited pages 591 and 594 teach the key switching decomposition operation being performed, where one of skill in the art understands that decomposition uses slot rotations / key shifting and key switching. Cited page 591 teaches SwitchKey and SwitchKeyGen and rotation keys / rotk (e.g., levels / shifting) regarding decomposition, which work together in hoisted techniques discussed further below. Examiner asserts that applicant argues the switch keys without addressing the rotation keys of page 591 of Basson. Further, the hoisted rotation technique and double hoisted rotation technique, taught starting on cited pages 597-598 of Basson, further teach hoisted rotation techniques, as discussed below.
Further, cited page 594 “The Baby-Step Giant step (BSGS) Algorithm” teaches multiplications being performed using decomposition based on trees, similar to applicant’s printed publication at [0062-63] describing figs. 4a, 4b, 5, and 6. Additionally, cited pages 597-598 teach hoisted rotation techniques, where hoisted Galois shifts are applied first, and then key shifting is applied, and also teaches re-usage of key in subsequent rotations on cited page 598. One of skill in the art understands that “overlap”, as recited in claim 1, determines key re-usage. Also, cited page 597-598 are directed to the application to matrix vector products (e.g., matrix vector multiplication) using hoisted rotation and double hoisted rotation where different levels are utilized and the use slot rotations and rotation keys. See also, page 605 for additional teaching of double hoisting to minimize complexity using different levels. Examiner asserts this is similar to fig. 3, [0009], and [0047] of applicant’s printed publication teaching levels and how different levels are related to shift / rotation.
Next, the BSGS or algorithm 5 also fails to disclose key generation. Here, the BSGS algorithm is directed to an efficient multiplication applied to the ciphertext. Bossuat, p. 594, 599. That is, the hoisting rotations (algorithm 4) and BSGS (algorithm 5) algorithms do not describe key generation.
Lastly, the key generation algorithms (e.g., SwitchKeyGen and PubKeyGen) in Sec.
2.1; page 591 of Bossuat is silent regarding hoisting or Galois key generation. Here, although the operations of the encryption scheme discuss key generation algorithms, these key generation (SwitchKeyGen and PubKeyGen) algorithms, however, do not apply hoisting and the generated key are not Galois keys. Rather, Bossuat only discloses the generation of public encryption key, relinearization key, rotation keys, and conjugation key. In other words, Bossuat fails to disclose the SwitchKeyGen or the PubKeyGen substituting a decomposition operation of a Galois key with a result of a decomposition operation for a different Galois key. Thus, Bossuat fails to disclose at least the emphasized features "in case that a decomposition operation for a first Galois key included in the second hierarchical Galois key set overlaps with a decomposition operation for a second Galois key, first perform the decomposition operation for the first Galois key, and then substitute the decomposition
Page 8 above
operation for the second Galois key with a result of the decomposition operation for the first Galois key" recited in claim 1.
Applicant asserts that Basson fails to teach hoisting or Galois key generation. Examiner disagrees. First, Bossuat, cited page 587, Abstract which teaches homomorphic encryption schemes using CKKS, which inherently utilize Galois keys that are generated in the process. Additionally, Park teaches Galois keys. Second, as discussed above the cited portions of Bossuat teach all of Switching keys, Rotation / Shifting keys, and rotation / shifting, as related to homomorphic encryption using Galois keys with matrix multiplication. Third, starting on cited page 597 of Bossuat, hoisting and double hoisting are taught by Bossuat, and hoisting and double hoisting are utilized in Galois key techniques to increase efficiencies in computation, as discussed in the CKKS technique of Bossuat.
Even if the references were combined, the combination would lack the emphasized features "in case that a decomposition operation for a first Galois key included in the second hierarchical Galois key set overlaps with a decomposition operation for a second Galois key, first perform the decomposition operation for the first Galois key, and then substitute the decomposition operation for the second Galois key with a result of the decomposition operation for the first Galois key".
Therefore, in view of above, Applicants respectfully submit that claim 1 is patentable over the cited references.
Similar arguments can be applied to independent claims 9 and 15 similar to those recited for claim 1. Thus, for the reasons similar to those discussed above, independent claims 9 and 15 are patentable over the cited references. Given that the rest of the claims depend from one of the above independent claims, at least for the reasons similar to those discussed above, it is respectfully submitted that the rest of the claims are patentable over the cited references.
Claims 5, 8, 12, 14, 18, and 20 are rejected under 35 U.S.C. 103 as being
unpatentable over Park, in view of Bossuat, in view of US 20230325529 to Sav et al. (hereinafter Sav), in view of NPL - "Cryptanalysis of a Protocol for Efficient Sorting on SHE Encrypted Data" to Shyam Murthy et al. 18 November 2019 pages 278-294 found at https://link.springer.eom/chapter/10.1007/978-3-030-35199-1 14 (hereinafter Murthy).
Page 9 above
In summary, the examiner asserts that Bossuat page 591 does teach switching keys and rotation keys that are used in Galois key techniques. Also, on cited pages 597-598, teaches application to matrix vector products (e.g., matrix vector multiplication) using hoisted rotation and double hoisting, and also uses slot rotations and rotation keys. See also, page 605 teaching double hoisting to minimize complexity where different levels are taught.
Thus, Bossuat does teach, “in case that a decomposition operation for a first Galois key included in the second hierarchical Galois key set overlaps with a decomposition operation for a second Galois key, first perform the decomposition operation for the first Galois key, and then substitute the decomposition operation for the second Galois key with a result of the decomposition operation for the first Galois key,” as recited in claim 1. Therefore, the applicant’s remarks are not persuasive, and the rejection is maintained.
Claims 6, 13, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Park, in view of Bossuat, in view of Sav, in view of Murthy, in view of US 20180262327 to Jain et al. (hereinafter Jain).
Claims 5-6, 8, 12-14, and 18-20 depend on one of the above independent claims. It is submitted Sav, Murthy, and Jain also fail to disclose or suggest the limitations set forth above.
Sav relates to privacy-preserving distributed training of neural network models. Sav, abstract. Murthy relates to cryptanalysis of SHE encrypted data. Murthy, abstract. Jain relates to minimization of side channel leakage for controller area network (CAN). Jain, abstract. Sav, Murthy, and Jain, however, do not disclose the above emphasized features "in case that a decomposition operation for a first Galois key included in the second hierarchical Galois key set overlaps with a decomposition operation for a second Galois key, first perform the decomposition operation for the first Galois key, and then substitute the decomposition operation for the second Galois key with a result of the decomposition operation for the first Galois key" in claim 1. According, Sav, Murthy, and Jain fail to cure the deficiencies of Park and Bossuat. Therefore, for reasons set forth above, it is respectfully submitted claims 1-20 are also patentable over the above cited references.
In view of the foregoing, Applicant respectfully submits the present application is in condition for allowance. If the Examiner believes a telephone conference would expedite or assist in the allowance of the present application, the Examiner is invited to call/email the undersigned attorney.
Page 10 above
Examiner notes that the applicant’s remarks on the remaining page 10 are directed to Jain’s alleged failure to teach the above discussed features of claim 1. However, as discussed above, the examiner relies upon Bossuat to teach these feature, and Jain was not cited as teaching these feature.
Applicant’s arguments have been considered, however, the applicant’s remarks are not persuasive, and the rejection is maintained.
Claim Rejections - 35 USC § 103
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-4, 7, 9-11, and 15-17 are rejected under 35 U.S.C. 103 as being unpatentable over NPL – “Homomorphic Encryption for Multiple Users With Less Communications” to Jeongeun Park (Oct 2021) (hereinafter Park), in view of NPL – “Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-sparse Keys” to Jean-Philippe Bossuat et al. from “Advances in Cryptology EUROCRYPT 2021” pages 587-617 June 16, 2021 (hereinafter Bossuat).
Regarding claim 1, Park teaches,
A server for performing an operation on a homomorphic ciphertext, the server being configured to: (last sentence page 2 & first sentence page 3, teaching server only runs key switching algorithm without requiring any interactions among users.)
receive a first homomorphic ciphertext, (page 3, Col. 1, teaches messages m encrypted as ciphertexts ct.) a public key, (Abstract teaches distributing public keys. Page, 3, col 1, teaches the server collects the information, and that the public key is common and known) and a first hierarchical Galois key set from a client device; (page 7, col. 1 teaches “in our case, bootstrapping key (also called Galois key) is generated by running CMKHE”, and also teaches “… a server can save the master bootstrapping key by adding all bootstrapping keys of users.” page, 3, col 1, teaches the server collects the information, and that the public key is common and known. )
in response to a request for generating a second hierarchical Galois key set for performing a rotation operation on the first homomorphic ciphertext, generate the second hierarchical Galois key set, based on the public key and the first hierarchical Galois key set; and (Page 7, col 1, teaches “… running key switching algorithm CMKHE : KeySwitch taking bootstrapping key on input”, which is called CMKHE. ENCSKPage 7, col. 1, also teaches “Then, in our case, bootstrapping key (also called Galois key) is generated by running CMKHE”. Page 6, col. 1, teaches) ([0008] of the applicant’s printed publication describes generating the second hierarchical Galois key set may include key switching, repeatedly, where the key switching may include decomposition.)
in case that a decomposition operation for a first Galois key included in the second hierarchical Galois key set (page 5, col. 2 & and Table 2, teaches using a gadget decomposition to control error during the evaluation state.) (One of skill in the art will understand that decomposition is used to manage noise within linearization of homomorphic encryption.)
Park fails to explicitly teach all of the details of decomposition operations related to key switching between a first & second Galois key,
However, Bossuat teaches,
in case that a decomposition operation for a first Galois key included in the second hierarchical Galois key set overlaps with a decomposition operation for a second Galois key, first perform the decomposition operation for the first Galois key, and then substitute the decomposition operation for the second Galois key with a result of the decomposition operation for the first Galois key. (page 587 / 1st page, Abstract, teaches homomorphic encryption including hoisted key switching and using CKKS, which uses Galois keys. See also, page 591, teaching PublicKeyGen, including the public key, and performing SwitchKeyGen and rotation keys. See also page, 597, “4 Key-Switch and Improved Matrix-Vector Product.”, teaching the optimized key switching using the hoisted and double hoisted rotation techniques which makes matrix multiplication using re-encryption from the keys more efficient by re-using keys, which the examiner asserts corresponds to the above limitation, as taught by the applicant’s printed publication at [0022], discussed immediately below. page 594, “3.1 The Baby-Step Giant Step BSGS Algorithm”, which teaches polynomial evaluation using decomposition in a tree like manner to minimize the number of non-scalar multiplications, to optimize / minimize depth of computation by pre-computing, also discussed on page 588 leveled encryption, where each multiplication is a level, also known as bootstrapping. bottom of page 591, teaches SwitchKey using decomposition. page 598, "4.2 Improved Hoisted-Rotations", teaches when several rotations have to be applied to the same ciphertext, the keys / key-switches may be re-used on subsequent rotations. Similar to applicant's figs. 4a&b & [0060-62] teaching substituted key switching. page 598, "4.2 Improved Hoisted-Rotations", teaches when several rotations have to be applied to the same ciphertext, the keys / key-switches are pre-computed and may be re-used (“substitute”) on subsequent rotations, as discussed in applicant's figs. 4b & [0060-62], discussed below. See also page 605 for further teachings of double hoisting and levels.) (The examiner interprets the above limitation as corresponding to hoisted homomorphic encryption / Galois key changes because the applicant’s printed publication at [0022] states: “In an embodiment, overlapping of a decomposition operation is removed using a hoisted Galois key generation technique and thus a key-switching operation which substitutes a value of a result of a preceding decomposition operation is performed.” Regarding substitution, see fig. 4b and [0060-62] of the applicant’s printed publication teaching “substituted key switching”.)
Before the effective filing date of the invention, it would have been obvious to one of ordinary skill in the art to combine the teachings of Park, which teaches homomorphic encryption and performing operations on encrypted data using bootstrapping / Galois keys while performing key switching without extensive communication between server and users (Abstract & page 7, col. 1), with Bossuat, which also teaches homographic encryption and performing operations on encrypted data including multiplication (Abstract & page 597), and additionally teaches the use of hoisted key rotations (page 597) for increasing computational efficiency in performing multiplication operations on homomorphically encrypted data with increased efficiency. One of ordinary skill in the art would have been motivated to perform such an addition to provide Park with the explicit capability to perform hoisted key rotations on homomorphically encrypted data, as taught by Bossuat, to increase computational efficiency while performing homomorphic operations (multiplication) on encrypted data which increases data security by not reveling the data from different parties and the computational server to increase security.
Regarding claim 2, Park and Bossuat teach,
The server of claim 1,
wherein the generating of the second hierarchical Galois key set comprises repeatedly performing a key-switching operation on each of all Galois keys included in the second hierarchical Galois key set by using the public key and the first hierarchical Galois key set, so as to generate all the Galois keys, and (Park, page 2, col. 2, teaches switching between keys, which is understood to be multiple operations, and further teaches performing the key switching without having to have the users have to compute the multiple keys for the multiple homomorphic operations. Park, [0008-9] teaches multiple operations, leveled and un-leveled, discussed further below.) (Bossuat, bottom page 591, teaches SwitchKey using decomposition.)
the key-switching operation comprises at least one decomposition operation. (Park, page 5, col. 2 & table 2 teach decomposition, but fail to explicitly teach decomposition while key switching.) (However, Bossuat, bottom page 591, teaches SwitchKey using decomposition. See also, Bossuat, page 594, “3.1 The Baby-Step Giant Step BSGS Algorithm”, teaches polynomial evaluation using decomposition in a tree like manner to minimize the number of non-scalar multiplications, to optimize / minimize depth of computation by pre-computing. The pre-computing is then used in page 598, "4.2 Improved Hoisted-Rotations", teaches when several rotations have to be applied to the same ciphertext, the keys / key-switches may be re-used on subsequent rotations.)
Regarding claim 3, Park and Bossuat teach,
The server of claim 2,
wherein the second hierarchical Galois key set corresponds to a lower level of the first hierarchical Galois key set, and (Bossuat, page 588, teaches leveled encryption where depth is the level of each multiplication operation, where evaluation of multiplication / depth circuits is performed. page 589, teaches an improved bootstrapping method of baby-step giant-step (BSGS), involving modified key rotation. See also page 594, “3.1 The Baby-Step Giant Step BSGS Algorithm”, which teaches polynomial evaluation using decomposition in a tree like manner to minimize the number of non-scalar multiplications, to optimize / minimize depth of computation by pre-computing. Thus, Bossuat teaches ordering of the operations such as multiplication, which also effects order of key generation.) (applicant’s printed publication at [0047] describes levels of Galois keys as corresponding to movement or shifts of data, used in multiplication, where the different levels are used with ordering to reduce the number of levels / depth before pre-generating the keys.)
each of the Galois keys included in the second hierarchical Galois key set is generated by a combination of a plurality of elements included in the first hierarchical Galois key set which is a higher level. (Bossuat, pages 600-601 “Improved BSGS Algorithm” teaching different levels for the key rotations. Also, pages 602-603, teaches “ reset the ciphertext modulus to a higher level in order to enable further homomorphic multiplications.” Also, page 588, generally teaches leveled encryption.)
Regarding claim 4, Park and Bossuat teach,
The server of claim 2, wherein the server is configured to:
determine, before generating the second hierarchical Galois key set, a generation order of the Galois keys included in the second hierarchical Galois key set, based on the number of key-switching operations required to generate each of the Galois keys; and (Bossuat, page 593-594 “3 Homomorphic Polynomial Evaluation”, teaches optimizing the depth of the circuit using polynomials, which includes ordering the computation, which includes key generation order. Depths at same level can be scaled.)
sequentially generate each of the Galois keys of the second hierarchical Galois key set according to the generation order. (Bossuat, Abstract teaches optimizing the homomorphic polynomial operation discussed in detail on pages 593-594 above regarding Chapter 3, and then optimizing key switches, discussed in chapter 4 (discussed next), where key switches use the optimized polynomial operations of chapter 3. Pages 597-599 “4 Key-Switch and Improved Matrix-Vector Product”, teaches the generation of key switches.)
Regarding claim 7, Park and Bossuat teach,
The server of claim 4, wherein a generation order of the first Galois key has priority over a generation order of the second Galois key. (Park, page 7, col 1, teaches “… running key switching algorithm CMKHE : KeySwitch taking bootstrapping key on input”. Thus, the bootstrapping key is generated first.) (Bossuat, page 588, teaches leveled encryption where depth is the level of each multiplication operation, where evaluation of multiplication / depth circuits is performed. page 589, teaches an improved bootstrapping method of baby-step giant-step (BSGS), involving modified key rotation. See also page 594, “3.1 The Baby-Step Giant Step BSGS Algorithm”, which teaches polynomial evaluation using decomposition in a tree like manner to minimize the number of non-scalar multiplications, to optimize / minimize depth of computation by pre-computing. Thus, Bossuat teaches ordering of the operations such as multiplication, which also effects order of key generation.) (applicant’s printed publication at [0047] describes levels of Galois keys as corresponding to movement or shifts of data, used in multiplication, where the different levels are used with ordering to reduce the number of levels / depth before pre-generating the keys.) (applicant’s printed publication at [0047] describes levels of Galois keys as corresponding to movement or shifts of data, used in multiplication, where the different levels are used with ordering to reduce the number of levels / depth before pre-generating the keys.)
Regarding claim 9, Park and Bossuat teach,
A method for generating a hierarchical Galois key set for a homomorphic encryption rotation operation, the method comprising:
determining a generation order of Galois keys included in the hierarchical Galois key set; and (See rejection of claim 4)
generating each of the Galois keys included in the hierarchical Galois key set according to the generation order, (See rejection of claim 4)
wherein, in the generating of each of the Galois keys included in the hierarchical Galois key set, a decomposition operation for a second Galois key, which overlaps with a decomposition operation included in a generation process of a first Galois key previously generated, is substituted with a result of the decomposition operation for the first Galois key. (see rejection of claim 1)
Claim 9 is rejected using the same basis of arguments used to reject claim 1 and 4 above.
Regarding claim 10, Park and Bossuat teach,
The method of claim 9, wherein the hierarchical Galois key set is generated by a combination of a plurality of elements included in a hierarchical Galois key corresponding to a higher level of the hierarchical Galois key set. (see rejection of claim 3)
Claim 10 is rejected using the same basis of arguments used to reject claim 3 above.
Regarding claim 11, Park and Bossuat teach,
The method of claim 10, wherein the hierarchical Galois key set is generated by repeatedly performing a key-switching operation (Bossuat, page 588, teaches different levels of encryption, where each multiplication operation is a level. Abstract, teaches key switching including double hoisting. Reduction of repeated key switching is the teaching of Bossuat.) by using the elements included in the hierarchical Galois key corresponding to the higher level, and (see rejection of claim 3)
the key-switching operation comprises at least one decomposition operation. (see rejection of claim 2)
Claim 11 is rejected using the same basis of arguments used to reject claims 2 & 3 above.
Regarding claim 15, Park, Bossuat, and Crockett teach,
A non-transitory computer-readable storage medium storing a computer program comprising at least one instruction, which when executed by a processor, causes the processor to perform a method for generating a hierarchical Galois key set for a homomorphic encryption rotation operation, the method comprising:
determining a generation order of Galois keys included in the hierarchical Galois key set; and (See rejection of claim 4)
generating each of the Galois keys included in the hierarchical Galois key set according to the generation order, (See rejection of claim 4)
wherein, in the generating of each of the Galois keys included in the hierarchical Galois key set, a decomposition operation for a second Galois key, which overlaps with a decomposition operation included in a generation process of a first Galois key previously generated, is substituted with a result of the decomposition operation for the first Galois key. (see rejection of claim 1)
Claim 15 is rejected using the same basis of arguments used to reject claims 1 & 4 above.
Regarding claim 16, Park and Bossuat teach,
The computer-readable storage medium of claim 15, wherein the hierarchical Galois key set is generated by a combination of a plurality of elements included in a hierarchical Galois key corresponding to a higher level of the hierarchical Galois key set. (see rejection of claim 3)
Claim 16 is rejected using the same basis of arguments used to reject claim 3 above.
Regarding claim 17, Park and Bossuat teach,
The computer-readable storage medium of claim 16, wherein the hierarchical Galois key set is generated by repeatedly performing a key-switching operation (Bossuat, page 588, teaches different levels of encryption, where each multiplication operation is a level. Abstract, teaches key switching including double hoisting. Reduction of repeated key switching is the teaching of Bossuat.) by using the elements included in the hierarchical Galois key corresponding to the higher level, and (see rejection of claim 3)
the key-switching operation comprises at least one decomposition operation. (see rejection of claim 2)
Claim 17 is rejected using the same basis of arguments used to reject claim 2 & 3 above.
Claims 5, 8, 12, 14, 18, and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Park, in view of Bossuat, in view of US 20230325529 to Sav et al. (hereinafter Sav), in view of NPL – “Cryptanalysis of a Protocol for Efficient Sorting on SHE Encrypted Data” to Shyam Murthy et al. 18 November 2019 pages 278–294 found at https://link.springer.com/chapter/10.1007/978-3-030-35199-1_14 (hereinafter Murthy).
Regarding claim 5, Park and Bossuat teach,
The server of claim 4,
wherein the determining of the generation order for the second hierarchical Galois key set (Bossuat, page 593-594 “3 Homomorphic Polynomial Evaluation”, teaches optimizing the depth of the circuit using polynomials, which includes ordering the computation, which includes ordering of key generation. Depths at same level can be scaled.) comprises, (Bossuat, page 594, Chap. 3.1 & 3.2 teaches tree usage in polynomial evaluation, page 590 teaches Hamming weights that are used throughout the evaluations, page 606 & Table 3 explicitly teach nodes.)
Park and Bossuat fail to explicitly teach the use of weights with nodes regarding generation of switching keys in the homomorphic evaluation / generation order,
However, Sav teaches,
wherein the determining of the generation order for the second hierarchical Galois key set comprises, with respect to ([0016] teaches sequence of operations including multiplication operations. [0018-19] teach homomorphic encryption with key switching and bootstrapping using weights and nodes during evaluation. [0021-27] teach weights and key switching. Additionally, [0023] & [0043] teaches the use of a tree structure using weights.)
Before the effective filing date of the invention, it would have been obvious to one of ordinary skill in the art to combine the teachings of Park, which teaches homomorphic encryption and performing operations on encrypted data using bootstrapping / Galois keys while performing key switching without extensive communication between server and users (Abstract & page 7, col. 1), with Bossuat, which also teaches homographic encryption and performing operations on encrypted data including multiplication (Abstract & page 597), and additionally teaches the use of hoisted key rotations (page 597) for increasing computational efficiency in performing multiplication operations on homomorphically encrypted data with increased efficiency, with Sav, which also teaches homomorphic encryption, and additionally teaches the use of weights related to key switching (Abstract & [0018-19]) and nodes with key switching in a tree structure to optimize training of a privacy preserving neural network (Title, Abstract, & [18-25]). One of ordinary skill in the art would have been motivated to perform such an addition to provide Park and Bossuat with the added ability to evaluate homomorphic operations using weights, nodes and trees with regards to key-switching, as taught by Sav, for the purpose of increasing efficiency and accuracy, reduce computational overhead, while maintaining privacy / security by using homomorphic encryption in operations / evaluations of data in a neural network.
Park, Bossuat, and Sav fail to explicitly teach the use of all of: nodes, edge weights, minimum spanning trees, and graphs together,
However, Murthy teaches,
wherein the determining of the generation order (pages 288-289 teach polynomial evaluation is performed using minimum spanning trees, weighted edges in graphs and subgraphs. It follows that optimization / re-ordering performed by Murthy would result in the generations of a different ordering of operation and generations of switching keys from that ordering, as taught by at least Bossuat.)
Before the effective filing date of the invention, it would have been obvious to one of ordinary skill in the art to combine the teachings of Park, which teaches homomorphic encryption and performing operations on encrypted data using bootstrapping / Galois keys while performing key switching without extensive communication between server and users (Abstract & page 7, col. 1), with Bossuat, which also teaches homographic encryption and performing operations on encrypted data including multiplication (Abstract & page 597), and additionally teaches the use of hoisted key rotations (page 597) for increasing computational efficiency in performing multiplication operations on homomorphically encrypted data with increased efficiency, with Sav, which also teaches homomorphic encryption, and additionally teaches the use of weights related to key switching (Abstract & [0018-19]) and nodes with key switching in a tree structure to optimize training of a privacy preserving neural network (Title, Abstract, & [18-25]), with Murthy, which also teaches homomorphic encryption and performing operations on homomorphically encrypted data (page 278, Abstract and Intro.) where polynomial evaluation is performed (page 288), and additionally teaches the use of weights, minimum spanning trees, weighted edges in graphs and subgraphs (pages 288-289). One of ordinary skill in the art would have been motivated to perform such an addition to provide Park, Bossuat, and Sav with the added ability to utilize trees & graphs to optimize the data, as taught by Murthy, for the purpose of increasing efficiency and accuracy, reduce computational overhead by evaluation / optimization of homomorphic operations, while maintaining privacy / security by using homomorphic encryption in optimized operations, by reducing the number of operations (depth) before generating switch keys, as taught by Murthy.
Regarding claim 8, Park, Bossuat, Sav, and Murthy teach,
The server of claim 5,
wherein the weight of the edge is changed according to substitution of the overlapping decomposition operation. (Rejection of claim 1, citing Bossuat at pages 591 & 598, teaches the reuse of the same keys (substitution) in subsequent rotations, saving processing. Sav, Abstract, teaches updating the weights. Murthy, pages 288-289 teaches the use of weights. Examiner asserts that substation performed during optimization to reduce depth of multiplications changes the parameters of the evaluation, as taught by Bossuat, which would result in the updating of the weights (parameters) used in the evaluation of Sav, and the edge weight used by Murthy.) (For example, Bossuat, bottom of page 591, teaches SwitchKey using decomposition. page 598, "4.2 Improved Hoisted-Rotations", teaches when several rotations have to be applied to the same ciphertext, the keys / key-switches may be re-used (substituted)on subsequent rotations. Similar to applicant's figs. 4a&b & [0060-62] teaching substituted key switching. page 598, "4.2 Improved Hoisted-Rotations", teaches when several rotations have to be applied to the same ciphertext, the keys / key-switches are pre-computed and may be re-used (“substitute”) on subsequent rotations, as discussed in applicant's figs. 4b & [0060-62], discussed below.) (See discussion of applicant’s printed publication [0022] included in the rejection of claim 1.)
Regarding claim 12, Park, Bossuat, Sav, and Murthy teach,
The method of claim 11, wherein the determining of the generation order of the Galois keys included in the hierarchical Galois key set comprises, with respect to a complete graph in which each element included in the hierarchical Galois key set is configured as a node, configuring a weight of an edge which connects each node by the number of key-switching operations required between two nodes, and using a minimum spanning tree for the complete graph to determine the generation order.
Claim 12 is rejected using the same basis of arguments used to reject claim 5 above.
Regarding claim 14, Park, Bossuat, Sav, and Murthy teach,
The method of claim 12, wherein the weight of the edge is changed according to substitution of the overlapping decomposition operation.
Claim 14 is rejected using the same basis of arguments used to reject claim 8 above.
Regarding claim 18, Park, Bossuat, Sav, and Murthy teach,
The computer-readable storage medium of claim 17, wherein the determining of the generation order of the Galois keys included in the hierarchical Galois key set comprises, with respect to a complete graph in which each element included in the hierarchical Galois key set is configured as a node, configuring a weight of an edge which connects each node by the number of key-switching operations required between two nodes, and using a minimum spanning tree for the complete graph to determine the generation order.
Claim 18 is rejected using the same basis of arguments used to reject claim 5 above.
Regarding claim 20, Park, Bossuat, Sav, and Murthy teach,
The computer-readable storage medium of claim 18, wherein the weight of the edge is changed according to substitution of the overlapping decomposition operation.
Claim 20 is rejected using the same basis of arguments used to reject claim 8 above.
Claims 6, 13, and 19 are rejected under 35 U.S.C. 103 as being unpatentable over Park, in view of Bossuat, in view of Sav, in view of Murthy, in view of US 20180262327 to Jain et al. (hereinafter Jain).
Regarding claim 6, Park, Bossuat, Sav, and Murthy teach,
The server of claim 5,
wherein the minimum spanning tree is obtained from the complete graph by (Murthy, pages 288-289, teaches obtaining minimum spanning tree and using nodes.)
Park, Bossuat, Sav, and Murthy fails to explicitly teach the use of Prim’s algorithm,
However, Jain teaches,
wherein the minimum spanning tree is obtained from the complete graph by using Prim's algorithm or Edmond's algorithm. ([0057] teaches cryptography using a spanning tree and Prim’s Algorithm on weighted edges to optimize the ordering of nodes.)
Before the effective filing date of the invention, it would have been obvious to one of ordinary skill in the art to combine the teachings of Park, which teaches homomorphic encryption and performing operations on encrypted data using bootstrapping / Galois keys while performing key switching without extensive communication between server and users (Abstract & page 7, col. 1), with Bossuat, which also teaches homographic encryption and performing operations on encrypted data including multiplication (Abstract & page 597), and additionally teaches the use of hoisted key rotations (page 597) for increasing computational efficiency in performing multiplication operations on homomorphically encrypted data with increased efficiency, with Sav, which also teaches homomorphic encryption, and additionally teaches the use of weights related to key switching (Abstract & [0018-19]) and nodes with key switching in a tree structure to optimize training of a privacy preserving neural network (Title, Abstract, & [18-25]), with Murthy, which also teaches homomorphic encryption and performing operations on homomorphically encrypted data (page 278, Abstract and Intro.) where polynomial evaluation is performed (page 288), and additionally teaches the use of weights, minimum spanning trees, weighted edges in graphs and subgraphs (pages 288-289), with Jain, which also teaches encryption of data (Abstract) and the use of minimum spanning trees using nodes and weighted edges ([0057]), which also teaches the use of Prim’s algorithm ([0057]). One of ordinary skill in the art would have been motivated to perform such an addition to provide Park, Bossuat, Sav, and Murthy with the added ability to utilize Prim’s algorithm to evaluate the minimum Spanning tree, also taught by Murthy, to optimize a minimum spanning tree using weighted edges, as taught by Jain, for the purpose of increasing efficiency and accuracy, reduce computational overhead by evaluation / optimization of homomorphic operations, while maintaining privacy / security by using homomorphic encryption in optimized operations, by reducing the number of operations (depth) before generating switch keys, as taught by Murthy.
Regarding claim 13, Park, Bossuat, Sav, Murthy, and Jain teach,
The method of claim 12, wherein the minimum spanning tree is obtained from the complete graph by using Prim's algorithm or Edmond's algorithm.
Claim 13 is rejected using the same basis of arguments used to reject claim 6 above.
Regarding claim 19, Park, Bossuat, Sav, Murthy, and Jain teach,
The computer-readable storage medium of claim 18, wherein the minimum spanning tree is obtained from the complete graph by using Prim's algorithm or Edmond's algorithm.
Claim 19 is rejected using the same basis of arguments used to reject claim 6 above.
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to BRIAN WILLIAM AVERY whose telephone number is (571)272-3942. The examiner can normally be reached on 9AM-5PM.
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, Farid Homayounmehr can be reached on (571)272-3739.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see https://ppair-my.uspto.gov/pair/PrivatePair. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/B.W.A./
/JASON K GEE/Primary Examiner, Art Unit 2495
Prosecution Insights