Office Action 1: Non-Final Rejection (2024-10-30)
Rejection types: 102 - Lack of Novelty, 103 - Obviousness, 101 - Patent-Eligible Subject Matter

CLAIMS:
Claims

1\. A method for performing computation of a function (f) over encrypted data by a computation entity, wherein the computation of a quadratic function (f) is performed by the computation entity, wherein the encrypted data are encrypted by means of a linearly homomorphic encryption scheme, and
wherein a homomorphic message authentication code is used for providing
verifiable computation on encrypted data.

2\. A method according to claim 1, wherein the homomorphic message authentication code is used to define a verifiable computation scheme.

3\. A method according to claim 1 or 2, wherein the linearly homomorphic encryption scheme is a linearly homomorphic ElGamal encryption scheme.

4\. A method according to one of claims 1 to 3, wherein a computation over authentication tags that accompany the encrypted data is performed, so that preferably the computation entity can output an encoding that includes a ciphertext encrypting the result of the computation and a tag.

5\. A method according to claim 4, wherein an integrity of the result is verified by means of a final tag.

6\. A method according to one of claims 1 to 5, wherein the linearly homomorphic encryption scheme produces one or more encodings, a public evaluation key and/or a private verification key.

7\. A method according to one of claims 1 to 6, wherein a degree-2 function (f) of the encrypted or encoded data is computed by the computation entity by means of homomorphic operations over the encryptions or encodings, thereby producing an output encoding.

8\. A method according to claim 7, wherein it is verified that the output encoding encodes the result of the function (f) over the encrypted or encoded data and, if so, the output encoding is decoded.

9\. A method according to one of claims 1 to 8, wherein the method is used in data-mining, for example as a service application, and/or in machine learning, for example as a service application.

10\. A method according to one of claims 1 to 9, wherein a data source provides and/or encrypts the data.

11\. A method according to claim 10, wherein the data source transmits and/or uploads the encrypted data to the computation entity.

12\. A method according to claim 10 or 11, wherein the data source is a metering device or a smart energy meter.

13\. A method according to one of claims 1 to 12, wherein the encrypted data are provided in the form of a ciphertext or ciphertexts.

14\. A method according to one of claims 1 to 13, wherein the computation entity is a server or cloud server.

15\. A computation entity for performing computation of a function (f) over encrypted data, preferably for carrying out the method according to any one of claims 1 to 14, wherein the computation of a quadratic function (f) is performed by the computation entity, wherein the encrypted data are encrypted by means of a linearly homomorphic encryption scheme, and
wherein a homomorphic message authentication code is used for providing verifiable computation on encrypted data. 5 10 15 20 25 30

OFFICE ACTION:
DETAILED ACTION
Claims 1-15 are pending. This is in response to the application filed on February 8, 2023 which claims priority to a foreign application filed on September 9, 2020. This application is a 371 of PCT/EP2021/053913 filed on February 17, 2021.
Notice of Pre-AIA  or AIA  Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 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.
Regarding claim 15, the claimed invention is directed to non-statutory subject matter.  The claim(s) does/do not fall within at least one of the four categories of patent eligible subject matter because a computing entity can be interpreted as a software device performing the recited features.
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.
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(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.
Claims 1-2, 6-8 and 13-15 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Pub 20150215123 (hereinafter Kipnis)
Regarding claim 1, Kipnis discloses a method for performing computation of a function over encrypted data by a computation entity, the method comprising:
performing computation of a quadratic function by the computation entity, and encrypting the encrypted data by a linearly homomorphic encryption scheme (Summary section and Polynomial Method section from par. [0175]-[0181] discloses using homomorphic encryption with quadratic equation as linear function),
wherein a homomorphic message authentication code is used for providing verifiable computation on encrypted data (par. [207]-[0215] discloses how  a hash value of a messages encrypted using  Homomorphic Encryption scheme is verified).
Regarding claim 2, Kipnis discloses wherein the homomorphic message authentication code is used to define a verifiable computation scheme (par. [207]-[0215]).
Regarding claim 6, Kipnis discloses wherein the linearly homomorphic encryption scheme produces one or more encodings, a public evaluation key and/or a private verification key (par. [0025]-[0027] discloses a key pair is produced and the private key is used to verify the hash value).
Regarding claim 7, Kipnis discloses wherein a degree-2 function of the encrypted or encoded data is computed by the computation entity by homomorphic operations over the encryptions or encodings, thereby producing an output encoding (par. [0259] discloses using polynomial of degree 2 or higher).
Regarding claim 8, Kipnis discloses wherein it is verified that the output encoding encodes the result of the function over the encrypted or encoded data and, if so, the output encoding is decoded (par. [0222]-[0235] discloses verification of R*  where R* is the encrypted returned to a secure client for decryption).
Regarding claim 13, Kipnis discloses wherein the encrypted data are provided in the form of a ciphertext or ciphertexts (par. [0169]).
Regarding claim 14, Kipnis discloses wherein the computation entity is a server or cloud server (Fig. 1 discloses a server performing the encryption).
Regarding claim 15, the claim is rejected in view of claim 1.
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 3 is rejected under 35 U.S.C. 103 as being unpatentable over  Kipnis in view of Patent 9641332 (hereinafter Yung)
Regarding claim 3, Kipnis does not disclose wherein the linearly homomorphic encryption scheme is a linearly homomorphic EIGamal encryption scheme. Yung disclose El Gamal can be added into a linear  homomorphic encryption (col. 9, lines 6-18). Therefore, it would have been obvious before the effective filing date of the claimed invention to modify Kipnis with Yung to further teach the aforementioned feature. One would have done so using known variation of homomorphic encryption to arrive at the claimed invention with reasonable expectation of success.
8.  	Claims 4-5 are rejected under 35 U.S.C. 103 as being unpatentable over  Kipnis in view of Patent 10630478 (hereinafter Yavuz)
Regarding claim 4, Kipnis does not disclose wherein a computation over authentication tags that accompany the encrypted data is performed, so that the computation entity can output an encoding that includes a ciphertext encrypting a result of the computation and a tag.  Yavuz discloses this feature (col. 5, line 36 to col. 6, line 44 discloses cryptographic techniques referred to as Sender Optimal, Breach-resilient Auditing with Post-Quantum security (SOBAP) using an authentication tag in the encrypted data for verification). Therefore, it would have been obvious before the effective filing date of the claimed invention to modify Kipnis with Yavuz to further teach the aforementioned feature. One would have done to provide a conditional non-repudiation in order to arrive at the claimed invention with reasonable expectation of success.
Regarding claim 5, Yavuz discloses wherein an integrity of the result is verified by a final tag (Yavuz asserts SOBAP achieves authenticity, integrity, and confidentiality).
Claims 9-11 are rejected under 35 U.S.C. 103 as being unpatentable over  Kipnis in view of Pub 20190386814 (hereinafter Ahmed)
Regarding claim 9, Kipnis does not disclose wherein the method is used in data-mining and/or in machine learning. Ahmed discloses homomorphic encryption can be used in data mining application (par. [0357]). Therefore, it would have been obvious before the effective filing date of the claimed invention to modify Kipnis with Ahmed to further teach the aforementioned feature. One would have done to provide the encryption process in various applications as suggested in Ahmed in order to arrive at the claimed invention with reasonable expectation of success.
Regarding claim 10, Ahmed further discloses wherein a data source provides and/or encrypts the data (Fig. 4 and related paragraphs discloses a cloud service storing encrypted data of clients where the cloud service performs a fully homomorphic encryption).
Regarding claim 11, Ahmed further discloses wherein the data source transmits and/or uploads the encrypted data to the computation entity (Fig. 4 discloses three different entities 418, 420 and 425 each with different functions such as computations, calculations the client encrypted data for homomorphic encryption). Therefore, it would have been obvious before the effective filing date of the claimed invention to modify Kipnis with Ahmed to further teach the aforementioned feature. One would have done to provide the encryption process in various applications as suggested in Ahmed in order to arrive at the claimed invention with reasonable expectation of success.
Claim 12 is rejected under 35 U.S.C. 103 as being unpatentable over  Kipnis in view of Ahmed and further in view of Pub CN-111294366-A (hereinafter Zhang)
Regarding claim 12, either Kipnis or Ahmed does not disclose wherein the data source is a metering device or a smart energy meter. Zhang discloses data used in smart meter in a power grid system is homomorphically encrypted (Summary section). Therefore, it would have been obvious before the effective filing date of the claimed invention to modify Kipnis and Ahmed with Zhang to further teach the aforementioned feature. One would have done to provide the encryption process in various applications as suggested in Ahmed and Zhang in order to arrive at the claimed invention with reasonable expectation of success.
Inquiry communication

APPLICANT REBUTTAL: REMARKS / ARGUMENTS Reconsideration of the application and claims in light of the foregoing amendments and following remarks/arguments is respectfully requested. Status of the Claims Claims 1-15 are currently pending in the present application. In the Office Action, claims 1-15 were rejected. The present Response amends claims 1, 10 and 15, and adds new claim 16. No new matter has been added. Upon entry of these amendments, claims 1-16 will be pending. Rejections under 35 U.S.C. & 101 Claim 15 was rejected under 35 U.S.C. § 101 as being directed to non-statutory subject matter. Claim 15 was rejected for not falling within at least one of the four categories of patent eligible subject matter because a computing entity can be interpreted as a software device performing the recited features. See Office Action, p. 3. Claim 15 has been amended to recite "A system ... comprising: one or more hardware processors configured to." Accordingly, reconsideration and withdrawal of the rejections of claims 15 under 35 U.S.C. § 101 is respectfully requested. Rejections under 35 U.S.C. 44 102 and 103 Claims 1-2, 6-8, and 13-15 were rejected under 35 U.S.C. § 102 as being anticipated by US 2015/0215123 by Kipnis ("Kipnis"). Claim 3 was rejected under 35 U.S.C. § 103 as being obvious over Kipnis in view of US 9,641,332 by Yung ("Yung"). Claims 4-5 were rejected under 35 U.S.C. § 103 as being obvious over Kipnis in view of US 10,630,478 by Yavuz ("Yavuz"). Claims 9-11 were rejected under 35 U.S.C. § 103 as being obvious over Kipnis in view of US 2019/0386814 by Ahmed ("Ahmed"). Claim 12 was rejected under 35 U.S.C. § 103 as being obvious over Kipnis in view of Ahmed and further in view of CN 111294366 by Zhang ("Zhang"). Independent claims 1 and 15 of the present application recite "a homomorphic message authentication code is used for providing verifiable computation on encrypted data." For example, an embodiment of the present invention provides a method for performing computation of a function over encrypted data by a computation entity so that a reliable computation result is obtainable by simple means. See published specification (US PAP 2023/0269089 Al), paragraph [0013]. The use of a homomorphic message authentication code provides verifiable computation on already encrypted data. A computation entity performs computation of the function over the encrypted data. The computation over the encrypted data can include a computation over authentication tags that accompany the encrypted data, so that the computation entity can output an encoding that includes a ciphertext encrypting the result of the computation and a tag. An integrity of the result can be verified by means of a final tag as received by the computation entity or server. This verifying step can advantageously be performed by any client. See published specification, paragraph [0020]. Contrary to the assertions in the Office Action, it is respectfully submitted that Kipnis fails to disclose at least the foregoing features that "a homomorphic message authentication code is used for providing verifiable computation on encrypted data," of independent claims 1 and 15. Rather, Kipnis is silent with respect to verifying any computations on encrypted data and merely describes verifying a signature. See Kipnis, paragraphs [0207]-[0215]. Specifically, the cited portion of Kipnis describes performing verification of a signature on a message by calculating a hash of the message and a matrix M in dimension 2 subspace of matrices. In order to verify the signature, a verifier computes the hash of the message and verifies a corresponding mathematical relationship. See Kipnis, paragraphs [0207]-[0215]. While Kipnis describes a regular signature scheme, Kipnis is completely silent regarding verifying any contents of the message for which the signature is provided, much less verifying any computations in the message. The signature scheme as described in Kipnis cannot verify that a specific computation in the message was carried out correctly, but is only able to verify that the signature associated with the message is correct. On the other hand, pending independent claims 1 and 15 recite using a homomorphic message authentication code to provide verifiable computation on encrypted data. This advantageously allows a client to verify computation carried out by a computation entity or server, as described above. In contrast, Kipnis makes no mention of verifying any contents of the message, and merely provides a way to verify the signature. Therefore, Kipnis does not disclose or suggest at least "using a homomorphic message authentication code for providing verifiable computation on encrypted data," as recited in independent claim 1. Because Kipnis fails to disclose at least the above-recited features of amended independent claims 1 and 15, Kipnis cannot anticipate claim 1 or 15 or their dependent claims 2, 6-8, and 13-14. Additionally, in rejecting claim 3, the Office correctly concedes that Kipnis does not disclose that the "the linearly homomorphic encryption scheme is a linearly ElGamal encryption scheme," but suggests that Yung teaches this subject matter at col. 9, lines 6-18. The Office alleges that it would be obvious to combine the teachings of Kipnis with the teachings of Yung to teach "the linearly homomorphic encryption scheme is a linearly ElGamal encryption scheme," because one would have done so using known variation of homomorphic encryption to arrive at the claimed invention. See Office Action, p. 5. Applicant respectfully disagrees because the nature of the key as described in Kipnis is completely different from a linearly homomorphic key like ElGamal as described in Yung. Kipnis describes using a symmetric key, in which encryption and decryption is performed using the same key. However, the ElGamal key is a linearly homomorphic key that has a public key and/or a private key for encryption and decryption purposes. The same key cannot be used for both encryption and decryption in Yung. Therefore, one of skill in the art would not look to Yung to remedy the deficiencies of Kipnis with respect to pending claim 3. Furthermore, in rejecting claims 4 and 5, the Office correctly concedes that Kipnis does not teach "a computation over authentication tags that accompany the encrypted data is performed, so that the computation entity can output an encoding that includes a ciphertext encrypting a result of the computation and a tag," but states that Yavus teaches this subject matter at col. 5 line 36 - col. 6, line 44. The Office is of the opinion that it would have been obvious to modify Kipnis with Yavuz because one would have done so to provide a conditional non-repudiation in order to arrive at the claimed invention with a reasonable expectation of success. See Office Action, p. 6. However, a person of skill in the art would not have, absent hindsight reasoning, combined Kipnis and Yavuz since the teachings of Yavuz are incompatible with the teachings of Kipnis. Particularly, the cited portion of Yavuz describes symmetric key primitives like encryption and a message authentication code. This message authentication code is not homomorphic, while, in contrast Kipnis relies on a homomorphic key. Therefore, one of skill in the art would not look to modify the teachings of Kipnis with Yavuz. Also, Yavuz is completely silent regarding verifying the integrity of a computation over authenticated data. Yavuz merely deals with data that is stored in remote storage and not used for computation. Zhang and Ahmed, used to reject other dependent claims does not remedy the deficiencies of Kipnis, Yung, and Yavuz. Accordingly, reconsideration and withdrawal of the rejection of claims 1-15 under 35 U.S.C. §§ 102 and 103 based on Kipnis alone or in combination with Yung, Yavuz, Ahmed, and Zhang is respectfully requested. New Claims New claim 16 depends from independent claim 1. It is therefore respectfully submitted that new claim 16 is allowable over the cited prior art for at least the same reasons as claim 1, discussed above. Support for the new claims can be found, for example, in paragraphs [0038] of the published specification. It is further respectfully submitted that claim 16 recites features which further distinguish the present invention from the cited prior art. For example, claim 16 recites to "the data source encrypts the encrypted data by the linearly homomorphic encryption scheme and a client performs the verification that the output encoding encodes the result of the function over the encrypted or encoded data." In contrast, Kipnis describes a symmetric key that is used by a singular entity to performs the encryption and decryption of data. CONCLUSION Applicant believes that all issues raised by the Office have been addressed and that the present application is allowable for the foregoing reasons. If there are any remaining issues which the Office believes could be resolved through either a Supplemental Response or an Examiner's Amendment, Applicant respectfully invites the Office to call the telephone contact at the number indicated below. The Commissioner is hereby authorized to charge any unpaid fees deemed required in connection with this submission, including any additional filing or application processing fees required under 37 C.F.R. §1.16, 1.17 or 1.492, except for fees based on multiple dependent claims under 37 CFR §1.16(i) or (j) or 37 CFR §1.492(e) or (f), or to credit any overpayment, to Deposit Account No. 12-1216. Dated: January 21, 2025 Respectfully submitted, By /James C. Signor/ Red. No. 59,233 Naman Seth (telephone contact) Limited Recognition No. 800,009 James C. Signor Registration No. 59,233LEYDIG, VOIT & MAYER, LTD. Leydig Two Prudential Plaza, Suite 4900 180 North Stetson Avenue Chicago, Illinois 60601-6731 (312) 616-5600 (Telephone) (312) 616-5700 (Fax) Attorneys/Agents For Applicant

NEXT OFFICE ACTION: DETAILED ACTION
Claims 1-3 and 6-16 are pending. Claims 4-5 are canceled.  Claims 1 and 15 are amended. This is in response to Applicant’s arguments and amendments filed on January 21, 2025.
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 .
EXAMINER'S AMENDMENT
An examiner’s amendment to the record appears below. Should the changes and/or additions be unacceptable to applicant, an amendment may be filed as provided by 37 CFR 1.312. To ensure consideration of such an amendment, it MUST be submitted no later than the payment of the issue fee.
Authorization for this examiner’s amendment was given in an interview with James Signor on March 10, 2025.
The application has been amended as follows:
Claim 1 (Currently Amended):  A method for performing verifiable computation of a quadratic function over encrypted data by a computation entity, the method comprising:
generating the encrypted data or receiving the encrypted data from a data source, wherein the encrypted data is encrypted by a linearly homomorphic encryption scheme, and
performing the computation of the over the encrypted data by the computation entity,
wherein a homomorphic message authentication code is used for providing the verifiable computation on the encrypted data,
wherein a computation over authentication tags that accompany the encrypted data is performed, so that the computation entity can output an encoding that includes a ciphertext encrypting a result of the computation and a tag, and
wherein an integrity of the result is verified by a final tag, and
wherein the tags are different from the homomorphic message authentication code.
Claim 4 (Canceled).
Claim 5 (Canceled).
Claim 15 (Currently Amended):  A system for performing verifiable computation of a quadratic function over encrypted data, the system comprising:
one or more hardware processors configured to:
generate the encrypted data or receive the encrypted data from a data source, wherein the encrypted data is encrypted by a linearly homomorphic encryption scheme, and
perform the computation of the
wherein a homomorphic message authentication code is used for providing the verifiable computation on the encrypted data,
wherein a computation over authentication tags that accompany the encrypted data is performed, so that the computation entity can output an encoding that includes a ciphertext encrypting a result of the computation and a tag,
wherein an integrity of the result is verified by a final tag, and
wherein the tags are different from the homomorphic message authentication code.
Reasons for Allowance
The following is an examiner’s statement of reasons for allowance:
Applicant agrees to the above amendments for compact prosecution since there is no art singly or in combination teaches the use of authentication tag in addition to using message authentication code. Therefore, claims 1 and 15 are allowed.
Prior art such as 20140310524 (hereinafter Yamanaka) also use the homomorphic message authentication code in the same field of power meter device data authentication. Yamanaka calculates aggregated encrypted data corresponding to a sum of the pieces of data encrypted. A second calculator is configured to sum up message authentication codes received to calculate a total value of the message authentication codes for the aggregated encrypted data. Yamanaka discloses using a second message authentication code to authenticate the sum of the first encrypted data (Fig. 11 and related text). Yamanaka does not disclose any other values used for verifying the data besides the message authentication code.
Any comments considered necessary by applicant must be submitted no later than the payment of the issue fee and, to avoid processing delays, should preferably accompany the issue fee.  Such submissions should be clearly labeled “Comments on Statement of Reasons for Allowance.”
Inquiry communication

CITED REFERENCE SUMMARIES: Ref US20150215123A1: Claims:
A fully homomorphic method for randomizing an input, wherein all computations are over a commutative ring hereinafter denoted as CR, the method comprising: receiving an input denoted INP comprising a sequence of k input elements in CR; performing either one of (a) or (b):
receiving an input denoted INP comprising a sequence of k input elements in CR;
performing either one of (a) or (b):
(a) randomly choosing a secret n×n matrix in CR, hereinafter denoted as S, S being utilized as a symmetric randomizing key, wherein S comprises an invertible matrix over CR; determining S −1 ; for each set i of m distinct input elements among k elements comprising INP, wherein 0<m<k+1 and m<n selected from INP that are to be jointly randomized, and denoted hereinafter as X 1 , X 2 , . . . , X m , selecting n−m (a minus m) random numbers Y 1 , Y 2 , . . . Y n−m , in CR, where the input elements X 1 , X 2 , . . . , X m ; at least one random number selected from among the set of random numbers Y 1 , Y 2 , . . . Y n−m ; and, optionally. one or more constants are placed in a diagonal of an n×n diagonal matrix, denoted M, wherein, aside from the diagonal, matrix M is only populated by zeros; and determining random output A im for the m input elements in set i denoted as {X im }=X 1 , X 2 , . . . , X m , by utilizing a matrix-based randomizing and homomorphic transformation function hereinafter denoted MRHT, wherein:
determining S −1 ; for each set i of m distinct input elements among k elements comprising INP, wherein 0<m<k+1 and m<n selected from INP that are to be jointly randomized, and denoted hereinafter as X 1 , X 2 , . . . , X m , selecting n−m (a minus m) random numbers Y 1 , Y 2 , . . . Y n−m , in CR, where the input elements X 1 , X 2 , . . . , X m ; at least one random number selected from among the set of random numbers Y 1 , Y 2 , . . . Y n−m ; and, optionally. one or more constants are placed in a diagonal of an n×n diagonal matrix, denoted M, wherein, aside from the diagonal, matrix M is only populated by zeros; and determining random output A im for the m input elements in set i denoted as {X im }=X 1 , X 2 , . . . , X m , by utilizing a matrix-based randomizing and homomorphic transformation function hereinafter denoted MRHT, wherein:
determining S −1 ;
for each set i of m distinct input elements among k elements comprising INP, wherein 0<m<k+1 and m<n selected from INP that are to be jointly randomized, and denoted hereinafter as X 1 , X 2 , . . . , X m , selecting n−m (a minus m) random numbers Y 1 , Y 2 , . . . Y n−m , in CR, where the input elements X 1 , X 2 , . . . , X m ; at least one random number selected from among the set of random numbers Y 1 , Y 2 , . . . Y n−m ; and, optionally. one or more constants are placed in a diagonal of an n×n diagonal matrix, denoted M, wherein, aside from the diagonal, matrix M is only populated by zeros; and
determining random output A im for the m input elements in set i denoted as {X im }=X 1 , X 2 , . . . , X m , by utilizing a matrix-based randomizing and homomorphic transformation function hereinafter denoted MRHT, wherein:
MRHT î¢ ( { X im } ) = A im = SMS - 1 = ( a 11 â¦ a 1 î¢ î¢ n â® â± â® a n î¢ î¢ 1 â¦ a nn )
thereby producing a random output Am corresponding to the i set of its input elements {X im }=X 1 , X 2 , . . . , X m ; and
(b) selecting n random numbers in CR, the n random numbers hereinafter denoted as v 1 , v 2 , . . . , v n ; determining a public polynomial P(v)=Î i=1 n (vâv i )=Î£ j=0 n C j Â·v j (C n =1); selecting a polynomial-based randomizing and homomorphic transformation function hereinafter denoted PRHT (X im ), comprising any function in variable v of the form Î£ j=0 nâ1 a ij Â·v j which satisfies the equations: Î£ j=0 nâ1 a ij Â·v 1 j =X 1 ,Î£ j=0 nâ1 a ij Â·v 2 j =X 2 , . . . ,Î£ j=0 nâ1 a ij Â·v m j =X m : choosing nâm random values in CR, for a i,m , a i,m+1 . . . , a i,nâ1 , that would yield a solution for the above equations for a i,0 , a i,1 . . . , a i,mâ1 ; and if (b) was performed, then performing either one of (c) or (d):
determining a public polynomial P(v)=Î i=1 n (vâv i )=Î£ j=0 n C j Â·v j (C n =1); selecting a polynomial-based randomizing and homomorphic transformation function hereinafter denoted PRHT (X im ), comprising any function in variable v of the form Î£ j=0 nâ1 a ij Â·v j which satisfies the equations: Î£ j=0 nâ1 a ij Â·v 1 j =X 1 ,Î£ j=0 nâ1 a ij Â·v 2 j =X 2 , . . . ,Î£ j=0 nâ1 a ij Â·v m j =X m : choosing nâm random values in CR, for a i,m , a i,m+1 . . . , a i,nâ1 , that would yield a solution for the above equations for a i,0 , a i,1 . . . , a i,mâ1 ; and if (b) was performed, then performing either one of (c) or (d):
determining a public polynomial P(v)=Î i=1 n (vâv i )=Î£ j=0 n C j Â·v j (C n =1);
selecting a polynomial-based randomizing and homomorphic transformation function hereinafter denoted PRHT (X im ), comprising any function in variable v of the form Σ j=0 n−1 a ij ·v j which satisfies the equations: Σ j=0 n−1 a ij ·v 1 j =X 1 ,Σ j=0 n−1 a ij ·v 2 j =X 2 , . . . ,Σ j=0 n−1 a ij ·v m j =X m :
Σ j=0 n−1 a ij ·v 1 j =X 1 ,Σ j=0 n−1 a ij ·v 2 j =X 2 , . . . ,Σ j=0 n−1 a ij ·v m j =X m :
choosing n−m random values in CR, for a i,m , a i,m+1 . . . , a i,n−1 , that would yield a solution for the above equations for a i,0 , a i,1 . . . , a i,m−1 ; and
if (b) was performed, then performing either one of (c) or (d):
(c) producing a random output A im corresponding to input elements X 1 , X 2 , . . . , X m comprising the set (a i0 , a i1 , . . . , a in−1 ) and public set of coefficients (C 0 , C 1 , . . . , C n−1 , C n ) of P(v), wherein the public set of coefficients (C 0 , C 1 , . . . , C n−1 , C n ) are required for arithmetic performing operations with input elements; and
(d) selecting for the given input dements X 1 , X 2 , . . . , X m , n−m random values R 1 , . . . , R n−m in CR that would solve the following n simultaneous equations:
ti Σ j=0 n−1 a ij ·v 1 j =X 1 ,Σ j=0 n−1 a ij ·v 2 j =X 2 , . . . ,Σ j=0 n−1 a ij ·v m j =X m , Σ j=0 n−1 a ij ·v m+1 j =R 1 , Σ j=0 n−1 a ij ·v m+2 j =R 2 , . . . , Σ j=0 n−1 a ij ·v n j =R n−m
Σ j=0 n−1 a ij ·v m+2 j =R 2 , . . . , Σ j=0 n−1 a ij ·v n j =R n−m
for unknowns a i0 , a i1 , . . . , a in−1 , thereby producing, for X 1 , X 2 , . . . X m a random text comprising the set (a i0 , a i1 , . . . , a in−1 ) and public set (C 0 , C 1 , . . . , C n−1 , C n ) of P(v).
The method according to claim 1 , wherein she randomization of the input INP comprises a successive application of a mix of functions PRHT(X i ) and MRHT(X i ), where Xi denotes a set of m distinct input elements of INP and wherein:
MRHT î¢ ( PRHT î¢ ( X i ) ) = ( MRHT î¢ ( a i î¢ î¢ 0 ) , MRHT î¢ ( a i î¢ î¢ 1 ) , â¦ î¢ , MRHT î¢ ( a i î¢ î¢ n - 1 ) ) == ( ( a 11 â¦ a 1 î¢ î¢ n â® â± â® a n î¢ î¢ 1 â¦ a nn ) i î¢ î¢ 0 , ( a 11 â¦ a 1 î¢ î¢ n â® â± â® a n î¢ î¢ 1 â¦ a nn ) i î¢ î¢ 1 , â¦ î¢ , ( a 11 â¦ a 1 î¢ î¢ n â® â± â® a n î¢ î¢ 1 â¦ a nn ) i î¢ î¢ n - 1 ) ; and î¢ PRHT î¢ ( MRHT î¢ ( X i ) ) = PRHT î¢ ( ( a 11 â¦ a 1 î¢ î¢ n â® â± â® a n î¢ î¢ 1 â¦ a nn ) ) î¢ where î¢ PRHT î¢ ( a mj ) = ( a 0 , a 1 , â¦ î¢ , a n - 1 ) mj , therefore PRHT î¢ ( MRHT î¢ ( X i ) ) = ( ( a 0 , a 1 , â¦ î¢ , a n - 1 ) 11 â¦ ( a 0 , a 1 , â¦ î¢ , a n - 1 ) 1 î¢ î¢ n â® â± â® ( a 0 , a 1 , â¦ î¢ , a n - 1 ) n î¢ î¢ 1 â¦ ( a 0 , a 1 , â¦ î¢ , a n - 1 ) nn ) .
A method for derandomizing the randomized input of claim 1 , the method comprising: performing either one of (a) or (b):
(a) receiving an output comprising a randomized X im input being an n×n diagonal matrix denoted hereinafter as A im , over CR, where:
A im = MRHT î¢ ( X im ) = SMS - 1 = ( a 11 â¦ a 1 î¢ î¢ n â® â± â® a n î¢ î¢ 1 â¦ a nn ) using S to determine
using S to determine
S - 1 = ( s 11 ′ … s 1   n ′ ⋮ ⋱ ⋮ s n   1 ′ … s nn ′ )
and determining X im by performing one of: S −1 , A im ·S=M where X 1 , X 2 , . . . , X m are the upper left elements of the resulting diagonal matrix above,
S −1 , A im ·S=M where X 1 , X 2 , . . . , X m are the upper left elements of the resulting diagonal matrix above,
alternatively: X i =(1 /s′ i1 )·Σ j=1 n a j1 ·s′ ij for = 1, . . . m; and
X i =(1 /s′ i1 )·Σ j=1 n a j1 ·s′ ij for = 1, . . . m; and
(b) receiving the randomized output for X im as (a i0 , a i1 , . . . , a in−1 ) and using v 1 , v 2 , . . . , v m to determine the derandomized input Σ j=0 n−1 a ij ·v 1 j =X 1 ,Σ j=0 n−1 a ij ·v 2 j =X 2 , . . . ,Σ j=0 n−1 a ij ·v m j =X m .
A method for addition of randomized X 1 and randomized X 2 X 1 and X 2 being randomized according to the fully homomorphic method for randomizing an input of claim 1 , the method comprising: for X i comprising MRHT (X i )=A i ; receiving A 1 and A 2 ; and MRHT ( X 1 )+ MRHT ( X 2 )= A 1 +A 2 ; and for X i comprising PRHT (X i )=a i0 , a i1 , . . . , a in−1 : receiving PRHT (X 1 )=a 10 , a 11 , . . . , a 1n−1 and PRHT (X 2 )=a 20 , a 21 , . . . , a 2n−1 and C 0 , C 1 , . . . , C n−1 , C n of P(v)=Σ j=0 n C j ·v j (C n =1; and PRHT ( X 1 )+ PRHT ( X 2 )= a 10 +a 20 ,a 11 +a 21 , . . . ,a 1n−1 +a 2n−1 .
for X i comprising MRHT (X i )=A i ; receiving A 1 and A 2 ; and MRHT ( X 1 )+ MRHT ( X 2 )= A 1 +A 2 ; and
receiving A 1 and A 2 ; and MRHT ( X 1 )+ MRHT ( X 2 )= A 1 +A 2 ; and
MRHT ( X 1 )+ MRHT ( X 2 )= A 1 +A 2 ; and
for X i comprising PRHT (X i )=a i0 , a i1 , . . . , a in−1 :
receiving PRHT (X 1 )=a 10 , a 11 , . . . , a 1n−1 and PRHT (X 2 )=a 20 , a 21 , . . . , a 2n−1 and C 0 , C 1 , . . . , C n−1 , C n of P(v)=Σ j=0 n C j ·v j (C n =1; and PRHT ( X 1 )+ PRHT ( X 2 )= a 10 +a 20 ,a 11 +a 21 , . . . ,a 1n−1 +a 2n−1 .
PRHT ( X 1 )+ PRHT ( X 2 )= a 10 +a 20 ,a 11 +a 21 , . . . ,a 1n−1 +a 2n−1 .
A method for multiplication of randomized X 1 and randomized X 2 , X 1 and X 2 being randomized according to the fully homomorphic method for randomizing an input of claim 1 , the method comprising: for X i comprising MRHT (X i )=A i: receiving A 1 and A 2 ; and MRHT ( X 1 )· MRHT ( X 2 )= A 1 ·A 2 ; and for X i comprising PRHT (X i )=a i0 , a i1 , . . . , a in−1 : receiving PRHT (X 1 )=a 10 , a 11 , . . . a 1n−1 and PRHT (X 2 )=a 20 , a 21 , . . . , a 2n−1 and C 0 , C 1 , . . . , C n−1 , C n of P(v)=Σ j=0 n C j ·v j (C n =1); and PRHT (X 1 )·PRHT (X 2 )=r 10 , r 11 , . . . , r 1n−1 , the coefficients of the resulting n−1 order polynomial r(v), where r(v)=((Σ j=0 n−1 a 1j ·v j )·(Σ j=0 n−1 a 2j ·v j ))mod Σ j=0 n C j ·v j .
for X i comprising MRHT (X i )=A i: receiving A 1 and A 2 ; and MRHT ( X 1 )· MRHT ( X 2 )= A 1 ·A 2 ; and
receiving A 1 and A 2 ; and MRHT ( X 1 )· MRHT ( X 2 )= A 1 ·A 2 ; and
MRHT ( X 1 )· MRHT ( X 2 )= A 1 ·A 2 ; and
for X i comprising PRHT (X i )=a i0 , a i1 , . . . , a in−1 : receiving PRHT (X 1 )=a 10 , a 11 , . . . a 1n−1 and PRHT (X 2 )=a 20 , a 21 , . . . , a 2n−1 and C 0 , C 1 , . . . , C n−1 , C n of P(v)=Σ j=0 n C j ·v j (C n =1); and
receiving PRHT (X 1 )=a 10 , a 11 , . . . a 1n−1 and PRHT (X 2 )=a 20 , a 21 , . . . , a 2n−1 and C 0 , C 1 , . . . , C n−1 , C n of P(v)=Σ j=0 n C j ·v j (C n =1); and
PRHT (X 1 )·PRHT (X 2 )=r 10 , r 11 , . . . , r 1n−1 , the coefficients of the resulting n−1 order polynomial r(v), where r(v)=((Σ j=0 n−1 a 1j ·v j )·(Σ j=0 n−1 a 2j ·v j ))mod Σ j=0 n C j ·v j .
A method for dividing of randomized X 1 and randomized X 2 , X 1 and X 2 being randomised according to the fully homomorphic method for randomizing an input of claim 1 , the method comprising: for X i comprising MRHT (X i )=A i : receiving A 1 and A 2 ; 1 /MRHT ( X 2 )= A 2 −1 and MRHT ( X 1 )/ MRHT ( X 2 )= A 1 ·A 2 −1 for X i comprising PRHT (X i )a i0 , a i1 , . . . , a in−1 : receiving PRHT (X 1 )=a 10 , a 11 , . . . , a 1n−1 and PRHT (X 2 )=a 20 , a 21 , . . . , a 2n−1 and C 0 , C 1 , . . . C n−1 , C n of P(v)=Σ j=0 n C j ·v j (C n =1); deriving 1/PRHT(X 2 )=u 20 , u 21 , . . . , u 2n−1 by calculating ((Σ j=0 n−1 u 2j ·v j )·(Σ j=0 n−1 a 2j ·v j ))mod Σ j=0 n C j ·v j =1 terms of n unknown coefficients u 2j , (j=0, . . . , n−1), thereby determining Σ j=0 n−1 g 2j (u 20 , u 21 , . . . , u 2n−1 , a 10 , a 21 , . . . , a 2n−1 , c 10 , c 21 , . . . , c 2n−1 )·v i ), wherein g 2j ( ) is a linear combination of a plurality of n unknowns u 2j ; solving n derived equations g 20 ( )=1, and g 2j ( )=0 for j=1, . . . , n−1 for all u 2j j=0, . . . , n−1; and PRHT ( X 1 )/ PRHT ( X 2 )= PRHT ( X 1 )·(1 /PRHT ( X 2 ))=Σ j=0 n−1 a 1j ·v j )·(Σ j=0 n−1 u 2j ·v j ))mod Σ j=0 n C j ·v j .
for X i comprising MRHT (X i )=A i : receiving A 1 and A 2 ; 1 /MRHT ( X 2 )= A 2 −1 and MRHT ( X 1 )/ MRHT ( X 2 )= A 1 ·A 2 −1
receiving A 1 and A 2 ; 1 /MRHT ( X 2 )= A 2 −1 and MRHT ( X 1 )/ MRHT ( X 2 )= A 1 ·A 2 −1
/MRHT ( X 2 )= A 2 −1
MRHT ( X 1 )/ MRHT ( X 2 )= A 1 ·A 2 −1
for X i comprising PRHT (X i )a i0 , a i1 , . . . , a in−1 : receiving PRHT (X 1 )=a 10 , a 11 , . . . , a 1n−1 and PRHT (X 2 )=a 20 , a 21 , . . . , a 2n−1 and C 0 , C 1 , . . . C n−1 , C n of P(v)=Σ j=0 n C j ·v j (C n =1); deriving 1/PRHT(X 2 )=u 20 , u 21 , . . . , u 2n−1 by calculating ((Σ j=0 n−1 u 2j ·v j )·(Σ j=0 n−1 a 2j ·v j ))mod Σ j=0 n C j ·v j =1 terms of n unknown coefficients u 2j , (j=0, . . . , n−1), thereby determining Σ j=0 n−1 g 2j (u 20 , u 21 , . . . , u 2n−1 , a 10 , a 21 , . . . , a 2n−1 , c 10 , c 21 , . . . , c 2n−1 )·v i ), wherein g 2j ( ) is a linear combination of a plurality of n unknowns u 2j ; solving n derived equations g 20 ( )=1, and g 2j ( )=0 for j=1, . . . , n−1 for all u 2j j=0, . . . , n−1; and PRHT ( X 1 )/ PRHT ( X 2 )= PRHT ( X 1 )·(1 /PRHT ( X 2 ))=Σ j=0 n−1 a 1j ·v j )·(Σ j=0 n−1 u 2j ·v j ))mod Σ j=0 n C j ·v j .
receiving PRHT (X 1 )=a 10 , a 11 , . . . , a 1n−1 and PRHT (X 2 )=a 20 , a 21 , . . . , a 2n−1 and C 0 , C 1 , . . . C n−1 , C n of P(v)=Σ j=0 n C j ·v j (C n =1);
deriving 1/PRHT(X 2 )=u 20 , u 21 , . . . , u 2n−1 by calculating ((Σ j=0 n−1 u 2j ·v j )·(Σ j=0 n−1 a 2j ·v j ))mod Σ j=0 n C j ·v j =1 terms of n unknown coefficients u 2j , (j=0, . . . , n−1), thereby determining Σ j=0 n−1 g 2j (u 20 , u 21 , . . . , u 2n−1 , a 10 , a 21 , . . . , a 2n−1 , c 10 , c 21 , . . . , c 2n−1 )·v i ), wherein g 2j ( ) is a linear combination of a plurality of n unknowns u 2j ;
solving n derived equations g 20 ( )=1, and g 2j ( )=0 for j=1, . . . , n−1 for all u 2j j=0, . . . , n−1; and PRHT ( X 1 )/ PRHT ( X 2 )= PRHT ( X 1 )·(1 /PRHT ( X 2 ))=Σ j=0 n−1 a 1j ·v j )·(Σ j=0 n−1 u 2j ·v j ))mod Σ j=0 n C j ·v j .
PRHT ( X 1 )/ PRHT ( X 2 )= PRHT ( X 1 )·(1 /PRHT ( X 2 ))=Σ j=0 n−1 a 1j ·v j )·(Σ j=0 n−1 u 2j ·v j ))mod Σ j=0 n C j ·v j .
The method according to claim 1 , wherein at least one of the randomized inputs comprises a cryptographic key.
The method according to claim 1 , wherein the cryptographic key comprises an AES key.
The method according to claim 1 , wherein the at least one of the randomized inputs comprises a mod N-number polynomial coefficient.
The method according to claim 9 , wherein the mod N-number polynomial coefficient is used for a Private Function Key Generation.
The method according to claim 9 , wherein the mod N-number polynomial coefficient is used for a private hash-based message authentication code.
The method according to claim 9 , wherein the mod N-number polynomial coefficient is used for generating an OSS signature.
The method according to claim 1 , wherein the input comprises a plain text, the output comprises a cipher text, and all computations are performed modulo N over a ring Z N , where N is a product of two prime numbers, and matrix S comprises symmetric encryption key, wherein the encryption functions are denoted as MEnc and PEnc correspond to MRHT and PRHT, respectively.
The method according to claim 13 , wherein the encryption of the plain text comprises a successive application of a mix of encryption functions PEnc=PRHT(X i ) and MEnc=MRHT(X i ), wherein:
MEnc î¢ ( PEnc î¢ ( X i ) ) = ( MEnc î¢ ( a i î¢ î¢ 0 ) , MEnc î¢ ( a i î¢ î¢ 1 ) , â¦ î¢ , MEnc î¢ ( a i î¢ î¢ n - 1 ) ) == ( ( a 11 â¦ a 1 î¢ î¢ n â® â± â® a n î¢ î¢ 1 â¦ a nn ) i î¢ î¢ 0 , ( a 11 â¦ a 1 î¢ î¢ n â® â± â® a n î¢ î¢ 1 â¦ a nn ) i î¢ î¢ 1 , â¦ î¢ , ( a 11 â¦ a 1 î¢ î¢ n â® â± â® a n î¢ î¢ 1 â¦ a nn ) i î¢ î¢ n - 1 ) ; and î¢ PEnc î¢ ( MEnc î¢ ( X i ) ) = PEnc î¢ ( ( a 11 â¦ a 1 î¢ î¢ n â® â± â® a n î¢ î¢ 1 â¦ a nn ) ) î¢ where î¢ PEnc î¢ ( a ij ) = ( a 0 , a 1 , â¦ î¢ , a n - 1 ) ij .
The method according to claim 3 , wherein the received output comprises a cipher text denoted C, the cipher text C being produced as an output from a plain text input and all computations are performed modulo N over a ring Z N , where N is a product of two prime numbers, and matrix S comprises symmetric encryption key, wherein the encryption functions are denoted as MEnc and PEnc correspond to MRHT and PRHT, respectively and the randomized input comprises a plain text, and all computations are performed modulo N over a ring Z N , where N is a product of two prime numbers, and matrix 5 comprises symmetric encryption key.
A method for addition of a pair of cipher text outputs Ci and Cj, Ci and Cj being cipher texts produced as an output from a plain is a product of two prime numbers, and matrix S comprises symmetric encryption to MRHT and PRHT, respectively the method comprising adding Ci and Cj according to the method of claim 4 wherein ail computations are performed modulo H over a ring Z N , where N is a product of two prime numbers, and matrix S comprises symmetric encryption key.
A method for multiplication of a pair of cipher text outputs Ci and Cj, Ci and Cj comprising cipher texts produced as an output from a plain text input and all computations are performed modulo N over a ring Z N , where N is a product of two prime numbers, and matrix S comprises and PEnc correspond to MRHT and PRHT, respectively the method comprising multiplying Ci and Cj according to the method of claim 5 , wherein all computations are performed modulo N over a ring Z N , where N is a product of two prime numbers, and matrix S comprises a symmetric encryption key.
A method for division of a pair of cipher texts outputs Ci and Cj , Ci and Cj comprising cipher texts produced as an output from a plain text input and all computations are performed modulo N over a ring Z N , where N is a product of two prime numbers, and matrix S comprises symmetric encryption key, wherein the encryption functions are denoted as MEnc and PEnc correspond to MRHT and PRHT, respectively, the method comprising dividing Ci and Cj according to the method of claim 6 wherein all computations are performed modulo N over a ring Z N , where N is a product of two prime numbers, and matrix S comprises symmetric encryption key.
A method for verifying that a returned result of a calculation performed by a third party is valid, the result being performed by the method of claim 1 , the result being denoted R* M for a result returned using an MRHT or MEnc function denoted as M, and the result being denoted R* P for a result, returned using a PRHT or PEnc function denoted as P, the result comprising a result of a homomorphic calculation denoted f performed on A 1 ,A 2 , . . . ,A k wherein A i is equal to one of M(X i ) and P(X i ); f(A 1 , A 2 , . . . , A k ) is equal to one of: M (f(X 1 , X 2 , . . . , X k ))=f(M(X 1 ), M(X 2 ), . . . , M(X k )) and P(f(X 1 , X 2 , . . . , X k ))=f(P(X 1 ), P(X 2 ), . . . , P(X k )) the method comprising: receiving the result of f(A 1 , A 2 , . . . , A k ) in the one of the forms:
receiving the result of f(A 1 , A 2 , . . . , A k ) in the one of the forms:
M î¢ ( f î¢ ( X 1 , X 2 , â¦ î¢ , X K ) ) = S î¢ ( f î¢ ( X 1 , X 2 , â¦ î¢ , X K ) î¢ î¢ â¦ 0 î¢ î¢ â¦ 0 â¦ â¦ â¦ 0 î¢ î¢ â¦ f î¢ ( Y m î¢ î¢ 1 , Y m î¢ î¢ 2 , â¦ î¢ , Y mk ) î¢ î¢ â¦ 0 â¦ â¦ â¦ 0 î¢ î¢ â¦ 0 î¢ î¢ â¦ f î¢ ( Y n - 1 , 1 , Y 
[Truncated to input limit]