DETAILED ACTION
This action is in response to the application filed on July 8, 2024. Claims 1-15 are pending. Of such, claims 1-7 represent a device and claims 8-11 represent a method and claims 12-15 represent a non-transitory computer-readable storage media directed to distributed re-encryption.
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 .
Claim Rejections - 35 USC § 102
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 the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claim(s) 1-4 and 8-15 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Polyakov et al. (US 20210399874), hereinafter referred to as Polyakov.
Regarding Claim 1, Polyakov discloses:
A distributed re-encryption apparatus comprising: a distributed re-encryption key storage part that stores shares obtained by secret-sharing a re-encryption key (In ¶ 59 and 63, Polyakov discloses “In operation 310, at each of a plurality of parties (e.g., 140, 150, 160, and/or 170 of FIGS. 1-2), one or more processors (e.g., 146, 156, 166, 176, . . . of FIGS. 1-2) may store in one or more memories (e.g., 148, 158, 168, 178, . . . of FIGS. 1-2) a linear secret key share and a linear public key share associated with the party.”, the examiner notes the linear secret key share is used to reconstruct the re-linearization key used for re-encryption.) that re-encrypts a ciphertext into one encrypted with a different encryption key without decrypting the ciphertext (In ¶ 63, Polyakov discloses “In operation 350, one or more processors (e.g., 116, 146, 156, 166, and/or 176) may re-encrypt the result ciphertext with a re-linearization key to swap encryption keys from the non-linear public key to a linear public key.”); and a distributed re-encryption part that re-encrypts using the shares of the re-encryption key the ciphertext into one encrypted with a different encryption key without decrypting the ciphertext (In ¶ 64, Polyakov discloses “The plurality of parties may collaboratively generate the re-linearization key.” And further discloses in ¶ 65 “Re-encrypting the result ciphertext may comprise swapping encryption keys by composing the re-linearization key with the result ciphertext.”).
Regarding Claim 2, Polyakov discloses:
The distributed re-encryption apparatus according to Claim 1, wherein the ciphertext is a result of a homomorphic operation between ciphertexts encrypted with different keys (In ¶ 51, Polyakov discloses “The data owner(s) and model owner(s) send the HE data and HE model 180 and associated common evaluation key to the computational host 210. Thus, the computational host 210 does not have access to the unencrypted model or computations it performs, only the HE model or computations performed in the HE space. The computational host 210 performs the HE model computations, using the common evaluation key, on the HE data 180, all in HE space, without access to the unencrypted data or model, to generate a multiparty computational result.”).
Regarding Claim 3, Polyakov discloses:
The distributed re-encryption apparatus according to Claim 1, wherein the re-encryption key is configured by combining part of a decryption key for the ciphertext encrypted with the different encryption key and a decryption key for the ciphertext (In ¶ 64, Polyakov discloses “One or more processors (e.g., 116, 146, 156, 166, and/or 176) may combine one or more of the plurality of partial re-linearization operators (cj dj) to generate a re-linearization key (c,d) that represents encryptions of 2ir(Σj=1 N sj) 2 under the linear common public key pk associated with the linear common secret key Σj=1 N sj” wherein the examiner interprets the re-linearization key as the claimed re-encryption key).
Regarding Claim 4, Polyakov discloses:
The distributed re-encryption apparatus according to Claim 1, wherein the ciphertext encrypted with the different encryption key is obtained by decrypting what are computed as secret shares (In ¶ 6, Polyakov discloses “The re-encrypted result ciphertext may be distributed to the plurality of parties to each partially decrypt the re-encrypted result ciphertext by a linear secret key share associated with the party, which in combination with partial decryptions of the re-encrypted result ciphertext by each of the other parties, fully decrypts the result by a linear common secret key that is a sum of the secret key shares of the respective plurality of parties.”)
Claims 8-11 is directed to a method having functionality corresponding to the apparatus of Claims 1-4, and is rejected by a similar rationale, mutatis mutandis.
Claims 12-15 is directed to a non-transitory computer readable medium having functionality corresponding to the apparatus of Claims 1-4, and is rejected by a similar rationale, mutatis mutandis.
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 5-7 are rejected under 35 U.S.C. 103 as being unpatentable over Polyakov et al. (US 20210399874), hereinafter referred to as Polyakov, in view of Yasuda et al. (US 20200344049), hereinafter referred to as Yasuda.
Regarding Claim 5, Polyakov discloses:
A cryptographic system having: a plurality of the distributed re-encryption apparatuses according to Claim 1 (In ¶ 59, Polyakov discloses “In operation 310, at each of a plurality of parties (e.g., 140, 150, 160, and/or 170 of FIGS. 1-2), one or more processors (e.g., 146, 156, 166, 176, . . . of FIGS. 1-2) may store in one or more memories (e.g., 148, 158, 168, 178, . . . of FIGS. 1-2) a linear secret key share and a linear public key share associated with the party.”); a re-encryption key generation part that generates the re-encryption key (In ¶ 63, Polyakov discloses “In operation 350, one or more processors (e.g., 116, 146, 156, 166, and/or 176) may re-encrypt the result ciphertext with a re-linearization key to swap encryption keys from the non-linear public key to a linear public key.”); and a decryption apparatus that decrypts the ciphertext encrypted with the different encryption key (In ¶ 50, Polyakov discloses “The re-linearized or rotated/permuted computational result may be collaboratively decrypted by the multiple parties 140, 150, 160, . . . , where each data owner performs its respective partial decryption using its secret key share s.sub.j and the decrypted results are combined to generate the decryption of each party's data D.sub.i.”) connected to each other by a network (In ¶ 52, Polyakov discloses “Any or all of system devices may be connected via one or more network(s) 220.”).
However, Polyakov does not disclose the limitation of a multi-key fully homomorphic encryption.
Yasuda discloses:
a plurality of key generation apparatuses (In ¶ 36, Yasuda discloses “The privacy-preserving information processing system 10 includes a common parameter generation device 20, a plurality of key generation devices 30”), each of which comprising an encryption key generation part that generates an encryption key in multi-key fully homomorphic encryption (In ¶ 91, Yasuda discloses “The key generation unit 312 executes the KG algorithm in the multi-key homomorphic encryption, taking as input the retrieved common parameter pp, so as to generate a pair of a decryption key sk and a public key pk.”), a decryption key generation part that generates a decryption key in the multi-key fully homomorphic encryption (In ¶ 91, Yasuda discloses “The key generation unit 312 executes the KG algorithm in the multi-key homomorphic encryption, taking as input the retrieved common parameter pp, so as to generate a pair of a decryption key sk and a public key pk.”), an evaluation key generation part that generates an evaluation key in the multi-key fully homomorphic encryption (In ¶ 111, Yasuda discloses “The homomorphic operation unit 612 executes the Eval algorithm in the multi-key homomorphic encryption, taking as input the retrieved ciphertext TC, operation f, and public key pk, so as to generate a ciphertext EC resulting from performing the operation f on the ciphertext TC.”), an encryption key storage part that stores the encryption key (In ¶ 91, Yasuda discloses “The key generation unit 312 writes the generated pair of the decryption key sk and the public key pk in the memory 32.”), and a decryption key storage part that stores the decryption key (In ¶ 91, Yasuda discloses “The key generation unit 312 writes the generated pair of the decryption key sk and the public key pk in the memory 32.”); a plurality of encryption apparatuses, each of which comprising a ciphertext generation part that generates a ciphertext using the encryption key in the multi-key fully homomorphic encryption (In ¶ 105, Yasuda discloses “The encryption unit 512 executes the Enc algorithm in the multi-key homomorphic encryption, taking as input the retrieved plaintext M and public key pk, so as to encrypt the plaintext M with the public key pk to generate a ciphertext C.”); an encrypted data operation apparatus comprising a ciphertext storage part that stores a ciphertext (In ¶ 105, Yasuda discloses “The encryption unit 512 writes the generated ciphertext C in the memory 52.”), an evaluation key storage part that stores an evaluation key used for an operation between the ciphertexts (In ¶ 111, Yasuda discloses “The homomorphic operation unit 612 executes the Eval algorithm in the multi-key homomorphic encryption, taking as input the retrieved ciphertext TC, operation f, and public key pk, so as to generate a ciphertext EC resulting from performing the operation f on the ciphertext TC.”), and an operation part that performs a homomorphic operation on the ciphertexts (In ¶ 116, Yasuda discloses “The ciphertext TC to be processed is at least one of a ciphertext C generated by the encryption device 50 and a ciphertext EC resulting from performing a homomorphic operation by the homomorphic operation device 60.”);
One in ordinary skill in the art of cryptography would have been motivated, before the effective filing date of the claimed invention to modify Polyakov’s approach by utilizing Yasuda’s approach of the use of multi-key homomorphic encryption as the motivation would be to ensure the data being operated on remains encrypted as to allow privacy (See Yasuda, ¶ 2)
Regarding Claim 6, the combination of Polyakov and Yasuda disclose:
The cryptographic system according to Claim 5, wherein the re-encryption key is configured by combining part of a decryption key for the ciphertext encrypted with the different encryption key and a decryption key for the ciphertext. (In ¶ 64, Polyakov discloses “One or more processors (e.g., 116, 146, 156, 166, and/or 176) may combine one or more of the plurality of partial re-linearization operators (cj dj) to generate a re-linearization key (c,d) that represents encryptions of 2ir(Σj=1 N sj) 2 under the linear common public key pk associated with the linear common secret key Σj=1 N sj” wherein the examiner interprets the re-linearization key as the claimed re-encryption key).
Regarding Claim 7, the combination of Polyakov and Yasuda disclose:
The cryptographic system according to Claim 5, wherein the ciphertext encrypted with the different encryption key is obtained by decrypting what are computed as secret shares. (In ¶ 6, Polyakov discloses “The re-encrypted result ciphertext may be distributed to the plurality of parties to each partially decrypt the re-encrypted result ciphertext by a linear secret key share associated with the party, which in combination with partial decryptions of the re-encrypted result ciphertext by each of the other parties, fully decrypts the result by a linear common secret key that is a sum of the secret key shares of the respective plurality of parties.”)
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Rohloff et al. (US 20200151356) discloses a method for encryption of ciphertexts using fully homomorphic encryption.
Genise et al. (US 20230361986) discloses a multiparty scheme for homomorphic encryption.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SHADI H KOBROSLI whose telephone number is (571)272-1952. The examiner can normally be reached M-F 9am-5pm ET.
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, Rupal Dharia can be reached at 571-272-3880. 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.
/SHADI H KOBROSLI/Examiner, Art Unit 2492
/AMIR MEHRMANESH/Supervisory Patent Examiner, Art Unit 2491