6
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ I think this should be possible, given that inner-product focused functional encryption has been extensively researched the past few years, but I haven't looked into the details. $\endgroup$
    – SEJPM
    Aug 24, 2019 at 11:14
  • $\begingroup$ I have looked into some papers, but I still did not have any ideas... $\endgroup$
    – BorisWang
    Aug 24, 2019 at 11:54
  • $\begingroup$ I've changed some of the wording of the question, please check if it is correct. I've removed the word "exact" from it as that begs the question: how exact, and it seems to have been included as ways of exclamation mark rather than a property of the scheme. Please edit the question if this is not correct. $\endgroup$
    – Maarten Bodewes
    Aug 24, 2019 at 12:20
  • 2
    $\begingroup$ Homomorphic encryption schemes? $\endgroup$
    – Natanael
    Aug 24, 2019 at 12:20
  • 1
    $\begingroup$ @Natanael The outcome of those is still encrypted, and generally you would use the same private key to decrypt the components and the end result. So if it falls under homomorphic encryption - and I guess it does - then it is definitely a specific subset of homomorphic encryption. $\endgroup$
    – Maarten Bodewes
    Aug 24, 2019 at 12:22

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ You beat me to it. I just finished a pen and paper proof $\endgroup$
    – b degnan
    Aug 24, 2019 at 20:14
  • $\begingroup$ Maybe point out the performance difference between BGN and FHE. $\endgroup$
    – tylo
    Aug 24, 2019 at 21:59
  • $\begingroup$ @tylo I din't see any implementation of 2DNF except github.com/vherbert/BGN2 $\endgroup$
    – kelalaka
    Aug 24, 2019 at 22:04
  • 1
    $\begingroup$ The question didn't really mention implementations. And from that statement, it sounds like FHE was the better practical approach. But FHE is so much more inefficient than pairing friendly elliptic curves, if you just need multiplicative depth 1. $\endgroup$
    – tylo
    Aug 24, 2019 at 22:15
  • 1
    $\begingroup$ @tylo Yes, it sounds like FHE better. The decryption bothers me about BGN. level 1 depth may favor into BGN. Maybe I need a small implementation. $\endgroup$
    – kelalaka
    Aug 24, 2019 at 22:23
4
$\begingroup$

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:

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.

$\endgroup$
5
  • $\begingroup$ If I want to compute the inner product between y and xi(where xi is from multiple users), so can I encrypte the multipe xi with the same mpk? One of the multiple users can infer the other xi? $\endgroup$
    – BorisWang
    Aug 31, 2019 at 8:24
  • $\begingroup$ I found that in the scheme you recommended to me, the decryption process needs to input the original value of y, which will cause the exposure of one of the vectors. Is there any scheme that can protect the privacy of both vectors at the same time? $\endgroup$
    – BorisWang
    Sep 1, 2019 at 13:46
  • $\begingroup$ Yes, you are right: the vector $y$ is known from the third party with the ALS16 scheme. I should have detailed it in my answer, I'll update it accordingly. In case you want to have the vector $y$ remaining secret, you could rely on the so-called "function hiding inner product schemes". I will link to a couple of them in my updated answer. $\endgroup$
    – Lery
    Sep 3, 2019 at 8:38
  • $\begingroup$ I've updated it @BorisWang let me know if you need more details. $\endgroup$
    – Lery
    Sep 4, 2019 at 13:33
  • $\begingroup$ In function hiding inner product encryption sheme, both two users have the same msk to encrypt their vectors. When an attacker get the msk and the ciphertext of one vector, can he get the value of vector? $\endgroup$
    – BorisWang
    Sep 5, 2019 at 0:21
2
$\begingroup$

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$?

$\endgroup$
1
  • $\begingroup$ @tylo Can you help me? $\endgroup$
    – BorisWang
    Aug 25, 2019 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.