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 as failing to comply with 37 CFR 1.84(p)(4) because reference character “150a” has been used to designate both the initial data structure labelled as 105a in paragraph 00030, line 4 of the specification and the stage before the first segmentation labelled as 150a in paragraph 42, line 4 of the specification.
The drawings are objected to as failing to comply with 37 CFR 1.84(u)(1) because the views are not consecutively numbered starting with 1. See drawings: 1 and 1A; 3 and 3A; and 4, 4A and 4B. If applicant amends the drawings to correct this problem, the applicant should amend the specification accordingly to refer to the new numbering.
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. 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.
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-18 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, 7 and 13 recite the limitation "of the N" in line 14. There is insufficient antecedent basis for this limitation in the claim. The independent claims do not mention or define N before the reference. Claims 2-6, 8-12, and 14-18 are rejected by virtue of their dependence on claims 1, 7 and 13, respectively.
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 13-18 are rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter. The claims do not fall within at least one of the four categories of patent eligible subject matter because the broadest reasonable interpretation of the "computer-readable media" encompasses signals per se. The specification discloses that "computer-readable medium, such as a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid state memory device, or an array of devices, including devices in a storage area network or other configurations" (Paragraph 00071, lines 2-5). A claim whose BRI covers both statutory and non-statutory embodiments embraces subject matter that is not eligible for patent protection and therefore is directed to non-statutory subject matter. See MPEP 2106.03(II). It is suggested that the claims be amended to recite a “non-transitory” computer readable medium to overcome this rejection.
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-5, 7-11 and 12-17 are rejected under 35 U.S.C. 103 as being unpatentable over Chang et al., “On the Capacity of Secure Distributed Matrix Multiplication”, hereinafter Chang, in view of Lastovetsky et al., “Two-Dimensional Matrix Partitioning for Parallel Computing on Heterogeneous Processors Based on Their Functional Performance Models”, hereinafter Lastovetsky. System claims 7-11 will be addressed before method claims 1-5 and media claims 12-17.
Regarding claim 7, Chang discloses a system comprising one or more computers (Figure 1a); and one or more memories storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations (Figure 1a), the operations comprising: obtaining, by one or more computers, a first matrix data structure (Figure 1a); segmenting, by one or more computers, the obtained matrix data structure into a set of M different matrix data structure portions, wherein M is an integer number greater than 1 (Equation 8); for each of the respective sets of K matrix data structure sub-portions: generating, by one or more computers, an obfuscation matrix having the same dimensions as each of the K matrix data structure sub-portions (Equation 10, random matrix K1); and generating, by one or more computers, an obfuscated representation of each respective set of K matrix data structure sub-portions that includes (i) the K matrix data structure sub-portions and (ii) the obfuscation matrix (Equation 10); and transmitting, by one or more computers, data representing each (of the N) obfuscated representation of the (K) matrix data structure sub-portions of the respective sets of M matrix data structure portions to a different computer for processing (Figure 1a).
Chang does not disclose a second segmentation step. Lastovetsky discloses segmenting, by one or more computers, each of the different M matrix data structure portions into respective sets of K matrix data structure sub-portions, where K is an integer number greater than 1 (Figure 2). It would have been obvious to one of ordinary skill of the art before the effective filing date of the invention to have modified Chang to add a second segmentation step disclosed by Lastovetsky because the second segmentation step lowers execution time by several orders of magnitude compared to single step parallel matrix multiplication (Page 121).
Regarding claim 8, Chang discloses the system disclosed in claim 7, further comprising receiving, by one or more computers, result data that includes a resultant matrix from each of the different computers, wherein each resultant matrix of the resultant matrices is a product of (a) a different matrix and (b) an obfuscated representation of one of the M matrix data structure sub-portions (Figure 1a); and decoding, by one or more computers, the result data, wherein decoding the result data comprises identifying, by one or more computers and for each resultant matrix, a particular resultant matrix that is a product of the different matrix and one of the K matrix data structures (Equation 11).
Regarding claim 9, Chang discloses the system disclosed in claim 7, wherein generating, by one or more computers, an obfuscated representation of each respective set of K matrix data structure sub-portions that includes (i) the K matrix data structure portions and (ii) the obfuscation matrix comprises generating, by one or more computers, an expression that corresponds to a polynomial having at least one of the K matrix data structure sub-portions as a coefficient and an obfuscation matrix as coefficients (Equation 10).
Regarding claim 10, Chang discloses the system disclosed in claim 9, the operations further comprising receiving, by one or more computers, a set of result data from each of the different computers, wherein each set of result data includes data representing an expression that corresponds to a product of (a) a different matrix and (b) the generated expression (Equation 11); and decoding, by one or more computers, the result data, wherein decoding the result data comprises: determining, by one or more computers, that the generated expression in each set of result data has unknown parameters (Equation 12, A1B); identifying, by one or more computers and based on the generated expressions the relevant unknown parameters for each expression, a particular resultant matrix that is a product of the different matrix and one of the K matrix data structures (Equation 11).
Regarding claim 11, Chang discloses the system of claim 7, wherein transmitting, by one or more computers, data representing each (of the N) obfuscated representation of the (K) matrix data structure sub- portions of the respective sets of M matrix data structure portions to a different computer for processing comprises: for each particular obfuscated representation of the N obfuscated representations: transmitting the particular obfuscated representation to a different remote computer that is remote from the one or more computers using one or more networks (Figure 1a).
Regarding claims 1-5, they are method claims corresponding to apparatus claims 7-11, respectively. They are rejected for the same reasons.
Regarding claims 13-17, they are media claims corresponding to apparatus claims 7-11, respectively. They are rejected for the same reasons.
Claims 6, 12 and 18 are rejected under 35 U.S.C. 103 as being unpatentable over the combination of Chang and Lastovetsky as applied to claims 1, 7 and 13, respectively, above, and further in view of Smith et al., “Anatomy of High-Performance Many-Threaded Matrix Multiplication”, hereinafter Smith. System claim 12 will be addressed before method claim 6 and media claim 18.
Regarding claim 12, the combination of Chang and Lastovetsky does not disclose that each core of the machines that receive the obfuscated matrix receives a segment. Smith discloses the data representing each (of the N) obfuscated representation of the (K) matrix data structure sub- portions of the respective sets of M matrix data structure portions to a different computer for processing comprises: for each particular obfuscated representation of the N obfuscated representations: transmitting the particular obfuscated representation to a different processing core of one the one or more computers (Section III C, Paragraph 1). It would have been obvious to one of ordinary skill in the art before the effective filing date of the invention to have modified the combination of Chang and Lastovetsky to use the matrix multiplication algorithm disclosed by Smith because multicore matrix multiplication is several times faster than single core performance (Section V D, Paragraph 1).
Regarding claim 6, it is a method claim corresponding to apparatus claim 12, and is rejected for the same reasons.
Regarding claim 18, it is a media claim corresponding to apparatus claim 12, and 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. Korthikanti et al. (US 10,169,296) discloses segmenting two matrices before transmitting them to external computers to perform matrix multiplication. Avestimehr et al. (US 2020/0387777) discloses a method for computing a large polynomial by segmenting, obfuscating and transmitting the data to potentially malicious nodes via homomorphic encryption. Keshtkarjahromi (US 2021/0044609) discloses a method of securing distributed matrix multiplication from malicious nodes by sending nodes redundant tasks to verify if the nodes are acting correctly.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Matthew Strapp whose telephone number is (571)272-9343. The examiner can normally be reached Monday-Friday 8:00 AM-4: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 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.
/M.S./
Matthew StrappExaminer, Art Unit 2182
571-272-9343
/ANDREW CALDWELL/Supervisory Patent Examiner, Art Unit 2182
Prosecution Insights