CRYPTOGRAPHIC METHOD, SYSTEMS AND SERVICES FOR EVALUATING UNIVARIATE OR MULTIVARIATE REAL-VALUED FUNCTIONS ON ENCRYPTED DATA

Abstract

The invention relates to a cryptographic method and variants thereof based on homomorphic encryption enabling the evaluation of univariate or multivariate real-valued functions on encrypted data, in order to allow carrying out homomorphic processing on encrypted data more broadly and efficiently.

Claims

1. A cryptographic method executed in a digital form by at least one information processing system specifically programmed to perform the approximate homomorphic evaluation of a univariate function ƒ of a real variable x with an arbitrary accuracy in a domain of definition and with a real value in an image , taking as input the ciphertext of an encoding of x, E(encode(x)), and returning the ciphertext of an encoding of an approximate value of ƒ(x), E′(encode′(y)) with y≈ƒ(x), where E and E′ are homomorphic encryption algorithms the respective native space of the cleartexts thereof is and ′, parameterised by: an integer N≤1 quantifying the actual accuracy of the representation of the variables at the input of the function ƒ to be evaluated, an encoding function encode taking as input an element of the domain and associating thereto an element of , an encoding function encode taking as input an element of the image and associating thereto an element of , a discretisation function discretise taking as input an element of and associating thereto an index represented by an integer, a homomorphic encryption scheme having an encryption algorithm ε.sub.H the native space of the cleartexts of which .sub.H has a cardinality of at least N, an encoding function encode.sub.H taking as input an integer and returning an element of .sub.H, so that the image of the domain by the encodingencode followed by the discretisation discretise, (discretise∘encode)(), is a set of at most N indices selected from ={0, . . . , N−1}, and characterised by: a. a step of pre-calculating a table corresponding to said univariate function ƒ, consisting in decomposing the domain into N selected sub-intervals R.sub.0, . . . , R.sub.N−1 whose union makes up for each index i in ={0, N−1}, determining a representativex(i) in the sub-interval R.sub.i and calculating the value y(i)=ƒ(x(i)) returning the table T consisting of the N components T[0], . . . , T[N−1], with T[i]=y(i) for 0≤i≤N−1 b. a step of homomorphic evaluation of the table consisting in converting the ciphertext E(encode(x)) into the ciphertext ε.sub.H(encode.sub.H(ĩ) for an integer ĩ having as an expected value the index i =(discretise∘encode)(x) in the set ={0, . . . , N−1}if x ∈ R.sub.i obtaining the ciphertext E′ (encode′(T[ĩ]){tilde over ( )}) for an element encode′(T[ĩ]){tilde over ( )} having as an expected value encode′(T[ĩ]), based on the ciphertext ε.sub.H(encode.sub.H(ĩ)) and the table T returning E′ (encode′(T [ĩ]){tilde over ( )}).

2. The cryptographic method according to claim 1, wherein the domain of definition of the function ƒ to be evaluated is given by the real interval =[x.sub.min, x.sub.max), the N intervals R.sub.i (for 0≤i≤N−1) covering the domain are the semi-open sub-intervals $R_i=[\frac{i}{N}\left(x_{\max }-x_{\min }\right)+x_{\min },\frac{i+1}{N}\left(x_{\max }-x_{\min }\right)+x_{\min }),$ splitting in a regular manner.

3. The cryptographic method according to claim 1, wherein the set is a subset of the additive group for an integer M≤N.

4. The cryptographic method according to claim 3, wherein the group is represented in a multiplicative manner as the powers of a M-th primitive root of the unit denoted X, so that to the element i of is associated the element X.sup.i; all of the M-th roots of the unit {1, X, . . . , X.sup.M−1} forming a group isomorphic with for the multiplication modulo (X.sup.M−1).

5. The cryptographic method according to claim 1, wherein the homomorphic encryption algorithm E is given by an LWE-type encryption algorithm applied to the torus =/ and has as a native space of the cleartexts =.

6. The cryptographic method according to claim 5, parameterised by an integer M≤N wherein the encoding function encode has its image contained in the sub-interval $[0,\frac{N}{M}-\frac{1}{2M})$ of the torus, and the discretisation function discretise applies an element t of the torus to the rounded integer of the product M×t modulo M, where M33 t is calculated in ; in mathematical form: discretise: .fwdarw.discretise(t)=┌M×t┘ mod M.

7. The cryptographic method according to claim 6, wherein the when the domain of definition of the function ƒ is the real interval D=[x.sub.min, x.sub.max), the encoding function encode is $\mathrm{encode}:[x_{\min },x_{\max }).fwdarw.[0,\frac{N}{M}-\frac{1}{2M},$ $x\mapsto \mathrm{encode}\left(x\right)=\frac{2N-1}{2M}\frac{x-x_{\min }}{x_{\max }-x_{\min }}.$

8. The cryptographic method according to claim 5, wherein the homomorphic encryption algorithm ε.sub.H is an LWE-type encryption algorithm and the encoding function encode.sub.H is the identity function.

9. The cryptographic method according to claim 5, parameterised by an even integer M wherein the homomorphic encryption algorithm ε.sub.H is an RLWE-type encryption algorithm and the encoding function encode.sub.H is the function ${\mathrm{encode}}_H:{\mathbb{Z}}_M.fwdarw.{𝕋}_{\frac{M}{2}}\left[X\right],i\mapsto {\mathrm{encode}}_H\left(i\right)=X^{-i}.Math.p\left(X\right)$ for an arbitrary polynomial p of .sub.M/2[X].

10. The cryptographic method according to claim 8, parameterised by an even integer M equal to 2N, wherein an LWE-type ciphertext E′ (encode′(T[ĩ])) on the torus is extracted from an RLWE ciphertext approaching the polynomial X.sup.—ĩ.Math.q(X) ∈.sub.N[X], with q(X)=T′[0]+T′[1]X +. . . +T′[N−1]X.sup.N−1=Σ.sub.j=0.sup.N−1T′[j]X.sup.j in .sub.N[X] and where T′[j]=encode′(T[j]), 0≤j≤N−1.

11. The cryptographic method according to claim 1, wherein, when the image of the function ƒ is the real interval =[y.sub.min, y.sub.max), the homomorphic encryption algorithm E′is given by an LWE-type encryption algorithm applied to the torus =/ and has as a native space of the cleartexts ′=, the encoding function encode′ is ${\mathrm{encode}}^{\prime }:[y_{\min },y_{\max }).fwdarw.𝕋,y\mapsto {\mathrm{encode}}^{\prime }\left(y\right)=\frac{y-y_{\min }}{y_{\max }-y_{\min }}$

12. The cryptographic method according to claim 1, wherein the at least one univariate function subjected to said approximate homomorphic evaluation is derived from a prior processing of at least one multivariate function by implementing the following prior steps: a. a pre-calculation step consisting in transforming each of said multivariate functions into a network of univariate functions, consisting of compositions of univariate real-valued functions and sums, b. a pre-selection step consisting in identifying in said networks of pre-calculated univariate functions the redundancies of one of the three types: the same univariate functions applied to the same arguments, different univariate functions applied to the same arguments, the same univariate functions applied to arguments differing by a non-zero additive constant and selecting all or part thereof c. a step of homomorphic evaluation of each of the networks of pre-calculated univariate functions, wherein when all or part of one or more of these univariate functions is reused the redundancies selected in the pre-selection step are evaluated in a shared manner.

13. The cryptographic method according to claim 1, characterised in that the input encrypted data are derived from a prior re-encryption step so as to be set in the form of ciphertexts of encryptions of said homomorphic encryption algorithm E.

14. An information processing system characterised in that it is programmed to implement a homomorphic evaluation cryptographic method according to claim 1.

15. A computer program intended to be loaded and implemented by an information processing system according to claim 14.

16. A cloud computing type remote service implementing a cryptographic method according to claim 1 wherein the tasks are shared between a data holder and one or more third-parties acting as digital processing service providers.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0038] The invention allows carrying out, digitally by at least one specifically programmed information processing system, the evaluation, on encrypted data, of one or more function(s) with one or more real-valued variables f.sub.1, . . . , f.sub.q, each of the functions taking as input a plurality of real variables from among the real variables x.sub.1, . . . , x.sub.p.

[0039] When at least one of said functions takes as input at least two variables, a method according to the invention schematically comprises three steps: [0040] 1. a so-called pre-calculation step consisting in transforming each of said multivariate functions into a network of univariate functions, composed of sums and compositions of univariate real-valued functions, [0041] 2. a so-called pre-selection step consisting in identifying, in said pre-calculated univariate function networks, redundancies of different types and in selecting all or part of them, [0042] 3. a so-called step of homomorphic evaluation of each of the pre-calculated networks of univariate functions, in which the redundancies selected in the pre-selection step are evaluated in an optimised manner.

[0043] As regards the second step (pre-selection), the selection of all or part of the redundancies is primarily yet not exclusively guided by the objective of optimising the digital processing of the homomorphic evaluation, whether gain in terms of computation time or for availability reasons such as memory resources for storing intermediate computation values.

[0044] [FIG. 1] schematically replicates the first two steps as they are implemented according to the invention by a computer system programmed to this end.

[0045] Thus, in one of the embodiments of the invention, the evaluation of one or more multivariate real-valued functions ƒ.sub.1, . . . , ƒ.sub.q, each of the functions taking as input a plurality of real variables from among the variables x.sub.1, . . . , x.sub.p, and at least one of said functions taking as input at least two variables, taking as input the ciphertexts of the encryptions of each of the inputs x.sub.1, E(encode(x.sub.i)) with 1≤i≤p, and returning the plurality of ciphertexts of the encryptions of f.sub.1, . . . , f.sub.q applied to their respective inputs, where E is a homomorphic encryption algorithm and encode is an encoding function that associates to each of the reals x.sub.i an element of the native space of the cleartexts of E, may be characterised by: [0046] 1. a pre-calculation step consisting in transforming each of said multivariate functions into a network of univariate functions, composed of sums and compositions of univariate real-valued functions, [0047] 2. a pre-selection step consisting in identifying in said networks of pre-calculated univariate functions the redundancies of one of the three types [0048] a. the same univariate functions applied to the same arguments, [0049] b. different univariate functions applied to the same arguments, [0050] c. the same univariate functions applied to arguments differing by a non-zero additive constant, [0051] and selecting all or part thereof, [0052] 3. a step of homomorphic evaluation of each of the pre-calculated networks of univariate functions, in which the redundancies selected in the pre-selection step are evaluated in an optimised manner

[0053] As regards the pre-calculation step, an explicit version of Kolmogorov superposition theorem allows confirming that any continuous function ƒ:I.sup.p.fwdarw., defined on the identity hypercube I.sup.p=[0,1].sup.p with the dimension p, can be written as sums and compositions of univariate continuous functions:

[00001]$f\left(x_1,.Math.,x_p\right)=\underset{k=0}{\overset{2p}{.Math.}}{g}_k\left(\xi \left(x_1+\mathrm{ka},.Math.,x_p+ka\right)\right)$

with

[00002]$\xi \left(x_1+\mathrm{ka},.Math.,x_p+ka\right)=\underset{i=1}{\overset{p}{.Math.}}{\lambda }_i\Psi \left(x_i+ka\right)$

where, with a given number p of variables, the μ.sub.i and a are constants, and ψ is a continuous function. In other words

[00003]$f\left(x_1,.Math.,x_p\right)=\underset{k=0}{\overset{2p}{.Math.}}{g}_k\left(\underset{i=1}{\overset{p}{.Math.}}{\lambda }_i\Psi \left(x_i+ka\right)\right).$

[0054] As example, [FIG. 2] illustrates the case p=2.

[0055] The functions ψ and ξ are so-called “internal” and are independent of ƒ for a given arity. The function ψ associates, to any component x.sub.i of the real vector (x.sub.1, . . . , x.sub.p) of I.sup.p, a value in [0,1]. The function ξ allows associating, to each vector (x.sub.1, . . . , x.sub.p) ∈ I.sup.p the numbers z.sub.k=Σ.sub.i=1.sup.pλ.sub.i ψ (x.sub.i+ka) in the interval [0,1]which will then serve as arguments to the functions g.sub.k to rebuild the function ƒ by summing. It should be noted that the restriction of the domain of ƒ to the hypercube I.sup.p in Kolmogorov theorem is usually done in the scientific literature to simplify explanation thereof. However, it is obvious that this theorem naturally extends to any parallelepiped with a dimensionp by homothety.

[0056] Sprecher proposed an algorithm for the determination of internal and external functions in [David A. Sprecher, “A numerical implementation of Kolmogorovs superpositions”, Neural Networks, 9(5), pp. 765-772, 1996] and [David A. Sprecher, “A numerical implementation of Kolmogorovs superpositions II”, Neural Networks, 10(3), pp. 447-457, 1997], respectively. Instead of the function ψ initially defined by Sprecher to build ξ (which is discontinuous for some input values), it is possible to use the function ψ defined in [Jürgen Braun and Michael Griebel, “On a constructive proof of Kolmogorovs superposition theorem”, Constructive Approximation, 30(3), pp. 653-675, 2007].

[0057] Once the internal functions ψ and ξ have been fixed, it remains to determine the external functions g.sub.k (which depend on the function ƒ). For this purpose, Sprecher proposes the construction—for each k, 0≤k≤2p—of r functions g.sub.k.sup.r whose sum converges towards the external function g.sub.k. At the end of r.sup.—th step, the result of the approximation of ƒ is given in the following form:

[00004]$f\left(x_1,.Math.,x_p\right)\approx \underset{k=0}{\overset{K}{.Math.}}\underset{j=1}{\overset{r}{.Math.}}{g}_k^j.Math.\xi \left(x_1+\mathrm{ka},.Math.,x_p+\mathrm{ka}\right),$

where K is a parameter such that K≥2p. Thus, the algorithm provides an approximate result with respect to that of Kolmogorov decomposition theorem. Indeed, by taking r quite great, and by assuming g.sub.k=Σ.sub.j=1.sup.rg.sub.k.sup.j, the next approximate representation for the function ƒ is obtained:

[00005]$f\left(x_1,.Math.,x_p\right)\approx \underset{k=0}{\overset{K}{.Math.}}{g}_k.Math.\xi \left(x_1+\mathrm{ka},.Math.,x_p+\mathrm{ka}\right),$

or still

[00006]$f\left(x_1,.Math.,x_p\right)\approx \underset{k=0}{\overset{K}{.Math.}}{g}_k\left(\underset{i=1}{\overset{p}{.Math.}}{\lambda }_i\Psi \left(x_i+ka\right)\right).$

[0058] Thus, in one of the embodiments of the invention, the pre-calculation phase may be characterised in that for at least one function ƒ.sub.j from among ƒ.sub.1, . . . , ƒ.sub.q, the transformation of the pre-calculation step is an approximate transformation in the form ƒ.sub.j (x.sub.j.sub.i, . . . , x.sub.j.sub.t)≈Σ.sub.k=0.sup.k(Σ.sub.i=1.sup.tλ.sub.j.sub.iψ(x.sub.j.sub.i+ka)) with t≤p and j.sub.1, . . . , j.sub.t ∈ {1, . . . , p}, and where ψ is a univariate function defined on reals and with real value, where the λ.sub.j.sub.i are real constants and where the g.sub.k are univariate functions defined on reals and with real value, said functions g.sub.k being determined as a function of ƒ.sub.j, for a given parameter K.

[0059] Another technique for decomposing a multivariate function ƒ (x.sub.1, . . . , x.sub.p) consists in approximating it with a sum of so-called ridge functions, according to the transform

[00007]$f\left(x_1,.Math.,x_p\right)\approx \underset{k=0}{\overset{K}{.Math.}}{g}_k\left(\underset{i=1}{\overset{p}{.Math.}}{a}_{i,k}{x}_i\right),$

where the coefficients a.sub.i,k are real numbers and where the g.sub.k are univariate functions defined on the reals and with real value, said functions g.sub.k and said coefficients a.sub.i,k being determined as a function of ƒ.sub.j, for a given parameter K.

[0060] The decomposition is then approximate in the general case, and aims to identify the best approximation, or an approximation with enough quality. This approximation appears in the literature devoted to statistical optimisation as projection pursuit. As mentioned before, a noticeable result is that any function ƒ can be approximated in this manner with arbitrarily high accuracy. In practice, however, it is common that ƒ admits an exact decomposition, i.e. it is expressed analytically in the form of a sum of ridge functions for all or part of its inputs. When a function ƒ.sub.j takes as input a subset of t variables of {x.sub.1, . . . , x.sub.p} with t≤p, if these variables are denoted x.sub.j.sub.1, . . . , x.sub.j.sub.t with j.sub.1, . . . , j.sub.t ∈ {1, . . . , p}, then the previous ridge decomposition is written

[00008]$f_j\left(x_{j_1},.Math.,x_{j_t}\right)\approx \underset{k=0}{\overset{K}{.Math.}}{g}_k\left(\underset{i=1}{\overset{t}{.Math.}}{a}_{i,k}{x}_{j_i}\right)$

with x=(x.sub.j.sub.1, . . . , x.sub.j.sub.t) and a.sub.k=(a.sub.1,k, . . ., a.sub.t,k), for functions g.sub.k and coefficients a.sub.i,k determined as a function of ƒ.sub.j, for a given parameter K.

[0061] Thus, in one of the embodiments of the invention, the pre-calculation phase may be characterised in that, for at least one function ƒ.sub.j from among ƒ.sub.1, . . . , ƒ.sub.q, the transformation of the pre-calculation step is an approximate transformation in the form ƒ.sub.j(x.sub.j.sub.1, . . . , x.sub.j.sub.t)≈Σ.sub.k=0.sup.k (Σ.sub.i=1.sup.ta.sub.i,k x.sub.j.sub.i) with t≤p and j.sub.1, . . . , j.sub.t ∈ {1, . . . , p}, and where the coefficients a.sub.i,k are real numbers and where the g.sub.k are univariate functions defined on the reals and with real value, said functions g.sub.k and said coefficients a.sub.i,k being determined as a function of ƒ.sub.j, for a given parameter K.

[0062] A similar decomposition technique, using the same statistical optimisation tools, applies by taking the radial functions rather than the ridge functions, according to

[00009]$f\left(x_1,.Math.,x_p\right)\approx \underset{k=0}{\overset{K}{.Math.}}{g}_k\left(.Math.x-a_k.Math.\right)$

with x=(x.sub.1, . . . , x.sub.p), a.sub.k=(a.sub.1,k, . . . , a.sub.p,k) and where the vectors a.sub.k have as coefficients a.sub.i,k real numbers and where the g.sub.k are univariate functions defined on the reals and with real value, said functions g.sub.k and said coefficients a.sub.i,k being determined as a function of ƒ, for a given parameter K and a given norm ∥.Math.∥. Usually, the Euclidean norm is used.

[0063] When a function ƒ.sub.j takes as input a subset of t variables of {x.sub.1, . . . , x.sub.p}with t≤p, if one denotes x.sub.j.sub.1, . . . , x.sub.j.sub.t these variables with j.sub.1, . . . , j.sub.t ∈ {1, . . . , p}, then the previous decomposition is written

[00010]$f_j\left(x_{j_1},.Math.,x_{j_t}\right)\approx \underset{k=0}{\overset{K}{.Math.}}{g}_k\left(.Math.x-a_k.Math.\right)$

with x=(x.sub.j.sub.1, . . . , x.sub.j.sub.t) and a.sub.k=(a.sub.1,k, . . . , a.sub.t,k), for functions g.sub.k and coefficients a.sub.i,k determined as a function of ƒ.sub.j, for a given parameter K.

[0064] Thus, in one of the embodiments of the invention, the pre-calculation phase may be characterised in that for at least one function ƒ.sub.j from among ƒ.sub.1, . . . , ƒ.sub.q, the transformation of the pre-calculation step is an approximate transformation in the form ƒ.sub.j (x.sub.j.sub.1, . . . , x.sub.j.sub.t)≈∈ .sub.k=0.sup.kg.sub.k(∥x−a.sub.k∥) with x=(x.sub.j.sub.1, . . . , x.sub.j.sub.t), a.sub.k=(a.sub.1,k, . . . , a.sub.t,k) t≤p and j.sub.1, . . . , j.sub.t ∈ {1, . . . , p}, and where the vectors a.sub.k have as coefficients a.sub.i,k real numbers and where the g.sub.k are univariate functions defined on the reals and with a real value, said functions g.sub.k and said coefficients a.sub.i,k being determined as a function of ƒ.sub.j, for a given parameter K and a given norm ∥.Math.∥.

[0065] As indicated in the aforementioned Pinkus's article, another important class of decomposition of functions is when the coefficients a.sub.i,k are fixed, the functions g.sub.k are the variables. This class applies to decomposition both in the form of ridge functions and in the form of radial functions. Several methods are known for solving this problem, under the name: Von Neumann algorithm, cyclic coordinate algorithm, Schwarz domain decomposition method, Diliberto-Straus algorithm, as well as variants that are found in the literature dedicated to tomography; cf. this same Pinkus's article and the references therein.

[0066] Thus, in one of the particular embodiments of the invention, this pre-calculation phase is further characterised in that the coefficients a.sub.i,k are fixed.

[0067] In some cases, the transformation of the pre-calculation step may be performed exactly by means of an equivalent formal representation of multivariate functions.

[0068] Consider g a multivariate function. If this function g calculates the maximum of z.sub.1 and z.sub.2, g(z.sub.1, z.sub.2)=max(z.sub.1, z.sub.2), it can use the formal equivalence max(z.sub.1, z.sub.2)=z.sub.2+(z.sub.1−z.sub.2).sup.+, where zz.sup.+ corresponds to the univariate function zmax(z, 0). The use of this formal equivalence allows easily obtaining other formal equivalences for the function max(z.sub.1, z.sub.2). As example, since (z.sub.1−z.sub.2).sup.+ can be expressed in an equivalent manner as

[00011]${\left(z_1-z_2\right)}^{+}=\frac{1}{2}\left(z_1-z_2\right)+\frac{1}{2}.Math.z_1-z_2.Math.,$

the formal equivalence max(z.sub.1, z.sub.2)=(z.sub.1+z.sub.2+|z.sub.1−z.sub.2|)/2 is obtained where z|z| is the univariate function “absolute value”and where zz/2 is the univariate function “division by 2”

[0069] In general, for three variables or more z.sub.1, . . . , z.sub.m, given that

max(z.sub.1, . . . , z.sub.i, z.sub.i+1, . . . , z.sub.m)=max(max(z.sub.1, . . . , z.sub.i), max(z.sub.i+1, . . . , z.sub.m))

for any i meeting 1≤i≤m−1, max(z.sub.1, z.sub.m) is thus obtained iteratively as a combination of sums and functions |.Math.| (absolute value) or (.Math.).sup.+.

[0070] Thus, in one of the embodiments of the invention, the pre-calculation phase may be characterised in that the transformation of this pre-calculation step uses the formal equivalence max(z.sub.1, z.sub.2)=z.sub.2+(z.sub.1−z.sub.2).sup.+ to express the function (z.sub.1, z.sub.2) max(z.sub.1, z.sub.2) as a combination of sums and compositions of univariate functions.

[0071] In a particular embodiment of the invention, this pre-calculation phase is further characterised in that the formal equivalence is obtained from the iteration of the formal equivalence for two variables, for said function when the latter includes three variables or more.

[0072] Similarly, for the “minimum” function, g(z.sub.1, z.sub.2)=min(z.sub.1, z.sub.2), it is possible to use the formal equivalence min(z.sub.1, z.sub.2)=z.sub.2+(z.sub.1−z.sub.2).sup.− where zz.sup.−=min(z, 0), or else min(z.sub.1, z)=(z.sub.1+z.sub.2−|z.sub.1−z.sub.2|)/2 because (z.sub.1−z.sub.2).sup.−=½(z.sub.1−z.sub.2)−½|z.sub.1−z.sub.2|, which, by iterating, generally allows formally decomposing the m-variate function min(z.sub.1, . . . , z.sub.m) as a combination of sums and univariate functions, by observing that min(z.sub.1, . . . , z.sub.i, z.sub.i+1, . . . , z.sub.m)=min(min(z.sub.1, . . . , z.sub.i), min(z.sub.i+1, . . . , z.sub.m)).

[0073] Thus, in one of the embodiments of the invention, the pre-calculation phase may be characterised in that the transformation of this pre-calculation step uses the formal equivalence min(z.sub.1, z.sub.2)=z.sub.2+(z.sub.1−z.sub.2).sup.− to express the function (z.sub.1, z.sub.2)min(z.sub.1, z.sub.2) as a combination of sums and compositions of univariate functions.

[0074] In a particular embodiment of the invention, this pre-calculation phase is further characterised in that the formal equivalence is obtained from the iteration of the formal equivalence for two variables, for said function when the latter includes three variables or more.

[0075] Another very useful multivariate function that can be simply formally decomposed into a combination of sums and compositions of univariate functions is multiplication. A first embodiment is to use for g(z.sub.1, z.sub.2)=z.sub.1×z.sub.2 the formal equivalence z.sub.1×z.sub.2=(z.sub.1+z.sub.2).sup.2/4−(z.sub.1−z.sub.2).sup.2/4, involving the univariate function zz.sup.2/4. Of course, the use of a formal equivalence gives other formal equivalences. Thus, as example, by using z.sub.1×z.sub.2=(z.sub.1+z.sub.2).sup.2/4−(z.sub.1−z.sub.2).sup.2/4, z.sub.1×z.sub.2=(z.sub.1+z.sub.2).sup.2/4 −(z.sub.1−z.sub.2).sup.2/4+(z.sub.1+z.sub.2).sup.2/4−(z.sub.1+z.sub.2).sup.2/4=(z.sub.1+z.sub.2).sup.2/2−(z.sub.1−z.sub.2).sup.2/4−(z.sub.1+z.sub.2).sup.2/4=(z.sub.1+z.sub.2).sup.2/2−z.sub.1.sup.2/2z.sub.2.sup.2/2 is deduced; i.e., the formal equivalence z.sub.1×z.sub.2=(z.sub.1+z.sub.2).sup.2/2−z.sub.1.sup.2/2−z.sub.2.sup.2/2, involving the univariate function zz.sup.2/2.

[0076] Thus, in one of the embodiments of the invention, the pre-calculation phase may be characterised in that the transformation of this pre-calculation step uses the formal equivalence z.sub.1×z.sub.2=(z.sub.1+z.sub.2).sup.2/4−(z.sub.1−z.sub.2).sup.2/4 to express the function (z.sub.1, z.sub.2)z.sub.1 ×z.sub.2 as a combination of sums and compositions of univariate functions.

[0077] These embodiments are generalised to m-variate functions for m≤3 by observing that z.sub.1×. . . ×z.sub.i×z.sub.i+1×. . . ×z.sub.m=(z.sub.1×. . . ×z.sub.i)×(z.sub.i+1×. . . ×z.sub.m) with 1≤i≤m−1.

[0078] In a particular embodiment of the invention, this pre-calculation phase is further characterised in that the formal equivalence is obtained from the iteration of the formal equivalence for two variables, for said function when the latter includes three variables or more.

[0079] A second embodiment is to decompose g(z.sub.1, z.sub.2)=|z.sub.1×z.sub.2|=|z.sub.1|×z.sub.2| as |z.sub.1×z.sub.2|=exp(ln|z.sub.1|+lnÅz.sub.2|), involving the univariate functions zln|z| and zexp(z); or else, for an arbitrary base B, such as |z.sub.1×z.sub.2|=B.sup.log.sup.B.sup.|z.sup.1.sup.|+log.sup.B.sup.|z.sup.2.sup.| because

[00012]$\exp \left(\ln .Math.z_1.Math.+\ln .Math.z_2.Math.\right)=\exp \left(\frac{{\log }_B.Math.z_1.Math.}{{\log }_{B}e}+\frac{{\log }_B.Math.z_1.Math.}{{\log }_{B}e}\right)=e^{\frac{1}{{\log }_{B}e}\left({\log }_B.Math.z_1.Math.+{\log }_B.Math.z_2.Math.\right)}=B^{{\log }_B.Math.z_1.Math.+{\log }_B.Math.z_2.Math.}$

where e=exp(1), involving the univariate functions zlog.sub.B|z| and zB.sup.2. Herein again, these embodiments are generalised to m-variate functions for m≥3 while observing that z.sub.1×. . . ×z.sub.i×z.sub.i+1×. . . ×z.sub.m|=|z.sub.1×. . . ×z.sub.i|×|z.sub.i+1×. . . ×z.sub.m| with 1≤i≤m−1.

[0080] Thus, in one of the embodiments of the invention, the pre-calculation phase may be characterised in that the transformation of this pre-calculation step uses the formal equivalence |z.sub.1×z.sub.2|=exp (ln|z.sub.1|+ln|z.sub.2|) to express the function (z.sub.1, z.sub.2)|z.sub.1×z.sub.2| as a combination of sums and compositions of univariate functions.

[0081] In a particular embodiment of the invention, this pre-calculation phase is further characterised in that the formal equivalence is obtained from the iteration of the formal equivalence for two variables, for said function when the latter includes three variables or more.

[0082] As described before, the multivariate function(s) given as input are transformed into a network of multivariate functions. Such a network is not necessarily unique, even in the case where the transformation is exact.

[0083] As example, we have seen hereinabove at least two decompositions of the multivariate function max(x.sub.1, x.sub.2), namely max(x.sub.1, x.sub.2)=x.sub.2+(x.sub.1−x.sub.2).sup.+ and max(x.sub.1, x.sub.2)=(x.sub.1+x.sub.2+|x.sub.1−x.sub.2|)/2. Specifically, each of these transformations may proceed in detail as follows [0084] 1. max(x.sub.1, x.sub.2)=x.sub.2+(x.sub.1−x.sub.2).sup.+ [0085] assume z.sub.1=x.sub.1−x.sub.2 and define g.sub.1(z)=z.sup.+ [0086] write max (x.sub.1, x.sub.2)=x.sub.2+g.sub.1(z.sub.1) [0087] 2. max(x.sub.1, x.sub.2)=(x.sub.1+x.sub.2+|x.sub.1−x.sub.2|)/2 [0088] assume z.sub.1=x.sub.1−x.sub.2 and z.sub.2=x.sub.1+x.sub.2 [0089] define g.sub.1(z)=|z| and g.sub.2(z)=z/2 [0090] write max(x.sub.1, x.sub.2)=g.sub.2(z.sub.3) with z.sub.3=z.sub.2+g.sub.1(z.sub.1)

[0091] In general, two types of operations are observed in a network of univariate functions: sums and evaluations of univariate functions. When the evaluation of the network is done homomorphically on encrypted values, the most expensive operations are the evaluations of the univariate functions because this typically gives rise to a bootstrapping step. Consequently, it is interesting to produce networks of univariate functions minimizing these univariate function evaluation operations.

[0092] In the previous example, one can therefore see that the first transformation for the “maximum”function [max(x.sub.1, x.sub.2)=x.sub.2+(x.sub.1−x.sub.2).sup.+] seems to be more advantageous since it only requires one univariate function evaluation, namely that of the function g.sub.1(z)=z.sup.+. In practice, the difference is not noticeable because the second univariate function in the second transformation does not really need to be evaluated: all it needs is to return 2max(x.sub.1, x.sub.2)=x.sub.1+x.sub.2+|x.sub.1−x.sub.2| or else to integrate this factor into the decoding function at the output. In general, the univariate functions consisting in multiplying by a constant can be ignored (i) by calculating a multiple of the starting function, or (ii) by “absorbing”by composition the constant when these functions are at the input of another univariate function. For example, the multivariate function sin(max(x.sub.1, x.sub.2)) may be written as [0093] 1. sin(max(x.sub.1,x.sub.2))=sin(x.sub.2+(x.sub.1−x.sub.2).sup.+) [0094] assume z.sub.1=x.sub.1−x.sub.2 and define g.sub.1(z)=z.sup.+ [0095] define g.sub.2(z)=sin(z) [0096] 2. write sin(max(x.sub.1,x.sub.2))=g.sub.2(z.sub.2) with z.sub.2=x.sub.2+g.sub.1(z.sub.1) [0097] sin(max(x.sub.1,x.sub.2))=sin((x.sub.1+x.sub.2+|x.sub.1−x.sub.2|)/2) [0098] assume z.sub.1=x.sub.1−x.sub.2 and z.sub.2=x.sub.1+x.sub.2 [0099] define g.sub.1(z)=|z| and g.sub.2(z)=sin(z/2) [0100] 3. write sin(max(x.sub.1,x.sub.2))=g.sub.2(z.sub.3) with z.sub.3=z.sub.2+g.sub.1(z.sub.1)
(the multiplication by ½ being “absorbed”by the function g.sub.2(z)=sin(z/2) in the second case).

[0101] Apart from the univariate functions of the type g (z)=z +a (addition of a constant a) or of the type g(z)=az (multiplication by a constant a), other situations may give rise to faster evaluations of univariate functions.

[0102] {g.sub.k(z.sub.i.sub.k)}.sub.k denotes the set of univariate functions with their respective argument (z.sub.i.sub.k∈) resulting from the transformation of ƒ.sub.1, . . . , ƒ.sub.q at the pre-calculation step some univariate functions g.sub.k may be the same.

[0103] Three types of optimisations are considered:

[0104] 1) The Same Function, the Same Argument:

[0105] g.sub.k=g.sub.k, and z.sub.i.sub.k=z.sub.i.sub.k, (Type 1). This optimisation is obvious. It consists in reusing results from previous calculations. Thus, if there is k′<k such that g.sub.k′(z.sub.i.sub.k′) has already been evaluated and for which g.sub.k′(z.sub.i.sub.k′)=g.sub.k(z.sub.i.sub.k), the value of g.sub.k(z.sub.i.sub.k) must not be recalculated.

[0106] 2) Different Function, the Same Argument:

[0107] g.sub.k≠g.sub.k, and z.sub.i.sub.k=z.sub.i.sub.k′(Type 2). In some cases, the cost of the homomorphic evaluation of two or more univariate function(s) on the same argument may be less than the sum of the costs of these functions considered separately. Typically, a single bootstrapping step is required. In this case, amongst two networks of univariate functions including the same number of univariate functions of the type g.sub.k(z.sub.i.sub.k), within multiplicity tolerances, it is advantageous to prefer that one sharing a maximum of arguments.

[0108] An example illustrates this situation very well. Consider the homomorphic evaluation of the multivariate function ƒ (x.sub.1,x.sub.2)=max(x.sub.1,x.sub.2)+|x.sub.1×x.sub.2|. Two possible embodiments of networks are [0109] a. max(x.sub.1,x.sub.2)+|x.sub.1×x.sub.2|=x.sub.2+(x.sub.1−x.sub.2).sup.++exp(ln|x.sub.1|+ln|x.sub.2|) [0110] assume z.sub.1=x.sub.1−x.sub.2 and define g.sub.1(z)=z.sup.+ [0111] define g.sub.2(z)=ln|z| and g.sub.3(z)=exp(z) [0112] write max (x.sub.1,x.sub.2)+|x.sub.1×x.sub.2|=x.sub.2+g.sub.1(z.sub.1)+g.sub.3(z.sub.2) with z.sub.2=g.sub.2(x.sub.1)+g.sub.2(x.sub.2) [0113] b. max(x.sub.1,x.sub.2)+|x.sub.1×x.sub.2|=x.sub.2+(x.sub.1−x.sub.2).sup.++|(x.sub.1+x.sub.2).sup.2/4−(x.sub.1−x.sub.2).sup.2/4| [0114] assume z.sub.1=x.sub.1−x.sub.2 and define g.sub.1(z)=z.sup.+ [0115] assume z.sub.2=x.sub.1+x.sub.2 and define g.sub.2(z)=z.sub.2/4 and g.sub.3(z)=|z| [0116] write max (x.sub.1,x.sub.2)+|x.sub.1×x.sub.2|=x.sub.2+g.sub.1(z.sub.1)+g.sub.3(z.sub.3) with z.sub.3=g.sub.2(z.sub.2)−g.sub.2(z.sub.1).

[0117] The two embodiments hereinabove include four univariate function evaluations. However, the second one includes two univariate functions on the same argument, namely g.sub.1(z.sub.1) and g.sub.2(z.sub.1) is therefore preferred.

[0118] Sharing of the univariate functions on the same argument is not limited to the transformations performed by means of an equivalent formal representation. This also applies to digital transformations. It should be recalled that a function defined on a parallelepiped of .sub.P can be transformed into a network of univariate functions. In particular, for a function ƒ with p variables x.sub.1, . . . , x.sub.p, Sprecher's algorithm allows obtaining an approximation of the function ƒ having the following form:

[00013]$f\left(x_1,.Math.,x_p\right)\approx \underset{k=0}{\overset{K}{.Math.}}{g}_k\left(\xi \left(x_1+\mathrm{ka},.Math.,x_p+\mathrm{ka}\right)\right)$

with ξ(x.sub.1+ka, . . . , x.sub.p+ka)=Σ.sub.i=1.sup.pλ.sub.i ψ(x.sub.i+ka).

[0119] In this construction, the so-called “internal”functions ψ and ξ do not depend on ƒ, for a given domain of definition. Consequently, if several multivariate functions ƒ.sub.1, . . . , ƒ.sub.q defined on the same domain were homomorphically evaluated, the homomorphic evaluations of the functions ψ and ξ do not need to be recalculated when they apply on the same inputs. This situation also appears for example in the decomposition of several multivariate functions using ridge functions or radial functions, when the coefficients (a.sub.i.sub.k) of the decompositions are fixed.

[0120] 3) The Same Function, Arguments Differing by an Additive Constant:

[0121] g.sub.k=g.sub.k′ and z.sub.i.sub.k=z.sub.i.sub.k′+a.sub.k for a known constant a.sub.k≠0 (Type 3). Another situation allowing accelerating the calculations is when the same univariate function is applied to arguments differing by an additive constant.

[0122] For example, still in Sprechers construction, the homomorphic evaluation of ƒ hereinabove involves several homomorphic evaluations of the same univariate function ψ on variables differing additively by a constant value, namely x.sub.i+ka for 1≤i≤p and where ka is known. In this case, the value of the encryption of ψ (x.sub.i+ka) for 1≤k≤K can be obtained efficiently from the encryption of ψ (x.sub.i); an embodiment is detailed hereinbelow.

[0123] In formal terms, in all of the univariate functions with their respective argument, {g.sub.k(z.sub.i.sub.k)}.sub.k, resulting from the transformation of ƒ.sub.1, . . . , ƒ.sub.q at the pre-calculation step, an element g.sub.k(z.sub.i.sub.k) meeting one of the three conditions is called “redundancy” [0124] 1. g.sub.k=g.sub.k′ and z.sub.i.sub.k=z.sub.i.sub.k′ [0125] 2. g.sub.k≠g.sub.k′ and z.sub.i.sub.k=z.sub.i.sub.k′ [0126] 3. g.sub.k=g.sub.k′ and z.sub.i.sub.k=z.sub.i.sub.k′+a.sub.k for a known constant a.sub.k≠0
for an index k′<k.

[0127] As illustrated in [FIG. 3], in the case of any univariate function ƒ of a real-valued variable with an arbitrary accuracy in a domain of definition and with real value in an image ,

ƒ:.Math..fwdarw..Math.xƒ(x),

a method according to the invention uses two homomorphic encryption algorithms, denoted E and E′. The native spaces of the cleartexts of which are denoted and ′, respectively. The method is parameterised by an integer N≥1 which quantifies the so-called actual accuracy of the inputs on which the function ƒ is evaluated. Indeed, although the inputs of the domain of definition of the function ƒ may have an arbitrary accuracy, these will be represented internally by at most N selected values. This has the direct consequence that the function ƒ will be represented by a maximum of N possible values. The method is also parametrised by encoding functions encode and encode′, where encode takes as input an element of and associates thereto an element of and encode takes as input an element of and associates thereto an element of . The method is parameterised by a so-called discretisation function discretise which takes as input an element of and associates thereto an integer. The encodingencode and discretisation discretise functions are such that the image of the domain by the encoding encode followed by the discretisation discretise, (discretise o encode) (), or a set of at most N indices taken from among ={0, . . . , N−1}. Finally, the method is parameterised by a homomorphic encryption scheme having an encryption algorithm ε.sub.H the native space of the cleartexts of which .sub.H has a cardinality of at least N, as well as an encoding function encode.sub.H which takes as input an integer and returns an element of .sub.H. In this case, the method comprises the following steps: [0128] A pre-calculation step in which the discretisation of said function ƒ and the construction of a table T corresponding to this discretised function ƒ are carried out. [0129] In a detailed manner, the domain of the function is decomposed into N sub-intervals R.sub.0, . . . , R.sub.N−1, the union of which is equal to . For each index i ∈{0, . . . , N−1}, a representative x(i) ∈ R.sub.i is selected and y(i)=ƒ(x(i)) is calculated. The table T consisting of the N components T[0], . . . , T[N−1] is returned, with T[i]=y(i) for 0≤i≤N−1. [0130] A step of so-called homomorphic evaluation of the table in which, given the ciphertext of an encryption of x, E(encode(x)), for a real value x∈ D where the function encode encodes x as an element of , the ciphertext E(encode(x)) is converted into the ciphertext ε.sub.H(encode.sub.H(ĩ)) for an integer ĩ having as an expected value the index i with i=(discretise∘encode)(x) in the set {0, . . . , N−1} if x ∈ R.sub.i. Starting from the ciphertext ε.sub.H(encode.sub.H(ĩ) and from the table T, the ciphertext E′ (encode′ (T [ĩ]){tilde over ( )}) is obtained for an element encode′ (T[ĩ]){tilde over ( )} having, as an expected value encode′ (T[ĩ]) with T[ĩ]=y(ĩ) and where y(ĩ)≈ƒ(x). The cipheretext E′ (encode(T[ĩ]){tilde over ( )}) is returned as the ciphertext of an encryption of an approximate value of ƒ(x).

[0131] Thus, in one of its embodiments, the invention covers the approximate homomorphic evaluation, performed digitally by a specifically programmed information processing system, of a univariate function ƒ of a real-valued variable x with an arbitrary accuracy in a domain of definition D and with real value in an image I, taking as input the ciphertext of an encryption of x, E(encode(x)), and returning the ciphertext of an encryption of an approximate value of ƒ(x), E′ (encode′ (y)), with y≈ƒ(x), where E and E′ are homomorphic encryption algorithms whose respective native space of the cleartexts is M and M′, which evaluation is parameterised by: [0132] an integer N≥1 quantifying the actual accuracy of the representation of the variables at the input of the function ƒ to be evaluated, [0133] an encoding function encode taking as input an element of the domain and associating thereto an element of , [0134] an encoding function encode taking as input an element of the image and associating thereto an element of , [0135] a discretisation function discretise taking as input an element of and associating thereto an index represented by an integer, [0136] a homomorphic encryption scheme having an encryption algorithm ε.sub.H the native space of the cleartexts of which .sub.H has a cardinality of at least N, [0137] an encoding function encode.sub.H taking as input an integer and returning an element of .sub.H,
so that the image of the domain by the encoding encode followed by the discretisation discretise, (discretise∘encode) (), is a set of at most N indices selected from ={0, . . . , N−1},

[0138] With these parameters, said approximate homomorphic evaluation of a univariate function ƒ requires the implementation of the two successive following steps by the specifically programmed information processing computer system: [0139] 1. a step of pre-calculating a table corresponding to said univariate function ƒ, consisting in [0140] a. decomposing the domain into N chosen subintervals R.sub.0, . . . , R.sub.N−1 the union of which is , [0141] b. for each index i in ={0, . . . , N−1}, determining a representative x(i) in the sub-interval R.sub.i and calculating the value y(i)=ƒ(x(i)), [0142] c. returning the table T consisting of the N components T[0], . . . , T[N−1], with T[i]=y(i) for 0≤i≤N−1; [0143] 2. a step of homomorphic evaluation of the table consisting in [0144] a. converting the ciphertext E (encode (x)) into the ciphertext ε.sub.H(encode.sub.H(ĩ) for an integer ĩ having as an expected value the index i=(discretise∘encode) (x) in the set ={0, . . . , N−1} if x ∈ R.sub.i, [0145] b. obtaining the ciphertext E′ (encode′ (T[ĩ]){tilde over ( )}) for an element encode′ (T [ĩ]){tilde over ( )} having as an expected value encode′(T[ĩ]), starting from the ciphertext ε.sub.H(encode.sub.H(ĩ) and from the table T, [0146] c. returning E′ (encode′(T[ĩ]){tilde over ( )}).

[0147] When the domain of definition of the function ƒ to be evaluated is the real interval [x.sub.min, x.sub.max), the N sub-intervals R.sub.i (for 0≤i≤N−1) covering can be chosen as the semi-open intervals

[00014]$R_i=[\frac{i}{N}\left(x_{\max }-x_{\min }\right)+x_{\min },\frac{i+1}{N}\left(x_{\max }-x_{\min }\right)+x_{\min })$

splitting regularly. Several choices are possible for the representative x:=x(i) of the interval R.sub.i. For example, it is possible to consider the midpoint of each interval, which is given by

[00015]$x\left(i\right)=\left(x_{\max }-x_{\min }\right)\frac{2i+1}{2N}+x_{\min }\in R_i$

(with 0≤i≤N−1). Another choice is to select for x(i) a value in R.sub.i such that ƒ(x(i)) is close to the average of ƒ(x) over the interval R.sub.i, or else to an average weighted by a given prior distribution of the x over the interval R.sub.i for each 0≤i≤N−1, or to the median value.

[0148] Thus, in one of the embodiments of the invention, the approximate homomorphic evaluation of the univariate function ƒ is further characterised in that [0149] the domain of definition of the function ƒ to be evaluated is given by the real interval =[x.sub.min, x.sub.max), [0150] the N intervals R.sub.i (for 0≤i≤N−1) covering the domain are the semi-open sub-intervals

[00016]$R_i=[\frac{i}{N}\left(x_{\max }-x_{\min }\right)+x_{\min },\frac{i+1}{N}\left(x_{\max }-x_{\min }\right)+x_{\min }),$

splitting in a regular manner.

[0151] The choice of the algorithm ε.sub.H of the encoding function encode.sub.H has a predominant role in the conversion of E(encode(x)) into ε.sub.H (encode.sub.H(ĩ). It should be recalled that for x ∈, we have (discretise∘encode)(x) ∈ where ={0, . . . , N−1}. An important case is when the elements of are seen as the elements of a subset, not necessarily a subgroup, of an additive group. This additive group is denoted .sub.M (the set of integers {0, . . . , M−1} provided with the addition modulo M) for an integer M≥N.

[0152] Thus, in one of the embodiments of the invention, the approximate homomorphic evaluation of the univariate function ƒ is further characterised in that the set is a subset of the additive group .sub.M for an integer M≥N.

[0153] There are several ways of representing the group .sub.M. Thus, Ducas and Miccipanio in the aforementioned article of EUROCRYPT 2015 represent the elements of .sub.M as the exponents of a variable X; to an element i of .sub.M is associated an element X.sup.i, with X.sup.M=X.sup.0=1 and X.sup.j≠1 for any 0<j<M. It is said that X is an M-th primitive root of the unit. This representation allows switching from an additive notation into a multiplicative notation: for all elements i, j∈ .sub.M, the element i+j (mod M) is associated to the element

X.sup.i+j=X.sup.i.Math.X.sup.j(mod (X.sup.M−1)).

[0154] The modulo multiplication operation (X.sup.M−1) induces a group isomorphism between the additive group .sub.M and the set {1, X, . . . , X.sup.M−1} of the M-th roots of the unit. When M is even, the relationship X.sup.M=1 implies X.sup.M/2=−1. We then have X.sup.i+j=X.sup.i.Math.X.sup.j (mod (X.sup.M/2+1)) for i, j ∈.sup.M and, the set of the M-th roots of the unit is {±1, ±X, . . . , ±X.sup.(M/2)−1}.

[0155] Thus, in one of the embodiments of the invention, the approximate homomorphic evaluation of the univariate function ƒ is further characterized in that the group .sup.M is represented multiplicatively as the powers of a primitive M-th root of the unit denoted X, so that to the element i of .sub.M is associated the element X.sup.i; all of M-th roots of the unit {1, X, . . . , X.sup.M−1} forming an isomorphic group to .sup.M for multiplication modulo (X.sup.M−1).

[0156] In the case where the homomorphic encryption algorithm E is given by an LWE-type encryption algorithm applied to the torus =/, we have = and, if we denote μ=encode(x) with x ∈ for an encoding function encode with a value in , we have E(encode(x))=(a.sub.1, . . . , a.sub.n, b) where a.sub.j ∈ (for 1≤j≤n) and b=Σ.sub.j=1.sup.ns.sub.j.Math.a.sub.j+μ+e (mod 1) with e a small random noise on .

[0157] Thus, in one of the embodiments of the invention, the approximate homomorphic evaluation of the univariate function ƒ is further characterized in that the homomorphic encryption algorithm E is given by an LWE-type encryption algorithm applied to the torus =/ and has as native space of cleartexts =.

[0158] The discretization function discretise is then parameterised for an integer M≥N as the function which, to an element t of the torus, associates the integer rounding of the product M×t modulo M, where M×t is calculated in ; written in the mathematical form discretise: .fwdarw., tdiscretise(t)=[M×t] mod M.

[0159] This discretisation function naturally extends to vectors of the torus. Applied to the vector c=(a.sub.1, . . . , a.sub.n, b) of .sup.n+1, we obtain the vector c of (.sub.M).sup.n+1 given by c=(, . . . , , b) with a.sub.j=┌M×a.sub.j┘ mod M (for 1≤j≥n) and b=┌M×b┘ mod M. In a more detailed manner, if we define i=┌M×μ┘ mod M and ē=┌M×e┘, we have

[00017]$\begin{array}{cc}\overline{b}=.Math.M\times \left({.Math.}_{j=1}^n{s}_j.Math.a_j+\mu +e\left(\mathrm{mod}1\right)\right).Math.\mathrm{mod}M& \\ =.Math.M\times \left({.Math.}_{j=1}^n{s}_j.Math.a_j+\mu +e+\delta \right).Math.\mathrm{mod}M& \mathrm{for}a\mathrm{given}\delta \mathrm{in}\mathbb{Z}\\ =.Math.M\times \left({.Math.}_{j=1}^n{s}_j.Math.a_j+\mu +e\right).Math.\mathrm{mod}M& \\ =.Math.{.Math.}_{j=1}^n{s}_j\left(M.Math.a_j\right)+M.Math.\mu +M.Math.e.Math.\mathrm{mod}M& \\ =\left({.Math.}_{j=1}^n{s}_j\overline{a_j}+i+\overline{e}+\Delta \right)\mathrm{mod}M& \mathrm{for}a\mathrm{small}\Delta \mathrm{in}\mathbb{Z}\end{array}$

the signed integer Δ captures the rounding error and is called “drift”. The expected value of the drift is zero. Moreover, of |e|<1/(2M) then ē=0. We assume

[00018]$\tilde{i}=i+\Delta \mathrm{with}\Delta \in \left\{-.Math.\frac{M}{2}.Math.+1,.Math.,.Math.\frac{M}{2}.Math.\right\},$

[0160] which ĩ has as an expected value the integer i =┌M×μ┘ mod M=discretise(μ). The encoding function encode is parameterised so that its image is contained in the sub-interval

[00019]$[0,\frac{N}{M}-\frac{1}{2M})$

of the torus. In this manner, if x ∈ then

[00020]$\mu =\mathrm{encode}\left(x\right)\in [0,\frac{N}{M}-\frac{1}{2M})\mathrm{and}$$i=\mathrm{discretise}\left(\mu \right)=.Math.M\times \mu .Math.\mathrm{mod}M\in [0,N).$

Indeed, it is verified that if

[00021]$0\le \mu <\frac{N}{M}-\frac{1}{2M}$

then ┌M×μ┘≥0 and

[00022]$\begin{array}{c}.Math.M\times \mu .Math.\le M\times \mu +\frac{1}{2}\\ <M\times \left(\frac{N}{M}-\frac{1}{2M}\right)+\frac{1}{2}=N\end{array}$

and therefore, since N≤M, ┌M×μ┘ mod M=┌M×μ┘∈[0, N). Hence, for these functions discretise and encode, we actually have (discretise∘encode) ().Math.{0, . . . , N−1}=, in other words (discretise∘encode) () is a subset of the set of the indexes ={0, . . . , N−1}. Thus, in one of the embodiments of the invention, the approximate homomorphic evaluation of the univariate function ƒ is further characterised in that [0161] the encoding function encode has its image contained in the sub-interval

[00023]$[0,\frac{N}{M}-\frac{1}{2M})$

of the torus, and [0162] the discretisation function discretise applies an element t of the torus to the integer rounding of the product M×t modulo M, where M×t is calculated in ; in mathematical form, discretise: .fwdarw., tdiscretise(t)=┌M×t┘ mod M.

[0163] It should be noticed that when the domain of definition of the function ƒ to be evaluated is the real interval =[x.sub.min, x.sub.max) and that the native space of cleartexts is the torus , a possible choice for the encoding function encode is

[00024]$\mathrm{encode}:𝒟.fwdarw.𝕋,x\mapsto \frac{2N-1}{2M}\frac{x-x_{\min }}{x_{\max }-x_{\min }}$

we then have

[00025]$\mathrm{encode}\left(x\right)\in [0,\frac{N}{M}-\frac{1}{2M})$

for x ∈ ; we note that

[00026]$\frac{N}{M}-\frac{1}{2M}=\frac{2N-1}{2M}.$

[0164] Thus, in one of the embodiments of the invention, the approximate homomorphic evaluation of the univariate function ƒ is further characterized in that when the domain of definition of the function ƒ is the real interval =[x.sub.min, x.sub.max), the encoding function encode is

[00027]$\mathrm{encode}:[x_{\min },x_{\max }).fwdarw.[0,\frac{N}{M}-\frac{1}{2M}),$$x\mapsto \mathrm{encode}\left(x\right)=\frac{2N-1}{2M}\frac{x-x_{\min }}{x_{\max }-x_{\min }}.$

[0165] The construction (discretise∘encode) () gives rise to a first embodiment of the conversion of E(encode(x)) into ε.sub.H (encode.sub.H(ĩ)). It supposes that the elements of the set are seen directly as integers of .sub.M. As an encoding function encode.sub.H, we consider the identity function, encode.sub.H: .sub.M.fwdarw..sub.M, ii. With the previous notations, if we denote μ=encode(x) ∈ and its LWE ciphertext on the torus c=(a.sub.1, . . . , a.sub.n, b) with b=Σ.sub.j=1.sup.ns.sub.j.Math.a.sub.j+μ+e (mod 1), then ε.sub.H(encode.sub.H(ĩ)∈().sup.n+1 is defined as

[00028]$\begin{array}{c}{\epsilon }_H\left({\mathrm{encode}}_H\left(\widetilde{\mathrm{.Math.}}\right)\right)={\epsilon }_H\left(\widetilde{\mathrm{.Math.}}\right)\\ =\left(\stackrel{\_}{a_1},.Math.,\stackrel{\_}{a_n},\stackrel{\_}{b}\right)\end{array}$

with =┌M×a.sub.j┘ mod M for 1≤j≤n and b=┌M×b┘ mod M. It should be noted that b=(Σ.sub.j=1.sup.ns.sub.ja.sub.j+ĩ+ē) mod M. In this case, we observe that ε.sub.H is an LWE-type encryption algorithm on the ring .sub.M; the encryption key is (s.sub.1, . . . , s.sub.n) ∈ {0,1}.sup.n.

[0166] Thus, in one of the embodiments of the invention, the approximate homomorphic evaluation of the univariate function ƒ is further characterised in that the homomorphic encryption algorithm ε.sub.H is an LWE-type encryption algorithm and the encoding function encode.sub.H is the identity function.

[0167] A second embodiment of the conversion of E(encode(x)) into ε.sub.H(encode.sub.H(ī) is obtained by considering the M-th roots of the unit; this allows working multiplicatively. More specifically, it is assumed that M is even and an arbitrary polynomial p :=p(X) of .sub.M/2[X]is fixed. The encoding function encode.sub.H is the function

encode.sub.H: .sub.M.fwdarw..sub.M/2[X], iencode.sub.H(i)=X.sup.−i, p(X)

and the encryption algorithm ε.sub.H is an RLWE-type encryption algorithm on .sub.M//2 [X]-modulus .sub.M/2 [X]. The conversion for this choice of encode.sub.H and of ε.sub.H uses the re-encryption technique. We denote b k [j] ∈ .sub.M/2 the RGSW-type ciphertext of s.sub.j, for 1≤j≤n, under a key (s′.sub.1, . . . , s′.sub.k) ∈E .sub.M/2 [X].sup.k. The conversion of E(encode(x))=(a.sub.1, . . . , a.sub.n, b) ∈.sup.n+1 into ε.sub.H(encode.sub.H(ĩ) is given by the following procedure: [0168] obtain the conversion public keys bk [1], . . . , bk [n] [0169] calculate =┌M×a.sub.j┘ mod M for 1≤j≤n and {tilde over (b)}=┌M×b┘ mod M [0170] initialise c′.sub.0←(0, . . . , 0, X.sup.—{tilde over (b)}.Math.p(X)) ∈ .sub.M/2[X].sup.k+1 [0171] for j ranging from 1 to n, evaluate c′.sub.j←((X.sup.ã.sup.j−1).Math.bk[j]+G)c′.sub.j−1 (in .sub.M/2 [X].sup.k+1) [0172] return c′.sub.n as the result ε.sub.H (encode.sub.H (ĩ).

[0173] In this case, it is observed that ε.sub.H is an RLWE-type encryption algorithm on the modulus .sub.M/2 [X]; the encryption key is (s′.sub.1, . . . , s′.sub.k) ∈ .sub.M/2 [X].sup.k. Indeed, if we set C.sub.j an RGSW-type encryption of under the key (s′.sub.1, . . . , s′.sub.k) (for 1≤j≤n), in mathematical form C.sub.j=RGSW(), we have

[00029]$\begin{array}{c}{C}_j\leftarrow \mathrm{RGSW}\left(X^{s_j\stackrel{\_}{a_j}}\right)\\ \leftarrow \mathrm{RGSW}\left(s_j\left(X^{\stackrel{\_}{a_j}}-1\right)+1\right)\\ \leftarrow \mathrm{RGSW}\left(s_j\left(X^{\stackrel{\_}{a_j}}-1\right)\right)+RGSW\left(1\right)\\ \leftarrow \left(X^{\stackrel{\_}{a_j}}-1\right).Math.\mathrm{RGSW}\left(s_j\right)+RGSW\left(1\right)\\ \leftarrow \left(X^{\stackrel{\_}{a_j}}-1\right).Math.\mathrm{bk}\left[j\right]+G\end{array}.$

[0174] Thus, if we denote RLWE(m) an RLWE-type encryption for m ∈.sub.M/2 [X], under the key (s′.sub.1, . . . , s′.sub.k), we have

[00030]$\begin{array}{c}{c}_1^{\prime }\leftarrow C_1{c}_0^{\prime }=\mathrm{RGSW}\left(X^{s_1\stackrel{\_}{a_1}}\right)\mathrm{RLWE}\left(X^{-\overline{b}}.Math.p\left(X\right)\right)\\ \leftarrow \mathrm{RLWE}\left(X^{-\overline{b}+s_1\overline{a_1}}.Math.p\left(X\right)\right)\end{array}$

and, by induction,

[00031]$\begin{array}{c}{c}_n^{\prime }\leftarrow \mathrm{RLWE}\left(X^{-\overline{b}+s_1\stackrel{\_}{a_1}+.Math.+s_n\stackrel{\_}{a_n}}.Math.p\left(X\right)\right)\\ \leftarrow {\epsilon }_H\left({\mathrm{encode}}_H\left(\widetilde{\mathrm{.Math.}}\right)\right)\end{array}.$

[0175] Thus, in one of the embodiments of the invention, the approximate homomorphic evaluation of the univariate function ƒ, parameterised by an even integer M, is further characterised in that the homomorphic encryption algorithm ε.sub.H is an RLWE-type encryption algorithm and the encoding function encode.sub.H is the function encode.sub.H: .sub.M.fwdarw..sub.M/2 [X], iencode.sub.H(i)=X.sup.—i, p(X) for an arbitrary polynomial p of .sub.M/2 [X].

[0176] It is now possible to perform the homomorphic evaluation of the table T from ε.sub.H (encode.sub.H(ĩ), according to either one of the previous two embodiments. In both cases, we suppose that E is an LWE-type algorithm on the torus and that M is even and it is equal to 2N. [0177] 1. The first case supposes that the encoding function encode.sub.H is encode.sub.H: .sub.2N.fwdarw..sub.2N, ii and that the algorithm ε.sub.H is an LWE-type encryption algorithm on .sub.2N. In this first case, we have ε.sub.H (encode.sub.H (ĩ))=(, . . . , , {tilde over (b)}). A fist substep consists in: [0178] forming the polynomial q ∈.sub.N[X]given by q(X)=T′[0]+T′[1]X+. . . + T′[N−1]X.sup.N−1=Σ.sub.j=0.sup.N−1T′[j]X.sup.j with T′[j]=encode′(T[j]) to 0≤j≤N−1 [0179] obtain the conversion public keys bk[1], . . . , bk[n] [0180] initialise c″.sub.0.fwdarw.(0, . . . , 0,X.sup.—{tilde over (b)}.Math.q(X)) ∈.sub.N [X].sup.k+1 [0181] for j ranging from 1 to n, evaluate c″.sub.j←((−1).Math.bk[j]+G)c″.sub.j−1 (in .sub.N[X].sup.k+1) [0182] assume d′=c″.sub.n [0183] returning d′=RLWE (X.sup.—ĩ.Math.q(X)). [0184] 2. The second case supposes the encoding function encode.sub.H:.sub.2N.fwdarw..sub.N [X]p(X) for an arbitrary polynomial p :=p(X) ∈ .sub.N [X]and that the algorithm ε.sub.H is an RLWE-type encoding algorithm on .sub.N [X] In this second case, we have ε(encode.sub.H (ĩ))=RLWE(X.sup.—ĩ.Math.p(X)) for the arbitrary polynomial p ∈ .sub.N [X]. A first substep consists in: [0185] selecting a polynomial P :=P (X) ∈ .sub.N[X]such that P.Math.p≈q with q ∈ .sub.N [X]given by q(X)=T′[0]+T′[1]X +. . . +T′[N−1]X.sup.N−1=Σ.sub.j=0.sup.N−1T′[j]X.sup.j with T′[j]=encode′(T[j]) to 0≤j≤N−1 [0186] evaluate d′←P.Math.RLWE(X.sup.—ĩ.Math.p(X)) [0187] return d′=RLWE(X.sup.—ĩ, (P(X).Math.p(X))) with P(X).Math.p(X)≈q(X).

[0188] In particular, it should be noted that, for an integer L>1, if

[00032]$p\left(X\right)=\left(1+X+.Math.+X^{N-1}\right).Math.\frac{1}{2L}$

then the choice

[00033]$P\left(X\right)=\underset{j=0}{\overset{N-1}{.Math.}}{P}_j{X}^j\mathrm{avec}\{\begin{array}{c}{P}_0=.Math.L\times \left(T^{\prime }\left[0\right]+T^{\prime }\left[N-1\right]\right).Math.\\ P_j=.Math.L\times \left(T^{\prime }\left[j\right]-T^{\prime }\left[j-1\right]\right).Math.\mathrm{pour}1\le j\le N-1\end{array}$

(where the multiplication by L is calculated in implies P(X).Math.p(X)≈T′[0]+T′[1]X +. . . +T′[N−1]X.sup.N−1. Indeed, it is observed that for this choice of the polynomial p we have

[00034]$\begin{array}{c}P\left(X\right).Math.p\left(X\right)=\left(P_0+P_{1}X+P_2{X}^2+.Math.+P_{N-2}{X}^{N-2}+P_{N-1}{X}^{N-1}\right).Math.\\ \left(\frac{1}{2L}\left(1+X+X^2+.Math.+X^{N-2}+X^{N-1}\right)\right)\\ =(\left(P_0-P_1-P_2-.Math.-P_{N-2}-P_{N-1}\right)+\\ \left(P_0+P_1-P_2-.Math.-P_{N-2}-P_{N-1}\right)X+\\ \left(P_0+P_1+P_2-.Math.-P_{N-2}-P_{N-1}\right)X^2+.Math.+\\ \left(P_0+P_1+P_2+.Math.+P_{N-2}-P_{N-1}\right)X^{N-2}+\\ \left(P_0+P_1+P_2+.Math.+P_{N-2}+P_{N-1}\right)X^{N-1}).Math.\frac{1}{2L}\\ \approx (.Math.2L\times T^{\prime }\left[0\right].Math.+.Math.2L\times T^{\prime }\left[1\right].Math.X+.Math.+\\ .Math.2L\times T^{\prime }\left[N-1\right].Math.X^{N-1}).Math.\frac{1}{2L}\\ \approx T^{\prime }\left[0\right]+T^{\prime }\left[1\right]X+.Math.+T^{\prime }\left[N-1\right]X^{N-1}=q\left(X\right)\end{array}$

while noting that, for 0≤r≤N−1, Σ.sub.j=0.sup.rP.sub.j=P.sub.0Σ.sub.j=1.sup.rP.sub.j≈┌L×(T′[0]+T′[N−1])┘+┌L×(T′[r]−T′[0])┘≈┌L×(T′[r]+T′[N−1])┘ and —Σ.sub.j=r+1.sup.N−1P.sub.j≈┌L×(T′[r]—T′[N−1])┘. It should be noticed that P.Math.p≈q; the equality being verified within a given drift, which has an expected value equal to zero.

[0189] In both cases, in return of this first substep of the homomorphic evaluation of the table T, an RLWE-type ciphertext d′of the expected polynomial X.sup.—ĩ.Math.q (X) is obtained under a key (s′.sub.1, . . . , s′.sub.k) ∈ .sub.N [X].sup.k+1, which key being that one used to produce the RGSW-type ciphertexts bk[j](1≤j≤n) encrypting the bits s.sub.j of the secret key (s.sub.1, . . . , s.sub.n) ∈ {0,1}.sup.n. By the form of q(X), the constant term of the polynomial X.sup.—ĩ.Math.q(X)=X.sup.—ĩ.Math.(T′[0]+T′[1]X+. . . +T′[N]X.sup.N−1) is T′[ĩ]=encode′(T[ĩ]). We denote (a′.sub.1, . . . , a′.sub.k, b′) ∈ .sub.N[X].sup.k+1 the components of the ciphertext d′.

[0190] A second sub-step (common to both cases) of the homomorphic evaluation of the table T extracts an LWE-type ciphertext of T′[ĩ]=encode′(T[ĩ]) from said RLWE ciphertext: [0191] for each 1≤j≤k, write the polynomial a′.sub.j :=a′.sub.j(X) ∈ .sub.N[X]as a′.sub.j(X)=Σ.sub.l=0.sup.N−1(a′.sub.j).sub.lX.sup.l with (a′.sub.j).sub.l ∈ (for 0≤l≤N−1) [0192] write the polynomial b′:=b′(X) ∈ .sub.N[X] as b′(X)=Σ.sub.l=0.sup.N−1(b′).sub.lX.sup.l with (b′).sub.l ∈ (for 0≤l≤N631 1) [0193] define the element vector on torus (a″.sub.1, . . . , a″.sub.kN) ∈.sup.kN where

[00035]$\{\begin{array}{cc}{a}_{1+\mathrm{jN}}^{″}={\left(a_j\right)}_0& \mathrm{for}1\le j\le k\\ a_{1+l+\mathrm{jN}}^{″}=-{\left(a_j\right)}_{N-l}& \mathrm{for}1\le j\le ket1\le l\le N-1\end{array}$ [0194] return the element vector on the torus (a″.sub.1, . . . , a″.sub.kN, b″) ∈ .sup.kN+1 where b″=(b′).sub.0 is the constant term of the polynomial b′.

[0195] If, for each 1≤j≤k, the polynomial s′.sub.j:=s′.sub.j(X) ∈ .sub.N[X] is written as s′.sub.j (X)=Σ.sub.t=0.sup.N−1(s′.sub.j).sub.lX.sup.l with (s′.sub.l).sub.l ∈ ={0,1} (for 0≤l≤N−1), one can see that the returned vector (a″.sub.1, . . . , a″.sub.kN, b″) is an LWE-type ciphertext on the torus of T′[ĩ]=encode′(T[ĩ]) under the key ((s′.sub.1).sub.0, (s′.sub.1).sub.1, . . . , (s′.sub.1).sub.n−1, . . . , (s′.sub.k).sub.0, (s′.sub.k).sub.N−1)∈{0,1}.sup.kN. This defines the encryption algorithm E′; we thus have (a″.sub.1, . . . , a″.sub.kN, b″)=E′ (encode′(T[ĩ])). In this case, the corresponding native space of cleartexts is ′=. Hence, since T [ĩ]=y(ĩ) and y(ĩ)≈ƒ(x), we actually obtain an LWE-type ciphertext of an encryption with an approximate value of ƒ(x).

[0196] Upon completion of this calculation, the ciphertext E′ (encode′(T[ĩ]){tilde over ( )}) can be decrypted and decoded to give an approximate value of ƒ(x).

[0197] Thus, in one of the embodiment of the invention, the approximate homomorphic evaluation of the univariate function ƒ, parameterised by an even integer M equal to 2N, is further characterised in that an LWE-type ciphertext E′ (encode′(T[ĩ])) on the torus is extracted from an RLWE ciphertext approximating the polynomial X.sup.—ĩ, q (X) ∈.sub.N [X] with q (X)=T′[0]+T′[1]X +. . . +T′[N−1]X.sup.N−1=Σ.sub.j=0.sup.N−1T′[j]X.sup.j in .sub.N[X] and where T′[j]=encode′(T[j]), 0≤j≤N−1.

[0198] When the image of the function ƒ to be evaluated is the real interval [y.sub.min, y.sub.max) and the native space of cleartexts ′ for an LWE-type encryption is the torus , a possible choice for the encoding function encode′is

[00036]${\mathrm{encode}}^{\prime }:𝒥.fwdarw.𝕋,y\mapsto {\mathrm{encode}}^{\prime }\left(y\right)=\frac{y-y_{\min }}{y_{\max }-y_{\min }}.$

In this case, the corresponding decoding function is given by y′y′(y.sub.max−y.sub.min)+y.sub.min.

[0199] Thus, in one of the embodiments of the invention, the approximate homomorphic evaluation of the univariate function ƒ is further characterised in that, when the image of the function ƒ is the real interval =[y.sub.min, y.sub.max), [0200] the homomorphic encryption algorithm E′ is given by an LWE-type encryption algorithm applied to the torus =/ and has as a native space of the cleartexts =, [0201] the encoding function encode′ is

[00037]${\mathrm{encode}}^{\prime }:[y_{\min },y_{\max }).fwdarw.𝕋,y\mapsto {\mathrm{encode}}^{\prime }\left(y\right)=\frac{y-y_{\min }}{y_{\max }-y_{\min }}.$

[0202] The encoding should be taken into account during the addition of the ciphertexts. If we denote encode the encoding function of a homomorphic encoding algorithm E, we then have E(μ.sub.1+μ.sub.2)=E(μ.sub.1)+E(μ.sub.2) with μ.sub.1=encode(x.sub.1) and μ.sub.1=encode(x.sub.2). If the encoding function is homomorphic, then we actually have E(encode(x.sub.1+x.sub.2))=E(encode(x.sub.1))+E(encode(x.sub.2)). Otherwise, if the encoding function does not comply with the addition, a correction ε should be applied on the encoding: ε=encode(x.sub.1+x.sub.2)−encode(x.sub.1)−encode(x.sub.2) so that E(encode(x.sub.1+x.sub.2))=E(encode(x.sub.1))+E(encode(x.sub.2))+E (ε). In particular, when the encoding is defined by

[00038]$\mathrm{encode}:x\mapsto \frac{N-1}{2M}\frac{x-x_{\min }}{x_{\max }-x_{\min }},$

the correction amounts to

[00039]$\epsilon =\frac{N-1}{2M}\frac{x_{\min }}{x_{\max }-x_{\min }}$

and is zero for x.sub.min=0. It should be recalled that for an LWE-type encryption scheme, an uplet in the form (0, . . . , 0, ε) is a valid ciphertext of ε.

[0203] Of course, the previous considerations remain valid on the images. For a homomorphic encryption algorithm E′ with an encoding function encode, we have E′ (encode′(ƒ(x.sub.1)+ƒ(x.sub.2)))=E′ (encode′(ƒ(x.sub.1)))+E′ (encode′(ƒ(x.sub.2)))+E′ (ε′) for a correction ε′=encode′(ƒ(x.sub.1)+ƒ(x.sub.2))−encode′(ƒ(x.sub.1))−encode′(ƒ(x.sub.2)). In particular, the correction ε′ is zero when the encoding encode′ complies with the addition. The correction ε′ amounts to

[00040]${\epsilon }^{\prime }=\frac{y_{\min }}{y_{\max }-y_{\min }}$

for the encoding

[00041]${\mathrm{encode}}^{\prime }:y\mapsto \frac{y-y_{\min }}{y_{\max }-y_{\min }}.$

[0204] Another important particular case is when the same univariate function ƒ should be homomorphically evaluated on inputs x.sub.1 and x.sub.2=x.sub.1+A for a given constant A. A typical example of application is the internal function « in Sprecher's application described hereinabove. For a homomorphic encryption algorithm E with an encoding function encode, given the fact that E(encode(x.sub.1)), it is possible to deduce E(encode(x.sub.2))=E(encode(x.sub.1+A)) and then obtain E′ (encode′(ƒ(x.sub.1))) and E′ (encode′(ƒ(x.sub.2))) as explained before. However, it is necessary to repeat all the steps. In the particular case where E is an LWE-type algorithm on the torus and that M=2N, at the input E(encode(x.sub.1)), we have seen that in return of the first substep of the homomorphic evaluation of the table T, we obtain an RLWE-type ciphertext d′ of the expected polynomial X.sup.—ĩ.sup.1.Math.q(X) where the polynomial q tabulates the function ƒ and where ĩ.sub.1 has as an expected value i.sub.1=discretise(encode(x.sub.1)) if x.sub.1 belongs to the sub-interval R.sub.i.sub.1. For example, for the discretisation function discretise: t{tilde over (t)}=┌M×t┘ (mod M) with M=2N, we obtain

[00042]$\begin{array}{c}{i}_2:=\mathrm{discretise}\left(\mathrm{encode}\left(x_2\right)\right)=\mathrm{discretise}\left(\mathrm{encode}\left(x_1+A\right)\right)\\ =\mathrm{discretise}\left(\mathrm{encode}\left(x_1\right)+\mathrm{encode}\left(A\right)+\epsilon \right)\\ =.Math.2N\times \left(\mathrm{encode}\left(x_1\right)+\mathrm{encode}\left(A\right)+\epsilon \right).Math.\mathrm{mod}2N\\ \approx i_1+\stackrel{\_}{{\mu }_A}\left(\mathrm{mod}2N\right)\mathrm{avec}\stackrel{\_}{{\mu }_A}:=.Math.2N\times \left(\mathrm{encode}\left(A\right)+\epsilon \right).Math.\end{array}$

and therefore X.sup.−ĩ.sup.2.Math.q(X)≈.Math.q(X)=.Math.(X.sup.—ĩ.sup.1.Math.q(X)). In this case, an RLWE-type ciphertext of the expected polynomial X.sup.—ĩ.sup.2.Math.q(X) can be obtained more rapidly like .Math.d′. A value for E′ (encode′(ƒ(x.sub.2)){tilde over ( )}) is therefore deduced by the second substep of the homomorphic evaluation of the table T.

[0205] The invention also covers an information processing system that is specifically programmed to implement a homomorphic cryptographic evaluation method according to either one of the alternative methods described hereinabove.

[0206] Also, it covers the computer program product that is specifically designed to implement either one of the alternative methods described hereinabove and to be loaded and implemented by an information processing system programmed for this purpose.

Application Examples of the Invention

[0207] The above-described invention can be very advantageously used to preserve the confidentiality of some data, for example yet not exclusively personal, health, classified information data or more generally all data that its holder wishes to keep secret but on which he would wish that a third-party can perform digital processing. The delocalisation of the processing to one or more third-party service provider(s) is interesting from several reasons: it allows performing operations that otherwise require some costly or unavailable resources; it also allows performing non-public operations. In turn, the third-party responsible for carrying out said digital processing operations might, indeed, wish not to communicate the actual content of the processing and the digital functions implemented thereby.

[0208] In such a use, the invention covers the implementation of a remote digital service, such as in particular a cloud computing service in which a third-party service provider responsible for the application of the digital processing on the encrypted data, carries out, on its part, a first pre-calculation step described hereinabove, which consists, for each multivariate function ƒ.sub.i among the functions ƒ.sub.1, . . . , ƒ.sub.q which will be used to process the encrypted data, in pre-calculating a network of univariate functions. Among all of the resulting univariate functions {g.sub.k(z.sub.i.sub.k)}.sub.k for a given z.sub.i.sub.k with k≤1), the third-party pre-selects in a second step univariate functions g.sub.k and their respective argument z.sub.i.sub.k such that there is k′<k meeting one of the three criteria (i) g.sub.k=g.sub.k and z.sub.i.sub.k=z.sub.i.sub.k′, (ii) g.sub.k≠g.sub.k, and z.sub.i.sub.k=z.sub.i.sub.k′, or (iii) g.sub.k=g.sub.k′ and z.sub.i.sub.k=z.sub.i.sub.k′+a.sub.k for a known constant a.sub.k≠0; these univariate functions will, where appropriate, be evaluated in an optimised manner

[0209] In turn, the holder of the confidential data (x.sub.1, . . . , x.sub.p) carries out the encryption thereof by a homomorphic encryption algorithm E so as to transmit to the third-party type data E(μ.sub.1), . . . , E(μ.sub.p), where μ.sub.i is the encoded value of x.sub.i by an encoding function. Typically, the choice of the algorithm E is imposed by the third-party provider of the service. Alternatively, the holder of data can use an encryption algorithm of his choice, not necessarily homomorphic, in which case a prior step of re-encryption will be performed by the third-party (or another service provider) to obtain the encrypted data in the desired format.

[0210] Thus, in one of the embodiments of the invention, the previously-described homomorphic evaluation cryptographic method(s) is characterised in that the input encrypted data are derived from a prior re-encryption step to be set in the form of ciphertexts of encryptions of said homomorphic encryption algorithm E.

[0211] Once the third-party has obtained the encrypted type data E(μ.sub.i), at the step of homomorphic evaluation of the network of univariate functions, it homomorphically evaluates in a series of successive steps based on these ciphertexts each of the networks of univariate functions, so as to obtain the ciphertexts of encryptions of ƒ.sub.j applied to their inputs (for 1≤j≤q) under the encryption algorithm E′.

[0212] Once it has obtained, for the considered different function(s) ƒ.sub.j the encrypted results of the encryptions on their input values, the concerned third-party sends all these results back to the holder of the confidential data.

[0213] The holder of the confidential data can then obtain, based on the corresponding decryption key held thereby, after decoding, a value of the result of one or more function(s) ƒ.sub.1, . . . , ƒ.sub.q) starting from homomorphically encrypted input data (x.sub.1, . . . , x.sub.p), without the third-party having carried out on said data the digital processing consisting in the implementation of one or more function(s), having been able to know the clear content of the data nor, reciprocally, the holder of the data having had to know the detail of the implemented function(s).

[0214] Such a sharing of tasks between the holder of the data and the third-party acting as a digital processing service provider can advantageously be carried out remotely, and in particular throughout cloud computing type services without affecting the security of the data and of the concerned processing. Moreover, the different steps of the digital processing may be the responsibility of different service providers.

[0215] Thus, in one of the embodiments of the invention, a cloud computing type remote service implements one or more of the previously-described homomorphic evaluation cryptographic methods, wherein the tasks are shared between the holder of the data and the third-part(y/ies) acting as digital processing service providers.

[0216] In a particular embodiment of the invention, this remote service involving the holder of the data x.sub.1, . . . , x.sub.p that he wishes to keep secret and one or more third-part(y/ies) responsible for the application of the digital processing on said data, is further characterised in that [0217] 1. the concerned third-part(y/ies) carry out, according to the invention, the first step of pre-calculating networks of univariate functions and the second pre-selection step [0218] 2. the holder of the data carries out the encryption of x.sub.1, . . . , x.sub.p by a homomorphic encryption algorithm E, and transmits to the third-party type data E(μ.sub.1), . . . , E(μ.sub.p), where μ.sub.i is the encoded value of x.sub.i by an encoding function [0219] 3. once the concerned third-party has obtained the encrypted type data E(μ.sub.i), he homomorphically evaluates in a series of successive steps based on these ciphertexts each of said networks of univariate functions, so as to obtain the ciphertexts of encryptions of ƒ.sub.j applied to their inputs (for 1≤j≤q) under the encryption algorithm E′ [0220] 4. once he has obtained, for the considered different function(s) ƒ.sub.j the encrypted results of the encryptions on their input values, the concerned third-party sends all these results back to the holder of the data [0221] 5. the holder of the data obtains, based on the corresponding decryption key held thereby, after decoding, a value of the result of one or more function(s) (ƒ.sub.1, . . . , ƒ.sub.q).

[0222] A variant of this embodiment is characterised in that, in the second step (2.) hereinabove: [0223] the holder of the data carries out the encryption of x.sub.1, . . . , x.sub.p by an encryption algorithm different from E and transmits said data thus encrypted. [0224] on said received encrypted data, the concerned third-party performs a re-encryption to obtain the ciphertexts E(μ.sub.1), . . . , E(μ.sub.p) under said homomorphic encryption algorithm E, where μ.sub.i is the encoded value of x.sub.i by an encoding function.

[0225] Different applications of the remote digital service according to the invention may be mentioned, inter alia. Thus, it is already known, as mentioned in the aforementioned article by MajecSTIC '08, a Kolmogorov-type decomposition applied to grey-level images—which may be viewed as bivariate functions ƒ(x, y)=I (x, y) where I (x, y) gives the grey intensity of the pixel of coordinates (x, y)—allows reconstructing an approximate image of the original image. Consequently, the knowledge of coordinates (x.sub.1, y.sub.1) and (x.sub.2, y.sub.2) defining a bounding box allows performing cropping operations in a simple way. A similar processing applies on colour images while considering the bivariate functions ƒ.sub.1(x, y)=R(x, y), ƒ.sub.2(x, y)=G (x, y) and ƒ.sub.3(x, y)=B (x, y) giving the red, green and blue levels respectively. While this processing type has been known on unencrypted data, the invention now allows carrying out it using homomorphic encryption. Thus, according to the invention, if a user sends in an encrypted manner his GPS coordinates recorded at regular intervals (for example every 10 seconds) during a sport activity as well as the extreme coordinates of his journey (defining a bounding box), the service provider in possession of the image of a cartographic plan will be able to obtain the ciphertext of the portion of the plan relating to the activity by cropping; furthermore, he will be able, still in the encrypted domain, to represent the journey using for example a colour code to indicate the local speed homomorphically computed based on the received encrypted images of the GPS coordinates. Advantageously, the (third-party) service provider has no knowledge of the exact location of the activity (except that it is on his plan) or of the performances of the user. Furthermore, the third-party does not disclose the entirety of the map. The invention can also be advantageously used to allow performing artificial intelligence processing, in particular of machine-learning type on input data which remain encrypted and on which the service provider implementing in particular a neural network applies one or more activation function(s) on values derived from said encrypted data. As example of this use of the invention in connection with the implementation of a neural network, reference may be made to the decomposition of the function g (z.sub.1, z.sub.2)=max(z.sub.1, z.sub.2), which serves in particular as the aforementioned “max pooling”used by the neural networks, into z.sub.2+(z.sub.1−z.sub.2).sup.+ where zz.sup.+ corresponds to the univariate function zmax(z, 0). Reference may also be made to the very popular activation functions ReLU: .fwdarw..sup.+, tt.sup.+ and

[00043]$\mathrm{sigmoid}:ℝ.fwdarw.\left[0,1\right],t\mapsto \frac{1}{1+\exp \left(-t\right)}.$

[0226] Thus, in one of the embodiments of the invention, a remote service implementing one or more of the previously-described cryptographic homomorphic evaluation methods is intended for digital processing implementing neural networks.

Disclosure of the Invention as it is Characterised

[0227] The invention enables the evaluation, on encrypted data, of one or more function(s) through the implementation of the data calculation and processing capabilities of one or more digital information processing system(s). Depending on the case, this or these function(s) may be univariate or multivariate. Hence, in its different variants, the method according to the invention allows proceeding with the evaluation of both types of functions.

[0228] In the case where the function(s) to be evaluated are of the univariate type, the invention provides, in one of its implementations, for the implementation respectively at the input and at the output of two homomorphic encryption algorithms and the step of pre-calculating a table for each considered function followed by a step of homomorphic evaluation of the table thus obtained, as claimed by claim 1.

[0229] In the case where the function(s) to be evaluated are of multivariate type, the invention further provides for carrying out two preliminary steps: the first pre-calculation step, followed by a second pre-selection step before applying to the univariate function network(s) obtained upon completion of the execution of these two preliminary steps a third step of homomorphic evaluation of said univariate function networks according to any known method for univariate function homomorphic evaluation. This is the object of claim 12.