Cryptographic method, systems and services for evaluating real-valued functions on encrypted data
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.
1 . A cryptographic method for privacy-preserving outsourced computation, executed in digital form by at least one information processing system specifically programmed to perform an approximated homomorphic evaluation of a univariate function ƒ of a real variable x of arbitrary precision in a definition domain and real-valued in an image , the cryptographic method comprising:
receiving as input, via a communication interface from an external computer, an encryption of an encoding of x, E(encode(x)), and transmitting computation results of the outsourced computation to the external computer in an encrypted format, via the communication interface, the outsourced computation including computing an encryption of an encoding of an approximated value of ƒ(x), E′(encode′(y)) with y≈ƒ(x), where E and E′ are homomorphic encryption algorithms for which a respective native plaintext space is and ′, wherein encode is an encoding function taking as input an element of the definition domain and associating thereto an element of , and wherein encode′ is an encoding function taking as input an element of the image and associating thereto an element of ′,
the cryptographic method being parameterized by:
an integer N≥1 quantifying an actual precision of a representation of input variables of the univariate function ƒ to be evaluated,
a discretization function discretise taking as input an element of and associating an index represented by an integer with it,
a homomorphic encryption scheme comprising an encryption algorithm ε H for which a native space H is of cardinality at least N,
an encoding function encode H taking as input an integer and returning an element of H ,
such that an image of the definition domain D by the encoding encode followed by the discretization discretise, (discretiseºencode) ( ), is a set of at most N indices taken from ={0, . . . , N−1},
and wherein the cryptographic method further comprises:
(a) pre-calculating a table T corresponding to said univariate function ƒ, comprising:
decomposing the definition domain into N selected sub-intervals R 0 , . . . , R N−1 , the union of which is ;
for each index i in ={0, . . . , N−1}, determining a representative x(i) in the sub-interval R i and calculating the value y(i)=ƒ(x(i));
returning the table T comprising the N components T[0], . . . , T[N−1], with T[i]=y (i) for 0≤i≤N−1;
(b) the outsourced computation comprising homomorphically evaluating the table T, comprising:
converting the ciphertext E(encode(x)) into the ciphertext ε H (encode H ({tilde over (ι)})) for an integer {circumflex over (ι)} having as expected value the index i=(discretizeºencode)(x) in the set ={0, . . . , N−1} if x∈R i ;
obtaining the encryption E′(encode′(T[{tilde over (ι)}]) ˜ ) for an element encode′(T[{tilde over (ι)}]) ˜ , having as expected value encode′(T[{tilde over (ι)}]), from the encryption ε H (encode H ({tilde over (ι)})) and from the table T; and
returning E′(encode′(T[{tilde over (ι)}]) ˜ );
and wherein the homomorphic encryption algorithm E is given by an encryption algorithm of LWE type applied to a torus = / and has its native plaintext space = .
2 . The cryptographic method according to claim 1 , wherein
a domain of definition of the univariate function ƒ to be evaluated is given by the real interval =[x min , x max ), for real values x min and x max , and
the N intervals R i (for 0≤i≤N−1) covering the domain are the semi-open sub-intervals
R
i
=
[
i
N
(
x
max
-
x
min
)
+
x
min
,
i
+
1
N
(
x
max
-
x
min
)
+
x
min
)
,
splitting in a regular manner.
3 . The cryptographic method according to claim 1 , wherein the set S is a subset of the additive group M for an integer M≥N.
4 . The cryptographic method according to claim 3 , wherein the group M is represented in a multiplicative manner as the powers of a M-th primitive root of a unit denoted as X, such that the element i of M is associated with the element X i ; all of the M-th roots of the unit {1, X, . . . , X M-1 }forming an isomorphic group at M for the multiplication modulo (X M-1 ).
5 . The cryptographic method according to claim 1 parameterized by an integer M≥N, wherein
the encoding function encode has its image contained in the sub-interval
[
0
,
N
M
-
1
2
M
)
of the torus, and
the discretise discretization function discretise applies an element t of the torus to the rounded integer of the product M×t modulo M, where M×t is calculated in ; in mathematical form:
discretise: → , t discretise(t)=┌M×t┘ mod M.
6 . The cryptographic method according to claim 5 , wherein when the definition domain of the function ƒ is the real interval =[x min , x max ), for real values x min and x max , the encoding function encode is:
encode
:
[
x
min
,
x
max
)
→
[
0
,
N
M
-
1
2
M
,
x
↦
encode
(
x
)
=
2
N
-
1
2
M
x
-
x
min
x
max
-
x
min
.
7 . The cryptographic method according to claim 1 , wherein the homomorphic encryption algorithm ε H is an encryption algorithm of LWE type and the encoding function encode H is the identity function.
8 . The cryptographic method according to claim 1 parameterized by an even integer M, wherein the homomorphic encryption algorithm ε H is an encryption algorithm of RLWE type and the encoding function encode H is the function
encode
H
:
ℤ
M
→
𝕋
M
2
[
X
]
,
i
↦
encode
H
(
i
)
=
X
-
i
·
p
(
X
)
for an arbitrary polynomial p of M/2 [X].
9 . The cryptographic method according to claim 7 parameterized by an even integer M equal to 2N, wherein an encryption of LWE type E′(encode′(T[{tilde over (ι)}])) on the torus is extracted from an RLWE encryption approximating the polynomial X −{tilde over (ι)} ·q(X)∈ N [X] with
q
(
X
)
=
T
′
[
0
]
+
T
′
[
1
]
X
+
…
+
T
′
[
N
-
1
]
X
N
-
1
=
∑
j
=
0
N
-
1
T
′
[
j
]
X
j
in N [X] and where T′[j]=encode′(T′[j]), 0≤j≤N−1.
10 . The cryptographic method according to claim 1 , wherein
when an image of the function ƒ is the real interval =[y min , y max ), for real values y min and y max ,
the homomorphic encryption algorithm E′ is given by an encryption algorithm of LWE type applied to the torus = / and has as native plaintext space ′= , and
the encoding function encode′ is:
encode
′
:
[
y
min
,
y
max
)
→
𝕋
,
y
↦
encode
′
(
y
)
=
y
-
y
min
y
max
-
y
min
.
11 . The cryptographic method according to claim 1 , wherein
the at least one univariate function subjected to said approximated homomorphic evaluation is derived from a prior processing of at least one multivariate function comprising:
(a) transforming in a pre-calculation each of said multivariate functions into a network of univariate functions, comprising compositions of real-valued univariate functions and of sums,
(b) identifying in said networks of precalculated univariate functions redundancies of one of the three types:
(1) same univariate functions applied to the same arguments,
(2) different univariate functions applied to the same arguments, or
(3) same univariate functions applied to arguments differing from a non-zero additive constant and selecting all or part of them, and
(c) homomorphically evaluating each of the networks of precalculated univariate functions, wherein when all or part of one or more of these univariate functions are reused the redundancies selected in the step (b) are evaluated in a shared manner.
12 . The cryptographic method according to claim 1 , wherein the encrypted input data result from a prior re-encryption step so as to be set in the form of encryptions of encodings of ciphertexts of encryptions of said homomorphic encryption algorithm E.
13 . An information processing system comprising a processor unit which is programmed to implement the cryptographic method for homomorphic evaluation according to claim 1 .