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 .
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 because the claimed invention is directed to an abstract idea without significantly more. The claim(s) recite(s) mathematical calculations.
The following rejection finds basis in the most recently issued guidance published in the Federal Register on 7 January 2019 entitled “2019 Revised Patent Subject Matter Eligibility Guidance”, available at <https://www.federalregister.gov/documents/2019/01/07/2018-28282/2019-revised-patent-subject-matter-eligibility-guidance>. The 2019 Revised Patent Subject Matter Eligibility Guidance applies the subject matter eligibility test as described within recently revised MPEP § 2106, revision 08.2017, namely, the “Alice/Mayo test” or “Mayo test” as laid out by the Supreme Court as a framework for determining claimed subject matter eligibility. See Alice Corp. Pty. Ltd. v. CLS Bank Int'l, 573 U.S. _, 134 S. Ct. at 2355, 110 USPQ2d at 1981 (citing Mayo, 566 U.S. 66, 101 USPQ2d 1961). Note that the 2019 Revised Patent Subject Matter Eligibility Guidance also supersedes all versions of the USPTO's “Eligibility Quick Reference Sheet Identifying Abstract Ideas” (first issued in July 2015 and updated most recently in July 2018).
A. Claim 1 is analyzed according to SME flowchart. Claim 1 is directed to a processing system performing fast number theoretic transform (NTT) using matrix multiplication. According to step 1, the system of claim 1 comprises computing circuits for performing mathematical calculations using NTT using a matrix multiplication calculation. Claim 1 also comprises computing circuits for performing matrix multiplication for NTT. The system of claim 1 fits one of the statutory categories and claim 1 qualifies as a machine
B. When considering step 2A, prong 1, claim 1 recites an abstract idea. The type of abstract is categorized under a mathematical computations. The system of claim 1 is directed to the mathematical calculations for performing fast number theoretic transform (NTT) calculation on a polynomial using matrix multiplication using NTT. Dependent claim 2 recites memory for storing and a conversion circuit for converting input data into an input matrix in vector form of a target dimension which is greater than 1. Implementing a multidimensional NTT. The computing circuitry converts matrix-vector multiplication into a multi-stage calculations through a plurality of one sub-calculation computing circuits. With respect to dependent claims 2-10, the performing fast number theoretic transform (NTT) is a mathematical calculation. Each of the sub-calculations, one stage conversion circuit, butterfly circuit and twiddle factor does not impact the mathematical calculations and does not advance computer technology.
C. The additional features of claim 1 are considered in step 2A, prong 2. The additional features of claim 1 are considered for determination of whether the claims are integrated in a practical application. The first addition feature is the implementation on a plurality of computing circuits. The computing circuits are used a tool for implementing the functions claimed not to make an improvement to computer technology. The second additional limitation is calculating a matrix multiplication through the fast number theoretic transform calculation which is insignificant post processing and extra solution activity. The matrix multiplication and performing theoretic transform calculation are not an improvement in computer technology. Thus, claim 1 fails to recite additional features to integrate into a practical application in a technological environment or field of use. Dependent claims 2-3 recite further a memory circuit for storing data and a data conversion circuit for converting the form of input into another dimension of data and transforming a vector to matrix. The additional limitation is the fast number theoretic transform calculation which is insignificant post processing and extra solution activity. Dependent claims 4-5 recites different types of circuits including staged circuits, twiddle circuits, and/or transposition circuit. Dependent claims 6-9 recites multidimensional calculations. Dependent claim 10 recites stage circuit, conversion circuit and memory circuit. The mathematical concepts and listening of different circuits fails to integrate 2-10 into a practical application.
D. The additional limitations of claim 1 are considered in Step 2B. Claim 1 does not recite additional limitations the amount to more than the judicial exception. One additional limitation is the concept of fast theoretic transform calculation. Dependent claims 2-4, recite further types of data structures including “target dimension” of input data which indicates size. Dependent claims 6-10, recites the computations of matrix-vector multiplication, butterfly computation, multiplication computation, twiddle factor and switching position. Distributed types of circuits for sub-calculation and accessing memory for storage. Dependent claim 5, recites arranging the data units in another dimension and performing multi-dimensional fast number theoretic transform. The calculations and circuits operating on the data as recited in claims 2-10 fail to provide an improvement to computer network technology.
E. Claim 11 is analyzed according to SME flowchart. Claim 11 is directed to a method. According to Step 1 of SME flowchart, claim 11 is the method comprises steps corresponding to operations of claim 1. Claim 11 fits at least one of the categories. Claim 11 qualifies as a process performing fast number theoretic transform (NTT) using matrix multiplication. According to step 1, the method of claim 11 comprises steps for performing mathematical calculations using NTT using performed on a multi-stage computation architecture. Claim 11 also comprises a plurality of sub-calculations and a t least one computing circuit for the sub-calculations. The method of claim 11 fits one of the statutory categories and claim 1 qualifies as a process.
F. When considering step 2A, prong 1, claim 11 recites an abstract idea. The additional features of claim 11 are considered for determination of whether the claims are integrated in a practical application. The first addition feature is the implementation on a plurality of computing circuits. The computing circuits are used a tool for implementing the functions claimed not to make an improvement to computer technology. The second additional limitation is calculating a matrix multiplication through the fast number theoretic transform calculation which is insignificant post processing and extra solution activity. The matrix multiplication and performing theoretic transform calculation are not an improvement in computer technology. Thus, claim 11 fails to recite additional features to integrate into a practical application in a technological environment or field of use. Dependent claims 12-13 recite further a memory circuit for storing data and a data conversion circuit for converting the form of input into another dimension of data and transforming a vector to matrix. The additional limitation is the fast number theoretic transform calculation which is insignificant post processing and extra solution activity. Dependent claims 14-15 recites different types of circuits including staged circuits, twiddle circuits, and/or transposition circuit. Dependent claims 16-19 recites multidimensional calculations. Dependent claim 20 recites stage circuit, conversion circuit and memory circuit. The mathematical concepts and listening of different circuits fails to integrate 12-20 into a practical application.
G. The additional features of claim 11 are considered in step 2A, prong 2. The additional features of claim 11 are considered for determination of whether the claims are integrated in a practical application. The first addition feature is the implementation on a plurality of computing circuits. The computing circuits are used a tool for implementing the functions claimed not to make an improvement to computer technology. The second additional limitation is calculating a matrix multiplication through the fast number theoretic transform calculation which is insignificant post processing and extra solution activity. The matrix multiplication and performing theoretic transform calculation are not an improvement in computer technology. Thus, claim 11 fails to recite additional features to integrate into a practical application in a technological environment or field of use. Dependent claims 12-13 recite further a memory circuit for storing data and a data conversion circuit for converting the form of input into another dimension of data and transforming a vector to matrix. The additional limitation is the fast number theoretic transform calculation which is insignificant post processing and extra solution activity. Dependent claims 14-15 recites different types of circuits including staged circuits, twiddle circuits, and/or transposition circuit. Dependent claims 16-19 recites multidimensional calculations. Dependent claim 20 recites stage circuit, conversion circuit and memory circuit. The mathematical concepts and listening of different circuits fails to integrate 12-20 into a practical application.
H. The additional limitations of claim 11 are considered in Step 2B. Claim 11 does not recite additional limitations the amount to more than the judicial exception. One additional limitation is the concept of fast theoretic transform calculation. Dependent claims 12-14, recite further types of data structures including “target dimension” of input data which indicates size. The computations of matrix-vector multiplication, butterfly computation, multiplication computation, twiddle factor and switching position. Distributed types of circuits for sub-calculation. Further additions of twiddle factors. calculating delay which is another instance of post processing activity. Dependent claim 15, recites arranging the data units in another dimension and performing multi-dimensional fast number theoretic transform. Dependent claims 12-20 fail to integrate the invention into as improvement to computer network technology.
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.
Claim(s) 1-2, 11-12, and 20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Bisheh et al., US 20240413995 A1 (hereafter referred to as Bisheh) in view of Gulak et al., US 20170293913 A1 (hereafter referred to as Gulak).
A. Claim 1, Bisheh teaches a processing system related to encryption (p. 81, “a first device, such as the device 880 performs key generation to generate a secret key (sk) 898 and a public key (pk) 812, using keygen circuit 884.”), comprising:
a plurality of computing circuits, performing a fast number theoretic transform (NTT) calculation on a polynomial (p. 49, “FIGS. 4 and 5 present further details of an architecture of a proposed NTT/INTT operator circuit.” And p. 50, “1) Butterfly Core Level: A reconfigurable butterfly core (sometimes called a butterfly operator or a butterfly circuit or a butterfly operator circuit) is proposed to support both CT and GS operations, which are used for NTT and INTT, respectively, such as to employ resource-sharing techniques and avoid the bit-reverse cost in polynomial multiplication.” See also p. 51, “A circuit, illustrated in FIGS. 4 and 5 can be configured with a selectable number of butterfly operator circuits.” And p. 82, “This architecture 800 includes NTT operator circuits 808 and 838, INTT operator circuits 822, 830, and 848, coefficient-wise polynomial multiplier 810, 828, and 848, Keccak-f[1600] 802 and 840, binomial centered distribution (CBD) 804 and 836, rejection sampler 806 and 844, and compress units 818 and 850, decompress units 814 and 832, adder 834, and subtractor 816.”), comprising:
performing a matrix multiplication calculation on the polynomial through the fast number theoretic transform calculation (p. 58, “FIG. 4 illustrates the NTT/INTT operation circuit at a polynomial level. Most lattice-based applications require performing NTT/INTT computation of a vector/matrix of polynomials. The NTT/INTT operations for each polynomial can be performed independently.”). Bishah teaches fast computation using NTTT/INTT circuits but does not specifically teach fast NTT algorithm. However, in the same field of endeavor, Gulak teaches using a fast NTT algorithm (p. 72, “To multiply ciphertexts, it is advantageous to use the fast NTT algorithm to speed up the ciphertext multiplication operation, as opposed to using regular polynomial circular convolution.” And p. 155, “A suitable hardware device may be configured to implement the computational techniques discussed herein using, for example, Chinese Remainder Theorem (CRT), Number Theoretic Transform (NTT), one or more memory blocks, one or more memory interfaces, matrix multiplications, matrix additions, or a combination of such.”). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Bishah to incorporate fast NTT algorithm from Gulak for the NTT from Bisheh to speed up the ciphertext multiplication used in encryption and thereby improve system responsiveness.
Claim 11 is a method that performs steps similar to the operations of claim 1 above. Claim 11 is rejected on a similar rationale.
B. Claim 2, Bisheh-Gulak teaches the processing system related to encryption according to claim 1, further comprising:
at least one memory (Bisheh, p. 59, “The circuit 500 as illustrated includes a polynomial memory 550, a twiddle factor memory 552, a pipelined polynomial circuit 554, a multiplexer 556, and the stage 558.”), coupled to the computing circuits and configured to store data (p. 60, “The polynomial memory 550 stores coefficients of polynomials to be converted to the NTT domain and converted back from the NTT domain. The pipelined polynomial circuit 554 includes circuitry to organize input from the polynomial memory 550.”);
a data conversion circuit, coupled to the at least one memory and the computing circuits (Bisheh, p. 60, “The pipelined polynomial circuit 554 includes circuitry to organize input from the polynomial memory 550. The pipelined polynomial circuit 554 organizes the input so that the butterfly operator circuits 300A, 300B, 300C receive the correct input coefficients.”), and configured to convert input data into an input matrix according to a target dimension (Bisheh, p. 60, “The pipelined polynomial circuit 554 includes circuitry to organize input from the polynomial memory 550.” And p. 58, “FIG. 4 illustrates the NTT/INTT operation circuit at a polynomial level. Most lattice-based applications require performing NTT/INTT computation of a vector/matrix of polynomials. The NTT/INTT operations for each polynomial can be performed independently.”),
wherein the input data is factors of the polynomial and is in vector form, the target dimension is greater than one dimension (Bishah, p. 62, “Let a and b be polynomial vectors in Rq a○ b ∈ Rq denote coefficient-wise multiplication of polynomials. The product of a matrix and a vector is the natural extension of coefficient-wise multiplication of the polynomial vectors.”), the fast number theoretic transform calculation is multi-dimensional fast number theoretic transform (Gulak, p. 72, “To multiply ciphertexts, it is advantageous to use the fast NTT algorithm to speed up the ciphertext multiplication operation, as opposed to using regular polynomial circular convolution.”), and the computing circuits are further configured to:
perform the multi-dimensional fast number theoretic transform of the target dimension on the input matrix (Gulak, p. 31, “BD (Matrix of polynomials) takes an input matrix of polynomials of size x×y (each polynomial is of size n with integer coefficients), then outputs a matrix of polynomials expanded by a factor l in the column dimension, yielding a matrix of size x×yl, where each consecutive l elements along the row contain the bit representation of each coefficient of each of the input polynomials.”), wherein the multi-dimensional fast number theoretic transform (in combination with Gulak) converts matrix-vector multiplication into a multi-stage computation architecture of the matrix multiplication calculation through a plurality of sub-calculations (Bisheh, p. 52, “2) Stage Level: The NTT computation of a polynomial of degree n includes log n stages of n/2 butterfly circuit 300 operations. The operation of n/2 butterfly circuits 300 provides n results since each butterfly circuit 300 provides 2 outputs. The number of stages is thus S=log n. Each of the stages uses output of the preceding stage as its input. Memory access to output of the previous result is thus an important potential bottleneck in stage level implementation.”), one computing circuit performs one sub-calculation, and each of the sub-calculations is located at one stage of the multi-stage computation architecture (See Figure 4, p. 54-55, “The throughput of the stage level 446, 448, 450 is proportional to the number of butterfly circuits 300A, 300B, 300C, 300D. Let ncore be the number of implemented butterfly circuits 300A, 300B, 300C, 300D in the stage level 446, 448, 450. Given full utilization of butterfly cores, 2n.sub.core coefficients are transformed in tcore. The architecture 400 uses an interleaved stage architecture with parallel register banks embedded into the butterfly circuit 300. The parallel register banks help avoid memory access limitations during stage 446, 448, 450 setup operations.”).
Claim 12 is a method that performs steps similar to the operations of claim 2 above. Claim 12 is rejected on a similar rationale.
C. Claim 10, Bisheh -Gulak teaches the processing system related to encryption according to claim 2, wherein the computing circuits comprise a stage conversion circuit (Bisheh, p. 60, “stage 558”) and a memory circuit (Bisheh, p. 60, “polynomial memory 550”), a sub-computation of the stage conversion circuit is a butterfly computation (Bisheh, p. 60, “The pipelined polynomial circuit 554 organizes the input so that the butterfly operator circuits 300A, 300B, 300C receive the correct input coefficients. The pipeline polynomial circuit 554 provides the relevant coefficients to the multiplexer 556.”), and a sub-computation of the memory circuit is to store data to the at least one memory (Bisheh, p. 55, “The parallel register banks help avoid memory access limitations during stage 446, 448, 450 setup operations.”).
Claim 20 is a method that performs steps similar to the operations of claim 10 above. Claim 20 is rejected on a similar rationale.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Liu et al., US 20240146517 A1, teaches the hash module 31 and the configurable sampling module 32 are configured to process the data into polynomial data. The fast NTT module 33 is configured to accelerate an operation of the polynomial data into terminal data.
Ren et al., US 20240048352 A1, teaches FIG. 2 shows program codes for performing the number field transform on 2N-dimensional polynomial P1 according to Cooley's and Tukey's number theoretic transform algorithm, where N denotes an integer greater than 1.
Hamburg et al., US 20230254115 A1, teaches A Fast NTT (similar to the FFT) amounts to first computing N /2 2-point transforms (a first iteration), followed by computing N/4 4-point transforms (a second iteration), and so on, until the last iteration where the ultimate N-point transform is obtained (log.sub.2 N-th iteration), as explained in more details in reference to FIGS. 2 and 3.
Khedr et al., US 20180294950 A1, teaches the multifunctional butterfly unit 300 provides circuitry for transforming ciphertexts (Ctxt) into number theoretic transforms (NTTs). For certain embodiments, the unit may also serve as an INTT engine to transform NTTs back to ciphertexts.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to PATRICE L WINDER whose telephone number is (571)272-3935. The examiner can normally be reached M-F 10am-6pm.
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, KAMAL B DIVECHA can be reached at (571)272-5863. 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.
/Patrice L Winder/Primary Examiner, Art Unit 2453