DETAILED ACTION
Claims 1-20 are pending in this action.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1-8, 10-16 and 18-20 are rejected under 35 U.S.C. 103 as being anticipated by Bai et al. (“Crystals-Dilithium Algorithm Specifications and Supporting Documentation (Version 3.1),” https://pq-crystals.org/dilithium/, February 8, 2021) [hereinafter “Bai”] in view of Millerd et al. (US Patent No. 4,942,349) [hereinafter “Millerd”]
As per claim 1, Bai teaches a lattice-based cryptographic engine comprising: a MakeHint unit to generate hints for polynomial coefficients (Section 5.1, makeHint routine that produces a hint for calculating polynomial coefficient); and logic hardware coupled to the MakeHint unit, the logic hardware comprising: a hint sum unit configured to add hints for coefficients of a polynomial, compare a hint sum to a threshold, and generate an invalid signal in response to the hint sum exceeding the threshold (Table 2, hint h is a plurality of 1-bit hints and w is the max number of 1-bit hints that are allowed under a respective NIST Security Level); a sample buffer configured to receive the hints (Section 5.4 para. 3, storing bits in h vector indicating nonzero coefficients); a hint bitpack coupled to store indices of non-zero hints (Section 5.4 para. 3, bit packed representation including the h vector sent with signature); and a controller coupled to control transfer of hints to output registers (Section 5.1, hint vector h will be outputted if it doesn’t exceed threshold value ω) (Examiner Note: using a buffer, controller and registers to simply output data is considered well-known in the art).
Bai does not explicitly teach receiving and processing a plurality of data in parallel in a cycle and configured to accumulate the data, compare a sum to a threshold each cycle and generate an output signal in response to the sum exceeding the threshold. Millerd teaches receiving and processing a plurality of data in parallel in a cycle and configured to accumulate the data (Col. 4 lines 59-68, rain drops are sensed in parallel and sent to an accumulator counter), compare a sum to a threshold each cycle (Col. 4 lines 66-67, lines periodically checking the threshold counter) and generate an output signal in response to the sum exceeding the threshold (Col. 4 line 68 – Col. 5 line 2, producing an output signal for the wiper if the counter exceeds a counter).
At the time of filing, it would have been obvious to one of ordinary skill in the art to combine Bai with the teachings of Millerd, receiving and processing a plurality of data in parallel in a cycle and configured to accumulate the data, compare a sum to a threshold each cycle and generate an invalid signal in response to the sum exceeding the threshold, to apply the utility of a threshold counter to other types of data including hints generated by makehint units. Examiner notes that a hardware implementation of a threshold counter would be easily adapted and combined with any unit that outputs counts like the makeHint units.
As per claim 2, the combination of Bai and Millerd teaches the engine of claim 1 wherein the hints are encoded and embedded into a signature (Bai; Section 5.4 para. 3, encoding h vector, i.e. hint vector, into signature).
As per claim 3, the combination of Bai and Millerd teaches the engine of claim 1 and further comprising: a memory storing the polynomial coefficients (Examiner Note: storage memory for simply storing data is considered well-known in the art); decompose units coupled to receive coefficients from the memory to selectively provide output to the memory (Bai; Fig. 3, Decompose provides output to a memory for UseHint, MakeHint, HighBit and LowBit to use), and provide decomposed values (Bai; Fig. 3, Decompose provides values); UseHint units selectively coupled to the decompose units (Examiner Note: connecting algorithms in a circuit implementation via multiplexer or switches is considered well known in the art); and encode units selectively coupled to the UseHint units or the decompose units (Examiner Note: connecting algorithms in a circuit implementation via multiplexer or switches is considered well known in the art).
As per claim 4, the combination of Bai and Millerd teaches the engine of claim 3 and further comprising a multiplexer coupled between the decompose units and the UseHint units to alternately couple the decompose units to the encode units or couple the decompose units to the UseHint units and encode units (Examiner Note: connecting algorithms in a circuit implementation via multiplexer or switches is considered well known in the art).
As per claim 5, the combination of Bai and Millerd teaches the engine of claim 3 and further comprising a switch coupled between the decompose units and the memory (Bai; Examiner Note: connecting algorithms in a circuit implementation via multiplexer or switches is considered well known in the art).
As per claim 6, the combination of Bai and Millerd teaches the engine of claim 1 wherein the threshold is 75 (Bai; Table 2, NIST security level 5 has ω threshold set to 75).
As per claim 7, the combination of Bai and Millerd teaches the engine of claim 1 wherein the MakeHint unit further comprises a decompose unit coupled to decompose bits of a polynomial t of a Dilithium public key into lower bits and higher bits (Bai; Section 2.4, extracting higher-order and lower-order bits from public key bits via a Decompose procedure which is used in conjunction with MakeHint) see also (Bai; Section 1.1 and Fig. 1, public key generated from combination of polynomial and Matrix).
As per claim 8, the combination of Bai and Millerd teaches the engine of claim 7 and further comprising a Hash and SampleInBall unit to perform a SampleInBall operation on the higher bits (Bai; Fig. 4, SampleinBall operation performed on HighBits).
As per claim 10, the Bai teaches a lattice-based cryptographic engine comprising: a MakeHint unit including a decompose unit (Section 2.4, Decompose procedure) to generate hints for polynomial coefficients (Section 5.1, makeHint routine that produces a hint for calculating polynomial coefficient); the decompose unit coupled to decompose received polynomial t into higher bits and lower bits (Fig. 3, Decompose used to determine high and low bits) and logic hardware coupled to the MakeHint unit, the logic hardware comprising: a hint sum unit configured to add hints for coefficients of a polynomial, compare a hint sum to a threshold, and generate an invalid signal in response to the hint sum exceeding the threshold (Table 2, hint h is a plurality of 1-bit hints and w is the max number of 1-bit hints that are allowed under a respective NIST Security Level); a sample buffer configured to receive the hints (Section 5.4 para. 3, storing bits in h vector indicating nonzero coefficients); a hint bitpack coupled to store indices of non-zero hints (Section 5.4 para. 3, bit packed representation including the h vector sent with signature); and a controller coupled to control transfer of hints to output registers (Section 5.1, hint vector h will be outputted if it doesn’t exceed threshold value ω) (Examiner Note: using a buffer, controller and registers to simply output data is considered well-known in the art).
Bai does not explicitly teach receiving and processing a plurality of data in parallel in a cycle and configured to accumulate the data, compare a sum to a threshold each cycle and generate an output signal in response to the sum exceeding the threshold. Millerd teaches receiving and processing a plurality of data in parallel in a cycle and configured to accumulate the data (Col. 4 lines 59-68, rain drops are sensed in parallel and sent to an accumulator counter), compare a sum to a threshold each cycle (Col. 4 lines 66-67, lines periodically checking the threshold counter) and generate an output signal in response to the sum exceeding the threshold (Col. 4 line 68 – Col. 5 line 2, producing an output signal for the wiper if the counter exceeds a counter).
At the time of filing, it would have been obvious to one of ordinary skill in the art to combine Bai with the teachings of Millerd, receiving and processing a plurality of data in parallel in a cycle and configured to accumulate the data, compare a sum to a threshold each cycle and generate an invalid signal in response to the sum exceeding the threshold, to apply the utility of a threshold counter to other types of data including hints generated by makehint units.
As per claim 11, the substance of the claimed invention is identical or substantially similar to that of claim 2. Accordingly, this claim is rejected under the same rationale.
As per claim 12, the substance of the claimed invention is identical or substantially similar to that of claim 3. Accordingly, this claim is rejected under the same rationale.
As per claim 13, the substance of the claimed invention is identical or substantially similar to that of claim 4. Accordingly, this claim is rejected under the same rationale.
As per claim 14, the substance of the claimed invention is identical or substantially similar to that of claim 5. Accordingly, this claim is rejected under the same rationale.
As per claim 15, the substance of the claimed invention is identical or substantially similar to that of claim 6. Accordingly, this claim is rejected under the same rationale.
As per claim 16, the substance of the claimed invention is identical or substantially similar to that of claim 8. Accordingly, this claim is rejected under the same rationale.
As per claim 18, the substance of the claimed invention is identical or substantially similar to that of claim 1. Accordingly, this claim is rejected under the same rationale.
As per claim 19, the substance of the claimed invention is identical or substantially similar to that of claim 2. Accordingly, this claim is rejected under the same rationale.
As per claim 20, the substance of the claimed invention is identical or substantially similar to that of claim 3. Accordingly, this claim is rejected under the same rationale.
Claims 9 and 17 are rejected under 35 U.S.C. 103 as being unpatentable over Bai and Millerd in view of Zheng et al. (“Optimized Vectorization Implementation of Cystals-Dilithium”, Journal of Latex Class Files, Vol. 14 No. 8, August 2021) [hereinafter “Zheng”].
As per claim 9, the combination of Bai and Millerd teaches the engine of claim 8 with MakeHint units comparing higher bits of polynomial t (Bai; Section 2.4, MakeHint, UseHint, Decompose, LowBit, HighBit defined).
Bai does not explicitly teach running Dilithium functions in parallel. Zheng teaches running Dilithium functions in parallel (Page 5, explanation and code example of an implementation of running parallel computations using Dilithium function like LowBit). At the time of filing, it would have been obvious to one of ordinary skill in the art to combine Bai and Millerd with the teachings of Zheng, running Dilithium functions in parallel, to improve the speed of and efficiency of the overall algorithm performance.
As per claim 17, the substance of the claimed invention is identical or substantially similar to that of claim 9. Accordingly, this claim is rejected under the same rationale.
Response to Arguments
Applicant’s arguments with respect to the rejection of claims 1-20 under 35 U.S.C. 103 have been fully considered. In light of the new amendments, a new prior art reference has been introduced and cited to, Millerd.
To expedite prosecution, Examiner is open to conducting an after-final interview to discuss claim amendments to overcome the current rejection and/or place the application into condition for allowance.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Beckwith et al. (WO-2023055377-A1), Mao et al. (US PGPUB No. 2024/0143524), Berzati et al. (EP-4422126-A1), Vemula (US Patent No. 7,596,707), Sailada et al., "Crystal Dilithium Algorithm For Post Quantum Cryptography:Experimentation and Usecase for eSign," 2022 First International Conference on Electrical, Electronics, Information and Communication Technologies (ICEEICT), Trichy, India, 2022, pp. 1-6, doi: 10.1109/ICEEICT53079.2022.9768654) and Sharma et al. ("Analysis of Crystals-Dilithium for BlockChain Security," 2021 2nd International Conference on Secure Cyber Computing and Communications (ICSCCC), Jalandhar, India, 2021, pp. 160-165, doi: 10.1109/ICSCCC51823.2021.9478087) all disclose various aspects of the claimed invention including optimizing the Dilithium algorithms such as makeHint and useHint.
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 PETER C SHAW whose telephone number is (571)270-7179. The examiner can normally be reached Max Flex.
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, Carl Colin can be reached at 571-272-3862. 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.
/PETER C SHAW/Primary Examiner, Art Unit 2493 March 31, 2026