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 .
Specification
The disclosure is objected to because of the following informalities: [0115] equation is illegible, [0125] “one or mor”, [0138] symbol is illegible, [0156] “FIG. 1t6”, [0196] 'singular t"rm "proce"sor""or "computer"ter" may'. See 37 CFR 1.52 (a)(1)(iv).
Appropriate correction is required.
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-3, 6, 11-13, 16 are rejected under 35 U.S.C. 103 as being unpatentable over US 20180294950 A1 Khedr et al. (hereinafter “Khedr”) in view of P. Duong-Ngoc, Y. -J. Kim and H. Lee, "Efficient $k$-Parallel Pipelined NTT Architecture for Post Quantum Cryptography," 2020 International SoC Design Conference (ISOCC), Yeosu, Korea (South), 2020, pp. 212-213, doi: 10.1109/ISOCC50952.2020.9332806. (hereinafter “Duong-Ngoc”).
Regarding claim 1, Khedr discloses an apparatus with homomorphic encryption, the apparatus comprising:
a first memory (Fig. 2 “228” [0063], [0100]) configured to receive and store a polynomial (Fig. 2 “228” input [0027], [0100], [0102]);
a second memory (Fig. 2 “230” [0063], [0100]) configured to store a twiddle factor (Fig. 2 “230” input [0100], [0103]);
a number theoretic transform (NTT) module (Fig. 2 “202a-n” [0098]) configured to perform an NTT operation (Fig. 4 [0005], [0084], [0102]) on the polynomial ([0102]) based on the twiddle factor ([0103]); and
a controller (Fig. 2 “218” [0098-0099]) configured to control the first memory (Fig. 2 “228” [0063], [0100]), the second memory (Fig. 2 “230” [0063], [0100]), and the NTT module (Fig. 2 “202a-n” [0098]),
wherein the NTT module comprises a butterfly unit (BU) array (Fig. 2 “206” [0098]; Fig. 3 “300” [0102], [0106], [0108]) that comprises a plurality of BUs configured to, for the performing of the NTT operation ([0102]), perform a modular operation (Fig. 3 “302, 304, 306, 308” [0103]) on coefficients of the polynomial (Fig. 3 “
I
n
L
,
I
n
H
,
I
n
a
d
d
_
L
,
I
n
a
d
d
_
H
” [0100], [0106], [0127]).
Khedr appears to be silent to disclosing the butterfly unit array further comprising a plurality of BUs.
Duong-Ngoc discloses a plurality of BUs (Fig. 1 “PE1, PE2”, Fig. 2(a)(b); Pg. 1, co. 2, sec. II., ⁋ 1).
It would have been obvious to one of ordinary skill in the art before the effective filing date to modify Khedr’s butterfly unit array to further comprise a plurality of BUs as disclosed by Duong-Ngoc’s features because they are in the claimed invention’s same field of endeavor of number theoretic transform (NTT) architecture (Abstract). Modifying with Duong-Ngoc’s plurality of BUs would have been obvious to one of ordinary skill in the art as the architecture is optimized to perform in a parallel pipelined implementation, and therefore yields significant improvements in performance for higher degree polynomials (Abstract, Table 1, Pg. 2, Sec. III-IV). Using Duong-Ngoc’s architecture to provide a predictable level of performance improvements in Khedr’s butterfly unit array before the effective filing date would have been obvious since one of ordinary skill in the art would recognize that Khedr’s circuitry was ready for improvement to incorporate the parallel pipelined features as doing so would be beneficial.
Regarding claim 2, the teachings addressed in the claim 1 analysis and rejection are incorporated, and Khedr in view of Duong-Ngoc discloses, wherein Khedr specifically discloses the BU array (see claim 1 mapping).
However, Khedr appears to be silent with disclosing the BU array is configured by two-dimensionally arranging the plurality of BUs.
Duong-Ngoc discloses the BU array is configured by two-dimensionally arranging (Fig. 1 four “PE1” in 8 stages, two “PE2” in two stages; Pg. 1, co. 2, sec. II., ⁋ 1) the plurality of BUs (Fig. 1 “PE1, PE2”, Fig. 2(a)(b); Pg. 1, co. 2, sec. II., ⁋ 1).
The motivation to combine provided with respect to claim 1 similarly applies.
Regarding claim 3, the teachings addressed in the claim 1 analysis and rejection are incorporated, and Khedr in view of Duong-Ngoc discloses, wherein Khedr specifically discloses:
the polynomial comprises a first coefficient (Fig. 3 “
I
n
L
,
I
n
a
d
d
_
L
” [0100], [0106], [0127]) and a second coefficient (Fig. 3 “
I
n
H
,
I
n
a
d
d
_
H
” [0100], [0106], [0127]), and
for the performing of the NTT operation ([0102]), each of the plurality of BUs comprises:
a multiplier (Fig. 3 “306, 308” [0103]) configured to perform a multiplication on the twiddle factor (Fig. 3 “
T
L
,
T
H
” [0103]) and the second coefficient (Fig. 3 “
I
n
H
,
I
n
a
d
d
_
H
” [0100], [0106], [0127]);
a modular reduction operator configured to perform a modular reduction on an output of the multiplier;
an adder configured to add an output of the modular reduction operator and the first coefficient (Fig. 3 “
I
n
L
,
I
n
a
d
d
_
L
” [0100], [0106], [0127]);
a modular addition performer configured to perform a modular addition on an output of the adder;
a subtractor configured to perform a subtraction between the first coefficient (Fig. 3 “
I
n
L
,
I
n
a
d
d
_
L
” [0100], [0106], [0127]) and an output of the modular reduction operator; and
a modular subtraction operator configured to perform a modular subtraction ([0104] subtractor logic) operation on an output of the subtractor.
Although Khedr generally discloses modular operations, adders, subtractors, and multipliers with respect to the NTT butterfly architecture (Fig. 2 “206” [0098]; Fig. 3 “300” [0102]), it appears, however, that they are silent with disclosing the arrangement of the butterfly unit computing elements as it corresponds to the way in which the data flows.
Duong-Ngoc discloses each of the plurality of BUs (Fig. 1 “PE2”, Fig. 2(b); Pg. 1, co. 2, sec. II., ⁋ 1) comprises:
a multiplier configured to perform a multiplication on the twiddle factor and the second coefficient;
a modular reduction operator (Fig. 2(b)(c) “MR”) configured to perform a modular reduction on an output of (Fig. 2(c) receives output of “
⊗
” as an input) the multiplier;
an adder (Fig. 2(b) “
⊕
”) configured to add an output of the modular reduction operator (Fig. 2(b) output of “
M
R
” connecting to upper branch arrow input to “⊕”) and the first coefficient;
a modular addition performer (Fig. 2(b) “MA” following “⊕”) configured to perform a modular addition on an output of the adder (Fig. 2(b) output of “⊕”);
a subtractor (Fig. 2(b) “⊖”) configured to perform a subtraction between the first coefficient and an output of the modular reduction operator (Fig. 2(b) output of “
M
R
” branch on lower level to “⊖”); and
a modular subtraction operator (Fig. 2(b) “MA” following “⊖”) configured to perform a modular subtraction operation on an output of the subtractor.
The motivation to combine provided with respect to claim 1 similarly applies.
Regarding claim 6, the teachings addressed in the claim 1 analysis and rejection are incorporated, and Khedr in view of Duong-Ngoc discloses, wherein Khedr specifically discloses:
the twiddle factor (Fig. 3 “
T
L
,
T
H
” [0103]) is determined based ([0107], [0126]) on an order of the polynomial ([0027], [0107], [0112] ‘n’ is degree of polynomial).
Claims 11-13, 16 are directed to the method that would be performed by the apparatus of claims 1-3, 6. Claims 11-13, 16 recite similar limitations to claims 1-3, 6. The claims 1-3, 6 analysis similarly applies, and claims 11-13, 16 are similarly rejected.
Claims 4-5, 14-15 are rejected under 35 U.S.C. 103 as being unpatentable over Khedr in view of Duong-Ngoc as applied to claims 1 and 11 above, and further in view of US 8654751 B2 Hamaguchi et al. (hereinafter “Hamaguchi”).
Regarding claim 4, the teachings addressed in the claim 1 analysis and rejection are incorporated, and Khedr in view of Duong-Ngoc discloses, wherein Khedr specifically discloses:
the NTT operation comprises a predetermined number of stages ([0027], [0107], [0112] ‘n’ is degree of polynomial),
and for the performing of the NTT operation, the NTT module is configured to perform the NTT operation (see claim 1 mapping) based on a radix corresponding to the predetermined number ([0027], [0107], [0112]).
Khedr appears to be silent with disclosing the radix corresponding to a predetermined number of stages.
Duong-Ngoc and the combination of Kehdr in view of Duong-Ngoc appear to be silent with disclosing the radix corresponding to a predetermined number of stages.
Hamaguchi discloses the radix corresponding to (co. 8 ln. 62-67, co. 9 ln. 1-4) a predetermined number of stages.
It would have been obvious to one of ordinary skill in the art before the effective filing date to modify Khedr in view of Duong-Ngoc’s NTT operation to base the radix on the predetermined number of stages as disclosed by Hamaguchi’s features because they are in the claimed invention’s same field of endeavor of butterfly unit architecture (co. 8 ln. 54-61). Modifying with Hamaguchi’s stage-based radix would have been obvious to one of ordinary skill in the art as the architecture is optimized to perform based on the particular size of data, and therefore yields significant improvement in performance of the device, in terms of speed, by avoiding unnecessary computations due to its flexibility in configuration (co. 8 ln. 54-61). Using Hamaguchi’s architecture to provide a predictable level of performance improvements in Khedr in view of Duong-Ngoc’s NTT operation before the effective filing date would have been obvious since one of ordinary skill in the art would recognize that Khedr in view of Duong-Ngoc’s operation was ready for improvement to incorporate the Hamaguchi’s stage-based radix features as doing so would be beneficial.
Regarding claim 5, the teachings addressed in the claim 4 analysis and rejection are incorporated, and Khedr in view of Duong-Ngoc in view of Hamaguchi discloses, wherein Khedr specifically discloses:
the predetermined number is determined based on an order of the polynomial ([0027], [0107], [0112] ‘n’ is degree of polynomial).
Claims 14-15 are directed to the method that would be performed by the apparatus of claims 4-5. Claims 14-15 recite similar limitations to claims 4-5. The claims 4-5 analysis similarly applies, and claims 14-15 are similarly rejected.
Claims 7-10, 17-20 are rejected under 35 U.S.C. 103 as being unpatentable over Khedr in view of Duong-Ngoc as applied to claims 1 and 11 above, and further in view of US 20210318869 A1 Cathebras et al. (hereinafter “Cathebras”).
Regarding claim 7, the teachings addressed in the claim 1 analysis and rejection are incorporated, and Khedr in view of Duong-Ngoc discloses, wherein Khedr specifically discloses:
the second memory (Fig. 2 “230” [0063], [0100]) is configured to, for the storing of the twiddle factor (Fig. 2 “230” input [0100], [0103]), store the twiddle factor in bit-reversed order in a number of memory banks that is determined based on an order of the polynomial ([0107], [0126]).
Khedr appears to be silent with disclosing storing in bit-reversed order in a number of memory banks.
Duong-Ngoc discloses storing in bit-reversed order (Pg. 2, co. 1, ⁋ 1).
The motivation to combine provided with respect to claim 1 similarly applies.
Duong-Ngoc and the combination of Kehdr in view of Duong-Ngoc appear to be silent with disclosing in a number of memory banks.
Cathebras discloses in a number of memory banks (Fig. 2 “220--0-220G” [Abstract], [0050]).
It would have been obvious to one of ordinary skill in the art before the effective filing date to modify Khedr in view of Duong-Ngoc’s homomorphic encryption device to incorporate memory banks and addressing for reading/writing as disclosed by Cathebras’s features because they are in the claimed invention’s same field of endeavor of NTT architecture ([abstract]). Modifying with Cathebras’s memory banks and addressing for reading/writing would have been obvious to one of ordinary skill in the art as the memory and addressing features are optimized to perform successively as the number of stages sequentially passes, and therefore yields significant improvement in performance of the device, in terms of speed, by readying the next set of twiddle factors for the next transform of the sequence ([0026-0027], [0046], [0049], [0052]). Using Cathebras’s memory architecture to provide a predictable level of performance improvements in Khedr in view of Duong-Ngoc’s homomorphic encryption device before the effective filing date would have been obvious since one of ordinary skill in the art would recognize that Khedr in view of Duong-Ngoc’s circuitry was ready for improvement to incorporate the Cathebras’s programmable memory features as doing so would be beneficial.
Regarding claim 8, the teachings addressed in the claim 1 analysis and rejection are incorporated, and Khedr in view of Duong-Ngoc discloses, wherein Khedr specifically discloses:
for the controlling, the controller (Fig. 2 “218” [0098-0099]) is configured to:
determine an iteration count of the NTT module ([0123]);
measure a number of receptions of an input coefficient ([0099] core inputs to Port1L, Port1H, Port2L, Port2H) according to a progress step ([0100-0101] loading) of the plurality of BUs; and
generate an address for performing read and write operations of the first memory (Fig. 2 “228” [0063], [0100]).
Khedr appears to be silent to disclosing the butterfly unit array further comprising a plurality of BUs and generating an address for performing read and write operations.
Duong-Ngoc discloses a plurality of BUs (Fig. 1 “PE1, PE2”, Fig. 2(a)(b); Pg. 1, co. 2, sec. II., ⁋ 1).
The motivation to combine provided with respect to claim 1 similarly applies.
Duong-Ngoc and the combination of Khedr in view of Duong-Ngoc appear to be silent with disclosing generating an address for performing read and write operations.
Cathebras discloses generate an address for performing read and write operations ([0055-0056]).
The motivation to combine provided with respect to claim 7 similarly applies.
Regarding claim 9, the teachings addressed in the claim 8 analysis and rejection are incorporated, and Khedr in view of Duong-Ngoc in view of Cathebras discloses, wherein Khedr specifically discloses:
for the controlling, the controller (Fig. 2 “218” [0098-0099]) is configured to:
generate a bank address and an order for writing a coefficient of the polynomial to the first memory (Fig. 2 “228” input [0027], [0100], [0102]) based on the address; and
generate a bank address and an order for reading the coefficient of the polynomial from the first memory (Fig. 2 “228” input [0027], [0100], [0102]) based on the address and reading the twiddle factor from the second memory (Fig. 2 “230” input [0100], [0103]).
Khedr appears to be silent to disclosing generate a bank address and an order for writing based on the address; and generate a bank address and an order for reading based on the address and reading.
Duong-Ngoc and the combination of Khedr in view of Duong-Ngoc appear to be silent to disclosing generate a bank address and an order for writing based on the address; and generate a bank address and an order for reading based on the address and reading.
Cathebras discloses generate a bank address and an order for writing based on the address ([0056], [0060]); and generate a bank address and an order for reading based on the address and reading ([0055], [0067-0068]).
The motivation to combine provided with respect to claim 7 similarly applies.
Regarding claim 10, the teachings addressed in the claim 8 analysis and rejection are incorporated, and Khedr in view of Duong-Ngoc in view of Cathebras discloses, wherein Khedr specifically discloses:
for the performing of the NTT operation, the NTT module (see claim 1 mapping) is configured to:
load the input coefficient ([0099] core inputs to Port1L, Port1H, Port2L, Port2H) that is determined based on an order of the polynomial ([0107], [0126]) from the first memory (Fig. 2 “228” [0063], [0100]) during each iteration ([0123]) using the address; and
store an NTT operation result (Fig. 3 “
O
u
t
L
,
O
u
t
H
” [0103]; Fig. 2 “
O
u
t
L
,
O
u
t
H
” output to memory units “220, 222, 224, 226” [0100]) in the address.
Khedr appears to be silent to disclosing using the address.
Duong-Ngoc and the combination of Khedr in view of Duong-Ngoc appear to be silent with disclosing using the address.
Cathebras discloses using the address ([0055-0056]).
The motivation to combine provided with respect to claim 7 similarly applies.
Claims 17-20 are directed to the method that would be performed by the apparatus of claims 7-10. Claims 17-20 recite similar limitations to claims 7-10. The claims 7-10 analysis similarly applies, and claims 17-20 are similarly rejected.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MARKUS A VILLANUEVA whose telephone number is (703)756-1603. The examiner can normally be reached M - F 8:30 am - 5:30 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, James Trujillo can be reached at (571) 272-3677. 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.
/MARKUS ANTHONY VILLANUEVA/Examiner, Art Unit 2151
/James Trujillo/Supervisory Patent Examiner, Art Unit 2151
Prosecution Insights