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 .
Claims 1-15 are pending.
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.
Claim 1-15 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.
The term “a plurality of moduli each having a size corresponding to a machine word size” in claims 1 and 9 is a relative term which renders the claim indefinite. The term “a plurality of moduli each having a size corresponding to a machine word size” is not defined by the claim, the specification does not clearly provide a standard for ascertaining the requisite degree, and one of ordinary skill in the art would not be reasonably apprised of the scope of the invention. The term is subjective and fails to provide an objective standard for determining the scope of the claimed moduli. It is unclear whether the moduli must be exactly the same size as the machine word size, approximately the same size, or merely sized to be processed in a single machine word. Accordingly, claims 1 and 9 fail to particularly point out and distinctly claim the subject matter regarded as the invention and are rejected under 112b as being indefinite.
The term “rational rescaling” in claims 1 and 9 is a coined or otherwise undefined expression that lacks a well-established meaning in the art. Because the claim does not specify the parameters, mathematical basis, or operational steps that constitute “rational rescaling,” the scope of the limitation is uncertain. Therefore, claims 1 and 9 are indefinite under 35 U.S.C. § 112(b).
The phrase “a machine word size included in the electronic apparatus” recited in claim 9 is indefinite under 35 U.S.C. § 112(b) because it is unclear how a machine word size is “included in” an electronic apparatus. The limitation does not provide an objective boundary for determining whether the recited machine word size refers to a processor architecture, a hardware specification, or some other property of the electronic apparatus. Therefore, the claim 9 fails to particularly point out and distinctly claim the subject matter regarded as the invention and is rejected under 112b indefinite.
The phrase “sprout moduli” in claims 2 and 10 is indefinite under 35 U.S.C. § 112(b) because it does not have a well-recognized meaning in the relevant art and is not defined with sufficient clarity in the claim language. Similarly, the phrase “resurrecting the sprout modulus” recited in claims 3 and 11 is indefinite because “resurrecting” is a non-standard and ambiguous term that fails to identify with reasonable certainty the claimed operation. The claim therefore fails to particularly point out and distinctly claim the subject matter regarded as the invention. Therefore, claims 2-3 and 3-11 are rejected under 112b as being indefinite.
The phrase “the plurality of homomorphic ciphertexts” recited in claim 8 is indefinite under 35 U.S.C. § 112(b) because it lacks antecedent basis and fails to clearly identify the referenced set of ciphertexts. Without a prior introduction of the plurality, the metes and bounds of the limitation are uncertain. Claim 8 is rejected under 112b as being indefinite.
For examination purpose, these limitations are interpreted in BRI in view of the applicant’s disclosure see the rejections below for interpretation.
Dependent claims 2-8 and 10-15 are rejected under 112b at least by dependency.
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 1-15 are rejected under 35 U.S.C. § 101 because the claimed invention is directed to a judicial exception, namely an abstract idea, without significantly more. Under Step 1, claims 1-8 are directed to a machine and claims 9-15 are directed to a process. Under Step 2A, Prong 1, the claims recite mathematical concepts by manipulating ciphertext and modulus values using algebraic and transform-based operations, as shown by limitations such as “acquire a homomorphic ciphertext by using a Residue Number System (RNS) modulus,” “perform an operation on the homomorphic ciphertext by using rational rescaling,” “generate an intermediate modulus,” “acquire an output modulus by rescaling,” “perform a key switching operation,” “adjust the plurality of homomorphic ciphertexts having different moduli and scaling factors,” and, in claims 5, 6, 13, and 14, processing g1g2 using Composite NTT, processing g3 using embedded NTT, and using one or two NTT processors based on machine word size. These limitations amount to mathematical calculations, transforms, and algebraic manipulation of encrypted numerical data. Under Step 2A, Prong 2, the claims do not integrate the abstract idea into a practical application because the additional elements, an electronic apparatus, memory, processor, and NTT processor(s), merely invoke generic computing components as tools to perform the mathematics, and the recitations of machine word size, prime size, modulus structure, and processor count merely limit the abstract idea to a particular technological environment rather than reciting a specific improvement to computer functionality or other technology. Under Step 2B, the claims do not add significantly more than the abstract idea because the specification describes the memory and processor generically and as performing ordinary computer functions, and the claimed NTT processor usage is likewise recited only as execution of the mathematical operations. Accordingly, the claims are directed to patent-ineligible subject matter.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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.
Claim(s) 1-4, 7-12, and 15 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 2022/0376891 A1 (herein after Polyakov et al.) in view of US 20230188320 A1 (Part et al.).
Regarding claims 1 and 9, Polyakov et al. teaches An electronic apparatus/method comprising:
a memory for storing at least one instruction ; and a processor ([0030] [0036]: “Computing device 100A may include a controller or computer processor 105A … memory 120A …”; …”),
wherein the processor is configured to acquire a homomorphic ciphertext ([0012]: “a homomorphic operation is performed on the encrypted complex input…”; [0049]: “receiving an encrypted message m+e+e′…”; [0020]: “…memory … instructions … cause the processor … to receive a complex input… perform encrypting …”; [0048]) by using a Residue Number System (RNS) modulus ( [0003] [0038] [0040] : “CKKS variants used in practice typically work with large numbers … represented in the Residue Number Representation (RNS) obtained using the Chinese Remainder Theorem.”… Each large number can be decomposed into multiple small numbers (RNS residues) with respect to moduli… ) including a plurality of moduli ([0003]: “Each large number can be decomposed into multiple small numbers (RNS residues) with respect to moduli…”; [0040]: “instead of using machine-word-size 64-bit integers for residue numeral systems (RNS), larger words… are used…”) each having a size corresponding to a machine word size (([0003]: “moduli that are limited to the 64 bit limit of modern CPU-based computer architectures.”; [0040]: “instead of using machine-word-size 64-bit integers for residue numeral systems (RNS)… larger words … are used…”; [0031]: “Processor 105A may be a 128 bit processor.”; [0039]: background references “64-bit limit.”; moduli sized to conventional machine word limits, particularly 64-bit moduli, and also teaches use of larger-than-64-bit integers), and
perform an operation on the homomorphic ciphertext ([0056]-[0065]: modular reduction approximations for CKKS bootstrapping; [0060]: “more accurate approximation of the modular reduction…”; [0065]: precision comparisons of interpolation methods).
Polyakov fails to teach using rational rescaling.
However, Park et al. teaches by using rational rescaling ([0009]: homomorphic
multiplication, re-linearization/key switching, and modulus switching…; [00101]: modulus switching operator performs modulus switching on the operation result…; [0059]–[0061]: modulus switching recovers word size / manages ciphertext growth…; [0117]–[0118]: modulus switching performed after the selected operation … modulus switching after homomorphic multiplication and after the selected follow-on operation. That is a ciphertext-parameter adjustment operation used to control ciphertext growth and preserve continued homomorphic processing).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify the homomorphic encryption apparatus of Polyakov to adopt the disclosed modulus switching operation in the system of Polyakov because it provides a predictable technique for adjusting ciphertext parameters and enabling continued encrypted-domain computation in the operation of rational rescaling.
Regarding claims 2 and 10, Polyakov et al. in view of Part et al. teaches the electronic apparatus/method, Polyakov et al. further teaches wherein the plurality of moduli include sprout moduli composed of a product of primes each having a size less than or equal to the machine word size (par. 40: an RNS-based CKKS variant where the modulus set is constrained by the 64-bit machine word size; See, e.g., paragraphs [0040]–[0041], [0056]–[0060], [0066]–[0067] [0031]–[0034] further: homomorphic encryption implementations using residue number representation / RNS-style arithmetic with large-word implementation considerations. Polyakov et al. discusses use of large integers, including 128-bit integers and modulus-related processing for CKKS-style cryptography. … discusses use of 128-bit integers and notes that in practice RNS residues may be supported by hardware integer sizes…practical residue arithmetic sizes and machine architecture limitations.).
Regarding claims 3 and 11, Polyakov et al. in view of Park et al. teaches the electronic apparatus/method, Polyakov et al. further teaches wherein the processor is configured to generate an intermediate modulus by resurrecting the sprout modulus ([0003]–[0007], [0043]–[0058], and [0111]–[0114]: homomorphic encryption using a scaling factor and modulus-related arithmetic in the CKKS / approximate HE context... encryption and decryption involving scaling, and the modulus and scaling factor are related to ciphertext processing.), and acquire an output modulus by rescaling the intermediate modulus ([0043]–[0058]: use of a scaling factor in encryption and decryption and discusses maintaining approximate precision through such scaling), the intermediate modulus being a multiple of the output modulus ([0009], [00109], [0044]–[0045]: performing a homomorphic multiplication operation on the homomorphic ciphertext… output of 64 and 128 moduli).
Regarding claims 4 and 12, Polyakov et al. in view of Park et al. teaches the electronic apparatus/method, Park et al. further teaches wherein the processor is configured to perform a key switching operation on the homomorphic ciphertext by using the sprout modulus ([0007]–[0010], [0055]–[0061], and [0096]–[0101]: key switching in a homomorphic encryption context. The reference describes a computing apparatus that processes homomorphic ciphertexts and selectively performs operations including key switching and re-linearization based on encryption scheme information…. [0086]–[0104]: the operations, including key switching, are performed on a homomorphic ciphertext).
Regarding claims 7 and 15, Polyakov et al. in view of Part et al. teaches the electronic apparatus/method, Park et al. further teaches wherein the processor is configured to generate an intermediate modulus by upscaling the RNS modulus, perform a key switching operation on the intermediate modulus ([0009], [00101], [00117]–[00118]: after re-linearization/ key switching performing modulus switching ), and
perform rescaling on the intermediate modulus on which the key switching operation is performed ([0009], [00101], [00117]–[00118]: performing modulus switching after key switching).
It would have been obvious to one ordinary skill in the art before the effective filing date of the invention to combine the teachings of Polyakov et al. in view of Part et al. because both references address practical homomorphic encryption implementation issues, including modulus management, scaling, and efficient encrypted computation. Polyakov et al. teaches that RNS-CKKS efficiency depends on the relationship between the modulus and the scaling factor and expressly discloses rational rescaling using intermediate modulus values. Park et al. teaches that key switching and modulus switching are standard homomorphic operations and further teaches performing key switching via modulus expansion and intermediate-modulus handling. A person of ordinary skill in the art would have been motivated to combine these teachings to reduce implementation complexity, maintain ciphertext compatibility, and improve computational efficiency when processing homomorphic ciphertexts.
Regarding claim 8, Polyakov et al. in view of Part et al. teaches the apparatus as claimed in claim 1, wherein the processor is configured to adjust the plurality of homomorphic ciphertexts having different moduli and scaling factors by using the rational rescaling (Park et al. [0103]–[0104]: the homomorphic multiplication operator, selector, re-linearization operator, key switching operator, and modulus switching operator may be integrated iSnto one dedicated chip).
Claim(s) 5-6 and 13-14 is/are rejected under 35 U.S.C. 103 as being unpatentable over US 2022/0376891 A1 (herein after Polyakov et al.) in view of US 20230188320 A1 (Part et al.) and further in view of US 2023/0318829 A1 (herein after Sim et al.).
Regarding claims 5 and 13, Polyakov et al. in view of Park et al. teaches the electronic apparatus/method.
Polyakov et al. in view of Park et al. fails to explicitly teach the below limitations, however, Sim et al teaches:
wherein in case that the sprout modulus is expressed as a product of g.sub.1 ([0062]–[0070]: polynomial memory banks, transform operation circuits, NTT/INTT, and twiddle factors…; [0079]: double CRT representation and decomposition using RNS…), which is a 31-bit Number Theoretic Transform (NTT) prime ([0086]: use of stored twiddle factors; [0095]–[0101]: modular multiplication using a LUT and a modulus q that is a k-bit number.; [0066]: Discloses modular multiplication LUT for a particular modulus; [0073]–[0077]: Discloses NTT regularity and transform operations.), g.sub.2, which is a 16-bit NTT prime or in the form of [2.sup.16+1] ([0097]–[0100]: modular multiplication circuitry and examples using a k-bit modulus; [0090]–[0094]:NTT/INTT operation cell structure with multiplexers, multiplier, adder, subtractor), and g.sub.3, which is a value in the form of 2;
([0078]–[0084]: NTT stages and coefficient shuffling; [0090]–[0093]: Butterfly operation cell uses selection logic and twiddle multiplication.),
the processor is configured to process a product of g.sub.1 and g.sub.2 by using composite number-based NTT (Composite NTT) ([0079]: double-CRT representation using RNS decomposition; [0080]–[0084]: Discloses combined butterfly circuits and two-stage operations without intermediate memory storage; [0088]: an NTT/INTT operation circuit that can perform NTT or INTT and output results back to memory banks.), and
process g.sub.3 by using embedded NTT ([0080]–[0088]: combined butterfly and sequence reordering for NTT/INTT; [0090]–[0093]: Discloses NTT/INTT operation cell behavior under mode control) to thus integrate their results into G.sub.3 if the machine word size is greater than 38 bits and less than or equal to 64 bits ([0095]–[0101]: General modular multiplication hardware for arbitrary modulus; [0118]: a 28 nm LP CMOS implementation supporting lattice-based protocols with modulus q<2^24) ([0087]: Notes that two-stage operations can be done with reduced memory accesses; [0094]: Mentions a 4-to-4 bijection structure and parallel butterfly circuits; [0100]: Modular multiplication can be performed with reduced latency), and process g.sub.3 by using the embedded NTT to thus acquire G.sub.3 if the machine word size is less than or equal to 38 bits ([0087]: Notes that two-stage operations can be done with reduced memory accesses; [0094]: Mentions a 4-to-4 bijection structure and parallel butterfly circuits; [0100]: Modular multiplication can be performed with reduced latency).
It would have been obvious to one ordinary skill in the art before the effective filing date of the invention to because Polyakov et al. teaches that CKKS/RNS implementations are constrained by machine word size and modulus budgeting, Park et al. teaches NTT/RNS-based homomorphic processing in a dedicated hardware accelerator, and Sim et al. teaches combined butterfly and sequence-reordering NTT/INTT circuitry that reduces memory access and supports efficient multi-stage transform execution. It would have been an obvious matter of engineering design choice to implement the NTT hardware using a word-size-dependent partition of the modulus and to scale the number of NTT processing resources according to the available machine word size.
Regarding claims 6 and 14, Polyakov et al. in view of Part et al. teaches the apparatus/method. Regarding “wherein two NTT processors are used if the machine word size is greater than 38 bits and less than or equal to 64 bits”, Polyakov et al. teaches homomorphic encryption using large-word arithmetic and practical implementation constraints tied to machine-supported integer sizes; further teaches that CKKS implementations are constrained by machine word size and the 64-bit architectural limit, while also teaching the use of larger words and even 128-bit processing (See, e.g., paragraphs [0031]–[0034], [0040]–[0041] integer size, arithmetic …). Park et al. teaches homomorphic computation with NTT-related processing for efficient encrypted multiplication and NTT/RNS-based high-speed parallel processing (See paragraph [0095] “The homomorphic multiplication operator is implemented using NTT and RNS “so as to perform high-speed parallel processing ” discussion of homomorphic multiplication and processing flow … [0103]–[0104] Discloses integration of operators into one dedicated chip). Sim et al. teaches TT/INTT can be implemented with combined butterfly structures, reducing memory accesses and allowing efficient operation; modular arithmetic hardware and NTT/INTT circuit blocks (¶ [0087]–[0094] ¶ [0090]–[0101]). While none of the reference expressly states that two NTT processors are used in the specific word-size range of greater than 38 bits and less than or equal to 64 bits, the references collectively teach that: NTT is used to accelerate homomorphic computation, implementation is hardware-dependent, and the amount of processing hardware may be selected based on operand size and efficiency requirements. Thus, this limitation can be viewed as an implementation-level hardware scaling choice built on the NTT-based homomorphic processing of the prior art. Furthermore, While neither reference expressly states “two NTT processors,” Park et al. teaches NTT-based parallel processing, which supports a hardware arrangement using multiple NTT processing units for increased throughput. Polyakov et al. supplies the word-size-driven implementation context showing that larger-word computations in CKKS/RNS are hardware-constrained and may require more robust processing resources.
Regarding limitation “and one NTT processor is used if the machine word size is less than or equal to 38 bits”, Polyakov et al. teaches a machine-word-sensitive implementation of homomorphic encryption arithmetic, supporting the notion that processor resources may be matched to the available word size (see [0003] the implementation is tied to machine architecture and word-size limitations; [0005] Explains that precision and modulus sizing are constrained by existing CKKS RNS implementations.; [0040] States that larger words may be used instead of 64-bit machine words, implying the implementation can vary with available word size.). Park et al teaches NTT-based ciphertext processing as part of homomorphic multiplication (See paragraph [0095] NTT/RNS-based processing can be used for high-speed parallel processing, but the reference does not tie processor count to a specific word-size threshold). Sim et al. teaches TT/INTT can be implemented with combined butterfly structures, reducing memory accesses and allowing efficient operation; modular arithmetic hardware and NTT/INTT circuit blocks (¶ [0087]–[0094] ¶ [0090]–[0101]). Although the exact single-processor threshold is not expressly disclosed, a skilled artisan would have understood that a smaller machine-word environment may require less parallel NTT hardware or can be efficiently served by a single NTT processor. The specific threshold of 38 bits or less is not expressly disclosed Polyakov et al., Park et al., and Sim et al.. However, selecting a particular machine-word-size threshold for assigning one NTT processor versus multiple NTT processors would have been an obvious matter of engineering design choice and routine optimization, because the references already teach that homomorphic encryption implementations are constrained by hardware word size, modulus/residue size, and throughput considerations, and a POSITA would have been motivated to select a threshold for allocating one versus multiple NTT processors based on routine optimization of hardware resources and processing efficiency.
It would have been obvious to one ordinary skill in the art before the effective date of the claimed invention to combine the teachings of Polyakov et al., Park et al. and Sim et al. because both are directed to practical homomorphic encryption implementation efficiency. Polyakov et al. emphasizes large-word approximate HE and implementation considerations tied to arithmetic representation and machine support. Park et al. teaches NTT-based processing for homomorphic multiplication and ciphertext management. Sim et al. teaches combined butterfly NTT/INTT circuitry. A person of ordinary skill in the art would have been motivated to allocate NTT processing resources based on machine-word size in order to: improve throughput, reduce computational overhead, match hardware parallelism to operand complexity, and optimize homomorphic encryption performance across different processor architectures.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
CN115935383A discloses CKKS / FHE / RNS / CRT / ModUp / key switching system. See steps 5-7. Step 5: “… homomorphically encrypt the client model”; step 6: “uses CRT, iCRT, NTT and inverse NTT” step 7: “optimize ModUp (that changes modulus)… scaling kernels and batch iNTT in ModUp … Key Switching and modulus/scale handling…”.
WO 2023/163652 A2 discloses performing homomorphic operations on ciphertext and further discloses homomorphic rounding and key switching to change the ciphertext modulus and reduce ciphertext size. See, e.g., paragraphs [00110], [00126], and [00131].
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ELENI A SHIFERAW whose telephone number is (571)272-3867. The examiner can normally be reached 7-3:30 M-F.
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.
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.
/ELENI A SHIFERAW/Supervisory Patent Examiner, Art Unit 2497
Prosecution Insights