DETAILED ACTION
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Priority
Applicant’s claim to priority to provisional application No. 63/650,343 has been acknowledged.
Information Disclosure Statement
The 5/20/2025 IDS document has been considered by the examiner.
Drawings
Figure 1 should be designated by a legend such as --Prior Art-- because only that which is old is illustrated. See MPEP § 608.02(g). Corrected drawings in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. The replacement sheet(s) should be labeled “Replacement Sheet” in the page header (as per 37 CFR 1.84(c)) so as not to obstruct any portion of the drawing figures. If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claims 1-14 and 17-20 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention. Example independent claim 1 is drawn to a method comprising “a low part of the second value is mapped to a high part of a product value,” “a high part of the second value is mapped to a low part of the product value,” which renders the claim indefinite because it is not clear whether the mapping (“is mapped” language) is part of the scope of the claim. For instance, “is mapped” may refer to mapping that takes place before any computation, or by an agent outside of the method claim steps. As such, a person of ordinary skill in the art could not interpret the metes and bounds of the claim so as to understand how to avoid infringement because it is not clear whether the mapping is part of the claim steps or a description of, e.g., preexisting properties. It is suggested to positively recite the formula / definitions of, e.g., [0025]-[0028] of the instant specification.
Independent claim 17 recites substantially similar language where “one or more processing units” perform steps such that it is not clear whether the mapping is part of the claim steps. As such, claim 17 is rejected under the same analysis.
The dependent claims do not rectify this issue and are therefore likewise rejected. Additionally, dependent claim 4 recites “wherein the second value is represented by a plurality of shares;” dependent claim 12 recites “wherein the high part of the second value corresponds to a difference between a reference value and the high part of the product value.” These are rejected under the same analysis as above (i.e., it is not clear whether “is represented” and “corresponds to” are part of the scope of the claims).
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more. Note that the courts do not distinguish between mental processes that are performed entirely in the human mind and mental processes that require a human to use a physical aid (e.g., pen and paper or a slide rule) to perform the claim limitation (refer to MPEP 2106.04(a)(2)).
Example independent claim 17 recites the following abstract idea limitations: A [system] comprising:
[a first entity] to store a first value associated with a cryptographic operation (observation / storing information as part of a mental process—e.g., a first analyst writes down or memorizes information such as a first input value); and
[a second entity] communicatively coupled to the [first entity] (collaboration as part of certain methods of organizing human activity—e.g., the first analyst working together with a second analyst and communicating verbally or using pen and paper), the one or more processing units to:
compute a second value (evaluation as part of a mental process—e.g., the second analyst performs calculations according to a given formula), wherein:
a low part of the second value is mapped to a high part of a product value, wherein the product value comprises a multiplication product of a public value and the first value (observation and evaluation as part of a mental process—e.g., the second analyst either obtains known mappings, or implements their own mapping via pen and paper or memorization), and
a high part of the second value is mapped to a low part of the product value (observation and evaluation as part of a mental process—e.g., the second analyst either obtains known mappings, or implements their own mapping via pen and paper or memorization);
compute, by the processing device and using the second value, an output of the cryptographic operation (evaluation as part of a mental process—e.g., the second analyst performs calculations according to a given formula using given inputs), wherein the output of the cryptographic operation comprises at least one of:
a digital signature for an input into the cryptographic operation, or a ciphertext encrypting the input into the cryptographic operation (evaluation as part of a mental process—e.g., the second analyst uses a particular formula).
Example independent claim 17 recites the following limitations which may comprise additional elements that are sufficient to amount to significantly more than the judicial exception: the system further comprising a “processing device;” the first entity further comprising “one or more registers;” and the second entity further comprising “one or more processing units.”
With respect to step 2A, this judicial exception is not integrated into a practical application because adding the words "apply it" (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea is not considered to be sufficient—see MPEP 2106.05(f). In this case the claim is drawn to defining the inputs of, and then performing, a cryptographic calculation at a high level of generality. No particular machine is recited beyond base level computer components (registers and processing units) of any computer which could perform the abstract idea. Additionally, particular steps of the calculation are not recited beyond merely stating that an operation is performed using specific inputs. As such, the claim is drawn to steps performable by a human and is addressing a problem that transcends computing (i.e., defining inputs to a cryptographic calculation) rather improving the functioning of a computer, or an improvement to other technology or technical field.
With respect to step 2B, the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because the “processing device,” “one or more registers,” and “one or more processing units” are considered to be adding the words "apply it" (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea, which is not considered to be sufficient-see MPEP 2106.05(f). In this case, the processing device having one or more registers and processing units describes a base level computer for performing the steps of the abstract idea. Further, the claim merely suggests their use rather than any particular structure or arrangement. Since these limitations amount to using any computer to perform the abstract idea, they are not considered to include additional elements that are sufficient to amount to significantly more than the judicial exception.
Independent claim 1 recites substantially similar claim language, and is therefor rejected under the same analysis as claim 17.
Regarding dependent claim 2, it recites the following abstract idea limitations: wherein the first value comprises a random value and the public value comprises a public matrix associated with at least one of a Dilithium digital signature generation or a Kyber key encapsulation mechanism (further defining the input values as part of the mental process). As such, it is rejected under the same analysis as above.
Regarding dependent claims 3-4, they are rejected for substantially the same reasons as claim 2 above (i.e., they merely further define the input values as part of the abstract idea).
Regarding dependent claim 5, it recites the following abstract idea limitations: wherein computing the output of the cryptographic operation comprises: computing, using the low part of the second value and the input into the cryptographic operation, a hash value; and computing, using the hash value, the output of the cryptographic operation (evaluation as part of a mental process—e.g., the second analyst performs calculations using a given formula). As such, it is rejected under the same analysis as above.
Regarding claim 6, it is rejected for substantially the same reasons as claim 5 above (i.e., merely further specifying the formula at a high level of generality).
Regarding dependent claim 7, it recites the following abstract idea limitations: wherein computing the hash value comprises: computing, using the second value and the hash value, a third value (evaluation as part of a mental process—e.g., the second analyst performs calculations using a given formula); and determining, using the third value, whether the output of the cryptographic operation is to be maintained or discarded (observation and judgement as part of a mental process—e.g., the second analyst performs rejection sampling as part of a given algorithm). As such, it is rejected under the same analysis as above.
Regarding dependent claim 8, it recites the following abstract idea limitations: wherein determining whether the output of the cryptographic operation is to be maintained or discarded comprises: computing, using the third value, one or more hints indicating locations of one or more errors in the output of the cryptographic operation (performing mathematical calculations as part of Dilithium / Learning With Errors problem). Claim 8 merely further specifies the existing Dilithium algorithm without integration into a practical application or any additional elements. As such, it is rejected under the same analysis as above.
Regarding dependent claims 9-12, they are rejected for substantially the same reasons as claims 2-4 above (i.e., merely further specifying the input values).
Regarding dependent claims 13-14, they are rejected for substantially the same reasons as claims 7-8 above (i.e., merely further specifying the mathematical algorithm without integration into a practical application or any additional elements).
Regarding claims 18-20, they are substantially similar to claims 2, 5, and 7 above, and are therefore likewise rejected.
Regarding independent claim 15, it recites the following abstract idea limitations: A method comprising:
generating, by [an entity], a first value, wherein the first value is generated using (i) a public value and (ii) a first input into a cryptographic operation (observation and evaluation as part of a mental process—e.g., an analyst plugging given input values into a given formula via pen and paper), wherein the cryptographic operation comprises at least one of:
a Dilithium digital signature operation, or a Kyber key encapsulation mechanism operation (merely further specifying the formula as part of the mental process);
computing, by the [entity], a low part of the first value, wherein the low part of the first value comprises a remainder of the first value with respect to a first divisor (evaluation as part of a mental process—e.g., the analyst continuing to perform calculations using the formula), wherein the first divisor is between 15 and 2049 (merely further specifying the input values); and
computing, by the [entity] and using the low part of the first value, an output of the cryptographic operation (evaluation as part of a mental process—e.g., the analyst continuing to perform calculations using the formula).
Independent claim 15 recites the following limitations which may comprise additional elements that are sufficient to amount to significantly more than the judicial exception: the entity further comprising “a processing device.”
With respect to step 2A, this judicial exception is not integrated into a practical application because adding the words "apply it" (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea is not considered to be sufficient—see MPEP 2106.05(f), and because it merely recites performing calculations at a high level of generality, and according to the known CRYSTALS suite of cryptographic algorithms (select an α that is a divisor of q −1 and write r = r1 ·α+r0). No particular machine is recited beyond a base level computer (processing device) which could perform the abstract idea, nor add any structure beyond specific input values to use. The claim further does not comprise any particular use of the algorithms (e.g., for establishing a quantum-safe communication channel between networked computers). As such, the claim is drawn to steps performable by a human and is addressing a problem that transcends computing (i.e., modifying a cryptographic algorithm in a vacuum) rather improving the functioning of a computer, or an improvement to other technology or technical field.
With respect to step 2B, the claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception because the “processing device” is considered to be adding the words "apply it" (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea, which is not considered to be sufficient-see MPEP 2106.05(f). In this case, a “processing device” is the base level computer necessary to perform the abstract idea.
Regarding dependent claim 16, it is substantially similar to elements of claim 7 above, and is therefore likewise rejected.
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.
Claim(s) 1-5, 7-14, and 17-20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Berzati (“Exploiting Intermediate Value Leakage in Dilithium: A Template-Based Approach”) in view of Gribok (US 2023/0239136 A1).
Regarding claim 1, Berzati discloses: A method to perform a cryptographic operation, the method comprising:
generating, by a processing device, a first value;
Refer to at least the first paragraph on page 189, “Signature” on page 191, and the “Algorithm 2” table on page 192 of Berzati with respect to sampling (i.e., random selection) a vector y.
computing, by the processing device, a second value (i.e., w=Ay in Berzati), wherein:
wherein the product value comprises a multiplication product of a public value and the first value, and
Refer to at least pages 189 and 191-192 of Berzati with respect to computing w=Ay, where A is a public matrix. The value w is divided into high bits w1 and low bits w0.
computing, by the processing device and using the second value, an output of the cryptographic operation, wherein the output of the cryptographic operation comprises at least one of:
a digital signature for an input into the cryptographic operation, or a ciphertext encrypting the input into the cryptographic operation.
Refer to at least pages 191-192 of Berzati with respect to computing a signature using w (e.g., challenge c as the hash of the message; output vectors in Algorithm 2).
Berzati does not specify: a low part of the second value is mapped to a high part of a product value; a high part of the second value is mapped to a low part of the product value. However, Berzati in view of Gribok discloses: a low part of the second value is mapped to a high part of a product value; a high part of the second value is mapped to a low part of the product value.
Refer to at least [0051], [0055] and, [0064] of Gribok with respect to multiplication split into high parts and low parts, multiplication of high*low, and flipping inputs.
The teachings of both Berzati and Gribok relate to cryptography, hash calculation, and decomposition functions. As such, they are considered to be within the same field of art and combinable.
Therefore it would have been obvious to one of ordinary skill in the art before the filing date of Applicant’s invention to modify the teachings of Berzati to further implement a multiplication of high parts to low parts because the particular known technique was recognized as part of the ordinary capabilities of one skilled in the art
Regarding claim 2, it is rejected for substantially the same reasons as claim 1 above (i.e., sampling a vector y and obtaining a public matrix under the Dilithium scheme).
Regarding claim 3, it is rejected for substantially the same reasons as claims 1-2 above (i.e., the vector y).
Regarding claim 4, Berzati-Gribok discloses: The method of claim 1, wherein the second value is represented by a plurality of shares.
Refer to at least “Secret sharing” on page 207 of Berzati with respect to implementing secret sharing for values of w.
Regarding claim 5, Berzati-Gribok discloses: The method of claim 1, wherein computing the output of the cryptographic operation comprises: computing, using the low part of the second value and the input into the cryptographic operation, a hash value; and computing, using the hash value, the output of the cryptographic operation.
Refer to at least pages 191-192 with respect to calculating the hash value and verifying the signature, where w0 is used for the hint.
Regarding claim 7, Berzati-Gribok discloses: The method of claim 5, wherein computing the hash value comprises: computing, using the second value and the hash value, a third value (e.g., “new signature” in Berzati); and determining, using the third value, whether the output of the cryptographic operation is to be maintained or discarded.
Refer to at least “Signature” on page 191 of Berzati with respect to the rejection sampling loop of Dilithium.
Regarding claim 8, Berzati-Gribok discloses: The method of claim 7, wherein determining whether the output of the cryptographic operation is to be maintained or discarded comprises: computing, using the third value, one or more hints (hint / makehint in Berzati) indicating locations of one or more errors in the output of the cryptographic operation.
Refer to at least the first paragraph of 189 and the first paragraph of 191 of Berzati with respect to learning with errors and Dilithium.
Regarding claim 9, it is rejected for substantially the same reasons as claim 1 above (e.g., “Decompose” on page 191 of Berzati defining w1 and w0).
Regarding claim 10, it is rejected for substantially the same reasons as claim 9 above.
Regarding claim 11, it is rejected for substantially the same reasons as claim 1 above (e.g., flipping inputs).
Regarding claim 12, it is rejected for substantially the same reasons as claim 9 above (e.g., w1 = (w-w0)/a).
Regarding claim 13, Berzati-Girbok discloses: The method of claim 1, wherein computing the output of the cryptographic operation comprises performing, using the second value, a first modulo 2d arithmetic computation to obtain a first portion of the output of the cryptographic operation, wherein d is a first number of bits of the low part of the second value.
Refer to at least “Algorithm 1” on page 191 of Berzati with respect to the Power2Round function of Dilithium.
Regarding claim 14, it is rejected for substantially the same reasons as claims 1, 7-8, and 13 above (i.e., repeating the operation with new values and/or rejection sampling).
Regarding independent claim 17, it is substantially similar to independent claim 1 above, and is therefore likewise rejected.
Regarding claims 18-20, they are substantially similar to claims 2, 5, and 7 above, and are therefore likewise rejected.
Claim(s) 6 is/are rejected under 35 U.S.C. 103 as being unpatentable over Berzati-Gribok as applied to claims 1-5, 7-14, and 17-20 above, and further in view of Azouaoui (US 2023/0396436).
Regarding claim 6, Berzati-Gribok does not specify: wherein computing the hash value comprises: transforming the second value from a first plurality of arithmetic shares to a second plurality of Boolean shares; and computing the hash value using the second plurality of Boolean shares.
Refer to at least the abstract of Azouaoui with respect to implementing Boolean shares for masking as part of the Dilithium scheme.
The teachings of Berzati-Gribok and Azouaoui both concern Dilithium and masking, and are considered to be within the same field of endeavor and combinable as such. Further, Berzati already discusses secret sharing on page 207.
Therefore it would have been obvious to one of ordinary skill in the art before the filing date of Applicant’s invention to modify the teachings of Berzati-Gribok to further implement Boolean shares for masking for at least the purpose of better preventing side-channel attacks.
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claim(s) 15-16 is/are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Berzati (“Exploiting Intermediate Value Leakage in Dilithium: A Template-Based Approach”).
Regarding claim 15, Berzati discloses: A method comprising:
generating, by a processing device, a first value, wherein the first value is generated using (i) a public value (e.g., at least pages 189 and 191-192 of Berzati with respect to public matrix A) and (ii) a first input into a cryptographic operation (e.g., pages 191-192 of Berzati, where the public matrix is used as part of calculations such as for w=Ay), wherein the cryptographic operation comprises at least one of:
a Dilithium digital signature operation, or a Kyber key encapsulation mechanism operation;
Refer to at least 2.2 of Berzati concerning Dilithium.
computing, by the processing device, a low part of the first value, wherein the low part of the first value comprises a remainder of the first value with respect to a first divisor, wherein the first divisor is between 15 and 2049; and
Refer to at least “Decompose” on page 191 of Berzati with respect to low part w0 = r moda.
Refer to at least 2.1 of Berzati with respect to integer values of a.
computing, by the processing device and using the low part of the first value, an output of the cryptographic operation.
Refer to at least pages 191-192 of Berzati with respect to computing a signature using the previous values (e.g., w1 and w0).
Regarding claim 16, it is substantially similar to elements of claim 7 above, and is therefore likewise rejected.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to VADIM SAVENKOV whose telephone number is (571)270-5751. The examiner can normally be reached 12PM-8PM.
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, Jeffrey L Nickerson can be reached at (469) 295-9235. 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.
/Jeffrey Nickerson/Supervisory Patent Examiner, Art Unit 2432
/V.S/Examiner, Art Unit 2432
Prosecution Insights