1
$\begingroup$

There is a matrix $A$ that we don't want to be revealed, and there is a matrix $B$ that is known. Is there any way to calculate $A \times B$ without revealing $A$? $A$ can be encrypted. But we don't want anyone to know it, but we want anyone to be able to calculate the multiplication of it to another matrix.

Is there anyway to do such a thing?

$\endgroup$
2
$\begingroup$

Yes there is. It is called functional encryption for inner product (IPFE), and there are many schemes for that, with different features in terms of underlying assumption (typically DDH, DCR, or LWE), security (IND-CPA, IND-CCA, static or adaptive, etc) and compactness.

An IPFE has four algorithms:

  • $\mathsf{Setup}$ generates a public encryption key $\mathsf{pk}$ and a master secret key $\mathsf{msk}$
  • $\mathsf{Enc}$ takes as input a fixed-length message vector $\vec m$, and outputs a ciphertext $c$
  • $\mathsf{KeyDer}$ takes as input a linear function $f$, the master secret key $\mathsf{msk}$, and outputs a functional secret key $\mathsf{sk}_f$
  • $\mathsf{Decrypt}$ takes as input a functional secret key $\mathsf{sk}_f$, a ciphertext $c$, and outputs $f(\vec m)$, where $\vec m$ is the message encrypted in $c$.

In your case, the linear function $f$ would be the function $f_B: A \mapsto A\times B$.

IPFE was first defined in this paper, where it was also constructed from a variety of standard assumptions. Since this work, there has been many follow ups, achieving stronger security notions, or more features.

In your context: the matrix $A$ would be encrypted with $\mathsf{Enc}$, and the dealer would reveal the secret key $\mathsf{sk}_B$ associated to the function $f_B: A \mapsto A \times B$. This would allow anyone to obtain $A\times B$ from any ciphertext encrypting a matrix $A$.

Of course, usual safeguards apply: if your matrix $B$ is invertible, this would just reveal $A$ in clear, so $B$ better be a highly compressing, or very low rank matrix, if you want this process to preserve some security.

$\endgroup$
7
  • $\begingroup$ Thank you so much for your answer. However, this scheme needs one dealer to compute secret key for each matrix B. Is there any way to encrypt the matrix A once, and then anyone be able to calculate A×B with any matrix B without the need for computing anything? $\endgroup$ – Arian B Oct 6 '20 at 13:32
  • $\begingroup$ Then the answer is clearly no. How do you limit the number of matrices B used by an attacker? If you allow any B, then any attacker can obtain A*B for as many different B as he wants, which allows him to recover A entirely, see Poncho's answer. $\endgroup$ – Geoffroy Couteau Oct 6 '20 at 13:47
  • $\begingroup$ The matrixes are really big so it is hard for the attacker to solve the equations. I'm looking for something like ZKSnark, but for matrixes. $\endgroup$ – Arian B Oct 6 '20 at 16:27
  • $\begingroup$ If A is polysize, then B is polysize, and solving the equations takes polynomial time. You cannot hope for any asymptotic security this way. $\endgroup$ – Geoffroy Couteau Oct 6 '20 at 17:05
  • $\begingroup$ Is functional encryption verifiable? I mean, can it be verified that the dealer did right? $\endgroup$ – Arian B Oct 20 '20 at 17:53
0
$\begingroup$

is there anyway to do such a thing?

I do not believe so.

If the attacker knows $B, A \times B$ for a number of different $B$ values (the number required would depend on the dimensions of $A, B$), it's easy to recover $A$. This means that, no matter how securely you compute $A \times B$, it's still insecure.

$\endgroup$
3
  • $\begingroup$ Yes you are right. But imagine that B is produced once. So can we do it? $\endgroup$ – Arian B Oct 5 '20 at 14:55
  • $\begingroup$ @ArianB: could you then outline how this computation is envisioned to take place? If it's a whitebox implementation of $F(B) = A \times B$, I don't see any reason to limit the number of times $F$ is queried. If it is a multiparty computation, what are the other security goals? If there aren't any, you have pass the server the value $B$ and it'll return the value $A \times B$... $\endgroup$ – poncho Oct 5 '20 at 17:08
  • $\begingroup$ I want something like ZKSnark. I want to put a matrix in a blockchain and then everyone be able to compute A×B with different B. I don't want A to be plain and everyone know it. $\endgroup$ – Arian B Oct 6 '20 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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