DETAILED ACTION
This action is in response to the application filed on December 13, 2024. Claims 1-20 are pending. Claims 1-11 represents a method, claim 12 represents a non-transitory computer readable medium, and claims 13-20 represent a device directed to a homomorphic encryption operation.
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 § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-20 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 1 and 13 – “performing a first NTT operation on a data lane of a fourth root of the N for each of the lane groups” is grammatically unclear which leads the limitation to become indefinite. It is unclear to the examiner whether the limitation is (a) a data lane out of
N
4
data lanes or (b) data lanes whose count equals
N
4
or something else.
Claims 1, 13 – discloses “a data lane” in the first wherein clause, then refers to “the data lane of the first lane group” it is unclear if these are the same data lane. This occurs throughout Claim 1 and 13.
Claim 1, line 10 – discloses “based on the adjustment…” The claim is silent on what adjustment is conducted and how it is based on. This leaves the limitation unclear.
Claim 12 is rejected as being indefinite because it improperly depends on Claim 1, which is a different statutory class.
Claim 12 inherits the rejections of claim 1 as it is a non-transitory computer readable medium performing the operations of the method of claim 1.
Claims 2-11 and 14-20 are rejected due to their dependency on the independent claims.
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 following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
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) or pre-AIA 35 U.S.C. 112, sixth paragraph, 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) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(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) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, 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) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, 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) or pre-AIA 35 U.S.C. 112, sixth paragraph, 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) or pre-AIA 35 U.S.C. 112, sixth paragraph, 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) or pre-AIA 35 U.S.C. 112, sixth paragraph, 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:
Claim 13 – discloses “submodule for an NTT operation”, “transposing and twisting module”, “first NTT unit (NTTU) configured to perform a first operation”, and “a second NTTU configured to perform a second NTT operation”.
Claim 16 – discloses “a twiddle factor feeder configured to provide a twiddle factor used in a butterfly operation of the submodule”
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, 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) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (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) or pre-AIA 35 U.S.C. 112, sixth paragraph.
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-13 are rejected under 35 U.S.C. 101 because the identified claim limitation(s) that recite(s) an abstract idea without significantly more.
Claim 1 recites mathematical calculations intended to perform arithmetic operations on data stored in a table format. The claim discloses “performing a first NTT operation”, “performing a second NTT operation”, “transpose…based on adjustment of a reading order”, “allocating an element of a matrix to a data land” as drafted, is a process that, under its broadest reasonable interpretation, that merely covers mathematical calculations using mathematical formulas but for exception of the recitation of generic computer components. Nothing in the claim element precludes the step of performing the mathematical calculations using generic computational methods such as using pen, paper, calculators and other generic computer products. There is no recitation to the claims to physical hardware and no recitation of how the lane structure improves the computer or solves a technical problem. Claims 12 follows the same analysis as Claim 1.
If a claim limitation, under its broadest reasonable interpretation, covers mathematical concepts but for the recitation of generic computer components, then it falls within the “Mathematical Concepts” grouping of abstract ideas. Accordingly, the claim recites an abstract idea.
This judicial exception is not integrated into a practical application. In particular, the claim recites multiple mathematical concepts such as performing a first and second NTT operation, transposing and allocating an element of a matrix to a data lane at its core is transforming, reordering, and indexing of data. Accordingly, this additional element such as “data lane” or “lane group” does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. There is no recitation of how the lane structures improve the computer or solves a technological problem. The claim is directed to an abstract idea.
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. As discussed above with respect to integration of the abstract idea into a practical application, the additional element of using data lanes or lane groups to perform the computation amounts to no more than mere instructions to apply the exception using a generic computer component. Mere instructions to apply an exception using a generic computer component cannot provide an inventive concept. The claim is not patent eligible. Claim 12 represents a non-transitory computer readable medium, of the limitations presented in Claim 1. It is abstract for the same reasons as Claim 1, and do not integrate the abstract ideas into a practical application or add significantly more to the abstract ideas recited in Claim 1. Claims 2-11 are rejected due to their dependency on Claim 1.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-20 are rejected under 35 U.S.C. 103 as being unpatentable over Feldmann et al. (NPL: F1: A Fast and Programmable Accelerator for Fully Homomorphic Encryption), hereinafter referred to as Feldmann, in view of Wang et al. (NPL: SAM: A Scalable Accelerator for Number Theoretic Transform Using Multi-Dimensional Decomposition), hereinafter referred to as Wang.
Regarding Claim 1, Feldmann discloses:
A method with a number-theoretic transform (NTT) operation (In section 3, Feldmann discloses “F1 features wide-vector execution with functional units (FUs) tailored to primitive FHE operations. Specifically, F1 implements vector FUs for modular addition, modular multiplication, NTTs (forward and inverse in the same unit), and automorphisms.”), the method comprising: allocating an element of a matrix to a data lane such that elements in a first column of the matrix corresponding to a polynomial are allocated to the data lane of a first lane group among lane groups (In section 5.2, Feldmann discloses “To compute an 𝑁 = 𝐸×𝐸 NTT, the unit first computes an 𝐸-point NTT on each 𝐸-element group, multiplies each group with twiddles, transposes the 𝐸 groups, and computes another 𝐸-element NTT on each transpose.” further Feldmann discloses in section 3 “Compute clusters: Functional units are grouped in compute clusters, as Fig. 2 shows.” Wherein the examiner reads the compute clusters as the claimed data lane.), wherein the matrix is a square matrix, and a number of elements comprised in the matrix is N (In section 5.2, Feldmann discloses “compute an 𝑁 = 𝐸×𝐸 NTT, the unit first computes an 𝐸-point NTT on each 𝐸-element group”); performing a first NTT operation on a data lane (In section 5.2, Feldmann discloses “Fig. 8 illustrates our four-step NTT pipeline for 𝐸 = 4; we use the same structure with 𝐸 = 128. The unit is fully pipelined and consumes 𝐸 elements per cycle. To compute an 𝑁 = 𝐸×𝐸 NTT, the unit first computes an 𝐸-point NTT on each 𝐸-element group”); allocating a result of the first NTT operation to the data lane such that the matrix is transposed, based on adjustment of a reading order of a buffer that stores the result of the first NTT operation (In section 5.2, Feldmann discloses “Transpose unite: Our quadrant-swap transpose unit transposes an E x E (e.g., 128 x 128) matrix by recursively decomposing it into quadrants and exploiting the identity (see Figure 7).” and performing a second NTT operation on the data lane (In section 5.2, Feldmann discloses “and computes another 𝐸-element NTT on each transpose.”).
Feldmann discloses the limitations of claim 1, however fails to disclose the fourth root functionality.
Wang discloses:
performing a first NTT operation on a data lane of a fourth root of the N for each of the lane groups (In section II.D, Wang discloses “the NTT operations on each decomposed dimension can be regarded as standalone NTT kernels, and thus decomposed again, expanding the total number of dimensions in a hierarchical and recursive manner. Mathematically, we decompose a size-N NTT into a d-dimensional hypercube, i.e., N = m×nd−1, where m ≤ n represents an incomplete dimension to support more general values of N.”); and performing a second NTT operation on the data lane of the fourth root of the N for each of the lane groups (In section II.D, Wang discloses “the NTT operations on each decomposed dimension can be regarded as standalone NTT kernels, and thus decomposed again, expanding the total number of dimensions in a hierarchical and recursive manner. Mathematically, we decompose a size-N NTT into a d-dimensional hypercube, i.e., N = m×nd−1, where m ≤ n represents an incomplete dimension to support more general values of N.”).
One in ordinary skill in the art of cryptography would have been motivated, before the effective filing date of the claimed invention to modify Feldmann’s approach by utilizing Wang’s approach of implementing a d-dimensional decomposition to the NTT operation as the motivation would be chip-area efficiency and reaching the best utilization by using fewer hardware resources (See Wang, Section II.D.)
Regarding Claim 2, the combination of Feldmann and Wang disclose:
The method of claim 1, wherein the matrix is a matrix having a size of N×N in which N coefficients of the polynomial are stored in a row-majored order (In section 5.2, Feldmann discloses “To compute an 𝑁 = 𝐸×𝐸 NTT, the unit first computes an 𝐸-point NTT on each 𝐸-element group” and further in Section 5.1 “Because F1 uses 𝐸 vector lanes, each residue polynomial is stored and processed as 𝐺 groups, or chunks, of 𝐸 elements each (𝑁=G·𝐸).”).
Regarding Claim 3, the combination of Feldmann and Wang disclose the limitations of claim 1.
However fails to disclose the fourth root functionality.
Wang discloses:
The method of claim 1, wherein the matrix corresponds to a four-dimensional (4D) matrix comprising a submatrix having a size of
N
4
×
N
4
as an element (In section II.D, Wang discloses “Mathematically, we decompose a size-N NTT into a d-dimensional hypercube, i.e., N = m×nd−1, where m ≤ n represents an incomplete dimension to support more general values of N.”)
One in ordinary skill in the art of cryptography would have been motivated, before the effective filing date of the claimed invention to modify Feldmann’s approach by utilizing Wang’s approach of implementing a d-dimensional decomposition to the NTT operation as the motivation would be chip-area efficiency and reaching the best utilization by using fewer hardware resources (See Wang, Section II.D.)
Regarding Claim 4, the combination of Feldmann and Wang disclose the limitations of claim 1.
However fails to disclose the fourth root functionality.
Wang discloses:
The method of claim 1, wherein an element of a submatrix having a size of
N
4
×
N
4
comprised in the matrix is allocated to one type of the data lane (In section III.B. Wang discloses “Each time t planes are processed in the t lanes in parallel. We make each group of these t planes have consecutive base addresses, as shown in Fig. 3.” Further, see Figure 3 for the submatrix).
One in ordinary skill in the art of cryptography would have been motivated, before the effective filing date of the claimed invention to modify Feldmann’s approach by utilizing Wang’s approach of implementing a d-dimensional decomposition to the NTT operation as the motivation would be chip-area efficiency and reaching the best utilization by using fewer hardware resources (See Wang, Section II.D.)
Regarding Claim 5, the combination of Feldmann and Wang disclose the limitations of claim 1.
However fails to disclose the fourth root functionality.
Wang discloses:
The method of claim 1, wherein each of the lane groups comprises
N
4
data lanes, and an element comprised in the first column is allocated to
N
4
data lanes of the first lane group in one cycle of an NTT operation (In section III.B. Wang discloses “In each compute lane of SAM, the NTT pipeline natively processes a size-n NTT operation” and further in Section II.D “Mathematically, we decompose a size-N NTT into a d-dimensional hypercube, i.e., N = m×nd−1, where m ≤ n represents an incomplete dimension to support more general values of N.”)).
One in ordinary skill in the art of cryptography would have been motivated, before the effective filing date of the claimed invention to modify Feldmann’s approach by utilizing Wang’s approach of implementing a d-dimensional decomposition to the NTT operation as the motivation would be chip-area efficiency and reaching the best utilization by using fewer hardware resources (See Wang, Section II.D.)
Regarding Claim 6, the combination of Feldmann and Wang disclose the limitations of claim 1.
However fails to disclose the fourth root functionality.
Wang discloses:
The method of claim 1, wherein an element comprised in
N
4
consecutive columns of the matrix is allocated to one type of a lane group (In section III.B. Wang discloses “We make each group of these t planes have consecutive base addresses, as shown in Fig. 3. The base address of the first plane starts from 0, and increments by t each time, until reaching ndc−1, at which point it is set to ndc+1 (when dc < d−1), and repeats.”).
One in ordinary skill in the art of cryptography would have been motivated, before the effective filing date of the claimed invention to modify Feldmann’s approach by utilizing Wang’s approach of implementing a d-dimensional decomposition to the NTT operation as the motivation would be chip-area efficiency and reaching the best utilization by using fewer hardware resources (See Wang, Section II.D.)
Regarding Claim 7, the combination of Feldmann and Wang disclose:
The method of claim 1, wherein the first NTT operation and the second NTT operation comprise: a butterfly operation on columns of the matrix; a twisting operation; a transpose operation of the matrix; and a butterfly operation on rows of the matrix (In section 5.2, Feldmann discloses “the unit first computes an 𝐸-point NTT on each 𝐸-element group, multiplies each group with twiddles, transposes the 𝐸 groups, and computes another 𝐸-element NTT on each transpose.”)
Regarding Claim 8, the combination of Feldmann and Wang disclose:
The method of claim 1, wherein the first NTT operation and the second NTT operation comprise either one or both of a discrete Fourier transform (DFT) operation and a fast Fourier transform (FFT) operation (In section 5.2, Feldmann discloses “There are many ways to implement NTTs in hardware: an NTT is like an FFT [19] but with a butterfly that uses modular multipliers.”).
Regarding Claim 9, the combination of Feldmann and Wang disclose:
The method of claim 7, wherein the twisting operation is performed based on a twiddle factor corresponding to a geometric sequence of a predetermined common ratio (In section 5.2, Feldmann discloses “we modify the contents of the Twiddle SRAM so that the multiplier does the pre-multiplication necessary to implement a forward NCN in the second NTT (which is DIF and thus requires the pre-multiplication).”).
Regarding Claim 10, the combination of Feldmann and Wang disclose the limitations of claim 1.
However fails to disclose the fourth root functionality.
Wang discloses:
The method of claim 1, wherein a number of the lane groups is determined to be at least one and less than or equal to a fourth root of the N (In section III.A. Wang discloses “We use t to denote the number of lanes instantiated in SAM. Section IV discusses how to concretely set the above design parameters, n, t, b.”).
Regarding Claim 11, the combination of Feldmann and Wang disclose:
The method of claim 1, further comprising storing a result of the second NTT operation in a register file (RF) (In section 3, Feldmann discloses “Compute clusters: Functional units are grouped in compute clusters, as Fig. 2 shows. Each cluster features several FUs (1 NTT, 1 automorphism, 2 multipliers, and 2 adders in our implementation) and a banked register file”).
Claim 12 is directed to a non-transitory computer-readable storage medium having functionality corresponding to the method of Claim 1, and is rejected by a similar rationale, mutatis mutandis.
Regarding Claim 13, Feldmann discloses:
A number-theoretic transform (NTT) operator electronic device (In figure 1, Feldmann discloses an F1 FHE accelerator) comprising: a data lane to which an element of a matrix corresponding to a polynomial is allocated (In section 3, Feldmann discloses “FUs process vectors of configurable length 𝑁 using a fixed number of vector lanes E”), wherein the matrix is a square matrix, and a number of elements comprised in the matrix is N (In section 5.2, Feldmann discloses “compute an 𝑁 = 𝐸×𝐸 NTT, the unit first computes an 𝐸-point NTT on each 𝐸-element group”); a submodule for an NTT operation corresponding to a lane group(In section 5.2, Feldmann discloses “Fig. 8 illustrates our four-step NTT pipeline for 𝐸 = 4; we use the same structure with 𝐸 = 128. The unit is fully pipelined and consumes 𝐸 elements per cycle. To compute an 𝑁 = 𝐸×𝐸 NTT, the unit first computes an 𝐸-point NTT on each 𝐸-element group”); and a transposing and twisting module corresponding to the submodule (In section 5.2, Feldmann discloses “the unit first computes an 𝐸-point NTT on each 𝐸-element group, multiplies each group with twiddles, transposes the 𝐸 groups, and computes another 𝐸-element NTT on each transpose.”), wherein the submodule comprises a first NTT unit (NTTU) configured to perform a first NTT operation on the data lane of the fourth root of the N and a second NTTU configured to perform a second NTT operation (In section 5.2, Feldmann discloses “and computes another 𝐸-element NTT on each transpose.”).
However fails to disclose the fourth root functionality.
Wang discloses:
a submodule for an NTT operation corresponding to a lane group comprising a data lane of a fourth root of the N (In section II.D, Wang discloses “the NTT operations on each decomposed dimension can be regarded as standalone NTT kernels, and thus decomposed again, expanding the total number of dimensions in a hierarchical and recursive manner. Mathematically, we decompose a size-N NTT into a d-dimensional hypercube, i.e., N = m×nd−1, where m ≤ n represents an incomplete dimension to support more general values of N.”); wherein the submodule comprises a first NTT unit (NTTU) configured to perform a first NTT operation on the data lane of the fourth root of the N and a second NTTU configured to perform a second NTT operation on the data lane of the fourth root of the N (In section II.D, Wang discloses “the NTT operations on each decomposed dimension can be regarded as standalone NTT kernels, and thus decomposed again, expanding the total number of dimensions in a hierarchical and recursive manner. Mathematically, we decompose a size-N NTT into a d-dimensional hypercube, i.e., N = m×nd−1, where m ≤ n represents an incomplete dimension to support more general values of N.” and further in Section III.B. “The hardware then starts a round of processing on the 2-D planes of the dimensions dc and dc−1, including the row and column NTT operations and the twiddle factor multiplications.”).
One in ordinary skill in the art of cryptography would have been motivated, before the effective filing date of the claimed invention to modify Feldmann’s approach by utilizing Wang’s approach of implementing a d-dimensional decomposition to the NTT operation as the motivation would be chip-area efficiency and reaching the best utilization by using fewer hardware resources (See Wang, Section II.D.)
Regarding Claim 14, the combination of Feldmann and Wang disclose:
The electronic device of claim 13, wherein the transposing and twisting module further comprises a buffer configured to store an operation result of the first NTTU (In section 5.2, Feldmann discloses “Transpose unite: Our quadrant-swap transpose unit transposes an E x E (e.g., 128 x 128) matrix by recursively decomposing it into quadrants and exploiting the identity (see Figure 7).”
Regarding Claim 15, the combination of Feldmann and Wang disclose:
The electronic device of claim 13, further comprising a register configured to store an operation result of the second NTTU (In section 3, Feldmann discloses “Compute clusters: Functional units are grouped in compute clusters, as Fig. 2 shows. Each cluster features several FUs (1 NTT, 1 automorphism, 2 multipliers, and 2 adders in our implementation) and a banked register file”).
Regarding Claim 16, the combination of Feldmann and Wang disclose:
The electronic device of claim 13, wherein the submodule further comprises a twiddle factor feeder configured to provide a twiddle factor used in a butterfly operation of the submodule (In Figure 8, Feldmann discloses a “Twiddle SRAM” that feeds directly into the multiplier (i.e. butterfly operation)).
Regarding Claim 17, the combination of Feldmann and Wang disclose:
The electronic device of claim 13, wherein the first NTT operation and the second NTT operation comprise: a butterfly operation on columns of the matrix; a twisting operation; a transpose operation of the matrix; and a butterfly operation on rows of the matrix. (In section 5.2, Feldmann discloses “the unit first computes an 𝐸-point NTT on each 𝐸-element group, multiplies each group with twiddles, transposes the 𝐸 groups, and computes another 𝐸-element NTT on each transpose.”)
Regarding Claim 18, the combination of Feldmann and Wang disclose:
The electronic device of claim 13, wherein the first NTT operation and the second NTT operation comprise either one or both of a discrete Fourier transform (DFT) operation and a fast Fourier transform (FFT) operation. (In section 5.2, Feldmann discloses “There are many ways to implement NTTs in hardware: an NTT is like an FFT [19] but with a butterfly that uses modular multipliers.”).
Claims 19 and 20 are directed to a device having functionality corresponding to the method of Claims 5 and 6, and is rejected by a similar rationale, mutatis mutandis.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Sadrossadat et al. (US 20230229801) discloses a method for a string matching leveraging number theoretic transform (NTT) operations.
Khedr et al. (US 11537601) discloses a method for a Configurable Number Theoretic Transform (NTT) Butterfly Circuit 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 /RUPAL DHARIA/Supervisory Patent Examiner, Art Unit 2492
Prosecution Insights