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 .
Detailed Action
Claims 1, 8, 9, 10, 17, and 20 are amended
Claims 1-20 are pending
Priority
This application claims the benefit of U.S. Provisional Patent Application No. 63/529,243, filed Jul. 27, 2023. Therefore, the effective filing date of this application is 07/27/2023.
Response to Arguments
Applicant’s arguments filed on 07/01/2026 have been fully considered.
With respect to the claim objection for claim 17. The objection has been overcome due to Applicant’s amendments.
With respect to the USC 112(b) rejection for claims 1-20. Most rejections have been overcome. However, claims 9 and 20 are still being rejected due to Applicant not amending all limitations to overcome the 112(b) issues.
With respect to the USC 101 abstract rejection for claims 1-20. Applicant has argued that the amended limitation of “and wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device, or a digital signature for the digital communication between the processing device and the additional processing device” overcomes the abstract rejection. Examiner respectfully disagrees. The limitation “or a digital signature for the digital communication between the processing device and the additional processing device” recites of obtaining from an output of a cryptographic operation a digital signature. This feature recites a computation that can be performed by a user. Obtaining a digital signature simply recites obtaining data. This limitation does not recite establishing a secure channel or utilizing the digital signature in manner that cannot be performed abstractly. As for the limitation “and wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device” Examiner believes this limitation is sufficient to overcome the 101 abstract rejection. Examiner suggests removing the “or” and replacing it with an “and” or either removing the limitation “or a digital signature for the digital communication between the processing device and the additional processing device” in its entirety.
With respect to the USC 103 rejection Applicant has argued that JOYE-VIGILANT fail to teach of the use of masking polynomials associated with a kernel of homomorphism. Examiner respectively disagrees. JOYE teaches a kernel of a homomorphism transformation from the auxiliary domain to the working domain; ([JOYE, para. 0092] “The figure shows the two polynomials f, 241 and g, 243, represented in the coefficient domain”) ([JOYE, para. 0093] “To multiply the polynomials, a number-theoretic transform NTT, 233, may be applied to convert the polynomials into a Fourier domain.”) Examiner is interpreting homomorphic transformation as a mapping between two algebraic structures that preserves the underlying operations. A Fourier transformations is a homomorphic transformation. Every homomorphic transform between algebraic structures has a kernel. A kernel is a measurement of how much information is lost in the mapping. The kernel of transformation in the Fourier domain is the exponential function. The working domain is the Fourier domain and the auxiliary domain is the non-Fourier domain. Therefore, JOYE’s teaching of converting polynomials into a Fourier domain teaches this limitation.
Applicant has further argued that JOYE-VIGILANT fail to teach the limitation of “mapping, to an auxiliary domain, each of (i) a first polynomial associated with a first data and defined on a working domain and (2) a second polynomial associated with a second data and defined on the working domain, wherein the working domain has a first dimension and the auxiliary domain has a second dimension that is greater than the first dimension”. Examiner respectfully disagrees. JOYE teaches of ([JOYE, para. 0091] “FIG. 2 schematically shows an example of an embodiment of a method of computing a polynomial product of two polynomials f(X) and g(X). The two polynomials in this example are defined modulo a quotient polynomial p(X).”) ([JOYE, para. 0093] “To multiply the polynomials, a number-theoretic transform NTT, 233, may be applied to convert the polynomials into a Fourier domain. The figure shows Fourier-domain representation 242 of polynomials 241 and Fourier-domain representation 244 of polynomial 243.”) the conversion from the non-Fourier domain to the Fourier domain is a conversion from a auxiliary domain to a working domain. Therefore, JOYE teaches of this limitation. Furthermore, the claim language recited in this limitation is broad. Examiner suggests amending the claim to better define what is meant by “auxiliary domain”, “working domain”, “first dimension”, and “second dimension” to help better differentiate from the cited prior arts. JOYE teaches ([JOYE, para. 0109] “Denoting the degree of p(X) as N, the coefficient representation of a polynomial may comprise N elements, whereas the Fourier domain representation may comprise M elements. … If M>N,”) ([JOYE, para. 0093] “To multiply the polynomials, a number-theoretic transform NTT, 233, may be applied to convert the polynomials into a Fourier domain. The figure shows Fourier-domain representation 242 of polynomials 241 and Fourier-domain representation 244 of polynomial 243. Typically, a Fourier-domain representation of the polynomial 241, 243 comprises evaluations of the polynomial in powers of a primitive root of unity from a finite ring, e.g., the ring from which the coefficients of the polynomials 241, 243 are selected or to which they correspond.”) the coefficients of the Fourier domain being greater teaches of a higher second dimension.
Applicant has further argued that the combination of JOYE and VIGILANT is incoherent. Examiner respectfully disagrees. Both references relate to polynomial masking and computation. VIGILANT further recognizes the need to counter side channel attacks. ([VIGILANT, para. 0004] “A commonly used countermeasure against side-channel attacks is the masking of the intermediate values of an encryption process with a random mask.”) ([VIGILANT, para. 0006] “there is a need for a masking scheme applicable to polynomial coefficients in order to protect it against side-channel analysis, and compatible with both polynomial additions and multiplications.”) ([VIGILANT, para. 0007] “this invention therefore relates to a method secured against side channel attacks performing a cryptographic operation of a cryptographic algorithm”)
Applicant has further argued with respect to claim 10. That VIGILANT -LI fail to teach “masking polynomials with coefficients divisible by the first modulus and defined modulo a second modulus that is greater than the first modulus”. Applicant has further mentioned that this limitation is inseparable limitation. Examiner respectfully disagrees. LI teaches this limitation as seen in the following citations ([LI, para. 0065] “at the integer generation step S11, before generating concatenated integers, the coefficients of the input polynomials are masked using a multiplicative masking. For example, each coefficient of A[X] ai with i in {0, . . . , Nc−1} may be multiplied by a random mask rnd modulo q with q=2^Nb”) ([LI, para. 0006] “a polynomial multiplication between a first input polynomial A[X] and a second input polynomial B[X], wherein the first input polynomial A[X] and the second input polynomial B[X] comprise Nc coefficients and said coefficients of the first and second input polynomials are of size Nb bits, with Nc and Nb non-zero integers”) ([LI, para. 0068] “By doing so the product of the mask coefficients with the same index is equal to the product of the original coefficients of this index plus a random value depending on rnd1 and rnd2 that is a multiple of q”). The teaching of rnd1 and rnd2 teaches of first modulus and second modulus. Furthermore, the combination of VIGILANT and LI is proper, and LI recognizes the need to improve polynomial multiplication. ([LI, para. 0005] “There is a need for a method enabling to compute polynomial multiplications between large polynomials at a lower cost than existing methods.”) ([LI, para. 0006] “this invention therefore relates to a method for performing a cryptographic algorithm, performed by a cryptographic device comprising a cryptographic co-processor comprising an integer multiplier”)
With respect to the newly amended limitation of “and wherein the first data is associated with a digital communication between the processing device and an additional processing device” JOYE further teaches this limitation ([JOYE, 0080] “The devices 111 and/or 112 in this example may each be based on device 110 of FIG. 1 a , e.g., may each comprise processor system 130, storage 140, and/or communication interface 150 of FIG. 1 a.”) ([JOYE, 0084] “ For example, encrypted computing device 112 may be operated by a cloud provider. The cloud provider may offer computation and storage services to its clients. By employing homomorphic encryption, data provider device 160 of FIG. 1 b , e.g., a client of the cloud provider, can send their data in encrypted form.”)
With respect to the newly amended limitation of “and wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device, or a digital signature for the digital communication between the processing device and the additional processing device.” JOYE further teaches this limitation ([JOYE, para. 0162] “Encrypted multiplication unit 332 may output the computed polynomial products in various formats as desired. For example, the polynomial products may be output in their Fourier domain representation 354, or, as shown in the figure, INNT unit 334 may be used to apply an inverse number theoretic transform in order to convert representations 354 of some or all of the computed polynomial products in the Fourier domain to coefficient representations 353.”) ([JOYE, para. 0184] “For example, encrypted computing device 112 may be operated by a cloud provider. The cloud provider may offer computation and storage services to its clients. By employing homomorphic encryption, data provider device 160 of FIG. 1 b , e.g., a client of the cloud provider, can send their data in encrypted form. The cloud provider can still perform the required computations, and/or the required storage”) ([JOYE, para. 0084] “ For example, data provider device 160 may use an encryption key of a type corresponding to the particular homomorphic encryption system used to encrypt the data items. When computations results are received by data-provider 160 from encrypted computing device 112, a corresponding decryption key may be used to decrypt the encrypted data items. Encryption and decryption keys may be the same- and typically are so.”)
Therefore, JOYE teaches the newly amended limitations. Furthermore, JOYE-VIGILANT teach all limitations of claim 1, VIGILANT-LI-JOYE teach all limitations of claim 10, and JOYE-VIGILANT-BAJPEYI teach all limitations of claim 17. Examiner suggests further amending the claim to better differentiate from the cited prior arts.
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.
Claims 1-20 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.
Claim 9 recites the limitation "the first modulus". There is insufficient antecedent basis for this limitation in the claim. For the purpose of examination Examiner is interpreting this limitation as “a first modulus”. Appropriate correction is required.
Claim 20 recites the limitation “the second NTT ". There is insufficient antecedent basis for this limitation in the claim. For the purpose of examination Examiner is interpreting this limitation as “a second NTT”. Appropriate correction is required.
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 they directed to an abstract idea.
Claim 1 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. The claim recites a judicial exception (an abstract idea) that is not integrated into a practical application.
Step 1: Statutory Category
Claim 1 satisfied the statutory category requirement because it is directed to a “method” or “process” under 35 U.S.C. 101(a). The claim recites a series of steps to perform a cryptographic operation.
Step 2A, Prong 1 – Judicial Exception (Abstract Area)
The claim recites a method to perform a cryptographic operation, the method comprising: mapping, using a processing device, to an auxiliary domain, each of (i) a first polynomial associated with first data and defined on a working domain and (2) a second polynomial associated with second data and defined on the working domain, wherein the working domain has a first dimension and the auxiliary domain has a second dimension that is greater than the first dimension, and wherein the first data is associated with a digital communication between the processing device and an additional processing device; masking, using the processing device, the first mapped polynomial with a first masking polynomial to obtain a first masked polynomial; masking, using the processing device, the second mapped polynomial with a second masking polynomial to obtain a second masked polynomial, wherein the first masking polynomial and the second masking polynomial are associated with a kernel of a homomorphism transformation from the auxiliary domain to the working domain; performing, using the processing device, one or more computations in the auxiliary domain based at least on the first masked polynomial and the second masked polynomial; and obtaining, using the processing device, an output of the cryptographic operation, wherein obtaining the output comprises transforming an output of the one or more computations from the auxiliary domain to the working domain, and wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device, or a digital signature for the digital communication between the processing device and the additional processing device.
The limitation of mapping, using a processing device, to an auxiliary domain, each of (i) a first polynomial associated with first data and defined on a working domain and (2) a second polynomial associated with second data and defined on the working domain, wherein the working domain has a first dimension and the auxiliary domain has a second dimension that is greater than the first dimension, and wherein the first data is associated with a digital communication between the processing device and an additional processing device, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can be performed in the mind. A user can manually map to an auxiliary domain a first polynomial and a second polynomials and determine the first data is associated with a digital communication.
The limitation of masking, using the processing device, the first mapped polynomial with a first masking polynomial to obtain a first masked polynomial, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can be performed in the mind. A user can manually mask the first mapped polynomial with a first masking polynomial to obtain a first masked polynomial.
The limitation of masking, using the processing device, the second mapped polynomial with a second masking polynomial to obtain a second masked polynomial, wherein the first masking polynomial and the second masking polynomial are associated with a kernel of a homomorphism transformation from the auxiliary domain to the working domain, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can be performed in the mind. A user can manually mask the second mapped polynomial with a second masking polynomial to obtain a second masked polynomial.
The limitation of performing, using the processing device, one or more computations in the auxiliary domain based at least on the first masked polynomial and the second masked polynomial, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can be performed in the mind. A user can manually perform using the first masked polynomial and the second masked polynomial, one or more computations.
The limitation of obtaining, using the processing device, an output of the cryptographic operation, wherein obtaining the output comprises transforming an output of the one or more computations from the auxiliary domain to the working domain, and wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device, or a digital signature for the digital communication between the processing device and the additional processing device., as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can be performed in the mind. A user can manually obtain an output of the cryptographic operation, wherein the output is a digital signature.
Therefore claim 1 recites of multiple judicial exceptions within the abstract idea category.
Step 2A, Prong 2 – Integration into a practical Application
This judicial exception is not integrated into a practical application. The claim recites of limitations of mapping, masking, performing computation, and obtaining an output of a cryptographic operation. The claim does not recite any limitation to implement these limitations into a practical application. The specification of the current application recites of side-channel attacks. However, the claim does not recite of limitation showing how a side-channel attack can be prevented using the steps of the method. Merely, performing mapping, masking, and computation does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. The claim is directed to an abstract idea.
Step 2B- “Significantly More” (Inventive concept)
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. In particular, the claim only recites one additional element of “processing device” recited at a high-level of generality (i.e., as a generic processing device implementing the method) such that it amounts no more than mere instructions to apply the exception using a generic processing device. Mere instructions to apply an exception using a generic processing device cannot provide an inventive concept. The claim is not patent eligible.
Claim 2 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein coefficients of each of the first polynomial and the second polynomial are defined modulo a first modulus in the working domain, wherein coefficients of each of the first masked polynomial and the second masked polynomial are defined modulo a second modulus in the working domain, and wherein the first modulus divides the second modulus. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually determine coefficients of each of the first polynomial and the second polynomial and coefficients of first masked polynomial and the second masked polynomial.
Claim 3 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein masking the first mapped polynomial with the first masking polynomial comprises adding a product of the first modulus and each of a plurality of randomly-sampled coefficients of the first masking polynomial to a respective same-degree coefficient of the first mapped polynomial. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually mask the first mapped polynomial with the first masking polynomial.
Claim 4 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein the second modulus is randomly sampled from a target range of values. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually determine the second modulus is randomly sampled from a target range of values.
Claim 5 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein the target range of values is determined by at least one of: a bit size of one or more registers storing coefficients of the first masked polynomial; or an operand size of a processing unit that performs the one or more computations in the auxiliary domain. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually determine target range of values based on bit size or operand size.
Claim 6 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein the one or more computations in the auxiliary domain comprise a first Number Theoretic Transform (NTT) of the first masked polynomial, and a second NTT of the second masked polynomial. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually perform Number Theoretic Transform (NTT) of polynomials.
Claim 7 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein the one or more computations in the auxiliary domain further comprise: an elementwise multiplication of the first NTT and the second NTT, and an inverse NTT of an output of the elementwise multiplication of the first NTT and the second NTT. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually perform elementwise multiplication of the first NTT and the second NTT and an inverse NTT of an output of the elementwise multiplication.
Claim 8 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein the first NTT and the second NTT are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein one or more twiddle factors of the plurality of twiddle factors are masked using random numbers divisible by a first modulus. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually compute a first NTT and a second NTT based on butterfly operations that deploy a plurality of twiddle factors.
Claim 9 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein the first NTT of the first masked polynomial is based on a root of unity modulo a second modulus, and wherein the root of unity modulo the second modulus is computed using a root of unity modulo the first modulus. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually determine the first NTT of the first masked polynomial is based on a root of unity modulo the second modulus.
The dependent claims 2-9 are directed to abstract ideas and do not include additional elements that are sufficient to amount to significantly more than the judicial exception. This judicial exception is not integrated into a practical application. Therefore, the claims are not patent eligible.
Claim 10 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. The claim recites a judicial exception (an abstract idea) that is not integrated into a practical application
Step 1: Statutory Category
Claim 10 satisfied the statutory category requirement because it is directed to a “method” or “process” under 35 U.S.C. 101(a). The claim recites a series of steps to perform a cryptographic operation.
Step 2A, Prong 1 – Judicial Exception (Abstract Area)
The claim recites of a method to perform a cryptographic operation, the method comprising: identifying, using a processing device, a plurality of input polynomials with coefficients defined modulo a first modulus, wherein at least one of the plurality of input polynomials is associated with a digital communication between the processing device and an additional processing device; generating, using the processing device, a plurality of masking polynomials with coefficients divisible by the first modulus and defined modulo a second modulus that is greater than the first modulus; obtaining, using the processing device, a plurality of masked polynomials, wherein each of the plurality of masked polynomials is computed, modulo the second modulus, using a respective input polynomial of the plurality of input polynomials and a respective masking polynomial of the plurality of masking polynomials; computing, using the processing device, a polynomial multiplication product of the plurality of masking polynomials using one or more Number Theoretic Transforms (NTTs) performed modulo the second modulus; and obtaining, using the processing device, an output of the cryptographic operation using the polynomial multiplication product reduced modulo the first modulus, wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device, or a digital signature for the digital communication between the processing device and the additional processing device.
The limitation of identifying, using a processing device, a plurality of input polynomials with coefficients defined modulo a first modulus, wherein at least one of the plurality of input polynomials is associated with a digital communication between the processing device and an additional processing device, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can be performed in the mind. A user can manually identify a plurality of input polynomials with coefficients defined modulo a first modulus and determine the plurality of input polynomials are associated with digital communication.
The limitation of generating, using the processing device a plurality of masking polynomials with coefficients divisible by the first modulus and defined modulo a second modulus that is greater than the first modulus, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can be performed in the mind. A user can manually generate a plurality of masking polynomials.
The limitation of obtaining, using the processing device, a plurality of masked polynomials, wherein each of the plurality of masked polynomials is computed, modulo the second modulus, using a respective input polynomial of the plurality of input polynomials and a respective masking polynomial of the plurality of masking polynomials, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can be performed in the mind. A user can manually obtain a plurality of masked polynomials by computing modulo the second modulus, using a respective input polynomial of the plurality of input polynomials and a respective masking polynomial.
The limitation of computing, using the processing device, a polynomial multiplication product of the plurality of masking polynomials using one or more Number Theoretic Transforms (NTTs) performed modulo the second modulus, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can be performed in the mind. A user can manually compute using one or more Number Theoretic Transforms (NTTs) performed modulo the second modulus, a polynomial multiplication product.
The limitation of obtaining, using the processing device, an output of the cryptographic operation using the polynomial multiplication product reduced modulo the first modulus, wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device, or a digital signature for the digital communication between the processing device and the additional processing device., as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can be performed in the mind. A user can manually obtain an output of the cryptographic operation using the polynomial multiplication product comprising a digital signature.
Therefore claim 1 recites of multiple judicial exceptions within the abstract idea category.
Step 2A, Prong 2 – Integration into a practical Application
This judicial exception is not integrated into a practical application. The claim recites of limitations of identifying, generating, obtaining, computing, and obtaining an output of a cryptographic operation. The claim does not recite any limitation to implement these limitations into a practical application. The specification of the current application recites of side-channel attacks. However, the claim does not recite of limitation showing how a side-channel attack can be prevented using the steps of the method. Merely, performing identifying, generating, obtaining, computing, and obtaining an output of a cryptographic operation does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. The claim is directed to an abstract idea.
Step 2B- “Significantly More” (Inventive concept)
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. In particular, the claim only recites one additional element of “processing device” recited at a high-level of generality (i.e., as a generic processing device implementing the method) such that it amounts no more than mere instructions to apply the exception using a generic processing device. Mere instructions to apply an exception using a generic processing device cannot provide an inventive concept. The claim is not patent eligible.
Claim 11 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein the first modulus divides the second modulus. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually determine the first modulus divides the second modulus.
Claim 12 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein coefficients of each of the plurality of masking polynomials are randomly-sampled from a set of numbers divisible by the first modulus. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually randomly-sample coefficients of each of the plurality of masking polynomials.
Claim 13 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein the second modulus is randomly sampled from a target range of values. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually determine the second modulus is randomly sampled from a target range of values.
Claim 14 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein the target range of values is determined by at least one of: a bit size of one or more registers storing coefficients of the plurality of masked polynomials; or an operand size of a processing unit that supports computation of the one or more NTTs. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually determine target range of values based on bit size or operand size.
Claim 15 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein computing the polynomial multiplication product comprises computing, modulo the second modulus: a first NTT of a first masked polynomial of the plurality of masked polynomials; a second NTT of a second masked polynomial of the plurality of masked polynomials; an elementwise multiplication product of the first NTT and the second NTT, and an inverse NTT of the elementwise multiplication product of the first NTT and the second NTT. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually compute the polynomial multiplication product by computing a first NTT of a first masked polynomial, a second NTT of a second masked polynomial, an elementwise multiplication product of the first NTT and the second NTT, and an inverse NTT of the elementwise multiplication product of the first NTT and the second NTT.
Claim 16 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein the one or more NTTs are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein at least a subset of the plurality of twiddle factors are masked using random numbers divisible by the first modulus. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually determine one or more NTTs are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors.
The dependent claims 11-16 are directed to abstract ideas and do not include additional elements that are sufficient to amount to significantly more than the judicial exception. This judicial exception is not integrated into a practical application. Therefore, the claims are not patent eligible.
Claim 17 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. The claim recites a judicial exception (an abstract idea) that is not integrated into a practical application
Step 1: Statutory Category
Claim 17 satisfied the statutory category requirement because it is directed to a “processing device”. The claim recites a series of steps to perform a cryptographic operation using a processing device.
Step 2A, Prong 1 – Judicial Exception (Abstract Area)
The claim recites of a processing device comprising: one or more registers to store a first polynomial associated with a first data and a second polynomial associated with a second data, wherein the first polynomial and the second polynomial are defined on a working domain having a first dimension and wherein the first data is associated with a digital communication between the processing device and an additional processing device; and one or more processing units to: map the first polynomial and the second polynomial to an auxiliary domain having a second dimension that is greater than the first dimension; mask the first mapped polynomial with a first masking polynomial to obtain a first masked polynomial; mask the second mapped polynomial with a second masking polynomial to obtain a second masked polynomial, wherein the first masking polynomial and the second masking polynomial are associated with a kernel of a homomorphism transformation from the auxiliary domain to the working domain; perform, using the first masked polynomial and the second masked polynomial, one or more computations in the auxiliary domain; and obtain an output of a cryptographic operation, wherein obtaining the output comprises transforming an output of the one or more computations from the auxiliary domain to the working domain, and wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device, or a digital signature for the digital communication between the processing device and the additional processing device.
Claim 17 recites of limitations similar to that of claim 1. Therefore, a similar Step 2A, Prong 1 analysis applies. Claim 17 further recites the limitation one or more registers to store a first polynomial associated with a first data and a second polynomial associated with a second data, wherein the first polynomial and the second polynomial and defined on a working domain having a first dimension. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually store a first polynomial associated with a first data and a second polynomial associated with a second data.
Therefore claim 1 recites of multiple judicial exceptions within the abstract idea category.
Step 2A, Prong 2 – Integration into a practical Application
This judicial exception is not integrated into a practical application. The claim recites of limitations of storing, mapping, masking, performing computation, and obtaining an output of a cryptographic operation. The claim does not recite any limitation to implement these limitations into a practical application. The specification of the current application recites of side-channel attacks. However, the claim does not recite of limitation showing how a side-channel attack can be prevented using the steps of the method. Merely, performing mapping, masking, and computation does not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. The claim is directed to an abstract idea.
Step 2B- “Significantly More” (Inventive concept)
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. In particular, the claim only recites one additional element of “processing device” recited at a high-level of generality (i.e., as a generic processing device implementing the method) such that it amounts to no more than mere instructions to apply the exception using a generic processing device. Mere instructions to apply an exception using a generic processing device cannot provide an inventive concept. Furthermore, the claim recites of one or more registers to store a first polynomial associated with a first data and a second polynomial associated with a second data. Registers recited at a high-level of generality such that it amounts to no more than storing data in memory. The claim is not patent eligible.
Claim 18 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein coefficients of each of the first polynomial and the second polynomial are defined modulo a first modulus in the working domain, wherein coefficients of each of the first masked polynomial and the second masked polynomial are defined modulo a second modulus in the working domain, and wherein the first modulus divides the second modulus. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually determine coefficients of each of the first polynomial and the second polynomial are defined modulo a first modulus in the working domain, wherein coefficients of each of the first masked polynomial and the second masked polynomial are defined modulo a second modulus in the working domain.
Claim 19 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein to mask the first mapped polynomial with the first masking polynomial, the one or more processing units are to add a product of the first modulus and each of a plurality of randomly-sampled coefficients of the first masking polynomial to a respective same-degree coefficient of the first mapped polynomial. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually mask the first mapped polynomial with the first masking polynomial.
Claim 20 is rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. This claim recites of wherein the one or more computations in the auxiliary domain further comprise: an elementwise multiplication of a first Number Theoretic Transform (NTT) of the first masked polynomial and the second NTT of the second masked polynomial, and an inverse NTT of an output of the elementwise multiplication of the first NTT and the second NTT; wherein the first NTT and the second NTT are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein one or more twiddle factors of the plurality of twiddle factors are masked using random numbers divisible by the first modulus. Therefore, the limitations of this claim, as drafted, is a process that, under its broadest reasonable interpretation, covers steps that can also be performed in the mind. A user can manually compute an elementwise multiplication of the first NTT and the second NTT, and an inverse NTT of an output of the elementwise multiplication of the first NTT and the second NTT, wherein the first NTT and the second NTT are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors.
The dependent claims 18-20 are directed to abstract ideas and do not include additional elements that are sufficient to amount to significantly more than the judicial exception. This judicial exception is not integrated into a practical application. Therefore, the claims are not patent eligible.
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-7 are rejected under 35 U.S.C. 103 as being unpatentable over JOYE (US-20250047484-A1) in view of VIGILANT (US-20250055687-A1), hereinafter JOYE-VIGILANT.
Regarding claim 1, JOYE teaches “A method to perform a cryptographic operation, the method comprising: ([JOYE, abstract] “Some embodiments are directed to a computer-implemented encrypted computation method (500)”) mapping, using a processing device, to an auxiliary domain, each of (i) a first polynomial associated with first data and defined on a working domain and (2) a second polynomial associated with second data and defined on the working domain, wherein the working domain has a first dimension and the auxiliary domain has a second dimension that is greater than the first dimension, and wherein the first data is associated with a digital communication between the processing device and an additional processing device; ([JOYE, para. 0091] “FIG. 2 schematically shows an example of an embodiment of a method of computing a polynomial product of two polynomials f(X) and g(X). The two polynomials in this example are defined modulo a quotient polynomial p(X).”) ([JOYE, para. 0092] “The figure shows the two polynomials f, 241 and g, 243, represented in the coefficient domain, e.g., by respective values for the coefficients fi of f(X)=ΣifiXimodp(X) and gi of g(X)=ΣigiXimodp(X).”) ([JOYE, para. 0093] “To multiply the polynomials, a number-theoretic transform NTT, 233, may be applied to convert the polynomials into a Fourier domain. The figure shows Fourier-domain representation 242 of polynomials 241 and Fourier-domain representation 244 of polynomial 243. Typically, a Fourier-domain representation of the polynomial 241, 243 comprises evaluations of the polynomial in powers of a primitive root of unity from a finite ring, e.g., the ring from which the coefficients of the polynomials 241, 243 are selected or to which they correspond. As demonstrated by the examples below, the Fourier-domain representations can comprise all M powers of a Mth primitive root of unity, for example, or only a strict subset of the powers.”) ([JOYE, para. 0109] “Denoting the degree of p(X) as N, the coefficient representation of a polynomial may comprise N elements, whereas the Fourier domain representation may comprise M elements. … If M>N, there a one-to-one mapping between Fourier domain representations and polynomials mod (XM−1), but not between Fourier domain representations and polynomials mod p(X). Interestingly, however, the operation h=h′ mod p in INTT 234 may guarantee that each coefficient representation 245 of a polynomial mod p(X) has an equal number of Fourier domain representations 246 corresponding to it.”) ([JOYE, 0080] “The devices 111 and/or 112 in this example may each be based on device 110 of FIG. 1 a , e.g., may each comprise processor system 130, storage 140, and/or communication interface 150 of FIG. 1 a.”) ([JOYE, 0084] “ For example, encrypted computing device 112 may be operated by a cloud provider. The cloud provider may offer computation and storage services to its clients. By employing homomorphic encryption, data provider device 160 of FIG. 1 b , e.g., a client of the cloud provider, can send their data in encrypted form.”) masking, using the processing device, the first mapped polynomial with a first masking polynomial to obtain a first masked polynomial; ([JOYE, para. 0015] “First, that it is also possible to define the stored data for a ciphertext in such a way that the PRNG does not generate the mask polynomials in their regular coefficient representation, but instead generates representations of the mask polynomials in the Fourier domain, e.g., as evaluations of the polynomials in a set of evaluation values.”) ([JOYE, para. 0074] “ In this case, processor system 130 may be configured to obtain respective multiplicand polynomials by which to multiply the mask polynomials and the body polynomial … The expanding may comprise using the pseudo-random number generator according to the seed to generate representations of the mask polynomials in the Fourier domain. Processor system 130 may be further configured to compute polynomial products of the mask polynomials and the body polynomial by the respective multiplicand polynomials. The polynomial products may be computed in the Fourier domain, resulting in representations of the computed polynomial products in the Fourier domain. Processor system 130 may be further configured to output the computed polynomial products, for example, for use in a remainder of the encrypted computation.”) … wherein the first masking polynomial and the second … polynomial are associated with a kernel of a homomorphism transformation from the auxiliary domain to the working domain; ([JOYE, para. 0092] “The figure shows the two polynomials f, 241 and g, 243, represented in the coefficient domain”) ([JOYE, para. 0093] “To multiply the polynomials, a number-theoretic transform NTT, 233, may be applied to convert the polynomials into a Fourier domain.”) [Examiner’s note: Examiner is interpreting homomorphic transformation as a mapping between two algebraic structures that preserves the underlying operations. A Fourier transformations is a homomorphic transformation. Every homomorphic transform between algebraic structures has a kernel. A kernel is a measurement of how much information is lost in the mapping. The kernel of transformation in the Fourier domain is the exponential function. Therefore, JOYE’s teaching of converting polynomials into a Fourier domain teaches this limitation.] performing, using the processing device, one or more computations in the auxiliary domain based at least on the first masked polynomial and the second masked polynomial ([JOYE, para. 0094] “Given the Fourier- domain representations 242, 244, the polynomial product of the polynomials may be computed in an operation Mul, 238, in the Fourier domain. This is typically implemented as a pointwise multiplication of the evaluations of the polynomials. The pointwise multiplications may correspond to respective multiplications modulo a polynomial XM-1 for a value n that corresponds to the quotient polynomial, as highlighted in the examples below. As a result, a Fourier domain representation 246 of the product of the polynomials f and g may be obtained”) ([JOYE, para. 0127] “The Fourier domain representation 344 and the seed 345 may be used to represent the ciphertext. By storing the body polynomial in the Fourier domain, it can be directly used for Fourier-domain multiplication. It is also possible the store the body polynomial in coefficient form, in which case the translation to the Fourier domain may then be performed at the point where a multiplication is needed.”) wherein obtaining the output comprises transforming an output of the one or more computations from the auxiliary domain to the working domain, and wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device, or a digital signature for the digital communication between the processing device and the additional processing device. ([JOYE, para. 0094] “As a result, a Fourier domain representation 246 of the product of the polynomials f and g may be obtained, e.g., as evaluations of the quotient polynomial in the set of powers of the primitive root of unity.”) ([JOYE, para. 0095] “An inverse INTT, 234, of the number theoretic transform 233 may be applied to the Fourier domain representation 246 of the product polynomial to obtain a representation 245 of the product polynomial in coefficient form h(X)=ΣihiXimod p(X).”) ([JOYE, para. 0177] “The multiplication 438 may result in mask and body polynomials of a GLWE-based ciphertext 454, represented in the Fourier domain. The ciphertext 454 may represent an encryption of the product of the values encrypted by GLWE-based ciphertext 455 and GGSW-type ciphertext 456. This product is also referred to as an external product. The encryption may optionally be converted to coefficient form 453 by an INTT unit 434 applying an inverse of the number-theoretic transform as in FIGS. 2, 3 a, and 3 b.”) ([JOYE, para. 0162] “Encrypted multiplication unit 332 may output the computed polynomial products in various formats as desired. For example, the polynomial products may be output in their Fourier domain representation 354, or, as shown in the figure, INNT unit 334 may be used to apply an inverse number theoretic transform in order to convert representations 354 of some or all of the computed polynomial products in the Fourier domain to coefficient representations 353.”) ([JOYE, para. 0184] “For example, encrypted computing device 112 may be operated by a cloud provider. The cloud provider may offer computation and storage services to its clients. By employing homomorphic encryption, data provider device 160 of FIG. 1 b , e.g., a client of the cloud provider, can send their data in encrypted form. The cloud provider can still perform the required computations, and/or the required storage”) ([JOYE, para. 0084] “ For example, data provider device 160 may use an encryption key of a type corresponding to the particular homomorphic encryption system used to encrypt the data items. When computations results are received by data-provider 160 from encrypted computing device 112, a corresponding decryption key may be used to decrypt the encrypted data items. Encryption and decryption keys may be the same- and typically are so.”)
However, JOYE does not teach “… masking, using the processing device, the second mapped polynomial with a second masking polynomial to obtain a second masked polynomial …”
In analogous teaching VIGILANT teaches “… masking, using the processing device, the second mapped polynomial with a second masking polynomial to obtain a second masked polynomial, …” ([VIGILANT, para. 0072] “A first example is given where the at least one polynomial operation comprises a multiplication between a first input polynomial A[X] and a second input polynomial B[X]in the first polynomial ring Rq, and where the random polynomials are integers.”) ([VIGILANT, para. 0073] “In such a case, at the second step S2, determining a random polynomial for each input polynomial may comprise determining a first random integer rA for the first input polynomial A[X] and a second random integer rB for the second input polynomial B[X].”) ([VIGILANT, para. 0074] “At the third step S3, randomizing the coefficients of each input polynomial may comprise obtaining a randomized first input polynomial A″ [X] with coefficients Ai″ from said first input polynomial A[X] and a randomized second input polynomial B″ [X] with coefficients Bi″ from said second input polynomial B[X], such that Ai″=rA*(Ai+q) mod q′ and Bi″=rB*(Bi+q) mod q′.”) ([VIGILANT, para. 0050] “The main idea of the invention in order to randomize the coefficients of such polynomials in a way that remains compatible with both polynomial additions and multiplications is to apply to such polynomials two randomization operations … first an additive masking operation by adding to each coefficient of the polynomial the prime number q. In order to effectively change the coefficients, they are lifted to a representation modulo q′ instead of modulo q, with q′ a multiple of q;”)
Thus, given the teaching of VIGILANT, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine the teaching of masking polynomials by VIGILANT into the teaching of a method to perform a cryptographic operation by JOYE. One of ordinary skill in the art would have been motivated to do so because VIGILANT recognizes the need to counter side channel attacks. ([VIGILANT, para. 0004] “A commonly used countermeasure against side-channel attacks is the masking of the intermediate values of an encryption process with a random mask.”) ([VIGILANT, para. 0006] “there is a need for a masking scheme applicable to polynomial coefficients in order to protect it against side-channel analysis, and compatible with both polynomial additions and multiplications.”) ([VIGILANT, para. 0007] “this invention therefore relates to a method secured against side channel attacks performing a cryptographic operation of a cryptographic algorithm”)
Regarding claim 2, JOYE-VIGILANT teach all limitations of claim 1. VIGILANT further teaches “wherein coefficients of each of the first polynomial and the second polynomial are defined modulo a first modulus in the working domain, wherein coefficients of each of the first masked polynomial and the second masked polynomial are defined modulo a second modulus in the working domain, and wherein the first modulus divides the second modulus. ([VIGILANT, para. 0073] “In such a case, at the second step S2, determining a random polynomial for each input polynomial may comprise determining a first random integer rA for the first input polynomial A[X] and a second random integer rB for the second input polynomial B[X].”) ([VIGILANT, para. 0074] “At the third step S3, randomizing the coefficients of each input polynomial may comprise obtaining a randomized first input polynomial A″ [X] with coefficients Ai″ from said first input polynomial A[X] and a randomized second input polynomial B″ [X] with coefficients Bi″ from said second input polynomial B[X], such that Ai″=rA*(Ai+q) mod q′ and Bi″=rB*(Bi+q) mod q′.”) ([VIGILANT, para. 0050] “The main idea of the invention in order to randomize the coefficients of such polynomials in a way that remains compatible with both polynomial additions and multiplications is to apply to such polynomials two randomization operations … first an additive masking operation by adding to each coefficient of the polynomial the prime number q. In order to effectively change the coefficients, they are lifted to a representation modulo q′ instead of modulo q, with q′ a multiple of q;”)
The same motivation to modify JOYE with VIGILANT as in the rejection of claim 1 applies.
Regarding claim 3, JOYE-VIGILANT teach all limitations of claim 2. VIGILANT further teaches “wherein masking the first mapped polynomial with the first masking polynomial comprises adding a product of the first modulus and each of a plurality of randomly-sampled coefficients of the first masking polynomial to a respective same-degree coefficient of the first mapped polynomial. ([VIGILANT, para. 0050] “The main idea of the invention in order to randomize the coefficients of such polynomials in a way that remains compatible with both polynomial additions and multiplications is to apply to such polynomials two randomization operations … first an additive masking operation by adding to each coefficient of the polynomial the prime number q. In order to effectively change the coefficients, they are lifted to a representation modulo q′ instead of modulo q, with q′ a multiple of q”) ([VIGILANT, para. 0053] “the additive masking can be removed easily by a simple “modulo q” operation. Therefore, polynomial additions and multiplications can be performed using randomized polynomials sharing the same masking (same q) without prior derandomization and the masking can be removed after addition”) ([VIGILANT, para. 0055] “In a first step S1, the processing system selects a multiplier integer t and determines a second integer q′ by multiplying the first integer q by the selected multiplier integer t, such that q′=q*t.”) ([VIGILANT, para. 0056] “ the value of the multiplier integer t is selected such that the value of the second integer q′ corresponds to a width of the processor in order to keep modulo q′ operations single precision operations. Alternatively t may be chosen such that q′ is above a predetermined minimal value corresponding to a specific security level. Alternatively t may be a power of 2 in order to optimize the speed of modular operations modulo q′.”)
The same motivation to modify JOYE with VIGILANT as in the rejection of claim 1 applies.
Regarding claim 4, JOYE-VIGILANT teach all limitations of claim 2. VIGILANT further teaches “wherein the second modulus is randomly sampled from a target range of values. ([VIGILANT, para. 0055] “In a first step S1, the processing system selects a multiplier integer t and determines a second integer q′ by multiplying the first integer q by the selected multiplier integer t, such that q′=q*t.”) ([VIGILANT, para. 0056] “ the value of the multiplier integer t is selected such that the value of the second integer q′ corresponds to a width of the processor in order to keep modulo q′ operations single precision operations. Alternatively t may be chosen such that q′ is above a predetermined minimal value corresponding to a specific security level. Alternatively t may be a power of 2 in order to optimize the speed of modular operations modulo q′.”) ([VIGILANT, para. 0057] “several second integers q′ may be precomputed and stored in a memory of the processing system. In such a case, determining a second integer q′ comprises choosing randomly one integer among the precomputed second integer values q′.”)
The same motivation to modify JOYE with VIGILANT as in the rejection of claim 1 applies.
Regarding claim 5, JOYE-VIGILANT teach all limitations of claim 4. VIGILANT further teaches “wherein the target range of values is determined by at least one of: a bit size of one or more registers storing coefficients of the first masked polynomial; or an operand size of a processing unit that performs the one or more computations in the auxiliary domain. ([VIGILANT, para. 0055] “In a first step S1, the processing system selects a multiplier integer t and determines a second integer q′ by multiplying the first integer q by the selected multiplier integer t, such that q′=q*t.”) ([VIGILANT, para. 0056] “ the value of the multiplier integer t is selected such that the value of the second integer q′ corresponds to a width of the processor in order to keep modulo q′ operations single precision operations.”) [Examiner’s note: The operand size of a processor generally refers to the width of the data (in bits) that a specific instruction operates. The processor width dictates the maximum native operand size.]
The same motivation to modify JOYE with VIGILANT as in the rejection of claim 1 applies.
Regarding claim 6, JOYE-VIGILANT teach all limitations of claim 1. JOYE further teaches “wherein the one or more computations in the auxiliary domain comprise a first Number Theoretic Transform (NTT) of the first masked polynomial, and a second NTT of the second masked polynomial. ([JOYE, para. 0093] “To multiply the polynomials, a number-theoretic transform NTT, 233, may be applied to convert the polynomials into a Fourier domain. The figure shows Fourier-domain representation 242 of polynomials 241 and Fourier-domain representation 244 of polynomial 243.”) ([JOYE, para. 0107] “when performing the NTT 233 on polynomials f, g, it is possible to add random multiples of the quotient polynomial to f and/or g to randomize the obtained Fourier domain representations 242, 243.”)
Regarding claim 7, JOYE-VIGILANT teach all limitations of claim 6. JOYE further teaches “wherein the one or more computations in the auxiliary domain further comprise: an elementwise multiplication of the first NTT and the second NTT, and an inverse NTT of an output of the elementwise multiplication of the first NTT and the second NTT. ([JOYE, para. 0157] “The encrypted multiplication unit 332 may act on a ciphertext that comprises one or more random mask polynomials, and a body polynomial that is derived from the mask polynomials and a plaintext. For example, the ciphertext may be GLWE-based ciphertext as described herein. The encrypted multiplication unit 332 may act on a ciphertext represented in a compressed way by a seed 345 of a pseudo-random number generator, and by a representation 344 of the body polynomial in a Fourier domain of a number-theoretic transform.”) ([JOYE, para. 0161] “Fourier domain representations 354 of the computed polynomial products in the Fourier domain may be obtained. For example, the multiplication unit 338 may be multiplication unit 238 of FIG. 2 . Typically, the Fourier domain representations comprise evaluations of the respective polynomials in a set of evaluation values, and multiplication 338 may be implemented by pointwise multiplication of the polynomial evaluations as known per se.”) ([JOYE, para. 0095] “An inverse INTT, 234, of the number theoretic transform 233 may be applied to the Fourier domain representation 246 of the product polynomial to obtain a representation 245 of the product polynomial in coefficient form h(X)=ΣihiXimod p(X).”)
Claim 8 is rejected under 35 U.S.C. 103 as being unpatentable over JOYE-VIGILANT in view of KWON (US-20230171084-A1).
Regarding claim 8, JOYE-VIGILANT teach all limitations of claim 6. However, JOYE-VIGILANT does not teach “wherein the first NTT and the second NTT are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein one or more twiddle factors of the plurality of twiddle factors are masked using random numbers divisible by a first modulus”.
In analogous teaching KWON teaches “wherein the first NTT and the second NTT are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein one or more twiddle factors of the plurality of twiddle factors are masked using random numbers divisible by a first modulus. ([KWON, para. 0008] “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; and a controller configured to control the first memory, the second memory, and the NTT module, wherein the NTT module comprises a butterfly unit (BU) array that comprises a plurality of BUs configured to, for the performing of the NTT”) ([KWON, para. 0080] “Each of the plurality of BUs may include a multiplier configured to perform a multiplication on the twiddle factor and the second coefficient”) ([KWON, para. 0149] “BU1 may receive two coefficients and may output new two coefficients. BU1 may include a multiplication using a twiddle factor and a modular reduction operator configured to perform a modulus operation with a Q value used in each NTT”)
Thus, given the teaching of KWON, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine the teaching of butterfly operations and twiddle factor by KWON into the teaching of a method to perform a cryptographic operation by JOYE-VIGILANT. One of ordinary skill in the art would have been motivated to do so because KWON recognizes the need to improve homomorphic encryption technology. ([KWON, para. 0006] “The homomorphic encryption technology may perform arithmetic operations on lattice-based encrypted data that is a type of quantum-resistant encryption and thus, is attaining a high attention. However, when original data is encrypted, a word size of data may increase, which may lead to increasing an operation processing time between ciphertexts.”) ([KWON, para. 0098] “The homomorphic encryption operation apparatus 10 of one or more embodiments may easily expand the NTT structure using a 16*5-BU array to improve data processing.”)
Claim 9 is rejected under 35 U.S.C. 103 as being unpatentable over JOYE-VIGILANT in view of BAJPEYI (US-20230188322-A1).
Regarding claim 9, JOYE-VIGILANT teach all limitations of claim 6. However, JOYE-VIGILANT does not teach “wherein the first NTT of the first masked polynomial is based on a root of unity modulo a second modulus, and wherein the root of unity modulo the second modulus is computed using a root of unity modulo the first modulus”.
In analogous teaching BAJPEYI teaches “wherein the first NTT of the first masked polynomial is based on a root of unity modulo a second modulus, and wherein the root of unity modulo the second modulus is computed using a root of unity modulo the first modulus. ([BAJPEYI, para. 0070] “Referring now to FIGS. 6A and 6B, a LAWS embodiment of a ciphertext multiplication module 600 is shown. Generally speaking, for the LAWS embodiment, ciphertext multiplication may be defined by Relationship 2 b below … he LAWS embodiment of the ciphertext multiplication module produces four output coefficients, or two output coefficients per output polynomial, per cycle. In this design, roots of unity generated using the modulus q are used for NTT operations to take the product of two ciphertext polynomials and roots of unity generated using the modulus Q are used for NTT operations to take the product with key polynomials. Roots of unity and other constants required for the modules shown are stored in eSRAMs”)
Thus, given the teaching of BAJPEYI, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine the teaching of root of unity by BAJPEYI into the teaching of a method to perform a cryptographic operation by JOYE-VIGILANT. One of ordinary skill in the art would have been motivated to do so because BAJPEYI recognizes the need to improve encrypted operations. ([BAJPEYI, para. 0004] “While offering great promise by preserving privacy for data owners, operations involving encrypted data are nevertheless computation-intensive.”) ([BAJPEYI, para. 0115] “In terms of efficiency comparisons, a cryptographic processor employing an RNS architecture to execute a 1,024-point logistic regression benchmark including the ciphertext addition, multiplication and rotation modules, running at a frequency of 600 MHz, achieves a latency 192.6 times faster than an Intel Xeon Platinum 8175 processor with 128 GB of RAM running at 3.1 GHz (a clock rate over five times faster).”)
Claims 10-15 are rejected under 35 U.S.C. 103 as being unpatentable over VIGILANT (US-20250055687-A1) in view of LI (US-20250254044-A1), and further in view of JOYE (US-20250047484-A1), hereinafter VIGILANT-LI-JOYE.
Regarding claim 10, VIGILANT teaches “A method to perform a cryptographic operation, the method comprising: identifying, using a processing device, a plurality of input polynomials with coefficients defined modulo a first modulus, wherein at least one of the plurality of input polynomials is associated with a digital communication between the processing device and an additional processing device; ([VIGILANT, para. 0007] “this invention therefore relates to a method secured against side channel attacks performing a cryptographic operation of a cryptographic algorithm”) ([VIGILANT, para. 0050] “first an additive masking operation by adding to each coefficient of the polynomial the prime number q. In order to effectively change the coefficients, they are lifted to a representation modulo q′ instead of modulo q, with q′ a multiple of q”) generating, using the processing device a plurality of masking polynomials … ; ([VIGILANT, para. 0058] “the processing system determines for each input polynomial A[X] an invertible random polynomial R[X]in the first polynomial ring Rq.”) ([VIGILANT, para. 0058] “In a second step S2, the processing system determines for each input polynomial A[X] an invertible random polynomial R[X]in the first polynomial ring Rq.”) ([JOYE, 0080] “The devices 111 and/or 112 in this example may each be based on device 110 of FIG. 1 a , e.g., may each comprise processor system 130, storage 140, and/or communication interface 150 of FIG. 1 a.”) ([JOYE, 0084] “ For example, encrypted computing device 112 may be operated by a cloud provider. The cloud provider may offer computation and storage services to its clients. By employing homomorphic encryption, data provider device 160 of FIG. 1 b , e.g., a client of the cloud provider, can send their data in encrypted form.”) … obtaining, using the processing device, a plurality of masked polynomials, wherein each of the plurality of masked polynomials is computed, modulo the second modulus, using a respective input polynomial of the plurality of input polynomials and a respective masking polynomial of the plurality of masking polynomials; ([VIGILANT, para. 0060] “transforming the input polynomial A[X]into a lifted input polynomial A′[X] with coefficients Ai′ by lifting the coefficients Ai of the input polynomial A[X] from a representation modulo said first integer q to a representation modulo said second integer q′ such that Ai′=Ai+q mod q′, with i in [0, . . . ,n−1]. By doing so, the lifted input polynomial A′[X] is a polynomial in a second polynomial ring Rq′=Fq′[X]/(Xn+1), randomizing the lifted input polynomial A′[X] by multiplying it by the random polynomial R[X] modulo the second integer q′ to obtain a randomized input polynomial A″ [X]in the second polynomial ring Rq′.”)
However, VIGILANT does not teach “masking polynomials with coefficients divisible by the first modulus and defined modulo a second modulus that is greater than the first modulus … computing, using the processing device, a polynomial multiplication product of the plurality of masking polynomials using one or more Number Theoretic Transforms (NTTs) performed modulo the second modulus; and obtaining, using the processing device, an output of the cryptographic operation using the polynomial multiplication product reduced modulo the first modulus, wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device, or a digital signature for the digital communication between the processing device and the additional processing device.”
In analogous teaching LI teaches “… masking polynomials with coefficients divisible by the first modulus and defined modulo a second modulus that is greater than the first modulus … ([LI, para. 0064] “In order to protect a polynomial multiplication performed according to the method presented above against side channel attacks, the coefficients of the input polynomials A[X] and B[X] may be blinded.”) ([LI, para. 0065] “at the integer generation step S11, before generating concatenated integers, the coefficients of the input polynomials are masked using a multiplicative masking. For example, each coefficient of A[X] ai with i in {0, . . . , Nc−1} may be multiplied by a random mask rnd modulo q with q=2^Nb”) ([LI, para. 0006] “a polynomial multiplication between a first input polynomial A[X] and a second input polynomial B[X], wherein the first input polynomial A[X] and the second input polynomial B[X] comprise Nc coefficients and said coefficients of the first and second input polynomials are of size Nb bits, with Nc and Nb non-zero integers”) ([LI, para. 0068] “By doing so the product of the mask coefficients with the same index is equal to the product of the original coefficients of this index plus a random value depending on rnd1 and rnd2 that is a multiple of q”)
Thus, given the teaching of LI, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine the teaching of masking polynomials with coefficients by LI into the teaching of a method to perform a cryptographic operation by VIGILANT. One of ordinary skill in the art would have been motivated to do so because LI recognizes the need to improve polynomial multiplication. ([LI, para. 0005] “There is a need for a method enabling to compute polynomial multiplications between large polynomials at a lower cost than existing methods.”) ([LI, para. 0006] “this invention therefore relates to a method for performing a cryptographic algorithm, performed by a cryptographic device comprising a cryptographic co-processor comprising an integer multiplier”)
However, VIGILANT-LI does not teach “… computing, using the processing device, a polynomial multiplication product of the plurality of masking polynomials using one or more Number Theoretic Transforms (NTTs) performed modulo the second modulus; and obtaining, using the processing device, an output of the cryptographic operation using the polynomial multiplication product reduced modulo the first modulus, wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device, or a digital signature for the digital communication between the processing device and the additional processing device.”
In analogous teaching JOYE teaches “… computing, using the processing device, a polynomial multiplication product of the plurality of masking polynomials using one or more Number Theoretic Transforms (NTTs) performed modulo the second modulus; and ([JOYE, para. 0018] “The number-theoretic transform is a technique that is known per se to perform efficient multiplications in polynomial rings. To perform polynomial multiplications using the NTT, the polynomials may be represented in the Fourier-domain representation of the NTT.”) ([JOYE, para. 0159] “number theoretic transform unit NTT, 333, is used to apply the number-theoretic transform to convert the coefficients 351 of the respective multiplicand polynomials to Fourier-domain representations 352.”) ([JOYE, para. 0161] “Given Fourier domain representations of mask polynomials 342, body polynomial 344, and the multiplicand polynomials 352, a multiplication unit 338 may be used to compute polynomial products of the mask polynomials 342 and the body polynomial 344 by the respective multiplicand polynomials 352 in the Fourier domain.”) ([JOYE, para. 0091] “FIG. 2 schematically shows an example of an embodiment of a method of computing a polynomial product of two polynomials f(X) and g(X). The two polynomials in this example are defined modulo a quotient polynomial p(X).”) and obtaining, using the processing device, an output of the cryptographic operation using the polynomial multiplication product reduced modulo the first modulus, wherein the output of the cryptographic operation comprises at least one of: a decryption of the digital communication between the processing device and the additional processing device, or a digital signature for the digital communication between the processing device and the additional processing device. ([JOYE, para. 0094] “Given the Fourier- domain representations 242, 244, the polynomial product of the polynomials may be computed in an operation Mul, 238, in the Fourier domain. This is typically implemented as a pointwise multiplication of the evaluations of the polynomials. The pointwise multiplications may correspond to respective multiplications modulo a polynomial XM-1 for a value n that corresponds to the quotient polynomial, as highlighted in the examples below. As a result, a Fourier domain representation 246 of the product of the polynomials f and g may be obtained, e.g., as evaluations of the quotient polynomial in the set of powers of the primitive root of unity.”) ([JOYE, para. 0095] “An inverse INTT, 234, of the number theoretic transform 233 may be applied to the Fourier domain representation 246 of the product polynomial to obtain a representation 245 of the product polynomial in coefficient form h(X)=ΣihiXimod p(X)”) ([JOYE, para. 0154] “the techniques of the corresponding example of FIG. 2 may be used. When performing INNT 334, it is possible to obtain coefficient representations ai(x), 341, mod p(X)”) ([JOYE, para. 0154] “As an alternative, it is also possible for INTT 334 to avoid reduction modulo p(X). “) ([JOYE, para. 0162] “Encrypted multiplication unit 332 may output the computed polynomial products in various formats as desired. For example, the polynomial products may be output in their Fourier domain representation 354, or, as shown in the figure, INNT unit 334 may be used to apply an inverse number theoretic transform in order to convert representations 354 of some or all of the computed polynomial products in the Fourier domain to coefficient representations 353.”) ([JOYE, para. 0184] “For example, encrypted computing device 112 may be operated by a cloud provider. The cloud provider may offer computation and storage services to its clients. By employing homomorphic encryption, data provider device 160 of FIG. 1 b , e.g., a client of the cloud provider, can send their data in encrypted form. The cloud provider can still perform the required computations, and/or the required storage”) ([JOYE, para. 0084] “ For example, data provider device 160 may use an encryption key of a type corresponding to the particular homomorphic encryption system used to encrypt the data items. When computations results are received by data-provider 160 from encrypted computing device 112, a corresponding decryption key may be used to decrypt the encrypted data items. Encryption and decryption keys may be the same- and typically are so.”)
Thus, given the teaching of JOYE, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine the teaching of computing using one or more Number Theoretic Transforms (NTTs) by JOYE into the teaching of a method to perform a cryptographic operation by VIGILANT-LI. One of ordinary skill in the art would have been motivated to do so because JOYE recognizes the need to improve polynomial multiplication. ([JOYE, para. 0038] “the techniques provided herein, e.g., the improved polynomial multiplication, programmable bootstrapping, and external product, improve the efficiency of evaluating the neural network and/or reduce storage and transmission requirements for the used ciphertexts or key material.”)
Regarding claim 11, VIGILANT-LI-JOYE teach all limitations of claim 10. VIGILANT further teaches “wherein the first modulus divides the second modulus.” ([VIGILANT, para. 0050] “The main idea of the invention in order to randomize the coefficients of such polynomials in a way that remains compatible with both polynomial additions and multiplications is to apply to such polynomials two randomization operations … first an additive masking operation by adding to each coefficient of the polynomial the prime number q. In order to effectively change the coefficients, they are lifted to a representation modulo q′ instead of modulo q, with q′ a multiple of q;”) [Examiner’s note: q’ is a multiple of q therefore it also is divisible by q.]
Regarding claim 12, VIGILANT-LI-JOYE teach all limitations of claim 10. VIGILANT further teaches “wherein coefficients of each of the plurality of masking polynomials are randomly-sampled from a set of numbers divisible by the first modulus.” ([VIGILANT, para. 0050] “The main idea of the invention in order to randomize the coefficients of such polynomials in a way that remains compatible with both polynomial additions and multiplications is to apply to such polynomials two randomization operations … first an additive masking operation by adding to each coefficient of the polynomial the prime number q. In order to effectively change the coefficients, they are lifted to a representation modulo q′ instead of modulo q, with q′ a multiple of q”) ([VIGILANT, para. 0053] “the additive masking can be removed easily by a simple “modulo q” operation. Therefore, polynomial additions and multiplications can be performed using randomized polynomials sharing the same masking (same q) without prior derandomization and the masking can be removed after addition”) ([VIGILANT, para. 0055] “In a first step S1, the processing system selects a multiplier integer t and determines a second integer q′ by multiplying the first integer q by the selected multiplier integer t, such that q′=q*t.”) ([VIGILANT, para. 0056] “ the value of the multiplier integer t is selected such that the value of the second integer q′ corresponds to a width of the processor in order to keep modulo q′ operations single precision operations. Alternatively t may be chosen such that q′ is above a predetermined minimal value corresponding to a specific security level. Alternatively t may be a power of 2 in order to optimize the speed of modular operations modulo q′.”)
Regarding claim 13, VIGILANT-LI-JOYE teach all limitations of claim 10. VIGILANT further teaches “wherein the second modulus is randomly sampled from a target range of values.” ([VIGILANT, para. 0055] “In a first step S1, the processing system selects a multiplier integer t and determines a second integer q′ by multiplying the first integer q by the selected multiplier integer t, such that q′=q*t.”) ([VIGILANT, para. 0056] “the value of the multiplier integer t is selected such that the value of the second integer q′ corresponds to a width of the processor in order to keep modulo q′ operations single precision operations. Alternatively t may be chosen such that q′ is above a predetermined minimal value corresponding to a specific security level. Alternatively t may be a power of 2 in order to optimize the speed of modular operations modulo q′.”) ([VIGILANT, para. 0057] “several second integers q′ may be precomputed and stored in a memory of the processing system. In such a case, determining a second integer q′ comprises choosing randomly one integer among the precomputed second integer values q′.”)
Regarding claim 14, VIGILANT-LI-JOYE teach all limitations of claim 13. VIGILANT further teaches “wherein the target range of values is determined by at least one of: a bit size of one or more registers storing coefficients of the plurality of masked polynomials; or an operand size of a processing unit that supports computation of the one or more … .” ([VIGILANT, para. 0055] “In a first step S1, the processing system selects a multiplier integer t and determines a second integer q′ by multiplying the first integer q by the selected multiplier integer t, such that q′=q*t.”) ([VIGILANT, para. 0056] “the value of the multiplier integer t is selected such that the value of the second integer q′ corresponds to a width of the processor in order to keep modulo q′ operations single precision operations.”) [Examiner’s note: The operand size of a processor generally refers to the width of the data (in bits) that a specific instruction operates. The processor width dictates the maximum native operand size.]
Furthermore, JOYE teaches of NTTs as can be seen in the rejection of claim 10. The same rejection and motivation apply.
Regarding claim 15, VIGILANT-LI-JOYE teach all limitations of claim 10. JOYE further teaches “wherein computing the polynomial multiplication product comprises computing, modulo the second modulus: a first NTT of a first masked polynomial of the plurality of masked polynomials; a second NTT of a second masked polynomial of the plurality of masked polynomials; ([JOYE, para. 0093] “To multiply the polynomials, a number-theoretic transform NTT, 233, may be applied to convert the polynomials into a Fourier domain. The figure shows Fourier-domain representation 242 of polynomials 241 and Fourier-domain representation 244 of polynomial 243.”) ([JOYE, para. 0107] “when performing the NTT 233 on polynomials f, g, it is possible to add random multiples of the quotient polynomial to f and/or g to randomize the obtained Fourier domain representations 242, 243.”) an elementwise multiplication product of the first NTT and the second NTT, and an inverse NTT of the elementwise multiplication product of the first NTT and the second NTT. ([JOYE, para. 0157] “The encrypted multiplication unit 332 may act on a ciphertext that comprises one or more random mask polynomials, and a body polynomial that is derived from the mask polynomials and a plaintext. For example, the ciphertext may be GLWE-based ciphertext as described herein. The encrypted multiplication unit 332 may act on a ciphertext represented in a compressed way by a seed 345 of a pseudo-random number generator, and by a representation 344 of the body polynomial in a Fourier domain of a number-theoretic transform.”) ([JOYE, para. 0161] “Fourier domain representations 354 of the computed polynomial products in the Fourier domain may be obtained. For example, the multiplication unit 338 may be multiplication unit 238 of FIG. 2 . Typically, the Fourier domain representations comprise evaluations of the respective polynomials in a set of evaluation values, and multiplication 338 may be implemented by pointwise multiplication of the polynomial evaluations as known per se.”)
The same motivation to modify VIGILANT-LI with JOYE as in the rejection of claim 10 applies.
Claim 16 is rejected under 35 U.S.C. 103 as being unpatentable over VIGILANT-LI-JOYE in view of KWON (US-20230171084-A1).
Regarding claim 16, VIGILANT-LI-JOYE teach all limitations of claim 11. However, VIGILANT-LI-JOYE does not teach “wherein the one or more NTTs are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein at least a subset of the plurality of twiddle factors are masked using random numbers divisible by the first modulus.”.
In analogous teaching KWON teaches “wherein the one or more NTTs are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein at least a subset of the plurality of twiddle factors are masked using random numbers divisible by the first modulus.” ([KWON, para.0008] “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; and a controller configured to control the first memory, the second memory, and the NTT module, wherein the NTT module comprises a butterfly unit (BU) array that comprises a plurality of BUs configured to, for the performing of the NTT”) ([KWON, para. 0080] “Each of the plurality of BUs may include a multiplier configured to perform a multiplication on the twiddle factor and the second coefficient”) ([KWON, para. 0149] “BU1 may receive two coefficients and may output new two coefficients. BU1 may include a multiplication using a twiddle factor and a modular reduction operator configured to perform a modulus operation with a Q value used in each NTT”)
Thus, given the teaching of KWON, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine the teaching of butterfly operations and twiddle factor by KWON into the teaching of a method to perform a cryptographic operation by VIGILANT-LI-JOYE. One of ordinary skill in the art would have been motivated to do so because KWON recognizes the need to improve homomorphic encryption technology. ([KWON, para. 0006] “The homomorphic encryption technology may perform arithmetic operations on lattice-based encrypted data that is a type of quantum-resistant encryption and thus, is attaining a high attention. However, when original data is encrypted, a word size of data may increase, which may lead to increasing an operation processing time between ciphertexts.”) ([KWON, para. 0098] “The homomorphic encryption operation apparatus 10 of one or more embodiments may easily expand the NTT structure using a 16*5-BU array to improve data processing.”)
Claims 17-19 are rejected under 35 U.S.C. 103 as being unpatentable over JOYE (US-20250047484-A1) in view of VIGILANT (US-20250055687-A1) and further in view of BAJPEYI (US-20230188322-A1), hereinafter JOYE-VIGILANT-BAJPEYI.
Regarding claim 17, this claim recites of a processing device that performs the features of similar to that of method claim 1. Therefore, claim 17 is rejected in a similar manner as in the rejection of claim 1. However, JOYE-VIGILANT does not teach “one or more registers to store a first polynomial associated with a first data and a second polynomial associated with a second data”
In analogous teaching BAJPEYI teaches “one or more registers to store a first polynomial associated with a first data and a second polynomial associated with a second data” ([BAJPEYI, para. 0015] “the storage circuitry includes on-chip register circuitry configured to temporarily store the input of each stage.”) ([BAJPEYI, para. 0070] “Two input indices, such as at 602, from each input polynomial are processed in parallel to match the throughput of an NTT function provided by a stage of NTT circuits 604, where 0≤i<N/2. Key coefficients, at 606, are placed in a set of FIFO pipelining registers 608 until they are needed for a relinearization step (multiplications between aa and keym, in Relationship 2 b), and the polynomials ab and bb are put in a second set of FIFO pipelining registers 610 until they are needed”).
Thus, given the teaching of BAJPEYI, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine the teaching of root of unity by BAJPEYI into the teaching of a method to perform a cryptographic operation by JOYE-VIGILANT. One of ordinary skill in the art would have been motivated to do so because BAJPEYI recognizes the need to improve encrypted operations. ([BAJPEYI, para. 0004] “While offering great promise by preserving privacy for data owners, operations involving encrypted data are nevertheless computation-intensive.”) ([BAJPEYI, para. 0115] “In terms of efficiency comparisons, a cryptographic processor employing an RNS architecture to execute a 1,024-point logistic regression benchmark including the ciphertext addition, multiplication and rotation modules, running at a frequency of 600 MHz, achieves a latency 192.6 times faster than an Intel Xeon Platinum 8175 processor with 128 GB of RAM running at 3.1 GHz (a clock rate over five times faster).”)
Regarding claim 18, JOYE-VIGILANT-BAJPEYI teach all limitations of claim 17. VIGILANT further teaches “wherein coefficients of each of the first polynomial and the second polynomial are defined modulo a first modulus in the working domain, wherein coefficients of each of the first masked polynomial and the second masked polynomial are defined modulo a second modulus in the working domain, and wherein the first modulus divides the second modulus.” ([VIGILANT, para. 0073] “In such a case, at the second step S2, determining a random polynomial for each input polynomial may comprise determining a first random integer rA for the first input polynomial A[X] and a second random integer rB for the second input polynomial B[X].”) ([VIGILANT, para. 0074] “At the third step S3, randomizing the coefficients of each input polynomial may comprise obtaining a randomized first input polynomial A″ [X] with coefficients Ai″ from said first input polynomial A[X] and a randomized second input polynomial B″ [X] with coefficients Bi″ from said second input polynomial B[X], such that Ai″=rA*(Ai+q) mod q′ and Bi″=rB*(Bi+q) mod q′.”) ([VIGILANT, para. 0050] “The main idea of the invention in order to randomize the coefficients of such polynomials in a way that remains compatible with both polynomial additions and multiplications is to apply to such polynomials two randomization operations … first an additive masking operation by adding to each coefficient of the polynomial the prime number q. In order to effectively change the coefficients, they are lifted to a representation modulo q′ instead of modulo q, with q′ a multiple of q;”)
The same motivation to modify JOYE with VIGILANT as in the rejection of claim 1 applies.
Regarding claim 19, JOYE-VIGILANT-BAJPEYI teach all limitations of claim 18. VIGILANT further teaches “wherein to mask the first mapped polynomial with the first masking polynomial, the one or more processing units are to add a product of the first modulus and each of a plurality of randomly-sampled coefficients of the first masking polynomial to a respective same-degree coefficient of the first mapped polynomial.” ([VIGILANT, para. 0050] “The main idea of the invention in order to randomize the coefficients of such polynomials in a way that remains compatible with both polynomial additions and multiplications is to apply to such polynomials two randomization operations … first an additive masking operation by adding to each coefficient of the polynomial the prime number q. In order to effectively change the coefficients, they are lifted to a representation modulo q′ instead of modulo q, with q′ a multiple of q”) ([VIGILANT, para. 0053] “the additive masking can be removed easily by a simple “modulo q” operation. Therefore, polynomial additions and multiplications can be performed using randomized polynomials sharing the same masking (same q) without prior derandomization and the masking can be removed after addition”) ([VIGILANT, para. 0055] “In a first step S1, the processing system selects a multiplier integer t and determines a second integer q′ by multiplying the first integer q by the selected multiplier integer t, such that q′=q*t.”) ([VIGILANT, para. 0056] “the value of the multiplier integer t is selected such that the value of the second integer q′ corresponds to a width of the processor in order to keep modulo q′ operations single precision operations. Alternatively, t may be chosen such that q′ is above a predetermined minimal value corresponding to a specific security level. Alternatively, t may be a power of 2 in order to optimize the speed of modular operations modulo q′.”)
The same motivation to modify JOYE with VIGILANT as in the rejection of claim 1 applies.
Claim 20 is rejected under 35 U.S.C. 103 as being unpatentable over JOYE-VIGILANT-BAJPEYI in view of KWON (US-20230171084-A1).
Regarding claim 20, JOYE-VIGILANT-BAJPEYI teach all limitations of claim 19. JOYE further teaches “wherein the one or more computations in the auxiliary domain further comprise: an elementwise multiplication of a first Number Theoretic Transform (NTT) of the first masked polynomial and the second NTT of the second masked polynomial, and an inverse NTT of an output of the elementwise multiplication of the first NTT and the second NTT … ([JOYE, para. 0157] “The encrypted multiplication unit 332 may act on a ciphertext that comprises one or more random mask polynomials, and a body polynomial that is derived from the mask polynomials and a plaintext. For example, the ciphertext may be GLWE-based ciphertext as described herein. The encrypted multiplication unit 332 may act on a ciphertext represented in a compressed way by a seed 345 of a pseudo-random number generator, and by a representation 344 of the body polynomial in a Fourier domain of a number-theoretic transform.”) ([JOYE, para. 0161] “Fourier domain representations 354 of the computed polynomial products in the Fourier domain may be obtained. For example, the multiplication unit 338 may be multiplication unit 238 of FIG. 2. Typically, the Fourier domain representations comprise evaluations of the respective polynomials in a set of evaluation values, and multiplication 338 may be implemented by pointwise multiplication of the polynomial evaluations as known per se.”) ([JOYE, para. 0095] “An inverse INTT, 234, of the number theoretic transform 233 may be applied to the Fourier domain representation 246 of the product polynomial to obtain a representation 245 of the product polynomial in coefficient form h(X)=ΣihiXimod p(X).”)
However, JOYE-VIGILANT-BAJPEYI does not teach “… wherein the first NTT and the second NTT are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein one or more twiddle factors of the plurality of twiddle factors are masked using random numbers divisible by the first modulus.”.
In analogous teaching KWON teaches “… wherein the first NTT and the second NTT are computed using a plurality of butterfly operations that deploy a plurality of twiddle factors, wherein one or more twiddle factors of the plurality of twiddle factors are masked using random numbers divisible by the first modulus.” ([KWON, para. 0008] “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; and a controller configured to control the first memory, the second memory, and the NTT module, wherein the NTT module comprises a butterfly unit (BU) array that comprises a plurality of BUs configured to, for the performing of the NTT”) ([KWON, para. 0080] “Each of the plurality of BUs may include a multiplier configured to perform a multiplication on the twiddle factor and the second coefficient”) ([KWON, para. 0149] “BU1 may receive two coefficients and may output new two coefficients. BU1 may include a multiplication using a twiddle factor and a modular reduction operator configured to perform a modulus operation with a Q value used in each NTT”)
Thus, given the teaching of KWON, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention to combine the teaching of butterfly operations and twiddle factor by KWON into the teaching of a method to perform a cryptographic operation by JOYE-VIGILANT-BAJPEYI. One of ordinary skill in the art would have been motivated to do so because KWON recognizes the need to improve homomorphic encryption technology. ([KWON, para. 0006] “The homomorphic encryption technology may perform arithmetic operations on lattice-based encrypted data that is a type of quantum-resistant encryption and thus, is attaining a high attention. However, when original data is encrypted, a word size of data may increase, which may lead to increasing an operation processing time between ciphertexts.”) ([KWON, para. 0098] “The homomorphic encryption operation apparatus 10 of one or more embodiments may easily expand the NTT structure using a 16*5-BU array to improve data processing.”)
Pertinent Art
The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure.
MORIKAWA (US-20160352510-A1): This prior art teaches of a third encrypted polynomial that corresponds to a result of encrypting a third polynomial by use of a result of multiplying a first encrypted polynomial by a second encrypted polynomial, and outputs cryptographic information that represents the third encrypted polynomial. The first encrypted polynomial is a polynomial obtained by encrypting a first polynomial that corresponds to a first vector, and the second encrypted polynomial is a polynomial obtained by encrypting a second polynomial that corresponds to a second vector. The third polynomial includes a first term that has a coefficient based on an inner product of the first vector and the second vector and a second term other than the first term, in which a coefficient of the second term is masked.
RIETMAN (US-20180034630-A1): This prior art teaches of key generation device configured to generate a public key for use in a public key encryption device and a corresponding private key for use in a private key decryption device, the key generation device comprising a private key generator configured for obtaining in electronic form a private random value, and generating the private key, the private key comprising the private random value, and a public key generator configured for obtaining in electronic form a public set of bivariate polynomials, computing a public univariate polynomial by summing over univariate polynomials obtained by substituting the private random value into the polynomials of the public set, and generating the public key, the public key comprising the public univariate polynomial and the public set.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.Any inquiry concerning this communication or earlier communications from the examiner should be directed to AFAQ ALI whose telephone number is (571)272-1571. The examiner can normally be reached Mon - Fri 7:30am - 5:30pm EST.
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, ALI SHAYANFAR can be reached at (571) 270-1050. 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.
/A.A./
09/18/2026
/AFAQ ALI/Examiner, Art Unit 2434
/NOURA ZOUBAIR/Primary Examiner, Art Unit 2434
