DETAILED ACTION
Claims 1-20 are presented for examination.
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 § 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 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 13 recite two time “an output of the multiplier” and it is not clear if these two recitations refer to a same output or to different outputs. For the purpose of examination, it is construed that the two outputs are different. The dependent claims inherit this rejection.
Claims 1 and 13 recite two time “a second multiplexer coupled to an output of the multiplier and to the first input to, when enabled, output a selection between the output of the multiplier and the subtractor. This is inconsistent because if a multiplexer is coupled to an output of the multiplier and to the first input then it should output a selection between the output of the multiplier and the first input. For the purpose of examination and based at least on Figures 11(d) and 12(a), the claim is construed as reciting “a second multiplexer coupled to an output of the multiplier and to the output of the subtractor, when enabled, output a selection between the output of the multiplier and the output of the subtractor”. The dependent claims inherit this rejection.
Claim 10 recites “wherein the scratchpad memory is to provide and receive data to/from register file banks of the register file are not servicing a butterfly compute unit”. It is not clear what entity is not servicing a butterfly compute unit. The claim is construed as reciting “wherein the scratchpad memory is to provide and receive data to/from register file banks of the register file that are not servicing a butterfly compute unit”.
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-11 and 13-19 are rejected under 35 U.S.C. 103 as being unpatentable over Ren (US Pub.No.2022/0255721) in view of Duong-Ngoc et al “Configurable Butterfly Unit Architecture for NTT/INTT in Homomorphic Encryption”, IEEE 18th ISOCC conference, 2021, hereinafter, Duong.
Re Claim 1. Ren discloses an apparatus comprising: a register file to at least store polynomials to be processed; and a plurality of butterfly compute datapaths coupled to the register file to process the polynomials (i.e. Butterfly processing is created for repeated execution of such an operation. As shown in FIG. 4, a first polynomial coefficient storage subunit 2351 and a second polynomial coefficient storage subunit 2352 are provided in a number theoretic transform unit 235. The first polynomial coefficient storage subunit 2351 stores polynomial coefficients of an original polynomial loop. After being fetched from a predetermined position, a polynomial coefficient is processed by using a twiddle factor and is placed into another predetermined position of the second polynomial coefficient storage subunit 2352. In this way, new polynomial coefficients are obtained. Conversely, after being fetched from a predetermined position of the second polynomial coefficient storage subunit 2352, a polynomial coefficient is processed by using a twiddle factor and is placed into another predetermined position of the first polynomial coefficient storage subunit 2351. In this way, rearrangement processing is repeated until a predetermined requirement is satisfied, and the new polynomial coefficients stored in the first polynomial coefficient storage subunit 2351 or the second polynomial coefficient storage subunit 2352 is a result of number theoretic transform) [Ren, para.0104].
Ren does not explicitly disclose whereas Duong discloses: comprising: a multiplier coupled to a first input and a second input to multiply the first and second input to, when enabled, generate a multiplication output [Duong, Fig.1 (c), shows a multiplier takes a first input in2 and a second input when enabled to generate an output], a first multiplexer coupled to an output of the multiplier and to the first input to, when enabled, output a selection between the output of the multiplier and the first input [Duong, Fig.1 (c), shows a first multiplexer -bottom middle multiplexer- coupled to the first input in2 and to the output of the multiplier], an adder to add, when enabled, a third input to the selected output of the first multiplexer [Duong, Fig.1 (c), shows an adder coupled to the output of the first multiplexer and to a third input being the output of the upper middle multiplexer], a subtractor to subtract, when enabled, an output of the multiplier from the third input [Duong, Fig.1 (c), shows a subtractor coupled to the output of the multiplier when enabled and to the third input being the output of the upper middle multiplexer], and a second multiplexer coupled to an output of the multiplier and to the first input (see 112(b) rejection) to, when enabled, output a selection between the output of the multiplier and the subtractor [Duong, Fig.1 (c), shows a second multiplexer- bottom right multiplexer- coupled to the output of the multiplier and to the output of the subtractor to select between the two].
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify Ren with Duong because the butterfly unit BU designs achieve 3× acceleration with more efficient resource utilization compared with previous works. Thus, the proposed BU architecture is worthwhile to develop NTT INTT accelerators in advanced homomorphic encryption systems [Duong, Abstract]
Re Claim 2. Ren in view of Duong discloses the apparatus of claim 1, wherein the polynomials include operands to be operated on by the butterfly compute datapaths (i.e. Butterfly processing is created for repeated execution of such an operation. To be specific, two storage subunits are set for the polynomial loop, and after polynomial coefficients are fetched from predetermined positions of the first storage subunit and processed by using a twiddle factor, resulting polynomial coefficients are placed into other predetermined positions of the second storage subunit. Conversely, after polynomial coefficients are fetched from predetermined positions of the second storage subunit and processed by using a twiddle factor, resulting polynomial coefficients are placed into other predetermined positions of the first storage subunit. In this way, the process of repeated processing by using the twiddle factor in number theoretic transform is simplified, and the repeated process is considered as rearrangement operation for different storage subunits in the same process. Operations of fetching and processing of a polynomial coefficient, and writing a result into a different polynomial coefficient position each time are called butterfly processing) [Ren, para.0071].
Re Claim 3. Ren in view of Duong discloses the apparatus of claim 1, wherein the polynomials include twiddle factors (i.e. obtaining a twiddle factor corresponding to the first polynomial coefficient pair from the twiddle factor storage subunit) [Ren, para.0024].
Re Claim 4. Ren in view of Duong discloses the apparatus of claim 1, wherein the polynomials include key information (i.e. After key switch, the polynomial coefficient of the ciphertext is changed to another polynomial coefficient of the ciphertext. Key switch can be decomposed into a combination of a number theoretic transform, an inverse number theoretic transform, a modulus multiply, and a modulus switch) [Ren, para.0068].
Re Claim 5. Ren in view of Duong discloses the apparatus of claim 1, wherein the register file is divided into dedicated banks for each reconfigurable butterfly compute unit (i.e. Bank refers to a storage module, where storage modules each store one memory queue sequentially, for example, a queue formed by polynomial coefficients in the present disclosure. In the example shown in FIG. 8, the first polynomial coefficient storage subunit 2351 or the second polynomial coefficient storage subunit 2352 each include several banks 23511, and each bank stores a queue of 8 polynomial coefficients. When the ciphertext is expressed as a polynomial of 64 polynomial coefficients, the 64 polynomial coefficients may be distributed in 8 memories, and 8 polynomial coefficients are stored in each bank……………………..As shown in FIG. 4, a first polynomial coefficient storage subunit 2351 and a second polynomial coefficient storage subunit 2352 are provided in a number theoretic transform unit 235. The first polynomial coefficient storage subunit 2351 stores polynomial coefficients of an original polynomial loop. After being fetched from a predetermined position, a polynomial coefficient is processed by using a twiddle factor and is placed into another predetermined position of the second polynomial coefficient storage subunit 2352) [Ren, para.0072, 0108], (i.e. Through scheduling by the scheduler 234, several number theoretic transform units 235 and several arithmetic logic units 236 can perform different tasks separately, or form a pipeline to execute different stages of a same task. In this way, different types of algorithms are efficiently compatible in the embodiments of the present disclosure, improving global performance, scalability, and versatility) [Ren, para.0105].
Re Claim 6. Ren in view of Duong discloses the apparatus of claim 5, wherein the dedicated banks and associated reconfigurable butterfly compute unit comprise a compute tile (i.e. As shown in FIG. 4, a first polynomial coefficient storage subunit 2351 and a second polynomial coefficient storage subunit 2352 are provided in a number theoretic transform unit 235…………….. Operations of fetching and processing of a polynomial coefficient, and writing a result into a different polynomial coefficient position each time are called one butterfly processing, which is processed by the butterfly processing subunit 2354) [Ren, para.0108, Fig.4 shows the compute tile structure]
Re Claim 7. Ren in view of Duong discloses the apparatus of claim 6, wherein a number of compute tiles is scalable (i.e. Regardless of which homomorphic encryption algorithm, the algorithm can be finally decomposed into different combinations of number theoretic transform and arithmetic logic (modulus add, modulus multiply, and a combination thereof). In the embodiments of the present disclosure, the number theoretic transform unit 235 is introduced to execute number theoretic transform, and the arithmetic logic unit 236 is introduced to execute arithmetic logic. Through scheduling by the scheduler 234, several number theoretic transform units 235 and several arithmetic logic units 236 can perform different tasks separately, or form a pipeline to execute different stages of a same task. In this way, different types of algorithms are efficiently compatible in the embodiments of the present disclosure, improving global performance, scalability………….assign a number theoretic transform included in the operation to at least one of one or more number theoretic transform units) [Ren, para.0105, 0143].
Re Claim 8. Ren in view of Duong discloses the apparatus of claim 1, further comprising: scratchpad memory to provide and receive data to/from the register file (i.e. the acceleration unit 230 performs addressing on the parameters in the memory 210 based on the address of the parameters in the memory 210, and temporarily stores the parameters in its internal buffer for homomorphic encryption computing………….. The direct memory access unit 237 receives the access memory address, and indicates the memory interface 238 for performing data transmission with the memory 210 to fetch, from the memory 210 according to the access memory address, the data required by the to-be-executed homomorphic encryption instruction. In this case, the number theoretic transform unit 235 and the arithmetic logic unit 236 can obtain the data directly from the direct memory access unit 237 during actually instruction execution) [Ren, para.0090, para.0102, Fig.3, direct access memory unit 237].
Re Claim 9. Ren in view of Duong discloses the apparatus of claim 8, further comprising: [high-bandwidth] memory to provide data to the register file or scratchpad memory (i.e. The direct memory access unit 237 receives the access memory address, and indicates the memory interface 238 for performing data transmission with the memory 210 to fetch, from the memory 210 according to the access memory address, the data required by the to-be-executed homomorphic encryption instruction. In this case, the number theoretic transform unit 235 and the arithmetic logic unit 236 can obtain the data directly from the direct memory access unit 237 during actually instruction execution) [Ren, para.0102, Fig.3, memory 210].
Ren does not explicitly disclose that the memory is high-bandwidth, however it would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify Ren to include high-bandwidth memory because Ren’s acceleration units are developed to more efficiently improve a computing speed [Ren, para.0089], therefore coupling a high-bandwidth memory would yield the expected result of improved computing speed as desired by Ren.
Re Claim 10. Ren in view of Duong discloses the apparatus of claim 8, wherein the scratchpad memory is to provide and receive data to/from register file banks of the register file are not servicing a butterfly compute unit (i.e. the number theoretic transform unit 235 and the arithmetic logic unit 236 can obtain the data directly from the direct memory access unit 237 during actually instruction execution) [Ren, para.0102, Note: Fig.3 depicts direct transfer of data between units 237 and the arithmetic logic units and also to instruction buffer 231 which must have registers to receive the data].
Re Claim 11. Ren in view of Duong discloses the apparatus of claim 1, wherein the polynomial to be processed comprise ciphertexts (i.e. In homomorphic encryption, the plaintext or ciphertext is embodied in polynomial coefficients. The polynomial coefficients are connected sequentially to form a polynomial loop. During encryption, the plaintext is first processed into a polynomial coefficient) [Ren, para.0064].
Re Claims 13-19. These claims recite features similar to those in claims 1-7, respectively, therefore they are rejected in a similar manner.
Ren Fig.3 depicts an accelerator coupled to a processor core as in claim 13.
Claims 12 and 20 are rejected under 35 U.S.C. 103 as being unpatentable over Ren in view of Duong and further in view of Park et al (US Pub.No.2023/0163945).
Re Claim 12. Ren in view of Duong discloses the apparatus of claim 11, Ren in view of Duong does not explicitly disclose whereas Park does: wherein the ciphertexts are stored in a double-Chinese Remainder Theorem format (i.e. the homomorphically encrypted message modular multiplier generates an output ciphertext by merging the divided ciphertext obtained in operation S140 through an inverse Chinese remainder theorem (ICRT) operation (see FIG. 2E). The CRT expresses a ciphertext (divided ciphertext) by dividing each coefficient using q.sub.0 to q.sub.r−1 divided by q, whereas the ICRT is a process of merging polynomials expressed by division, and performs the process of merging polynomials in a reverse order of the CRT…………… When the CRT logic circuit unit 210 includes a plurality of CRT logic circuits, each CRT logic circuit independently processes a modular operation in parallel to generate the divided ciphertext) [Park, para.0069, 0080].
It would have been obvious to a person having ordinary skill in the art before the effective filing date of the invention to modify Ren in view of Duong with Park because capable of reducing the operation processing time of a homomorphically encrypted message by introducing a hardware-based parallel operation processing technique [Park, para.0005].
Re Claim 20. This claim recites features similar to those in claim 12, therefore it is rejected in a similar manner.
Prior art made of record however not relied upon includes:
Feng et al “Design of an Area-Efficient Million-Bit Integer Multiplier Using Double Modulus NTT”, IEEE Transactions on (VLSI) SYSTEMS, VOL.25, NO.9, SEPT. 2017.
Feng proposes a double modulus number theoretical transform (NTT) method for million-bit integer multiplication in fully homomorphic encryption. In our method, each NTT point is processed simultaneously under two moduli, and the final result is generated through the Chinese reminder theorem. [Feng, Abstract].
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to NOURA ZOUBAIR whose telephone number is (571)270-7285. The examiner can normally be reached Monday - Friday.
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.
/NOURA ZOUBAIR/Primary Examiner, Art Unit 2434
Prosecution Insights