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


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]