DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
The present application, filed on October 15, 2024, is accepted.
Claims 1 – 7 and 15 – 27 are being considered on the merits.
Drawings
The drawings, filed on October 15, 2024, are accepted.
Specification
The specification, filed on October 15, 2024, is accepted.
Double Patenting
No rejection warranted at application’s initial filling time of filling for a patent.
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.
Claim1 – 7 and 15 – 27 are rejected under 35 U.S.C. 103 as being unpatentable over US 8130947 B2 to Kerschbaum et al., (hereinafter, “Kerschbaum”) in view of US 20160352710 A1 to Hibshoosh et al., (hereinafter, “Hibshoosh”).
Regarding claim 1, Kerschbaum teaches a homomorphic encryption operation method, applied to an electronic device participating in a homomorphic encryption operation, wherein the method comprises: determining a homomorphic encryption operation to be performed on specified service data, wherein the homomorphic encryption operation is used to provide privacy preserving for the service data; [Kerschbaum, col. 3 lines 33 – 51 discloses preserve privacy, the vertices of the social network graph are encrypted applying a commutative encryption scheme. In such a scheme, an object could be encrypted with a plurality of different keys and order of encryption does not matter. The commutative encryption scheme holds that E.sub.1(E.sub.2(x))=E.sub.2(E.sub.1(x)), where E.sub.1( ) denotes a commutative encryption with a first key, E.sub.2( ) denotes commutative encryption with a second key, and x is a plain object, value or text to be encrypted. The commutative encryption cannot be semantically secure, as the encrypted objects are comparable. Another embodiment of the invention applies a homomorphic threshold encryption scheme for encrypting vertices or other values in a social network. The homomorphic property of an encryption scheme allows operations with the plain texts or values. It holds that E*(x)*E*(y)=E*(x+y), where E*( ) denotes homomorphic encryption, and x and y are plain texts or values. From this equation, by means of simple arithmetic operations is concluded that the homomorphic encryption scheme further holds that E*(x).sup.y=E*(xy).], but Kerschbaum does not teach obtaining a base parameter and an exponent parameter that are of an exponentiation operation comprised in the homomorphic encryption operation; querying an exponentiation operation result cache table corresponding to the base parameter based on the exponent parameter, to obtain a result of the exponentiation operation; and completing the homomorphic encryption operation based on the result of the exponentiation operation.
However, Hibshoosh does teach obtaining a base parameter and an exponent parameter that are of an exponentiation operation comprised in the homomorphic encryption operation; [Hibshoosh, para. 11 discloses a method for secure computation, which includes receiving in a server, over a communication channel from a device external to the server, a request to perform a modular exponentiation operation in which an exponent of the operation includes a secret value, which is not provided to the server, and at least two parameters that encode the secret value in accordance with a polynomial homomorphic encryption of the secret value computed by the device.] querying an exponentiation operation result cache table corresponding to the base parameter based on the exponent parameter, to obtain a result of the exponentiation operation; [Hibshoosh, para. 11 discloses the server performs, in response to the request, a homomorphic exponentiation using the parameters received from the device without decrypting the secret value in the server, so as to generate an output that is indicative of a result of the modular exponentiation operation.] and completing the homomorphic encryption operation based on the result of the exponentiation operation. [Hibshoosh, para. 12 discloses A homomorphic exponentiation is computed in the server using the encryption parameters and the second base value g.sup.b, so as to generate an output HE(g.sup.ab) that is indicative of the session key. The output is conveyed from the server over the communication channel to the first peer device, which applies a polynomial homomorphic decryption to the output conveyed by the server in order to recover the session key g.sup.ab. Communications between the first and second peer devices are encrypted and decrypted using the session key.]
Therefore, it would have been obvious to one of ordinary skill within the art before the effective filling date to combine Hibshoosh’s system with Kerschbaum’s system, with a motivation for the modular exponentiation required by cryptographic protocols is “secure” in the sense that the secret value used in the computation is not revealed to untrusted parties. Specifically, it is typically practically infeasible to compute the secret value from the result of the modular exponentiation or other public values. To achieve the desired security, in most cases, the computational task is carried out within a secure element, which holds the secret value internally. [Hibshoosh, para. 14]
Regarding claim 2, modified Kerschbaum teaches the method according to claim 1, but Kerschbaum does not teach wherein obtaining a base parameter of an exponentiation operation comprised in the homomorphic encryption operation comprises: obtaining a public key used in the homomorphic encryption operation; and obtaining, from the public key, the base parameter of the exponentiation operation comprised in the homomorphic encryption operation.
However, Hibshoosh does teach wherein obtaining a base parameter of an exponentiation operation comprised in the homomorphic encryption operation comprises: obtaining a public key used in the homomorphic encryption operation; [Hibshoosh, para. 50 discloses Alice's device pre-computes two key pairs: (t, g.sup.t) and (v, g.sup.v), wherein g is the public base and t and v are secrets. Techniques that may be used to perform this pre-computation securely, but with minimal expenditure of computation resources, are described hereinbelow with reference to FIG. 4. In addition, Alice's device chooses a number of large random values for use in the subsequent computations, including the secret exponent a, a pair of secret roots (w.sub.1, w.sub.2), and encryption parameters R.sub.a, R′.sub.a, and R.sub.G. Alice's device uses these parameters in a number of simple preparatory computations] and obtaining, from the public key, the base parameter of the exponentiation operation comprised in the homomorphic encryption operation. [Hibshoosh, para. 57 discloses Alice's device transmits the pair of encryption parameters (R′.sub.a,U′.sub.a) and the key value g.sup.t to server 22, at an initial transmission step 62. Server 22 uses these values in computing Alice's public key g.sup.a for purposes of the key exchange protocol]
Therefore, it would have been obvious to one of ordinary skill within the art before the effective filling date to combine Hibshoosh’s system with Kerschbaum’s system, with a motivation for the modular exponentiation required by cryptographic protocols is “secure” in the sense that the secret value used in the computation is not revealed to untrusted parties. Specifically, it is typically practically infeasible to compute the secret value from the result of the modular exponentiation or other public values. To achieve the desired security, in most cases, the computational task is carried out within a secure element, which holds the secret value internally. [Hibshoosh, para. 14]
Regarding claim 3, modified Kerschbaum teaches the method according to claim 1, but Kerschbaum does not teach wherein querying an exponentiation operation result cache table corresponding to the base parameter based on the exponent parameter, to obtain a result of the exponentiation operation comprises: obtaining an exponent parameter in a current operation cycle and a quantity of query rows in the exponentiation operation result cache table in the current operation cycle, and obtaining a quantity of exponentiation operation results comprised in each row in the exponentiation operation result cache table; when the obtained exponent parameter is unequal to a first value, upon determining that a result of performing an AND operation on the obtained exponent parameter and the quantity of the exponentiation operation results is greater than the first value, querying the exponentiation operation result cache table based on the quantity of query rows and the result of the AND operation; and multiplying an exponentiation operation result obtained through querying and an exponentiation operation result of a previous operation cycle, and using a product as an exponentiation operation result of the current operation cycle.
However, Hibshoosh does teach wherein querying an exponentiation operation result cache table corresponding to the base parameter based on the exponent parameter, to obtain a result of the exponentiation operation comprises: obtaining an exponent parameter in a current operation cycle and a quantity of query rows in the exponentiation operation result cache table in the current operation cycle, [Hibshoosh, para. 62 discloses For the purposes of pre-computation step 60, the values of g.sup.t and g.sup.v, corresponding to the value g raised to the secret exponents t and v, respectively, may be pre-computed offline and stored by Alice's device for subsequent use. Alternatively, to provide Alice's device with a large choice of values of t and v while avoiding the need for full on-line computation of g.sup.t and g.sup.v, Alice's device may acquire the values of x and g.sup.x (x=t or v) for each key exchange using pre-computed table containing T pairs of component values of the form (X.sub.j, g.sup.X.sup.j mod N), which are stored in memory 34 of device 24 in a table storage step 90.] and obtaining a quantity of exponentiation operation results comprised in each row in the exponentiation operation result cache table; [Kerschbaum, para. 63 discloses To compute the key pair (x, g.sup.x), Alice's device randomly selects a set of L indices, j.sub.1, j.sub.2, . . . j.sub.L (for example, with L=11), at a pair selection step 92. The number of indices is small compared to the number of pairs in the table. Using the selected L pairs of component values (X.sub.j, g.sup.X.sup.j mod N), Alice's device then computes t and g.sup.t as follows, at a key pair selection step 94: t=Σ.sub.k=1.sup.Lx.sub.j.sub.k mod N, g.sup.t = Π.sub.k = 1.sup.Lg.sup.x.sup.jk mod N.] when the obtained exponent parameter is unequal to a first value, upon determining that a result of performing an AND operation on the obtained exponent parameter and the quantity of the exponentiation operation results is greater than the first value, [Hibshoosh, para. 48 discloses Device 40 is assumed to be a trusted device with sufficient computing power to perform its own part in the key exchange protocol without assistance. Device 24 is assisted in performing exponentiation by untrusted server 22, and may also delegate certain homomorphic computations to peer device 40, as described below. Server 22 in this case is “untrusted” in the sense that the server assists device 24 in exponentiation without receiving the actual secret exponent, although the server may still be trusted to receive and hold certain encryption parameters in confidence] querying the exponentiation operation result cache table based on the quantity of query rows and the result of the AND operation; [Hibshoosh, para. 50 discloses Alice's device chooses and/or precomputes a number of secret values to be used in the protocol, at a pre-computation step 60. At this step, Alice's device pre-computes two key pairs: (t, g.sup.t) and (v, g.sup.v), wherein g is the public base and t and v are secrets. Techniques that may be used to perform this pre-computation securely, but with minimal expenditure of computation resources, are described hereinbelow with reference to FIG. 4. In addition, Alice's device chooses a number of large random values for use in the subsequent computations, including the secret exponent a, a pair of secret roots (w.sub.1, w.sub.2), and encryption parameters R.sub.a, R′.sub.a, and R.sub.G. Alice's device uses these parameters in a number of simple preparatory computations] and multiplying an exponentiation operation result obtained through querying and an exponentiation operation result of a previous operation cycle, [Hibshoosh, para. 51 – 53 discloses Alice's device uses R.sub.a and v to encrypt a, giving the encryption parameters (R.sub.a, U.sub.a), wherein U.sub.a=a−vR. Similarly, Alice's device uses R′.sub.a and t to perform another encryption of a, giving the encryption parameters (R′.sub.a,U′.sub.a), wherein U′.sub.a=a−tR′.sub.a. Alice's device uses R.sub.G and the secret roots (w.sub.1, w.sub.2) to homomorphically encrypt the key value g.sup.v, giving the parameters of HE(g.sup.v)≡G*=(R.sub.G, U.sub.G), wherein U.sub.G=g.sup.v−w.sub.1R.sub.G.] and using a product as an exponentiation operation result of the current operation cycle. [Hibshoosh, para. 54 – 55 discloses Alice's device computes the public helping values T.sub.w=w.sub.1+w.sub.2 and P.sub.w=w.sub.1.Math.w.sub.2. Alice's device encrypts the parameter Ra using the public key e of server 22 in an asymmetric encryption algorithm, such as RSA, to give the encrypted value Ra*=(Ra.sup.e)mod N*. Here N* is a large public modulus, while e has a small value to enable Alice's device to perform the computation quickly, for example e=3.]
Therefore, it would have been obvious to one of ordinary skill within the art before the effective filling date to combine Hibshoosh’s system with Kerschbaum’s system, with a motivation for the modular exponentiation required by cryptographic protocols is “secure” in the sense that the secret value used in the computation is not revealed to untrusted parties. Specifically, it is typically practically infeasible to compute the secret value from the result of the modular exponentiation or other public values. To achieve the desired security, in most cases, the computational task is carried out within a secure element, which holds the secret value internally. [Hibshoosh, para. 14]
Regarding claim 4, modified Kerschbaum teaches the method according to claim 3, but Kerschbaum does not teach wherein after obtaining an exponent parameter in a current operation cycle, the method further comprises: exiting the current operation cycle when the obtained exponent parameter is equal to the first value; and using the exponentiation operation result of the previous operation cycle as a final exponentiation operation result.
However, Hibshoosh does teach wherein after obtaining an exponent parameter in a current operation cycle, the method further comprises: exiting the current operation cycle when the obtained exponent parameter is equal to the first value; and using the exponentiation operation result of the previous operation cycle as a final exponentiation operation result. [Hibshoosh, para. 59 discloses Bob's device chooses its own secret exponent b, and uses this value together with the public base g and modulus N to compute the public key g.sup.b mod N, at a peer pre-computation step 70. Bob's device uses the parameters received in steps 66 and 68 to compute the homomorphic exponentiation (G*).sup.b mod N, as well as the secret session key g.sup.ab mod N, at a peer computation step 72. In cryptographic terms, (G*).sup.b mod N=HE(g.sup.bv) Bob's device returns the public values g.sup.b and (G*).sup.b mod N to server 22, at a parameter return step 74. Alternatively, Bob's device may pass these values directly to Alice's device, who then forwards them to server 22. For the purposes of the next computation by server 22, Alice's device also passes the encryption parameters R.sub.a* (i.e., the RSA-encrypted value of R.sub.a) and U.sub.a and the helping values T.sub.w and P.sub.w to the server]
Therefore, it would have been obvious to one of ordinary skill within the art before the effective filling date to combine Hibshoosh’s system with Kerschbaum’s system, with a motivation for the modular exponentiation required by cryptographic protocols is “secure” in the sense that the secret value used in the computation is not revealed to untrusted parties. Specifically, it is typically practically infeasible to compute the secret value from the result of the modular exponentiation or other public values. To achieve the desired security, in most cases, the computational task is carried out within a secure element, which holds the secret value internally. [Hibshoosh, para. 14]
Regarding claim 5, Kerschbaum teaches the method according to claim 3, but Kerschbaum does not teach wherein after multiplying an exponentiation operation result obtained through querying and an exponentiation operation result of a previous operation cycle, and using a product as an exponentiation operation result of the current operation cycle, the method further comprises: using a quotient of the exponent parameter in the current operation cycle and a width of the exponentiation operation result cache table as an exponent parameter in a next operation cycle; and increasing the quantity of query rows by a predetermined step.
However, Hibshoosh does teach wherein after multiplying an exponentiation operation result obtained through querying and an exponentiation operation result of a previous operation cycle, and using a product as an exponentiation operation result of the current operation cycle, [Hibshoosh, para. 59 discloses Bob's device chooses its own secret exponent b, and uses this value together with the public base g and modulus N to compute the public key g.sup.b mod N, at a peer pre-computation step 70. Bob's device uses the parameters received in steps 66 and 68 to compute the homomorphic exponentiation (G*).sup.b mod N, as well as the secret session key g.sup.ab mod N, at a peer computation step 72. In cryptographic terms, (G*).sup.b mod N=HE(g.sup.bv) Bob's device returns the public values g.sup.b and (G*).sup.b mod N to server 22, at a parameter return step 74. Alternatively, Bob's device may pass these values directly to Alice's device, who then forwards them to server 22. For the purposes of the next computation by server 22, Alice's device also passes the encryption parameters R.sub.a* (i.e., the RSA-encrypted value of R.sub.a) and U.sub.a and the helping values T.sub.w and P.sub.w to the server] the method further comprises: using a quotient of the exponent parameter in the current operation cycle and a width of the exponentiation operation result cache table as an exponent parameter in a next operation cycle; [Hibshoosh, para. 50 discloses Alice's device chooses and/or precomputes a number of secret values to be used in the protocol, at a pre-computation step 60. At this step, Alice's device pre-computes two key pairs: (t, g.sup.t) and (v, g.sup.v), wherein g is the public base and t and v are secrets. Techniques that may be used to perform this pre-computation securely, but with minimal expenditure of computation resources, are described hereinbelow with reference to FIG. 4. In addition, Alice's device chooses a number of large random values for use in the subsequent computations, including the secret exponent a, a pair of secret roots (w.sub.1, w.sub.2), and encryption parameters R.sub.a, R′.sub.a, and R.sub.G. Alice's device uses these parameters in a number of simple preparatory computations] and increasing the quantity of query rows by a predetermined step. [Hibshoosh, para. 86 discloses For Bob's device to compute a function with the encrypted Xi, the public coefficients, b and c, (defined above under key generation) are used; note that b and c do not change for encryption of different variables; they are given typically once (per some predefined period) by Alice's device to Bob's device. We also note that typically one large-number multiplication is used for encryption. When computing multivariate functions with the encrypted variables we consider the addition, multiplication and division of two variables. Addition and multiplication of encrypted values are defined by the addition and multiplication, respectively, of the corresponding linear functions in Z.sub.N[v]/PP(v).]
Therefore, it would have been obvious to one of ordinary skill within the art before the effective filling date to combine Hibshoosh’s system with Kerschbaum’s system, with a motivation for the modular exponentiation required by cryptographic protocols is “secure” in the sense that the secret value used in the computation is not revealed to untrusted parties. Specifically, it is typically practically infeasible to compute the secret value from the result of the modular exponentiation or other public values. To achieve the desired security, in most cases, the computational task is carried out within a secure element, which holds the secret value internally. [Hibshoosh, para. 14]
Regarding claim 6, modified Kerschbaum teaches the method according to claim 3, but Kerschbaum does not teach wherein querying the exponentiation operation result cache table based on the quantity of query rows and the result of the AND operation comprises: obtaining a difference obtained by subtracting the result of the AND operation by a second value; and querying the exponentiation operation result cache table based on a row corresponding to the quantity of query rows and a column corresponding to the difference, to obtain an exponentiation operation result.
However, Hibshoosh does teach wherein querying the exponentiation operation result cache table based on the quantity of query rows and the result of the AND operation comprises: obtaining a difference obtained by subtracting the result of the AND operation by a second value; [Hibshoosh, para. 12 discloses the server receives a second base value g.sup.b computed by the second peer device by raising the public value g to the second power. A homomorphic exponentiation is computed in the server using the encryption parameters and the second base value g.sup.b, so as to generate an output HE(g.sup.ab) that is indicative of the session key.] and querying the exponentiation operation result cache table based on a row corresponding to the quantity of query rows and a column corresponding to the difference, to obtain an exponentiation operation result. [Hibshoosh, para. 12 discloses The output is conveyed from the server over the communication channel to the first peer device, which applies a polynomial homomorphic decryption to the output conveyed by the server in order to recover the session key g.sup.ab. Communications between the first and second peer devices are encrypted and decrypted using the session key. Para. 17 discloses Using polynomial homomorphic encryption, the device computes and provides to the server at least two parameters that encode the secret value. In response to the request, the server performs a homomorphic exponentiation using the parameters received from the device without decrypting the secret value, and thus generates an output that is indicative of the result of the modular exponentiation operation.]
Therefore, it would have been obvious to one of ordinary skill within the art before the effective filling date to combine Hibshoosh’s system with Kerschbaum’s system, with a motivation for the modular exponentiation required by cryptographic protocols is “secure” in the sense that the secret value used in the computation is not revealed to untrusted parties. Specifically, it is typically practically infeasible to compute the secret value from the result of the modular exponentiation or other public values. To achieve the desired security, in most cases, the computational task is carried out within a secure element, which holds the secret value internally. [Hibshoosh, para. 14]
Regarding claim 7, modified Kerschbaum teaches the method according to claim 1, but Kerschbaum does not teach wherein before querying an exponentiation operation result cache table corresponding to the base parameter based on the exponent parameter, to obtain a result of the exponentiation operation, the method further comprises: generating the exponentiation operation result cache table corresponding to the base parameter based on the base parameter of the exponentiation operation comprised in the homomorphic encryption operation and a predetermined width.
However, Hibshoosh does teach wherein before querying an exponentiation operation result cache table corresponding to the base parameter based on the exponent parameter, to obtain a result of the exponentiation operation, the method further comprises: generating the exponentiation operation result cache table corresponding to the base parameter based on the base parameter of the exponentiation operation comprised in the homomorphic encryption operation and a predetermined width. [Hibshoosh, para. 66 discloses the use of pre-stored pairs of component values of the form (X.sub.j, g.sup.X.sup.j mod N) in generating a large secret value and its exponent by summation and multiplication, as described above, is by no means limited to this specific context. Rather, this technique can be applied in other settings in which a device with weak computational capabilities is required to generate a large secret value and its exponent. Para. 12 discloses the method includes computing in the first peer device an encryption of the first secret value a so as to generate encryption parameters that encode the first secret value, and conveying the encryption parameters over a communication channel to a server, which does not have access to either of the first and second secret values a and b. A first base value g.sup.a, equal to a public value g raised to a first power equal to the first secret value a, is computed and conveyed to the second peer device, which raises the first base value to a second power equal to the second secret value b in order to generate a session key g.sup.ab.]
Therefore, it would have been obvious to one of ordinary skill within the art before the effective filling date to combine Hibshoosh’s system with Kerschbaum’s system, with a motivation for the modular exponentiation required by cryptographic protocols is “secure” in the sense that the secret value used in the computation is not revealed to untrusted parties. Specifically, it is typically practically infeasible to compute the secret value from the result of the modular exponentiation or other public values. To achieve the desired security, in most cases, the computational task is carried out within a secure element, which holds the secret value internally. [Hibshoosh, para. 14]
Regarding claims 15 and 16, they recite features similar to features within claim 1, therefore, they are rejected in a similar manner.
Regarding claims 17 – 22, they recite features similar to features within claims 2 – 7, therefore, they are rejected in a similar manner.
Regarding claims 23 – 27, they recite features similar to features within claims 2 – 6, therefore, they are rejected in a similar manner.
Conclusion
Pertinent prior art made of record however not relied upon:
US 11296861 B1 to Zhang et al.
“A Paillier decryption system, IC, and method. The IC includes: a modular exponentiation module, for performing modular exponentiation operations related to a first subitem and a second subitem, where a Paillier decryption process of encrypted data is divided into a first subitem and a second subitem according to the Chinese remainder theorem, the first subitem corresponding to a first prime, the second subitem corresponding to a second prime, a public key of the encrypted data being a product of the first prime and the second prime, a bit width of the first prime being the same as a bit width of the second prime; a first module combination corresponding to the first subitem, for determining a computation result of the first subitem; and a second module combination corresponding to the second subitem, for determining a computation result of the second subitem.”
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Phuc Pham whose telephone number is (571)272-8893. The examiner can normally be reached Monday - Thursday 7:30 AM - 4:30 PM; Friday 8:00 AM - 12:00 PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Linglan Edwards can be reached at (571) 270-5440. 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.
/P.P./Patent Examiner, Art Unit 2408
/LINGLAN EDWARDS/Supervisory Patent Examiner, Art Unit 2408