DETAILED ACTION
This Office Action is in response to application 18/531,448 filed on December 6, 2023.
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 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.
Claims 1-20 are pending and herein considered.
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 .
Double Patenting
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the conflicting claims are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, e.g., In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998); In re Goodman, 11 F.3d 1046, 29 USPQ2d 2010 (Fed. Cir. 1993); In re Longi, 759 F.2d 887, 225 USPQ 645 (Fed. Cir. 1985); In re Van Ornum, 686 F.2d 937, 214 USPQ 761 (CCPA 1982); In re Vogel, 422 F.2d 438, 164 USPQ 619 (CCPA 1970); In re Thorington, 418 F.2d 528, 163 USPQ 644 (CCPA 1969).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on nonstatutory double patenting provided the reference application or patent either is shown to be commonly owned with the examined application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. See MPEP § 717.02 for applications subject to examination under the first inventor to file provisions of the AIA as explained in MPEP § 2159. See MPEP § 2146 et seq. for applications not subject to examination under the first inventor to file provisions of the AIA . A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The filing date of the application in which the form is filed determines what form (e.g., PTO/SB/25, PTO/SB/26, PTO/AIA /25, or PTO/AIA /26) should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to www.uspto.gov/patents/process/file/efs/guidance/eTD-info-I.jsp.
Claim 1 is provisionally rejected on the ground of nonstatutory double patenting as being unpatentable over claim 1 of copending Application No. 18/531,169 (reference application). Although the claims at issue are not identical, they are not patentably distinct from each other.
This is a provisional nonstatutory double patenting rejection because the patentably indistinct claims have not in fact been patented.
As per claim 1, Luo teaches a method to bootstrap ciphertext in a Fully Homomorphic encryption process, the method comprising: (Luo, claim 1 A method to bootstrap ciphertext in a Fully Homomorphic Encryption process, the method comprising:)
separating ciphertext into a vector of n samples; (Luo, claim 1 A method to bootstrap ciphertext in a Fully Homomorphic Encryption process, the method comprising: separating ciphertext into a vector of n samples)
performing a fast Fourier transfer (FFT) over the vector of the n samples; (Luo, claim 1 performing a fast Fourier transfer (FFT) over the vector of the n samples)
performing an FFT for each of n polynomial terms multiplied by a bootstrap key;
performing a point wise multiplication of each of the FFT outputs of the FFTs of the polynomial terms and the output of the FFT over the vector of the n samples; (Lou, claim1, performing a second set of pointwise multiplications of the results of the first set of pointwise multiplications with the FFT of the bootstrap key; and performing an inverse FFT (IFFT) on the accumulated result of the second set of point-wise multiplications to obtain a bootstrapping result of the ciphertext.)
adding the result of the FFT over the vector of the n samples to the results of the set of pointwise multiplications; performing an inverse FFT (IFFT) on the FFT over the vector of n samples and the accumulated results of the point-wise multiplications to obtain a bootstrapping result of the ciphertext. (Luo, claim 1 performing an inverse FFT (IFFT) on the accumulated result of the second set of point-wise multiplications to obtain a bootstrapping result of the ciphertext.)
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 as being directed to non-statutory subject matter.
Claim 1 is rejected under 35 USC 101 because the claims are/is directed to an abstract idea without being integrated into a practical application nor being significantly more.
The claims recite the limitations “separating ciphertext; performing a fast Fourier transfer (FFT) over the vector of the n samples; and
performing an FFT for each of n polynomial terms multiplied by a bootstrap key;” Accordingly, the claims recite an abstract idea. This judicial exception is not integrated into a practical application. It’s noted that the claims recite additional element(s) (i.e., a computing apparatus; the processing hardware). However, said additional elements are recited at a high-level of generality (i.e., as a processing device performing a generic computer function of performing FFT/ separating ciphertext) such that it amounts to no more than mere instructions to apply to data using a generic computer component. Accordingly, this additional element does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. Therefore, the claims are not integrated into a practical application.
The claims do not include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional elements when considered both individually and as an ordered combination do not amount to significantly more than the abstract idea because the additional elements perform generic computer content distributing functions routinely used in information technology field (i.e., receiving, and storing in the memory, data for performing a fast Fourier transfer (FFT), in view of Berkheimer memo). Generic computer components recited as performing generic computer functions that are well understood, routine and conventional activities amount to no more than implementing the abstract idea with a computerized system. Therefore, the claim is directed to non-statutory subject matter.
Regarding claims 2-20 are also rejected under 35 U.S.C 101 as being directed to non-statutory subject matter for the same reasons addressed above as the claims are directed to an abstract idea without being integrated into a practical application.
Claim Rejections - 35 USC § 102
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-6 and 8 are rejected under 35 U.S.C. 102(a)2 as anticipated by over Van Beirendonck et al. {US Pub. 2025/0167976) (hereinafter “Van Beirendonck’.
As per claim 1, Van Beirendonck teaches
separating ciphertext into a vector of n samples; ([Van Beirendonck, para. 0015] “A bootstrapping operation ... requires ... the ciphertext coefficients a,,..., a,”;[para. 0064] “assuming q ciphertexts, each with n portions, each batch is represented by a vector comprising q portions of ciphertext”)
performing a fast Fourier transfer (FFT) over the vector of the n samples; ([Van Beirendonck, para. 0015] “A bootstrapping operation ... requires ... the input ciphertext coefficients a,,...,a,”; [para.
0016-0017] “Bootstrapping is ... dominated by the calculation of the polynomial multiplications ... by
converting the input polynomials ... into another representation using the FFT”)
performing an FFT for each of n polynomial terms multiplied by a bootstrap key; ([Van Beirendonck, para. 0015] “A bootstrapping operation ... requires two major inputs: the input ciphertext coefficients a,, ..., a, and the bootstrapping key BK comprising bootstrapping key coefficients BK,, . . . , BK,”; [para. 0016-0017] “Bootstrapping is ... dominated by the calculation of the polynomial multiplications ... by converting
the input polynomials ... into another representation using the FFT”)
performing a point wise multiplication of each of the FFT outputs of the FFTs of the polynomial terms and the output of the FFT over the vector of the n samples; ([Van Beirendonck, para. 0017] “the multiplication operation with polynomials ... can be performed pointwise [performing a set of pointwise multiplications]”; [para.0019] “the coefficients of the input polynomial a [of the FFT as they are used in the FFT and of the vectors of samples as a represents the ciphertext] are multiplied [a set of pointwise multiplications as explained above] with aso-called twiddle factor ... P=w.) [each of the W(a) terms in the phase vector]’)
adding the result of the FFT over the vector of the n samples to the results of the set of pointwise multiplications; ([Van Beirendonck, para. 0006] The ciphertext data on which computations are performed in a FHE scheme, are large polynomials (length N) from a certain scheme-dependent polynomial ring. Typical operations on these polynomials include addition and multiplication. While addition is linear in the length of the polynomial (O(N) operations), multiplication has a quadratic cost (O(N.sup.2) operations) when using a generic straightforward technique, also known as schoolbook multiplication. and
performing an inverse FFT (IFFT) on the FFT over the vector of n samples and the accumulated results of the point-wise multiplications to obtain a bootstrapping result of the ciphertext. ([Van Beirendonck, para. 0016] “An acceleration of the polynomial multiplication can be achieved through the convolution theorem: c =a XxX b = IFFT(FFT (a): FFT (b)))’; [para. 0017] “The accumulation step of the vector-matrix product is preferably executed in FFT-domain ... Afterwards, the result needs to be converted back to the initial representation using the inverse FFT”
As per claim 2, Van Beirendonck teaches claim 1 wherein all the samples and vector computations are executed in a double precision floating point format. ([Van Beirendonck, para. 0081] “The vector elements and/or bootstrapping keys can be represented in ... floating point notation ... with ... double precision”)
As per claim 3, Van teaches wherein all samples and vector computations are executed in fully fixed-point format ([Van Beirendonck, para.0081] “The vector elements and/or bootstrapping keys can
be represented in ... fixed point notation”)
As per claim 4, Van Beirendonck teaches wherein all samples and vector computations are executed in a nearly fully fixed-point format, {([Van Beirendonck, para. 0081] “The vector elements ... can be represented in... fixed point notation when using the FFT”; Examiner understands “represented in” to mean the same as “nearly” in view of the BRI of the term) wherein the bootstrapping key is pre- calculated in double precision format. ([Para. 0081] “bootstrapping keys can be represented ... in floating point notation ... with ... double precision”)
As per claim 5, Van Beirendonck teaches wherein the FHE process is performed for a learning with error scheme. para. 0011] “the Torus Fully Homomorphic Encryption (TFHE) scheme and its working is provided ... Torus Fully Homomorphic Encryption is a homomorphic encryption scheme based on the Learning With Errors (LWE) problem”)
As per claim 6, Van Beirendonck teaches wherein the steps are performed by at least one of a central processor, a Field Programmable Gate Array (FPGA), a Digital Signal Processor (DSP), a Graphics Processing Unit (GPU), or an Application-Specific Integrated Circuit (ASIC). para. 0011] “the Torus Fully Homomorphic Encryption (TFHE) scheme and its working is provided ... Torus Fully Homomorphic Encryption is a homomorphic encryption scheme based on the Learning With Errors (LWE) problem”)
As per claim 8 the claim language is identical or substantially similar to that of claim 2. Therefor it is rejected under the same rationale applied to claim 2.
performing an FFT for each of n polynomial terms multiplied by a bootstrap key; performing a point wise multiplication of each of the FFT outputs of the FFTs of the polynomial terms and the output of the FFT over the vector of the n samples; adding the result of the FFT over the vector of the n samples to the results of the set of pointwise multiplications; and performing an inverse FFT (IFFT) on the FFT over the vector of n samples and the accumulated results of the point-wise multiplications to obtain a bootstrapping result of the ciphertext.
Allowable Subject Matter
Claims 7 and 9-20 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims and if rewritten or amended to overcome the double patenting rejection(s) set forth in this Office action and 35 USC 101 Rejection.
Related Art
The following prior art made of record and cited on PTO-892, but not relied upon, is considered pertinent to applicant’s disclosure:
U.S Pub. 2023/0171084 A1 to Kwon-Kwon teaches homomorphic encryption includes: receiving and storing a polynomial; storing a twiddle factor; performing a number theoretic transform (NTT) operation on the polynomial based on the twiddle factor; and controlling a first memory configured to store the polynomial, a second memory configured to store the twiddle factor, and an NTT module configured to perform the NTT operation, wherein the performing of the NTT operation comprises performing the NTT operation by performing a modular operation on coefficients of the polynomial using a butterfly unit (BU) array that may include a plurality of BUs. The NTT operation may include a predetermined number of stages, and the performing of the NTT operation may include performing the NTT operation based on a radix corresponding to the predetermined number.
U.S Pub. 2003/0021443 A1 to Haitsma-Haitsma teaches Fast Fourier Transform (FFT) of said first signal (W.sub.p') resulting in a first FFT signal and of said predetermined set of watermark signals (W.sub.l, . . . W.sub.N) or every cyclic shifted version of the watermark signal W.sub.i resulting in a set of second FFT signals, point-wise multiplication of the first FFT signal and a conjugate of the second FFT signals resulting in a set of third FFT signals, and inverse Fast Fourier Transform (FFT) of the third set of FFT signals..
U.S Pat. 7,583082 B1 to Hu-Hu teaches performed in image space according to Fourier theory by transforming the gridded data and convolution kernels into image space, performing image space point-wise multiplication and summing up the results to produce a composite data set in image space.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to VU V TRAN whose telephone number is (571)270-1708. The examiner can normally be reached M-F, 8 AM- 4 PM.
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, William Korzuch can be reached at 571-272-7589. 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.
/VU V TRAN/Primary Examiner, Art Unit 2491