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 .
Drawings
The drawings are objected to under 37 CFR 1.83(a). The drawings must show every feature of the invention specified in the claims. Therefore, the
Claims 2 and 8 recite “bucket status memory”. However, “bucket status memory” is not shown in the drawings.
Claims 3 and 9 recite “a second adder” and “a third adder”. However, “a second adder” and “a third adder” are not shown in the drawings.
Claims 1 and 7 recite “the first input being coupled to the output of the respective multiplexer, the second input being configured for obtaining the value of Pi". However, Figure 1 shows first input and second input as “being coupled” to the multiplexer.
Claim 7 recites a first memory … for storing successive values of di and a second memory for storing successive values of Pi. The figures, specifically, Fig. 1, shows a single low latency memory that the specification describes as storing these values.
The features specified above must be shown or the feature(s) canceled from the claim(s). No new matter should be entered.
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). 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.
Specification
The disclosure is objected to because of the following informalities:
Page 1, line 7 refers to “Knowledge,”. There appears to be an extra comma.
Page 4, line 22 refers to “MSM subsystem 110”. Figure 1, reference number 110 refers to “MSM FPGA or ASIC system”.
Appropriate correction is required.
Claim Rejections - 35 USC § 112(a)
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
The following is a quotation of the first paragraph of pre-AIA 35 U.S.C. 112:
The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor of carrying out his invention.
Claims 2 and 7-10 are rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the written description requirement.
Regarding claim 2, the claim recites “bucket status memory”. However, the specification discloses “Finally, associated with each bucket is a flag (also not shown) which is used to indicate whether or not the bucket contains valid data. We assume, for the sake of example, that the flag is set to “1” when the bucket contains valid data and is otherwise zero”. The specification does not disclose “bucket status memory”. It is understood that “bucket status memory” refers to “flag”.
Regarding claim 8, it is a system claim corresponding to apparatus claim 2. It is rejected for the same reasons.
Regarding claim 7, it recites a first memory … for storing successive values of di and a second memory for storing successive values of Pi. The figures, specifically, Fig. 1, sows a single low latency memory that the specification describes as showing these values. Spec. p. 8 lines 26-32.
As to any claim that was rejected but not discussed, it is rejected because it depends on one of the claims discussed above.
Claim Rejections - 35 USC § 112(b)
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-11 are rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claims 1 and 7 recites the limitation "The value of an active bucket", the respective accumulator”, “the respective partition” and “the corresponding accumulator” in lines 9-11. There is insufficient antecedent basis for this limitation in the claim.
Claims 1 and 7 recites the limitation “the selected bucket” in line 14. There is insufficient antecedent basis for this limitation in the claim.
Claims 1 and 7 recites the limitation “at least one multiplexer” in line 16. There is insufficient antecedent basis for this limitation in the claim.
Claims 1 and 7 recites the limitation “the output of the respective multiplexer” in line 19. There is insufficient antecedent basis for this limitation in the claim.
Claims 1 and 7 recites the limitation “the sum of the first input and the second input” in line 21. There is insufficient antecedent basis for this limitation in the claim.
Claims 1 and 7 recites the limitation “the respective output of each first adder” in line 25. There is insufficient antecedent basis for this limitation.
Claims 1 and 7 recites the limitation “the A computed sums” in line 27. There is insufficient antecedent basis for this limitation.
Claims 2 and 8 recites the limitation “the corresponding bucket” in line 3. There is insufficient antecedent basis for this limitation.
Claims 3 and 9 recites the limitation “the output of the second adder” in line 5. There is insufficient antecedent basis for this limitation.
Claims 5 and 11 recites the limitation “the zk-SNARK protocol” in line 2-3. There is insufficient antecedent basis for this limitation.
As to any claim not specifically addressed above, it is rejected because it depends on one of the claims discussed above.
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.
Claims 1-2, 4-8 and 10-11 are rejected under 35 U.S.C. 103 as being unpatentable over Xavier (PipeMSM: Hardware Acceleration for Multi-Scalar Multiplication) in view of Kusiak (Design of Modular Digital Circuits for Testability).
Regarding claim 1, Xavier discloses Figure 6, the design includes 29 bucket accumulators that are divided into 8 segments, each of them enclosing 64 buckets (page 8, column 1, lines 52-54); The bucket method partitions each xn from equation (27) into K parts such that each partition consists of c bits and K = [b/c]. (page 5, column 2, lines 33-34); tj = Gj are points of an Elliptic Curve (EC) group G over a prime order field Fq and xj are scalars. (page 1, column 1, lines 34-35); Xavier therefore teaches a plurality A of accumulators as claimed. Xavier also teaches a single scheduler circuit (Figure 6, scheduler) configured to perform the functionality of both the scheduler and multiplexer of the claims; Xavier also teaches a final accumulator coupled to the output of the EC adder. (Fig. 6 final accumulator).
Xavier does not teach the scheduler and the multiplexer as separate components.
Kusiak discloses the concept of partitioning that aims at splitting functions into logically separable units.
It would have been obvious to one of ordinary skill in the art before the effective filling date of the application to modify the design circuit of Xavier, to apply the general design principle known as “partitioning”, taught by Kusiak., to separate the scheduling from the routing of the data into a scheduler and a multiplexer. This modification would have been obvious because partitioning simplifies testing and troubleshooting and facilitates built-in test equipment (BITE) designs as the fault isolation can be easily achieved. (Kusiak: page 51, column 1, lines 13-18)
Regarding claim 2, Xavier discloses that the buckets initiate at zero (page 6, column 2, lines 6-7); If the bucket is empty then the input is written to it. If the bucket already contains a point then the accumulator sends an addition task to the EC adder with the current value and the new input. (page 8, column 2, lines 8-11); The bucket accumulator handles the output from the EC adder in higher priority than new input data. (page 8, column 2, lines 13-14)
Regarding claim 4, Xavier discloses tj = Gj as points on an Elliptic Curve (EC) group (page 1, column 1, line 34); EC adder. (Figure 6)
Regarding claim 5, Xavier discloses the application of MSM in cryptography, in particular ZK-SNARK. (page 1, column 1, lines 31-32)
Regarding claim 6, Xavier discloses that it is possible to squeeze in more than one EC adder in our design. (page 8, column 2, lines 30-31)
Regarding claims 7-8 and 10-11, they are system claims corresponding to apparatus claims 1-2 and 4-5 respectively. They are rejected for the same reasons.
Claims 3 and 9 are rejected under 35 U.S.C. 103 as being unpatentable over Xavier in view of Kusiak and further in view of Zhang (PipeZK: Accelerating Zero-Knowledge Proof with a Pipelined Architecture).
Regarding claim 3, the combination of Xavier in view of Kusiak teaches the invention substantially as claimed. See the rejection of claim 1 above. The combination of Xavier in view of Kusiak does not disclose the summation of the buckets in each accumulator and the summation of the accumulators.
Zhang discloses the Pippenger algorithm, we firstly represent the scalar k under radix 28, where s is a chosen window size. This is equivalent to dividing the λ-bit scalar k into λ / 8 chunks with s bits each. An example is shown in Figure 8, where λ = 12 and s = 4. Computing Q can be done with the following steps: First, sum up the elements in each chunk i (s-bit wide) to get Gi. Then sum up 2ix8 Gi to get the final result, with 2ix8 as the weights. (page 423, column 1, lines 34-41)
It would have been obvious to one of ordinary skill in the art before the effective filling date of the application to apply the Pippenger Algorithm to achieve high resource utilization and better load balancing. (page 423, column 1, lines 33-34)
Regarding claim 9, it is a system claim corresponding to apparatus claim 3. It is rejected for the same reasons.
Discussion of Pertinent Art
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Xavier explains that their design was implement using the Xilinx Alveo U55C accelerator board. Xavier p. 9 col. 1, § V Implementation. The non-patent literature references describing aspects of the U55C are pertinent to Xavier’s implementation.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JAIME JOSE CUEBAS RUIZ whose telephone number is (571)272-9131. The examiner can normally be reached M-F 9:00 am - 6:00 pm.
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, Andrew T Caldwell can be reached at 571-272-3702. 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.
/JC/
JAIME JOSE CUEBAS RUIZExaminer, Art Unit 2182
(571)272-9131
/ANDREW CALDWELL/Supervisory Patent Examiner, Art Unit 2182
Prosecution Insights