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 .
Information Disclosure Statement
The information disclosure statement filed 09/21/2022 fails to comply with 37 CFR 1.98(a)(2), which requires a legible copy of each cited foreign patent document; each non-patent literature publication or that portion which caused it to be listed; and all other information or that portion which caused it to be listed. It has been placed in the application file, but the information referred to therein has not been considered. See IDS filed on 09/21/2022 ref. no. 007, which is an NPL “An Algorithm for the Machine Calculation of Complex Fourier Series”. However, no copy is filed.
Specification
The disclosure is objected to because of the following informalities:
[0254] describes a BU group (BUG) and later describe GBU. Examiner suggests amending the specification to GBU when referring to group of BU.
The specification is objected to as failing to provide proper antecedent basis for the claimed subject matter. See 37 CFR 1.75(d)(1) and MPEP § 608.01(o). See the rejection under 35 U.S.C. 112 below.
Appropriate correction is required.
Claim Objections
Claims 1-11 are objected to because of the following informalities:
Claim 1 line 6; claim 2 line 2; claim 3 line 3-4; claim 3 line 7-10; claim 4 line 3; claim 5 line 3 and 5; “the base prime number information” should be “the predetermined base prime number information” as antecedently recited.
Claim 1 line 7 “the pre-stored base prime number information”. There is lack of antecedent basis for such limitation. Examiner interprets as “the predetermined base prime number information” as antecedently recited.
Claim 1 line 8 “the plurality of ciphertexts” should be “a plurality of ciphertexts” because there is lack of antecedent basis for such limitation.
Claim 2 line 1 “The ciphertext calculation apparatus as claimed in claim 1” should be “The calculation apparatus as claimed in claim 1” because there is lack of antecedent basis for “The ciphertext calculation apparatus”.
Claim 3 line 5 recites “a GBU including a plurality of BUs”. It is not clear what GBU and BUs stand for. Examiner suggests amending the claim, such as “a butterfly unit group (GBU) including a plurality of butterfly units (BUs)”. Support found on [0178] and [254].
Claim 8 line 3 “the same prime number information” should be “a same prime number information” because there is lack of antecedent basis for such limitation.
Dependent claims are also objected for inheriting the same deficiencies in which claims they depend on.
Appropriate correction is required.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f), is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f):
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f). The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f), is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f). The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f), is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f), except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f), except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f), because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation(s) is/are:
“A GBU including a plurality of BUs” in claims 3 and 8. Figure 12 illustrates a configuration of a GBU having a plurality of BUs, wherein [226] figure 8 illustrates a configuration of a BU having modular subtractor 810, modular adder 820, and a modular multiplier 830, [230] describes the modular subtractor 810 and modular adder 820 having the same system design as a general subtractor and adder. [231] describes the modular multiplier 830 having a configuration described above, which is [155] ModMult includes a first multiplier, a second multiplier, a third multiplier, a shift register, and a subtractor. Thus. together figures 8 and 12 [155], [226], [230], [231], provide structure for the GBU including a plurality of BUs to perform the claimed function.
“a prime number generator” in claims 3-5. However, the specification fails to provide sufficient structure, material or acts to perform the claimed functions, such as generate prime number information necessary by reversing the bits of the base prime number information, converting a bit value of kth-bit into log h bit integer, or generate first and second primary number information.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f), it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f), applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f).
Claim Rejections - 35 USC § 112(a)
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
Claims 3-10 are rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the written description requirement. The claim(s) contains subject matter which was not described in the specification in such a way as to reasonably convey to one skilled in the relevant art that the inventor or a joint inventor, or for applications subject to pre-AIA 35 U.S.C. 112, the inventor(s), at the time the application was filed, had possession of the claimed invention.
Claims 3-5 recites “a prime number generator” for generating prime number information, which invokes 112(f) interpretation. However, the written description fails to disclose the corresponding structure, material, or acts for performing the entire claimed function and to clearly link the structure, material, or acts to the function. Specification figure 7 illustrates an algorithm at line 7 having a function to perform BitReverse [221], but the specification does not provide step by step how such BitReverse function is performed. Furthermore, figure 15 [272] illustrates a configuration for a prime number generator, but the specification fails to describe or link how such configuration generate prime number information by reversing the bit of the based prime number information as required in the claimed function. Accordingly, the specification fails to provide sufficient structure, material, or acts for the prime number generator to perform the claimed function as required when invoking 112(f) interpretation.
Dependent claims are also rejected for inheriting the same deficiencies in which claims they depend on.
Claim Rejections - 35 USC § 112(b)
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.
Claims 3-10 and 12-15 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claims 3-5 recites “a prime number generator” for generating prime number information, which invokes 112(f) interpretation. However, the written description fails to disclose the corresponding structure, material, or acts for performing the entire claimed function and to clearly link the structure, material, or acts to the function. Specification figure 7 illustrates an algorithm at line 7 having a function to perform BitReverse [221], but the specification does not provide step by step how such BitReverse function is performed. Furthermore, figure 15 [272] illustrates a configuration for a prime number generator, but the specification fails to describe or link how such configuration generate prime number information by reversing the bit of the based prime number information as required in the claimed function. In other words, no association between the structure in figure 15 and the claimed function can be found in the specification. Therefore, the claim is indefinite and is rejected under 35 U.S.C. 112(b).
Applicant may:
(a) Amend the claim so that the claim limitation will no longer be interpreted as a limitation under 35 U.S.C. 112(f);
(b) Amend the written description of the specification such that it expressly recites what structure, material, or acts perform the entire claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(c) Amend the written description of the specification such that it clearly links the structure, material, or acts disclosed therein to the function recited in the claim, without introducing any new matter (35 U.S.C. 132(a)).
If applicant is of the opinion that the written description of the specification already implicitly or inherently discloses the corresponding structure, material, or acts and clearly links them to the function so that one of ordinary skill in the art would recognize what structure, material, or acts perform the claimed function, applicant should clarify the record by either:
(a) Amending the written description of the specification such that it expressly recites the corresponding structure, material, or acts for performing the claimed function and clearly links or associates the structure, material, or acts to the claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(b) Stating on the record what the corresponding structure, material, or acts, which are implicitly or inherently set forth in the written description of the specification, perform the claimed function. For more information, see 37 CFR 1.75(d) and MPEP §§ 608.01(o) and 2181.
claim 8 line 2 recites “the homomorphic calculations”. It is unclear whether “the homomorphic calculations” is referring to the different preset homomorphic calculations as recited in claim 3 line 6 or different homomorphic calculations. For examination purposes, Examiner interprets such limitations as “homomorphic calculations”.
Claim 9 line 6 recites “output an addition value of the two homomorphic ciphertexts”. It is unclear whether “the two homomorphic ciphertexts” is referring to the homomorphic ciphertexts received by the modulus subtractor or the modulus adder. For examination purposes, Examiner interprets such limitation as “output an addition value of the two homomorphic ciphertexts received by the modulus adder”.
Claim 12 line 6 recites “outputting a result of the calculation”. It is unclear whether “the calculation” is referring to the module calculation in line 3 or the ciphertext calculation in line 1. For examination purposes, Examiner interprets “outputting a result of the module calculation”.
Dependent claims are also rejected for inheriting the same deficiencies in which claims they depend on.
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-2 and 11-15 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Claim 1 recites a calculation apparatus.
Under Prong One of Step 2A of the USPTO current eligibility guidance (MPEP 2106), the claim recites limitations cover mathematical calculations, relationship, and/or formula, such as generate first prime number information different from the base prime number information by reversing bits of the pre-stored base prime number information (see at least figure 7 illustrates the step bit reverse, wherein bit reverse is mathematical operation for reversing order of bits), and perform a modular calculation for the plurality of ciphertexts by using the generated first prime number information (see at least [135] describes multiplication may be the modular calculation, the plurality of ciphertexts are merely recited as data and [83] describes modular multiplication means a modular calculation with q, wherein q element is used as illustrated in figure 5-6. Also see [150-154] describes the mathematical equation 9 for modular calculation). Therefore, the claim includes limitations that fall within the “Mathematical Concepts” grouping of abstract ideas. Accordingly, the claim recites an abstract idea.
Under Prong Two of Step 2A, this judicial exception is not integrated into a practical application. The claim additionally recites a calculation apparatus comprising: a memory configured to store at least one instruction; and a processor configured to execute the at least one instruction, wherein the processor is configured to execute the at least one instruction to store predetermined base prime number information. However, the additional elements are recited at a high level of generality, i.e., as a generic computer components performing generic computer functions of storing instructions and executing instructions to perform operation. Furthermore, the step of storing predetermined base prime number information is considered as insignificant extra solution activity because such activity is mere data gathering and well known. Moreover, the plurality of ciphertexts are merely described as data to be performed in the arithmetic operation or at most considered as mere generally linking the use of the judicial exception into a particular technological environment or field of use, such as homomorphic encryption. Such additional elements fail to provide a meaningful limitation on the judicial exception, and amount to no more than mere instructions to apply the exception using generic computer element. Thus, the claim is directed to an abstract idea.
Under Step 2B, as discussed with respect to Prong Two of Step 2A, the additional elements in the claim amount no more than mere instructions to apply the exception using a generic component. The same conclusion is reached in step 2B, i.e., mere instructions to apply an exception on a generic element cannot integrate a judicial exception into a practical application at step 2A or provide an inventive concept that is furnished by an element or combination of elements that is recited in the claim in addition to (beyond) the judicial exception. The step of storing predetermined base prime number information considered to be insignificant extra-solution activity in step 2A, and are determined to be well-understood, routine, conventional activity in the field. Court decisions cited in MPEP 2106.05(d)(II) section (iv) Storing and retrieving information in memory, is well-understood, routing, conventional function when it is claimed in a merely generic manner. Thus, the additional element fails to ensure the claim as a whole amount to significantly more than the judicial exception itself. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 2 further recites wherein the base prime number information and the first prime number information are values obtained by addition and subtraction of three, four, or five exponentiations of 2 with different exponents. Such limitations cover mathematical calculations, relationship, and/or formula (performing addition and subtraction of exponentiations of 2 with different exponents, see at least figures 5-6). The claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 11 further recites wherein the processor is a field programmable gate array (FPGA). Such limitation is recited at a high level of generality, e.g., implementing the processor as an FPGA to perform the abstract idea, which amounts to no more than mere instructions to apply the judicial exception using computer component under step 2A prong two. Thus, the claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 12 recites a ciphertext calculation method.
Under Prong One of Step 2A of the USPTO current eligibility guidance (MPEP 2106), the claim recites limitations cover mathematical calculations, relationship, and/or formula, such as performing a module calculation for the plurality of ciphertexts by using prime number information expressed by a combination of exponentiations of 2 (see at least [135] describes multiplication may be the modular calculation, the plurality of ciphertexts are merely recited as data, figures 5-6 illustrate the prime number information expressed by combination of exponentiations of 2, which is also a mathematical expression of the prime number); wherein, in the performing of the modular calculation, bits of the based prime number information are reversed to generate first prime number information different from the base prime number information (see at least figure 7 illustrates the step bit reverse, wherein bit reverse is mathematical operation for reversing order of bits), and the modular calculation for the plurality of ciphertexts is performed by using the generated first prime number information (see at least see at least [135] describes multiplication may be the modular calculation and [83] describes modular multiplication means a modular calculation with q, wherein q element is used as illustrated in figure 5-6. Also see [150-154] describes the mathematical equation 9 for modular calculation). Therefore, the claim includes limitations that fall within the “Mathematical Concepts” grouping of abstract ideas. Accordingly, the claim recites an abstract idea.
Under Prong Two of Step 2A, this judicial exception is not integrated into a practical application. The claim additionally recites a step for receiving a modular calculation command for a plurality of ciphertext, storing base prime number information and outputting a result of the calculation. However, the additional elements are recited at a high level of generality, i.e., as a generic computer functions of receiving command, storing data to perform operation, and outputting a result of the calculation. Furthermore, the step of receiving command, storing base prime number information, and outputting a result of the calculation are also considered as insignificant extra/post solution activities because receiving, storing data, and outputting results are mere data gathering/outputting and well known. Moreover, ciphertexts are recited as mere data description or at most considered as mere generally linking the use of the judicial exception into a particular technological environment or field of use, such as homomorphic encryption. Such additional elements fail to provide a meaningful limitation on the judicial exception, and amount to no more than mere instructions to apply the exception using generic computer element. Thus, the claim is directed to an abstract idea.
Under Step 2B, as discussed with respect to Prong Two of Step 2A, the additional elements in the claim amount no more than mere instructions to apply the exception using a generic component. The same conclusion is reached in step 2B, i.e., mere instructions to apply an exception on a generic element cannot integrate a judicial exception into a practical application at step 2A or provide an inventive concept that is furnished by an element or combination of elements that is recited in the claim in addition to (beyond) the judicial exception. The step of receiving command and storing base prime number information considered to be insignificant extra-solution activity in step 2A, and are determined to be well-understood, routine, conventional activity in the field. Court decisions cited in MPEP 2106.05(d)(II) (i) receiving and transmitting data over a network and section (iv) Storing and retrieving information in memory, are well-understood, routing, conventional functions when they are claimed in a merely generic manner. Thus, the additional element fails to ensure the claim as a whole amount to significantly more than the judicial exception itself. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 13 recites method claim that would be practiced by the apparatus claim 2. Thus, it is rejected for the same reasons.
Claim 14 further recites wherein in the performing of the modular calculation, the first prime number information is generated by converting a bit value of a k-th bit of the base prime number information into a log h-th bit integer. Such limitations cover mathematical calculations, relationship, and/or formula (performing bit conversion). The claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Claim 15 further recites wherein in the performing of the modular calculation, the first prime number information necessary for a first cycle is generated by using the base prime number information, and second prime number information necessary for a second cycle is generated by using the generated first prime number information and the base prime number information. Such limitations cover mathematical calculations, relationship, and/or formula (generating prime number information using bit reverse in multiple cycles). The claim does not recite additional element that would integrate the judicial exception into a practical application under step 2A prong two or ensure the claim as a whole amount to significantly more than the judicial exception itself under step 2B. Accordingly, the claim is not patent-eligible under 35 U.S.C. 101.
Allowable Subject Matter
Claims 1-2 and 11-15 would be allowable if rewritten or amended to overcome the claim objections and the rejections under 35 U.S.C. 101 and 112(b) set forth in this Office action.
Claims 3-10 would be allowable if rewritten to overcome the claims objections and rejections under 35 U.S.C. 112(a) and 112(b), set forth in this Office action and to include all of the limitations of the base claim and any intervening claims.
The following is a statement of reasons for the indication of allowable subject matter:
Regarding claims 1 and 12, the prior art of record does not teach or suggest a combination of limitations as claimed, including the limitations of storing the predetermined base prime number information, generate first prime number information different from the base prime number information by reversing bits of the base prime number information and perform modular calculation for the plurality of ciphertext by using the generated first prime number information.
Kim – NPL Hardware Architecture of a Number Theoretic Transform for a Bootstrappable RNS-based Homomorphic Encryption Scheme – an NPL discloses by the applicant that teaches the claimed invention, which includes the approach to limit the size of internal memory for roots of unity increased by the bootstrappable parameters, only a few roots of unity are stored and others are generated on the fly, see at least algorithm 2 on page 59.
Roy - NPL Hardware Assisted Fully Homomorphic Function Evaluation and Encrypted Search (filed in IDS 09/21/2022 ref. no. 22) – teaches an internal architecture of processor part of the recryption box as shown in figure 1, wherein the processor has two symmetric polynomial arithmetic and logic units (PALUs) for performing arithmetic modulo operation and configured to perform modular operation for NTT operation, wherein page 1569 describes in this architecture, the fixed twiddle factors are not stored, but instead being computed on the fly during an NTT operation. The small w-ROM stores the log (n) twiddle factors wm (line 4 in algorithm 1) to generate the new twiddle factors (line 12). As illustrated in line 12, the new twiddle factor is generated by performing multiplication. Thus, such algorithm does not teach or suggest the new twiddle factors or first prime number information to be generated using bit reversed of the base twiddle factors or predetermined base prime number information stored in ROM.
Roy – NPL Compact Ring -LWE Cryptoprocessor – teaches a processor for encryption scheme for Number Theoretic Transform (NTT) used for polynomial multiplication that reduce the fixed computation cost of the twiddle factors and propose an advanced memory access scheme. Page 10 describes the hardware architecture for NTT to use a small look-up table to store a few twiddle factors, and multiply the look-up table with wm to compute the next l twiddle factors. Thus, while Roy teaches a few primitive root of unit or twiddle factors (i.e.. predetermined base prime number information) to be stored and generate new twiddle factors on the fly and use the generated twiddle factor in modular calculation as illustrated in figures 1 and 2, but Roy does not teach the generating of new twiddle factor or first prime number information by reversing bits of the predetermined base prim number information.
Kwon – US 20230171084 teaches an apparatus with homomorphic encryption includes: a first memory configured to receive and store a polynomial; a second memory configured to store a twiddle factor; a number theoretic transform (NTT) module configured to perform an NTT operation on the polynomial based on the twiddle factor, wherein the NTT module comprises a butterfly unit (BU) array that comprises a plurality of BUs configured to, for the performing of the NTT operation, perform a modular operation on coefficients of the polynomial as illustrated in figure 2. Furthermore, the twiddle factor is stored in bit reverse order in a number of memory banks determined based on an order of the polynomial. However, Kwon does not teach or suggest the new twiddle factors or first prime number information to be generated using bit reversed of the base twiddle factors or predetermined base prime number information stored In memory.
Therefore, the prior art of records does not teach or suggest the limitations as required in claims 1 and 12. Accordingly, claims 1-2 and 11-15 would be allowable if rewritten or amended to overcome the claim objections and the rejections under 35 U.S.C. 101 and 112(b) set forth in this Office action, and claims 3-10 would be allowable if rewritten to overcome the claims objections and rejections under 35 U.S.C. 112(a) and 112(b), set forth in this Office action and to include all of the limitations of the base claim and any intervening claims.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to HUY DUONG whose telephone number is (571)272-2764. The examiner can normally be reached Mon-Friday 7:30-5:30.
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, Andrew Caldwell can be reached at (571) 272-3702. 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.
/HUY DUONG/Examiner, Art Unit 2182
/ANDREW CALDWELL/Supervisory Patent Examiner, Art Unit 2182