Machine learning based on homomorphic encryption

Abstract

A method for evaluating data is based on a computational model, the computational model comprising model data, a training function and a prediction function. The method includes training the computational model by: receiving training data and training result data for training the computational model, and computing the model data from the training data and the training result data with the training function. The method includes predicting result data by: receiving field data for predicting result data; and computing the result data from the field data and the model data with the prediction function. The training data may be plaintext and the training result data may be encrypted with a homomorphic encryption algorithm, wherein the model data may be computed in encrypted form from the training data and the encrypted training result data with the training function. The field data may be plaintext, wherein the result data may be computed in encrypted form from the field data and the encrypted model data with the prediction function.

Claims

1. A method for evaluating data based on a computational model, the computational model comprising model data, a training function and a prediction function, the method comprising: training the computational model by: receiving training data and training result data for training the computational model; computing the model data from the training data and the training result data with the training function; predicting result data by: receiving field data for predicting result data; and computing the result data from the field data and the model data with the prediction function; wherein, the training data is plaintext and the training result data is encrypted with a homomorphic encryption algorithm, the homomorphic encryption algorithm being additively homomorphic; the model data is computed in encrypted form from the plaintext training data and the encrypted training result data with the training function; the field data is plaintext, wherein the result data is computed in encrypted form from the plaintext field data and the encrypted model data with the prediction function, wherein two or less data types are encrypted at any given time, the datatypes including the training data, the model data, and the field data; and wherein, the computational model is a linear regression model, in which the prediction function is a linear function in the field data and the model data; wherein, the training function of the linear regression model is based on minimizing a cost function, which quadratically minimizes a difference between the prediction function and the training result data.

2. The method of claim 1, wherein the training function is a polynomial in at least one of the training data and the training result data; and wherein the prediction function is a polynomial in at least one of the field data and model data.

3. The method of claim 1, wherein each of the training data and the field data is a set of vectors or matrices of field data values; wherein each of the training result data and the result data is a vector of result data values; wherein the model data is a vector of model data values.

4. The method of claim 1, wherein, before encryption, data values are approximated by multiplication with an approximation factor and rounding to a closest integer; and wherein the homomorphic encryption algorithm is based on a finite field based on the product of two prime numbers and the approximation factor is smaller than this product.

5. The method of claim 1, wherein the training function for computing the model data is iteratively updated with the training data and the training result data; wherein in each iteration, the training function is evaluated in an evaluation server device, the updated model data is sent to a secure device, decrypted, multiplied with a convergence factor and encrypted in the secure device and sent back to the evaluation server device.

6. The method of claim 1, wherein at least one of the training data and the training result data is provided by a client device communicatively interconnected with an evaluation server device, wherein the client device encrypts at least one of the training data and the training result data and decrypts the result data and wherein the evaluation server device at least partially computes at least one of the model data and the result data; and wherein the field data is provided by at least one or a plurality of devices communicatively interconnected with the evaluation server device.

7. The method of claim 1, wherein the training data and the field data encodes at least one of local wind speed and local sunshine intensity and the training result data and the result data encodes at least one of electrical power production of wind turbine facilities and solar energy facilities.

8. A method for evaluating data based on a computational model, the computational model comprising model data, a training function and a prediction function, the method comprising: training the computational model by: receiving training data and training result data for training the computational model; computing the model data from the training data and the training result data with the training function; predicting result data by: receiving field data for predicting result data; and computing the result data from the field data and the model data with the prediction function; wherein, the training data and the training result data are encrypted with a homomorphic encryption algorithm, the homomorphic encryption algorithm being additively homomorphic; the model data is computed in plaintext from encrypted training data and the encrypted training result data with the training function; the field data is encrypted with homomorphic encryption algorithm, wherein the result data is computed in encrypted form from the encrypted field data and the plaintext model data with the prediction function, wherein two or less data types are encrypted at any given time, the data types including the training data, the model data, and the field data; and wherein, the computational model is a linear regression model, in which the prediction function is a linear function in the field data and the model data; wherein, the training function of the linear regression model is based on minimizing a cost function, which quadratically minimizes a difference between the prediction function and the training result data.

9. The method of claim 8, wherein the training function is a polynomial in at least one of the training data and the training result data; and wherein the prediction function is a polynomial in at least one of the field data and model data.

10. The method of claim 8, wherein each of the training data and the field data is a set of vectors or matrices of field data values, wherein each of the training result data and the result data is a vector of result data values; wherein the model data is a vector of model data values.

11. The method of claim 8, wherein, before encryption, data values are approximated by multiplication with an approximation factor and rounding to a closest integer; and wherein the homomorphic encryption algorithm is based on a finite field based on the product of two prime numbers and the approximation factor is smaller than this product.

12. The method of claim 8, wherein the training function for computing the model data is iteratively updated with the training data and the training result data; wherein in each iteration, the training function is evaluated in an evaluation server device, the updated model data is sent to a secure device, decrypted, multiplied with a convergence factor and encrypted in the secure device and sent back to the evaluation server device.

13. The method of claim 8, wherein at least one of the training data and the training result data is provided by a client device communicatively interconnected with an evaluation server device, wherein the client device encrypts at least one of the training data and the training result data and decrypts the result data and wherein the evaluation server device at least partially computes at least one of the model data and the result data; and wherein the field data is provided by at least one or a plurality of devices communicatively interconnected with the evaluation server device.

14. A computer-readable medium executing a computer program for evaluating data based on a computational model, the computational model comprising model data, a training function and a prediction function, which, when executed on an evaluation system, comprises: training the computational model by: receiving training data and training result data for training the computational model; computing the model data from the training data and the training result data with the training function; predicting result data by: receiving field data for predicting result data; and computing the result data from the field data and the model data with the prediction function; wherein, the training data is plaintext and the training result data is encrypted with a homomorphic encryption algorithm, the homomorphic encryption algorithm being additively homomorphic; the model data is computed in encrypted form from the plaintext training data and the encrypted training result data with the training function; the field data is plaintext, wherein the result data is computed in encrypted form from the plaintext field data and the encrypted model data with the prediction function, wherein two or less data types are encrypted at any given time, the data types including the training data, the model data, and the field data; and wherein, the computational model is a linear regression model, in which the prediction function is a linear function in the field data and the model data; wherein, the training function of the linear regression model is based on minimizing a cost function, which quadratically minimizes a difference between the prediction function and the training result data.

15. An evaluation system for evaluating data based on a computational model, the computational model comprising model data, a training function and a prediction function, which when the computational model is executed on the evaluation system, the system operable to: train the computational model by: receive training data and training result data for training the computational model; compute the model data from the training data and the training result data with the training function; predict result data by: receive field data for predicting result data; and compute the result data from the field data and the model data with the prediction function; wherein, the training data is plaintext and the training result data is encrypted with a homomorphic encryption algorithm, the homomorphic encryption algorithm being additively homomorphic; the model data is computed in encrypted form from the plaintext training data and the encrypted training result data with the training function; the field data is plaintext, wherein the result data is computed in encrypted form from the plaintext field data and the encrypted model data with the prediction function, wherein two or less data types are encrypted at any given time, the data types including the training data, the model data, and the field data; and wherein, the computational model is a linear regression model, in which the prediction function is a linear function in the field data and the model data; wherein, the training function of the linear regression model is based on minimizing a cost function, which quadratically minimizes a difference between the prediction function and the training result data.

16. An evaluation system for evaluation data based on a computational model, the computational model comprising model data, a training function and a prediction function, which when the computational model is executed on the evaluation system, the system operable to: train the computational model by: receive training data and training result data for training the computational model; compute the model data from the training data and the training result data with the training function; predict result data by: receive field data for predicting result data; and compute the result data from the field data and the model data with the prediction function; wherein, the training data and the training result data are encrypted with a homomorphic encryption algorithm, the homomorphic encryption algorithm being additively homomorphic; the model data is computed in plaintext from the encrypted training data and the encrypted training result data with the training function; the field data is encrypted with the homomorphic encryption algorithm, wherein the result data is computed in encrypted form from the encrypted field data and the plaintext model data with the prediction function, wherein two or less data types are encrypted at any given time, the data types including the training data, the model data, and the field data; and wherein, the computational model is a linear regression model, in which the prediction function is a linear function in the field data and the model data; wherein, the training function of the linear regression model is based on minimizing a cost function, which quadratically minimizes a difference between the prediction function and the training result data.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The subject-matter of the invention will be explained in more detail in the following text with reference to exemplary embodiments which are illustrated in the attached drawings.

(2) FIG. 1 schematically shows a system evaluation system according to an embodiment of the invention and illustrates a method for evaluating data based on a computational model system according to an embodiment of the invention.

(3) FIG. 2 schematically shows a system evaluation system according to a further embodiment of the invention and illustrates a method for evaluating data based on a computational model system according to a further embodiment of the invention.

(4) The reference symbols used in the drawings, and their meanings, are listed in summary form in the list of reference symbols. In principle, identical parts are provided with the same reference symbols in the figures.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

(5) FIG. 1 and FIG. 2 show an evaluation system 10 comprising a server device 12, which may be a cloud computing facility. The system 10 furthermore comprises several computing devices 14, 16, 18 and 20, which are communicatively interconnected with the server device 12, for example via Internet. The arrows in FIG. 1 illustrate method steps that will be described in more detail below. The direction of these arrows illustrates a possible data flow between the server device 12 and the computing devices 16, 18, 20.

(6) The training device 14 may be adapted for encrypting data with a homomorphic encryption algorithm, for example based on the Paillier encryption scheme, and may be adapted for sending plaintext, i.e. unencrypted, data and encrypted data to the server device 12.

(7) In a first method step S12, the training device 14 sends training data 22 and training result data 24 to the server device 12, which trains a computational model by receiving the training data 22 and training result data 24 and by computing model data 26 from the training data 22 and the training result 24 data with a training function.

(8) The computational model may comprise the model data 26, the training function used during a training phase and a prediction function used during a prediction phase of the method.

(9) On the server device 12, no data is encrypted and decrypted. Only homomorphic operations compatible with the homomorphic encryption scheme are applied to the data 22, 24, 26.

(10) The evaluation system 10 may comprise a secure device 16, which is adapted for encrypting and decrypting data with the homomorphic encryption algorithm. The term “secure” refers to the fact that the server device 12 needs not be secured with respect to third parties, i.e. it needs not be protected from an illegal access of third parties, which are interested in reading information from the data. Contrary to the server device 12, the devices 14, 16, 18 may be seen as “secure”, since they may store and/or process confidential data in plaintext form.

(11) During the step S12, when the server device 12 computes the model data 26, this may be performed iteratively and the server device 12 may send partial results in a step S14 to the secure device 16, which decrypts the partial results, performs calculations with the partial results, encrypts the calculation results and sends them back to the server device 12. It has to be noted that most of the calculations, such as more than 95% or more than 99%, may be performed in the server device 12 and only the rest may be performed by the secure device 16.

(12) The secure device 16 and the training device 14 may be provided by the same computational hardware.

(13) Step S12 and S14 refer to a training phase of the computational model. After the training phase, model data 26 may be stored, in for example encrypted or decrypted form, in the server device 12.

(14) The evaluation system 10 also may comprise one or more field devices 20, which are adapted for sending field data 28 to the server device 12. The field data may be encrypted or in plaintext, in the first case, the one or more field devices 20 may be adapted for encrypting field data 28 with the homomorphic encryption algorithm.

(15) In step S16, the one or more field devices 20 send the field data 28 to the server device, which predicts result data 30 by receiving field data 28 and computing the result data 30 from the field data 28 and the model data with the prediction function.

(16) In step S18, the result data 30 is sent from the server device 12 to a beneficiary device 18, which is adapted for decrypting the result data 30, which then may be further processed. The beneficiary device 18 may be provided by the same computational hardware as the training device 14 and/or the secure device 16.

(17) In both of the systems 10 of FIG. 1 and FIG. 2, only a part of the data 22, 24, 26, 28, 30 is encrypted to save computational power.

(18) In FIG. 1, the training data 22 is plaintext and the training result data 24 is encrypted with the homomorphic encryption algorithm, wherein the model data 26 is computed in encrypted form from the training data 22 and the encrypted training result data 24 with the training function. Furthermore, the field data 28 is plaintext, wherein the result data 30 is computed in encrypted form from the field data 28 and the encrypted model data 26 with the prediction function.

(19) In the training phase, i.e. step S12 and optionally S14 encrypted model data 26 is computed in the server device 12 based on unencrypted, non-critical training data 22, which may be old field data, and encrypted, confidential training result data 24, which corresponds to the training data 22. In the prediction phase, i.e. steps S16 and S18, new field data 28 is sent to the server device 12, for example from arbitrary devices 20 at arbitrary locations. The server device 12 uses the encrypted model data 26 to compute encrypted predictions/result data 30 based on the new field data 28.

(20) In FIG. 2, the training data 22 and the training result data 24 are encrypted with the homomorphic encryption algorithm, wherein the model data 26 is computed in plaintext from the encrypted training data 22 and the encrypted training result data 24 with the training function. Furthermore, the field data 28 is encrypted with the homomorphic encryption algorithm, wherein the result data 30 is computed in encrypted form from the encrypted field data 28 and the plaintext model data 26 with the prediction function.

(21) The method and system of FIG. 1 is more suitable when the training data 22 and/or field data 28 is confidential as well. The model data 26 of the training phase, however, is not encrypted. This may not be a security issue as the computed parameters in the model data 26 only may make sense with respect to the encrypted data 22, 24 or 28, 30. Furthermore, the provider of the server device 12 cannot abuse its knowledge of the model data 26 because it cannot decrypt the result data 30.

(22) In both FIGS. 1 and 2, the result data 30 may be sent to the client 18, where they may be decrypted and consumed, for example archived, displayed, or further processed.

(23) Typically, the training phase may be much more expensive in computational power. The model data 26 may be obtained once and then used several times. It also may be possible that new model data 26 is obtained periodically.

(24) By only encrypting two out of the three parts, input data 22, 28, model data 26 and output data 24, 30 substantial performance improvements are possible, which enable practical privacy-preserving model data 26 and result data 30 computations for remote service applications. For the computations in the server device 12, a homomorphic encryption scheme can be used that usually only offers a small set of operations that can be carried out on encrypted data. However, these operations suffice to compute model data 26 and result data 30 as shown in the following.

(25) If all three parts were encrypted, much more expensive, for example fully homomorphic encryption schemes may have to be used, degrading performance to the point where remote computation of model data 26 and result data 30 may become impractical.

(26) In the following, an embodiment to linear regression as computational model is described that may be generalized to other computational models based on model data 26, a training function and a prediction function.

(27) The Computational Model

(28) As already mentioned, the computational model comprises model data 26, a training function ƒ and a prediction function g.

(29) During the training phase, i.e. steps S12, S14, the model data 26 is fitted to the training data 22 and the training result data 24 according to the training function ƒ. The training data 22 may comprise m samples, where each sample i contains a vector x.sup.(i) of n features/data values. The training data 22, as well as the field data 28, may be seen as independent variables. The training result data 24, as well as the result data 30, may comprise m scalars y.sup.(i), which also may be seen as a vector and/or may constitute the dependent variable. Let X and y denote the matrix and the vector of all independent and dependent variables, respectively. Then the model data 26 may be provided by a vector θ may be computed in the training phase by θ=ƒ(X,y).

(30) During the training phase, i.e. steps S14, S16, the model data 26, θ is computed from known X and y, to predict the dependent variable for new independent variables. The field data 28 and the result data 30 may have the same format as the data 22, 24 and also may be denoted by X and y. Then, the result data 30, y may be computed through the prediction function g based on the vector X of independent variables and the model data θ:y=g(x,θ).

(31) In general, the method may be performed when the functions ƒ and g are or can be approximated by a bounded-degree polynomial.

(32) In order to ensure that the server device 12 learns as little as possible during the course of the computation, data is encrypted before being transmitted. Note that when using asymmetric cryptography, only the secure device 16 and/or the beneficiary device 18 needs access to a secret key. The devices 14 and 20 solely may use a public key for encryption.

(33) The homomorphic encryption scheme used in the following will be additively homomorphic, i.e., sums can be computed on encrypted values directly without access to the decryption key. Formally, let [v].sub.k denote the encrypted value corresponding to the plaintext value v encrypted with key k. An encryption scheme may be called additively homomorphic if there is an operator ⊕ such that [v.sub.1].sub.k ⊕[v.sub.2].sub.k is an encryption of v.sub.1+v.sub.2 for any key k and values v.sub.1 and v.sub.2. Note that there may be many valid encrypted values corresponding to the same plaintext value so it may not be assumed that [v.sub.1].sub.k⊕[v.sub.2].sub.k=[v.sub.1+v.sub.2].sub.k. Since it is always clear from the context which key is used, we omit the index and simply write [v].

(34) Furthermore, the homomorphic encryption scheme may be homomorphic multiplicative with respect to multiplication of an encrypted value with a plaintext value, resulting in an encryption of the product of the encrypted value and the plaintext value.

(35) Several known additively homomorphic encryption schemes, such as Paillier, support these operations. In the following, homomorphic operators are used implicitly whenever at least one operand is encrypted, e.g., [v.sub.1]+[v.sub.2] and v.sub.1[v.sub.2] denote the homomorphic addition, where both terms are encrypted, and multiplication, where one of the terms is encrypted, respectively.

(36) Linear Regression

(37) Linear regression may be seen as a method to compute model data 26, θ representing a best-fit linear relation between the training data 22, x.sup.(i) and training result data 24, y.sup.(i), resulting in x.sup.(i).Math.θ=y.sup.(i)+e.sup.(i) for all i∈{1, . . . , m}, where e.sup.(i) are error terms and the operation on the left-hand side denotes a scalar product. The model data 26, θ should minimize the cost function

(38) $J\left(\theta \right):=\frac{1}{2m}\underset{i=1}{\overset{m}{.Math.}}{\left(x^{\left(i\right)}.Math.\theta -y^{\left(i\right)}\right)}^2.$
The model data, θ can then be used to predict result data 30, y from field data 28, i.e. vectors x, matrix X, that are obtained later by computing the prediction function y=g(x,θ)=x.Math.θ.

(39) Several approaches may be used to compute the model data 26, θ in such a way that the cost function J(θ) is minimized.

(40) In one approach, the normal equation θ=(X.sup.T X).sup.−1X.sup.T y=My is solved. In this approach, the matrix (X.sup.T X) has to be inverted on the server device 12.

(41) Another approach is called gradient descent. In the gradient descent-based approach, the model data 26, θ is updated iteratively, using the derivative of the cost function J(θ), until the cost function J(θ) converges to a small value as follows:

(42) $\begin{array}{cc}{\theta }_j:={\theta }_j-\alpha \frac{\partial J}{\partial {\theta }_j}={\theta }_j-\alpha \frac{1}{m}\underset{i=1}{\overset{m}{.Math.}}\left(x^{\left(i\right)}.Math.\theta -y^{\left(i\right)}\right)x_j^{\left(i\right)}& \left(1\right)\end{array}$

(43) The parameter a influences the rate of convergence. The approach with normal equation requires the inversion of an n×n-matrix. Therefore, gradient descent can be significantly faster when the number of features/data values is large.

(44) Approximation

(45) For all calculations having nearly the same precision, data values should have a similar scale. It my be assumed that the numerical data values in the data 22, 24, 26, 28, 30 are normalized, i.e., the mean μ is shifted to 0 and all values are scaled to be in the range [−1,1]. The normalization may be performed by setting

(46) $x_i\leftarrow \frac{x_i-\mu }{\max \left\{x_{\max }-\mu ,\mu -x_{\min }\right\}}$
for all i∈{1, . . . m}, where x.sub.max and x.sub.min are the bonds of the data values.

(47) This feature scaling and fractional numbers in general may pose a problem when working with encrypted data 22, 24, 26, 28 as most homomorphic encryption schemes operate on integers in a finite field, for example based on the product of two large prime numbers.

(48) Thus, the normalized data values may be transformed into fixed-point numbers before they are encrypted and processed. In an approximation step, each normalized data value may be multiplied with a large approximation factor and then rounded to the closest integer, before encrypting the data values. The magnitude of the approximation factor may have an impact on the achievable precision.

(49) The approximation step may be denoted by
{circumflex over (x)}:=approximate(x,λ),

(50) where x is the independent variable, such as training data 22 and field data 26, λ is the approximation factor that is multiplied with x, and {circumflex over (x)} is the rounded result. The loss in precision may become negligible when the approximation factor λ is large enough.

(51) Training Phase: Encrypted Model Data 26, θ and Encrypted Training Result Data 24, y Using Gradient Descent

(52) In this case, in step S12, the training device 14 may send the training data 22, for example as matrix X, in plaintext and the corresponding training result data 24, for example as vector y, in encrypted approximate form ([ŷ]) to the server device 12. Thus, the training device 14 may send mn plaintext values and m encrypted values. The server device 12 then may apply equation (1) iteratively on the data 22, 24. To this end, server device 12 may perform the approximation for X.sup.T X and X.sup.T:
M:=approximate(X.sup.TX,λ)
T:=approximate(X.sup.T,λ)

(53) Subsequently, the server device 12 may compute a correction factor [r.sub.1]:=M[θ.sub.0]−T[ŷ], where the initial model data θ.sub.0 may be set to a suitable starting vector in encrypted form. For example, this may be an initial model data θ.sub.0 already stored in the server device 12 or may be sent from the training device 14 to the server device 12.

(54) In step S14, the server device 12 may send the correction factor [r.sub.1] to the secure device 16, which decrypts it, applies the multiplication with a convergence factor α/m, encrypts it and sends back the result. This operation may be assigned to the secure device 16, since the convergence factor α/m is a number close to zero, if there are many samples, and thus the precision loss by carrying out this multiplication on the server device 12 may be significant.

(55) The computation of the correction factor [r.sub.i]:=M[θ.sub.i-1]−T[ŷ] by the server device 12, the multiplication by the convergence factor d.sub.i=α/mr.sub.i by the secure device 16 and the calculation of the next model data 26 by [θ.sub.i]:=[θ.sub.i-1]−[r.sub.i] by the server device 12 may be repeated K times, where K may be a fixed value and/or may be repeated until the secure device 16 decides that the value of the difference of the actual correction factor and the last correction factor is smaller than a threshold value.

(56) In each iteration, 2n encrypted values are transmitted from the server device 12 to the secure device 16 and back. Thus, O(Kn) encrypted values are exchanged during gradient descent. Overall, the server device 12 must perform O(Kmn) homomorphic operations and O(Kn) operations on plaintext, whereas the secure device 16 carries out O(Kn) plaintext, encryption, and decryption operations.

(57) Training Phase: Encrypted Model Data 26, θ and Encrypted Training Result Data 24, y Using Normal Equation

(58) As already mentioned, another approach is to solve the normal equation on the server device 12 directly. No interaction with a secure device 16 may be necessary after receiving the training data 22, for example as matrix X, in plaintext and the corresponding training result data 24, for example as vector y, in encrypted approximate form ([ŷ]) in the server device 12.

(59) Given the training data 22, X and the approximation factor λ, S first computes (X.sup.T X).sup.−1 X.sup.T and applies the subroutine approximate: A:=approximate((X.sup.TX).sup.−1 X.sup.T, λ).

(60) The server device then uses the matrix A together with [ŷ] to compute [θ]:[θ]:=A[ŷ].

(61) Overall, O(mn.sup.2+n.sup.2373) plaintext operations are performed to compute A. The second term is the complexity of inverting X.sup.TX for optimized variants of the Coppersmith-Winograd algorithm.

(62) For problems with a large number of features, the inversion can be computed by other methods, e.g., with LU decompositions. In addition, O(nm) homomorphic operations, i.e. additions of encrypted values and multiplications of encrypted values with plaintext values, are needed to compute [θ]. If n is relatively small, e.g., 1000 or less, the homomorphic operations are likely to dominate the computational complexity as they may be typically several orders of magnitude slower than equivalent operations in the plaintext domain.

(63) Training Phase: Encrypted Model Data 26, θ and Encrypted Training Result Data 24, y Using Normal Equation with Preprocessing

(64) A third approach is also based on solving the normal equation but reduces the number of homomorphic operations on the server device 12 for the case when the number of samples m is greater than the number of features n.

(65) This reduction is achieved by preprocessing the training data 22, X and the training result data 24, y by the training device 14 as follows. As before, the training device 14 sends the matrix X to the server device 12. However, instead of sending the decrypted training result data 24, [ŷ] directly, the training device 24 sends preprocessed and encrypted training result data 24, [{circumflex over (b)}.sub.i] to the server device 12.

(66) In particular, the training device 24 computes b.sub.i:=X.sup.(i).sup.T y.sup.(i), where X.sup.(i) denotes the i.sup.th row of X, and transmits [{circumflex over (b)}.sub.i] for each i∈{1, . . . , m} to the server device 12.

(67) Then, the server device 12 computes A:=approximate((X.sup.T X).sup.−1, λ). Next, the server device 12, homomorphically sums up the vectors [{circumflex over (b)}.sub.i] for all i∈{1, . . . , m} which yields the encrypted vector [{circumflex over (b)}], where b=X.sup.T y: [{circumflex over (b)}]:=Σ.sub.i=1.sup.m[{circumflex over (b)}.sub.i].

(68) Finally, the model data 24, θ is computed by multiplying A and [{circumflex over (b)}] homomorphically: [θ]:=A[{circumflex over (b)}].

(69) If m>n, the advantage of the present approach as opposed to the previous approach is that the number of homomorphic multiplications on the server device 12 may be reduced from O(nm) to O(n.sup.2). Conversely, the training device 14 may have to perform O(nm) additional operations to compute the vectors of the preprocessed training result data 24, [{circumflex over (b)}.sub.1], . . . , [{circumflex over (b)}.sub.m]. In addition to transmitting the plaintext matrix X the training device 14 also sends these mn-dimensional vectors, i.e., O(mn) values in total.

(70) Since each vector [{circumflex over (b)}.sub.i] of training result data 24 may be sent individually, the method of the present approach may be performed by multiple clients as training device 14. If there is only one client that holds the training data 22, X and the training result data 24, y locally, the method may be optimized: The training device 14 computes b=X.sup.Ty directly and sends [{circumflex over (b)}] to the server device 12. In this case, the client must only encrypt {circumflex over (b)}, i.e., n values in total, in contrast to encrypting all vectors {circumflex over (b)}.sub.i, which requires the encryption of nm values. Moreover, S would not have to compute [{circumflex over (b)}].

(71) Training Phase: Encrypted Training Data 22, X and Encrypted Training Result Data 24, y Using Gradient Descent

(72) With respect to FIG. 2, the training data 22, X and training result data 24, y are encrypted and the model data θ is computed in plaintext.

(73) Solving the normal equation directly involves the multiplication of values of training data 22, X and the training result data 24, y, which may not be possible using an only additively homomorphic encryption scheme. Gradient descent may not be used directly either because X.sup.T must be multiplied with terms containing X and y.

(74) However, gradient descent may be used when the training device 14 performs some preprocessing on the data 22, 24: For each sample i, the training device 14 prepares a vector [{circumflex over (b)}.sub.i], where b.sub.i=X.sup.(i).sup.Ty.sup.(i), and matrix [Â.sub.i], where A.sub.i=x.sup.(i).sup.Tx.sup.(i), and transmits them to the server device 12.

(75) As above, the initial model data 26, θ.sub.0 may be set to a suitable starting vector. In order to support values smaller than 1 in the model data 26, θ.sub.0 may be scaled by λ.

(76) The server device 12 then sums up all received encrypted vectors [{circumflex over (b)}.sub.i] and multiplies the sum with λ homomorphically, resulting in the encrypted vector [{circumflex over (b)}]. The encrypted matrices [Â.sub.i] are also summed up by the server device 12 homomorphically, which yields the encrypted matrix [Â].

(77) Vector [{circumflex over (b)}] and matrix [Â] are used in each iteration i as follows: The server device 12 sends [r.sub.i]:=[Â]θ.sub.i-1−[{circumflex over (b)}] to the secure device 16, where it is decrypted and multiplied with α/m before being converted again to an integer using approximate. The result {circumflex over (d)}.sub.i is encrypted and sent back to the server device 12. The updated model data 26, θ.sub.i is computed by subtracting [{circumflex over (d)}.sub.1] from θ.sub.i-1.

(78) Again, due to the homomorphic property of the encryption scheme, we have that

(79) $\begin{array}{cc}\hat{A}=\underset{i=1}{\overset{m}{.Math.}}{\hat{A}}_i\simeq \lambda \underset{i=1}{\overset{m}{.Math.}}{A}_i=\lambda X^{T}X& \left(2\right)\\ \hat{b}=\lambda \underset{i=1}{\overset{m}{.Math.}}{\hat{b}}_i\simeq {\lambda }^2\underset{i=1}{\overset{m}{.Math.}}{b}_i={\lambda }^2{X}^{T}y,\mathrm{and}\mathrm{thus}{r}_i^{\prime }\simeq \frac{1}{{\lambda }^2}{r}_i=\frac{1}{{\lambda }^2}\left(\hat{A}{\theta }_{i-1}-\hat{b}\right)\stackrel{\left(2\right),\left(3\right)}{\simeq }{X}^{T}X{\theta }_{i-1}-X^{T}y,& \left(3\right)\end{array}$

(80) where r.sub.i denotes the correct difference between the two terms on the right-hand side. Hence, the algorithm implements gradient descent correctly.

(81) As far as the computational complexity is concerned, the server device 12 carries out O(mn.sup.2+Kn.sup.2) homomorphic additions and O(Kn.sup.2) homomorphic multiplications. At the beginning, the training device 14 sends m(n.sup.2+n) encrypted values. 2n encrypted values are exchanged in each iteration with the secure device 16, which has to decrypt them, carry out a multiplication, and encrypt them again before sending them back to the server device 12. Thus, O(mn.sup.2+Kn) values are exchanged in total.

(82) Prediction Phase

(83) In both cases, having computed the model data 26, the second task is to predict the result data 30, y given field data 28, x.

(84) With respect to FIG. 1, the field data 28, x is not encrypted and the model data 26, θ is encrypted. The server device 12 may then compute encrypted result data 30 by computing [y]=g(x,[θ])=x[θ], where only multiplications with a plaintext factor have to be computed.

(85) With respect to FIG. 2, the field data 28, x is encrypted and the model data 26, θ is not encrypted. The server device 12 may then compute encrypted result data 30 by computing [y]=g([x],θ)=[x]θ, where again only multiplications with a plaintext factor have to be computed.

(86) In both scenarios, the server device 12 needs O(n) homomorphic operations to compute the result data 30.

(87) While the invention has been illustrated and described in detail in the drawings and foregoing description, such illustration and description are to be considered illustrative or exemplary and not restrictive; the invention is not limited to the disclosed embodiments. Other variations to the disclosed embodiments can be understood and effected by those skilled in the art and practising the claimed invention, from a study of the drawings, the disclosure, and the appended claims. In the claims, the word “comprising” does not exclude other elements or steps, and the indefinite article “a” or “an” does not exclude a plurality. A single processor or controller or other unit may fulfil the functions of several items recited in the claims. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage. Any reference signs in the claims should not be construed as limiting the scope.

LIST OF REFERENCE SYMBOLS

(88) 10 evaluation system 12 server device 14 training device 16 secure device 18 beneficiary device 20 field device 22 training data 24 training result data 26 model data 28 field data 30 result data