How to compute the inner product on encrypted vector by using a third party?

Question

I want to compute the inner product of two vectors on a third party, i.e. $f(x) \cdot f(y) = x \cdot y$ where $x$ and $y$ are two vectors. However, I do not want the third party knows the real value of the two vectors.

So is there any encryption scheme that can do this?

Answer 1

One possible way to calculate the inner product is by using fully homomorphic encryption schemes.

First, you encrypt each vector $$x = (x_1,x_2,\ldots,x_n), \quad y = (y_1,y_2,\ldots,y_n)$$ with your public key $$X = Enc_{pub}(x) \text{ and } Y = Enc_{pub}(y)$$ where $$X = (X_1,X_2,\ldots,X_n), \quad Y = (Y_1,Y_2,\ldots,Y_n)$$ and $$X_i = Enc_{pub}(x_i) \text{ and } Y_i = Enc_{pub}(y_i)$$

Now, you can send $X$ and $y$ to the server to calculate the inner product, IP, under FHE.

$$IP = \langle X,Y \rangle = X_1 \odot Y_1 \oplus X_1 \odot Y_1 \oplus \cdots \oplus X_n \odot Y_n$$ when the server send you back the result, use your public key to decrypt the result. Where $\odot$ represent homomorphic multiplication and $\oplus$ represent homomoprhic addition.

$$res = \langle x,y \rangle = Dec_{priv}(IP)$$

Note 1 : You have to assume the server semi-honest. Here, there is no integrity against a malicious server.

Note 2 : For the implementation, you can use TFHE: Fast Fully Homomorphic Encryption over the Torus or Helib

Note 3 : You can also use 2DNF by Boneh et.al, which support one multiplication but many additions. This work is enough for the calculation of the inner product under 2DNF encryption. The decryption, however, is not straightforward. As noted on page 4 of the paper;

To recover $m$, it suffices to compute the discrete log of $C^{q_1}$ of base $\hat{q}$

Note that decryption in this system takes polynomial time in the size of the message space T. Therefore, the system as described above can only be used to encrypt short messages

Note 4: there is an article titled as Design and Implementation of Low Depth Pairing-based Homomorphic Encryption Scheme by Herbert at. al that that

can handle the homomorphic evaluation of polynomials of degree at most 4. and uses Elliptic Curves. And, they have an implementation posted on github.

Answer 2

Actually the idea proposed by SEJPM in the comment to use functional encryption is probably the simplest way if you want the third party doing the inner product computation to learn the actual result and not simply the encrypted result.

There have been multiple papers about inner product functional encryption schemes in the last few years, but let me first explain what is functional encryption, compared to homomorphic encryption:

• in the (fully) homomorphic encryption (FHE) case, you encrypt data so that a third party can evaluate a function on the encrypted data and obtain the encrypted result of that function. Grossly speaking, you have that the third party can compute: $$ f(E(x)) = E(f(x)) $$ without gaining any information about $x$, nor $f(x)$.
• in the functional encryption (FE) case, you encrypt data in a way that a third party can evaluate a function of the encrypted data and obtain the cleartext result of that function. So to say:$$f(E(x)) = f(x)$$ without obtaining more information about $x$ than the information that can be deduced from knowing $f(x)$.

Now, if you want to be able to encrypt a given vector $x$ and obtain its inner product with a vector $y$, functional encryption has multiple paper considering the case where you have a central authority issuing a public key $mpk$ that allows to encrypt vectors like $x$ and a secret key $z_y$ that allows one to evaluate the inner product of a vector $x$ encrypted with that public key with the vector $y$.

So, in this case the central authority would be you. You would issue the $mpk$, compute the encryption of the vector $x$ under that public key, and compute the secret key $z_y$ corresponding to the second vector $y$, then you could provide the third party with $E_{mpk}(x)$ and $z_y$ and the third party would then be able to compute the values of $\langle a, y \rangle$ when provided with $E_{mpk}(a)$, for any vector $a$ encrypted by the $mpk$. In particular when provided with $E_{mpk}(x)$, it would be able to compute the value of $\langle x, y \rangle$ thanks to its secret key $z_y$ corresponding to the vector $y$.

However, notice that in these basic FE schemes, the vector $y$ corresponding to the evaluation key $z_y$ has to be known from the third party in order to evaluate the inner product. That is: only the vector $x$ is remaining secret.

To see the full scheme, I refer you to the [ALS16] paper.

Also, notice that this is meant to work for integer vectors, or to evaluate inner products modulo a prime $p$ or a composite $N=pq$. If you are considering vector with real values, you might face some challenges. (Arguably, this is just a question of having the right encoding, though.)

Furthermore, since we are working with vectors $x\in \mathrm{Z}^\ell_p$ (or $\mathrm{Z}^\ell_N$), it is important to keep in mind that the inner product of two vectors is leaking information about the projection of the vectors onto each other! This means in particular that if you use the same public key $mpk$ and provide more than $\ell-1$ secret keys $z_{y_i}$ for independent vectors $y_i$ to the third party, then it is trivial to reconstruct the actual value of any given encrypted vector $x$, since it is possible to evaluate the inner product of $x$ being given $E_{mpk}(x)$ with $\ell$ independent vectors $y_i$, which form then a basis of our $\ell$ dimensional vector space.

The function hiding case

Now, what if you want both vectors $x$ and $y$ to remain secret, while you want that third party to still be able to evaluate there inner product? In that case, the [ALS16] scheme wouldn't work, as it assumes $y$ is known by the evaluator.

Thankfully, this is a field of research that has also known tremendous improvement over the past years and is named "FE with function hiding". Basically, an inner product encryption scheme is "function-hiding" if the keys and ciphertexts reveal no additional information about both vectors $x$ and $y$ beyond their inner product $\langle x,y\rangle$.

While I haven't really studied them, it appears there are at least a couple choice out there, which are a bit more complex, but allow you to have function hiding in the case of inner product schemes:

• The recent [ACF+18] paper is really interesting as it seems it is at least partially implemented in the GoFe library from the FENTEC project. However, it doesn't seem to feature the function hiding in the library (yet?).
• Most interesting for you, if you need to use it in practice, might be the [KLM+18] paper, as they have an open-source implementation on Github, that definitively features the function hiding.

In both case, they present schemes that should enable you to achieve computation of the inner product of vectors $x$ and $y$ by a third party that would obtain directly the plaintext value of that inner product, without revealing to that third party anything about $x$ and $y$.

However, since [KLM+18] is achieving its result in the generic group model for the two input case and has a practical python implementation, I would say it is currently the most practical one. (I don't know why I've surmised you wanted something practical, but if you want to look at the state of the art, then you can also delve into that paper, although they are more concerned about the multi-input case, which complicates things a bit.)

Reference

[ACF+18] $\quad$ M. Abdalla, D. Catalano, D. Fiore, R. Gay, and B. Ursu. Multi-input functional encryption for inner products: function-hiding realizations and constructions without pairings. In Annual International Cryptology Conference, pages 597-627. Springer, Cham, August 2018. Full version on eprint.

[ALS16] $\quad$ S. Agrawal, B. Libert, and D. Stehlé. Fully secure functional encryption for inner products, from standard assumptions. In CRYPTO 2016, Part III, LNCS 9816, pages 333–362. Springer, Heidelberg, August 2016. Full version on eprint.

[KLM+18] $\quad$ S. Kim, K. Lewi, A. Mandal, H. Montgomery, A. Roy, and D. J. Wu. Function-hiding inner product encryption is practical. In International Conference on Security and Cryptography for Networks, pages 544-562. Springer, Cham, September 2018. Full version on eprint.

Answer 3

If the third party is a trusted one, and also we have a key manageing center(KMC), the KMC first generate two random matrix $A$, $B$ and a invertable matrix $M$. Then it calculates the re-encryption key: $$R_A = A^{-1}M$$$$R_B = B^{-1}M$$when the owner of $x$ receving A, compute: $$A'=A^Tx$$ send $A'$ to the third party. When the owner of $y$ recieving $B$, like x: $$B'=B^{-1}x$$ And send $B'$ to the third party. The third party uses the re-encryption key to perform:$$A''=R_A^TA'=M^Tx$$$$B''=R_B^{-1}B'=M^{-1}y$$ Then compute the inner product:$$B'' \cdot A''^T=(M^{-1}y) \cdot (M^Tx)^T=M^{-1}yx^TM=yx^T$$But now the question is if the third party's computation is open and transparent, that is to say, the re-encrypted key is public, then how can we guarantee the privacy of vector $x$ and $y$?