Detailed Action
This is a Non-final Office action in response to communications received on 11/7/2024. Claims 1-43 are pending and are examined.
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 .
Foreign Priority
The foreign priority date of 11/7/2023 is acknowledged.
Claim Objections
Claims 4, 18, 24, 34, 37 and 40 are objected to because of the following informalities:
Regarding claim 4, the claim recites “wherein at least one of the first set of numbers, the second set of random prime numbers, and the third set of random numbers selected based on a security parameter”, which is grammatically incorrect. The claim should recite “are selected”.
Regarding claim 18, the claim recites “wherein l1 = … = lk = 1 are exponents” however, “are” implies multiple subjects, while only a single expression is provided. It appears as if a list of elements and not an equation is intended.
Regarding claims 24, 34 and 37, the claims recite “method” with numerous spaces in the middle of the word. Examiner regards these are typographical errors.
Regarding claim 40, the claim recites “are a a plurality of pairwise coprime numbers” with duplicate article “a”.
Appropriate correction is required.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitations are:
“means for performing the method” in claim 43.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
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-43 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more analyzed according to 2019 Revised Patent Subject Matter Eligibility Guidance (“2019 PEG”). Claim 1 recites a method of generating keys for fully homomorphic encryption, the method comprising: obtaining a first set of numbers, obtaining another parameter and calculating a secret key based on the first set of numbers and the another parameter. Claim 32 recites a method of performing encrypted homomorphic Plaintext to Ciphertext multiplication wherein the method is configured to perform a function on a ciphertext and a plaintext number to produce a ciphertext, the ciphertext in an encryption of a plaintext vector. Claim 37 recited a method of performing Public Key encryption, wherein the method is configured to encrypt a plaintext vector with a public key generated by a method configured to perform a function on a ciphertext and a plaintext number to produce a ciphertext, the ciphertext in an encryption of a plaintext vector.
Step 1: The claims 1, 32 and 37 do fall into one of the four statutory categories of method and system claims. Nevertheless the claims 1-43 still is/are considered as abstract idea for the following prongs and reasons.
Step 2A:
Prong 1: The limitation of the claims, as drafted, is a process that, under its broadest reasonable interpretation, covers performance of the limitation in the human mind and / or with pen and paper. There is nothing in the claim element precludes the step from practically being performed in human organized way and/or with pen and paper. Dependent claims are other steps that could be performed by human manually with/without need for a computer. If a claim limitation, under its broadest reasonable interpretation, covers performance of the limitation in the mind but for the recitation of generic computer components, then it falls within the “certain methods of organizing human activities” grouping of abstract ideas and can be done manually. Accordingly, the claim recites an abstract idea.
Prong 2: This judicial exception is not integrated into a practical application. In particular, the claims do not recite any additional element to perform beyond routine mathematical steps. Accordingly, these claims not integrate the abstract idea into a practical application because it does not impose any meaningful limits on practicing the abstract idea. Therefore the claims is directed to an abstract idea.
Step 2B: The claims do not include additional elements that are sufficient to amount to significantly more than the judicial exception. Mere instructions to apply an exception using a generic computer components cannot provide an inventive concept. The claims are not patent eligible.
Claims 41 and 42 are rejected under 35 U.S.C. 101 as being directed to non-statutory subject matter.
Under 35 U.S.C. 101, a claimed invention must fall within one of the four eligible categories of invention (i.e. process, machine, manufacture, or composition of matter) and must not be directed to subject matter encompassing a judicially recognized exception as interpreted by the courts. MPEP § 2106. The four eligible categories of invention include: (1) process which is an act, or a series of acts or steps, (2) machine which is an concrete thing, consisting of parts, or of certain devices and combination of devices, (3) manufacture which is an article produced from raw or prepared materials by giving to these materials new forms, qualities, properties, or combinations, whether by hand labor or by machinery, and (4) composition of matter which is all compositions of two or more substances and all composite articles, whether they be the results of chemical union, or of mechanical mixture, or whether they be gases, fluids, powders or solids. MPEP 2106(I).
Claim 41 recites a “A computer program comprising instructions which, when executed by a computing system, cause the computing system to carry out the method”. Claim 42 recites “A computer-readable storge medium or a data carrier signal carrying the computer program of claim 41” Applicant’s Specification does not explicitly define “computer program” as hardware. Notably absent from Applicant’s Specification is any definition of the computer readable storage medium that explicitly limits it to hardware. "While the recitation ‘non-transitory’ is a viable option for overcoming the presumption that those media encompass signals or carrier waves, merely indicating that such media are ’physical’ or ‘tangible’ will not overcome such presumption” (In re Mewherter, Appeal No. 2012-007692, p. 14 (BPAI 2013) (precedential) (quoting U.S. Patent and Trademark Office, Evaluating Subject Matter Eligibility Under 35 USC § 101 (August 2012 Update) (pp. 11-14), available at http://www.uspto.gov/patents/law/exam/101_training_aug2012.pdf). Pending claims are interpreted as broadly as their claims reasonably allow. See In re Zletz, 893 F.2d 319 (Fed. Cir. 1989). The broadest reasonable interpretation of a claim drawn to a recording medium (also called machine readable medium and other such variations) which typically covers forms of non-transitory tangible media and transitory propagating signals per se in view of the ordinary and customary meaning of recording medium, particularly when the specification is silent (See MPEP 2111.01). When the broadest reasonable interpretation of a claim covers a signal per se, the claim must be rejected under 35 U.S.C. §1 01 as covering non-statutory subject matter. See In re Nuijten, 500 F.3d 1346, 1356-57 (Fed. Cir. 2007) (transitory embodiments are not directed to statutory subject matter) and Interim Examination Instructions for Evaluating Subject Matter Eligibility under 35 U.S.C. § 101, Aug. 24, 2009; p. 2.
A claim drawn to such a recording medium that covers both transitory and non-transitory embodiments may be amended to narrow the claim to cover only statutory embodiments to avoid a rejection under 35 U.S.C. § 101 by adding the limitation "non-transitory" to the claim. Cf Animals - Patentability, 1077 Off. Gaz. Pat. Office 24 (April 21, 1987).
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 5, 12, 14, 22, 24, 27, 34, 37 and 43 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 pre-AIA the applicant regards as the invention.
Regarding claim 5, the claim recites “the second set of random prime numbers, and the third set of random numbers”. There is insufficient antecedent basis for these sets in the claims.
Regarding claim 12, the claim recites “the public parameter”. There is insufficient antecedent basis for this limitation in the claims.
Regarding claim 14, the claim recites “the cypher text”. There is insufficient antecedent basis for this limitation in the claims.
Regarding claim 22, the claim recites multiple terms which are also recited in claim 4, from which claim 22 depends. It makes it unclear if these recitations are distinct from or otherwise the same as those recited in claim 4.
Regarding claims 22, 24, 27, 34, the claims recite “a method” while the claims from which they depend also recite methods. These methods should be distinguished from each other.
Regarding claim 37, the claim recites multiple instances of “a method” and further recites “a public key generated by a method configured to perform a function”. It is unclear what a method configured to perform a function is meant to describe.
Regarding claim 43, the claim recites a “means for performing the method according to claim 1” which invokes 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. However, the written description fails to disclose the corresponding structure, material, or acts for performing the entire claimed function and to clearly link the structure, material, or acts to the function. Therefore, the claim is indefinite and is rejected under 35 U.S.C. 112(b) or pre-AIA 35 U.S.C. 112, second paragraph.
Applicant may:
(a) Amend the claim so that the claim limitation will no longer be interpreted as a limitation under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph;
(b) Amend the written description of the specification such that it expressly recites what structure, material, or acts perform the entire claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(c) Amend the written description of the specification such that it clearly links the structure, material, or acts disclosed therein to the function recited in the claim, without introducing any new matter (35 U.S.C. 132(a)).
If applicant is of the opinion that the written description of the specification already implicitly or inherently discloses the corresponding structure, material, or acts and clearly links them to the function so that one of ordinary skill in the art would recognize what structure, material, or acts perform the claimed function, applicant should clarify the record by either:
(a) Amending the written description of the specification such that it expressly recites the corresponding structure, material, or acts for performing the claimed function and clearly links or associates the structure, material, or acts to the claimed function, without introducing any new matter (35 U.S.C. 132(a)); or
(b) Stating on the record what the corresponding structure, material, or acts, which are implicitly or inherently set forth in the written description of the specification, perform the claimed function. For more information, see 37 CFR 1.75(d) and MPEP §§ 608.01(o) and 2181.
Claim Rejections - 35 USC § 102
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.
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
Claim(s) 32, 33 and 37 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Kim (NPL “CRT-based Fully Homomorphic Encryption over the Integers).
Regarding claim 32, Kim teaches the limitations of claim 32 substantially as follows:
A method of performing encrypted homomorphic Plaintext to Ciphertext multiplication wherein the method is configured to perform a function fmultiply2()on a ciphertext c and a plaintext number x to produce a ciphertext cmultiply2, the ciphertext in an encryption, enc(), of a plaintext vector (m1,...,mk) and cmultiply2= enc(x *m1, ..., x *mk). (Kim; p. 2 “Basic Idea”: Enc function outputs c as a CRT and multiplication of a series)
Regarding claim 33, Kim teaches the limitations of claim 32.
Kim teaches the limitations of claim 33 as follows:
The method of claim 32, wherein cmultiply2 = [(c0*,c1*, ..., cn*), (l1*, ..., lk*)], and wherein: t is an integer value greater than or equal to 0 and less than or equal to n (i.e. 0 ≤ t ≤ n));[AltContent: rect]ct* = x * ct mod q, t=0,1, ..., n; and lt* = t = 0, 1, ..., n. (Kim; p. 2 “Basic Idea”: Enc function outputs c as a CRT and multiplication of a series, including modulus)
Regarding claim 37, Kim teaches the limitations of claim 37 substantially as follows:
A method of performing Public Key encryption, wherein the method is configured to encrypt a plaintext vector (mi,...,m-k) with a public key generated by a method configured to perform a function fmultiply2() on a ciphertext c and a plaintext number x to produce a ciphertext cmultiply2, the ciphertext in an encryption, enc(), of a plaintext vector (m1,...,mk) and cmultiply2 = enc(x * m1,…, x * mk). (Kim; p. 5 “3.2 The Construction”: KeyGen outputs a public key which is further used to produce a ciphertext)
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, 12-14, 34 and 41-43 are rejected under 35 U.S.C. 103 as being unpatentable over Kim (NPL “CRT-based Fully Homomorphic Encryption over the Integers”), in view of Honorio (US 20210036849 A1).
Regarding claim 1, Kim teaches the limitations of claim 1 substantially as follows:
A method of generating keys for fully homomorphic encryption, the method comprising:
obtaining a first set of numbers S, wherein the first set of numbers S is a set of pairwise coprime numbers p1,...,Pk+1; (Kim; p. 2 “Basic Idea”: Key Gen incorporates a set of pairwise coprime integers (i.e., obtaining a first set of numbers S) and a security parameter in or to produce a secret key)
obtaining another parameter, (Kim; p. 2 “Basic Idea”: Key Gen incorporates a set of pairwise coprime integers and a security parameter (i.e., another parameter) in or to produce a secret key)
calculating a secret key, sk, based on the first set of numbers S, and the another parameter. (Kim; p. 2 “Basic Idea”: Key Gen incorporates a set of pairwise coprime integers and a security parameter in or to produce a secret key (i.e., calculating a secret key, sk))
Kim does not teach the limitations of claim 1 as follows:
wherein the another parameter is a random or pseudo random number P; and (Honorio; [0008]: generating by a secret key computing device at least one secret prime number (p) as a random prime number; calculating by the secret key computing device a public modulus (q) as a product of the at least one secret prime number (p) and at least one additional random number; generating by the secret key computing device at least one secret key value (k) as a random number (i.e., the another parameter is a random or pseudo random number ))
However, in the same field of endeavor, Honorio discloses the limitations of claim 1 as follows:
wherein the another parameter is a random or pseudo random number P; and (Honorio; [0008]: generating by a secret key computing device at least one secret prime number (p) as a random prime number; calculating by the secret key computing device a public modulus (q) as a product of the at least one secret prime number (p) and at least one additional random number; generating by the secret key computing device at least one secret key value (k) as a random number (i.e., the another parameter is a random or pseudo random number ))
Honorio is combinable with Kim because all are from the same field of endeavor of encryption key generation. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have modified the system of Kim to incorporate a random parameter in key generation as in Honorio in order to improve the security of the system by incorporate non-deterministic generation of keys.
Regarding claim 2, Kim and Honorio teach the limitations of claim 1.
Kim and Honorio teach the limitations of claim 2 as follows:
The method of claim 1, wherein k+1=2. (Kim; p. 2 “Basic Idea”: Key Gen incorporates a set of pairwise coprime integers and a security parameter in or to produce a secret key (2 is a predictable option of the set of numbers greater than 1 as a selection for k))
Regarding claim 3, Kim and Honorio teach the limitations of claim 1.
Kim and Honorio teach the limitations of claim 3 as follows:
The method of claim 1, wherein the secret key sk ={S, P}. (Kim; p. 2 “Basic Idea”: Key Gen incorporates a set of pairwise coprime integers and a security parameter in or to produce a secret key)
Regarding claim 12, Kim and Honorio teach the limitations of claim 1.
Kim and Honorio teach the limitations of claim 12 as follows:
A method of fully homomorphic encryption comprising obtaining a secret key, sk, and a plaintext mi, ...,mk to be encrypted, (Honorio; [0040]: For embodiments that intend to retain homomorphic properties for encrypted data messages, there is an additional restriction that the “packed” multivector that represents the original plaintext numeric message have a mathematical relationship (i.e., the homomorphic preserving mathematical relationship) to the original plaintext numeric message)
wherein the secret key and the public parameter are generated in accordance with the method of claim 1.
The same motivation to combine as in claim 1 is applicable to the instant claim.
Regarding claim 13, Kim and Honorio teach the limitations of claim 12.
Kim and Honorio teach the limitations of claim 13 as follows:
The method of claim 12, comprising generating and using a random number w. (Honorio; [0008]: generating by a secret key computing device at least one secret prime number (p) as a random prime number; calculating by the secret key computing device a public modulus (q) as a product of the at least one secret prime number (p) and at least one additional random number; generating by the secret key computing device at least one secret key value (k) as a random number (i.e., random number ))
The same motivation to combine as in claim 1 is applicable to the instant claim.
Regarding claim 14, Kim and Honorio teach the limitations of claim 12.
Kim and Honorio teach the limitations of claim 14 as follows:
The method of claim 12, wherein calculating the cypher text c comprises calculating c=P.w+CRT(S) (m1, …, mk, e), where e is a random integer in the range {0,1,…, pk+1-1}. (Kim; p. 2 “Basic Idea”: Enc function performs CRT using a random integer e)
Regarding claim 34, Kim and Honorio teach the limitations of claim 1.
Kim and Honorio teach the limitations of claim 34 as follows:
A method of generating Public Key, pk, from a secret key, wherein the secret key was generated by a method according to claim 1. (Kim; p. 5 “3.2 The Construction”: KeyGen outputs a public key)
Regarding claim 41, Kim and Honorio teach the limitations of claim 1.
Kim and Honorio teach the limitations of claim 41 as follows:
A computer program comprising instructions which, when executed by a computing system, cause the computing system to carry out the method according to claim 1. (Honorio; [0052]: One or more subsystems, in whole or in part, may alternatively be implemented as software or firmware instructions defining the operation of a computer system with specific regard to the one or more subsystems implemented as software or firmware instructions)
The same motivation to combine as in claim 1 is applicable to the instant claim.
Regarding claim 42, Kim and Honorio teach the limitations of claim 41.
Kim and Honorio teach the limitations of claim 42 as follows:
A computer-readable storge medium or a data carrier signal carrying the computer program of claim 41. (Honorio; [0052]: One or more subsystems, in whole or in part, may alternatively be implemented as software or firmware instructions defining the operation of a computer system with specific regard to the one or more subsystems implemented as software or firmware instructions)
The same motivation to combine as in claim 1 is applicable to the instant claim.
Regarding claim 43, Kim and Honorio teach the limitations of claim 1.
Kim and Honorio teach the limitations of claim 43 as follows:
A computing system comprising at least one computer, the computing system comprising means for performing the method according to claim 1. (Honorio; [0052]: One or more subsystems, in whole or in part, may alternatively be implemented as software or firmware instructions defining the operation of a computer system with specific regard to the one or more subsystems implemented as software or firmware instructions)
The same motivation to combine as in claim 1 is applicable to the instant claim.
Prior Art Considered But Not Relied Upon
Gentry (US 20120039473 A1) which teaches methods and systems to encrypt/decrypt a data message using Geometric Algebra and Hensel encoding.
Puiggali (US 20120144186 A1) which teaches a method for the verification of the correct decryption of a set of encrypted messages, characterized by using an encryption algorithm with homomorphic properties to encrypt the messages.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to BLAKE ISAAC NARRAMORE whose telephone number is (303)297-4357. The examiner can normally be reached on Monday - Friday 0700-1700 MT.
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, Taghi T Arani can be reached on (571) 272-3787. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see https://ppair-my.uspto.gov/pair/PrivatePair. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/BLAKE I NARRAMORE/Examiner, Art Unit 2438